TournamentBP: Fix some bugs with table sizes and counters

globalHistoryBits, globalPredictorSize, and choicePredictorSize are decoupled.
globalHistoryBits controls how much history is kept, global and choice
predictor sizes control how much of that history is used when accessing
predictor tables. This way, global and choice predictors can actually be
different sizes, and it is no longer possible to walk off the predictor arrays
and cause a seg fault.

There are now individual thresholds for choice, global, and local saturating
counters, so that taken/not taken decisions are correct even when the
predictors' counters' sizes are different.

The interface for localPredictorSize has been removed from TournamentBP because
the value can be calculated from localHistoryBits.

Committed by: Nilay Vaish <nilay@cs.wisc.edu>

1 files changed, 56 insertions, 36 deletions

diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc
index ba2b1decb..f36d30ae5 100644
--- a/src/cpu/pred/tournament.cc
+++ b/src/cpu/pred/tournament.cc
@@ -40,11 +40,11 @@
  * Authors: Kevin Lim
  */
 
+#include "base/bitfield.hh"
 #include "base/intmath.hh"
 #include "cpu/pred/tournament.hh"
 
-TournamentBP::TournamentBP(unsigned _localPredictorSize,
-                           unsigned _localCtrBits,
+TournamentBP::TournamentBP(unsigned _localCtrBits,
                            unsigned _localHistoryTableSize,
                            unsigned _localHistoryBits,
                            unsigned _globalPredictorSize,
@@ -53,28 +53,25 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize,
                            unsigned _choicePredictorSize,
                            unsigned _choiceCtrBits,
                            unsigned _instShiftAmt)
-    : localPredictorSize(_localPredictorSize),
-      localCtrBits(_localCtrBits),
+    : localCtrBits(_localCtrBits),
       localHistoryTableSize(_localHistoryTableSize),
       localHistoryBits(_localHistoryBits),
       globalPredictorSize(_globalPredictorSize),
       globalCtrBits(_globalCtrBits),
       globalHistoryBits(_globalHistoryBits),
-      choicePredictorSize(_globalPredictorSize),
+      choicePredictorSize(_choicePredictorSize),
       choiceCtrBits(_choiceCtrBits),
       instShiftAmt(_instShiftAmt)
 {
-    if (!isPowerOf2(localPredictorSize)) {
-        fatal("Invalid local predictor size!\n");
-    }
+    localPredictorSize = ULL(1) << localHistoryBits;
 
-    //Setup the array of counters for the local predictor
+    //Set up the array of counters for the local predictor
     localCtrs.resize(localPredictorSize);
 
     for (int i = 0; i < localPredictorSize; ++i)
         localCtrs[i].setBits(localCtrBits);
 
-    localPredictorMask = floorPow2(localPredictorSize) - 1;
+    localPredictorMask = mask(localHistoryBits);
 
     if (!isPowerOf2(localHistoryTableSize)) {
         fatal("Invalid local history table size!\n");
@@ -86,9 +83,6 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize,
     for (int i = 0; i < localHistoryTableSize; ++i)
         localHistoryTable[i] = 0;
 
-    // Setup the local history mask
-    localHistoryMask = (1 << localHistoryBits) - 1;
-
     if (!isPowerOf2(globalPredictorSize)) {
         fatal("Invalid global predictor size!\n");
     }
@@ -101,21 +95,45 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize,
 
     //Clear the global history
     globalHistory = 0;
-    // Setup the global history mask
-    globalHistoryMask = (1 << globalHistoryBits) - 1;
+    // Set up the global history mask
+    // this is equivalent to mask(log2(globalPredictorSize)
+    globalHistoryMask = globalPredictorSize - 1;
 
     if (!isPowerOf2(choicePredictorSize)) {
         fatal("Invalid choice predictor size!\n");
     }
 
+    // Set up choiceHistoryMask
+    // this is equivalent to mask(log2(choicePredictorSize)
+    choiceHistoryMask = choicePredictorSize - 1;
+
     //Setup the array of counters for the choice predictor
     choiceCtrs.resize(choicePredictorSize);
 
     for (int i = 0; i < choicePredictorSize; ++i)
         choiceCtrs[i].setBits(choiceCtrBits);
 
-    // @todo: Allow for different thresholds between the predictors.
-    threshold = (1 << (localCtrBits - 1)) - 1;
+    //Set up historyRegisterMask
+    historyRegisterMask = mask(globalHistoryBits);
+
+    //Check that predictors don't use more bits than they have available
+    if (globalHistoryMask > historyRegisterMask) {
+        fatal("Global predictor too large for global history bits!\n");
+    }
+    if (choiceHistoryMask > historyRegisterMask) {
+        fatal("Choice predictor too large for global history bits!\n");
+    }
+
+    if (globalHistoryMask < historyRegisterMask &&
+        choiceHistoryMask < historyRegisterMask) {
+        inform("More global history bits than required by predictors\n");
+    }
+
+    // Set thresholds for the three predictors' counters
+    // This is equivalent to (2^(Ctr))/2 - 1
+    localThreshold  = (ULL(1) << (localCtrBits  - 1)) - 1;
+    globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
+    choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
 }
 
 inline
@@ -131,7 +149,7 @@ void
 TournamentBP::updateGlobalHistTaken()
 {
     globalHistory = (globalHistory << 1) | 1;
-    globalHistory = globalHistory & globalHistoryMask;
+    globalHistory = globalHistory & historyRegisterMask;
 }
 
 inline
@@ -139,7 +157,7 @@ void
 TournamentBP::updateGlobalHistNotTaken()
 {
     globalHistory = (globalHistory << 1);
-    globalHistory = globalHistory & globalHistoryMask;
+    globalHistory = globalHistory & historyRegisterMask;
 }
 
 inline
@@ -163,8 +181,8 @@ void
 TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
 {
     unsigned local_history_idx = calcLocHistIdx(branch_addr);
-    //Update Global History to Not Taken
-    globalHistory = globalHistory & (globalHistoryMask - 1);
+    //Update Global History to Not Taken (clear LSB)
+    globalHistory &= (historyRegisterMask & ~ULL(1));
     //Update Local History to Not Taken
     localHistoryTable[local_history_idx] =
        localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
@@ -184,13 +202,15 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
     local_history_idx = calcLocHistIdx(branch_addr);
     local_predictor_idx = localHistoryTable[local_history_idx]
         & localPredictorMask;
-    local_prediction = localCtrs[local_predictor_idx].read() > threshold;
+    local_prediction = localCtrs[local_predictor_idx].read() > localThreshold;
 
     //Lookup in the global predictor to get its branch prediction
-    global_prediction = globalCtrs[globalHistory].read() > threshold;
+    global_prediction =
+      globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold;
 
     //Lookup in the choice predictor to see which one to use
-    choice_prediction = choiceCtrs[globalHistory].read() > threshold;
+    choice_prediction =
+      choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold;
 
     // Create BPHistory and pass it back to be recorded.
     BPHistory *history = new BPHistory;
@@ -201,9 +221,7 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
     history->localHistory = local_predictor_idx;
     bp_history = (void *)history;
 
-    assert(globalHistory < globalPredictorSize &&
-           local_history_idx < localHistoryTableSize &&
-           local_predictor_idx < localPredictorSize);
+    assert(local_history_idx < localHistoryTableSize);
 
     // Commented code is for doing speculative update of counters and
     // all histories.
@@ -283,10 +301,12 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
                  // If the local prediction matches the actual outcome,
                  // decerement the counter.  Otherwise increment the
                  // counter.
+                 unsigned choice_predictor_idx =
+                   history->globalHistory & choiceHistoryMask;
                  if (history->localPredTaken == taken) {
-                     choiceCtrs[history->globalHistory].decrement();
+                     choiceCtrs[choice_predictor_idx].decrement();
                  } else if (history->globalPredTaken == taken) {
-                     choiceCtrs[history->globalHistory].increment();
+                     choiceCtrs[choice_predictor_idx].increment();
                  }
 
              }
@@ -295,13 +315,15 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
              // resolution of the branch.  Global history is updated
              // speculatively and restored upon squash() calls, so it does not
              // need to be updated.
+             unsigned global_predictor_idx =
+               history->globalHistory & globalHistoryMask;
              if (taken) {
-                  globalCtrs[history->globalHistory].increment();
+                  globalCtrs[global_predictor_idx].increment();
                   if (old_local_pred_valid) {
                           localCtrs[old_local_pred_index].increment();
                   }
              } else {
-                  globalCtrs[history->globalHistory].decrement();
+                  globalCtrs[global_predictor_idx].decrement();
                   if (old_local_pred_valid) {
                           localCtrs[old_local_pred_index].decrement();
                   }
@@ -310,14 +332,14 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
         if (squashed) {
              if (taken) {
                 globalHistory = (history->globalHistory << 1) | 1;
-                globalHistory = globalHistory & globalHistoryMask;
+                globalHistory = globalHistory & historyRegisterMask;
                 if (old_local_pred_valid) {
                     localHistoryTable[local_history_idx] =
                      (history->localHistory << 1) | 1;
                 }
              } else {
                 globalHistory = (history->globalHistory << 1);
-                globalHistory = globalHistory & globalHistoryMask;
+                globalHistory = globalHistory & historyRegisterMask;
                 if (old_local_pred_valid) {
                      localHistoryTable[local_history_idx] =
                      history->localHistory << 1;
@@ -330,9 +352,7 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
 
     }
 
-    assert(globalHistory < globalPredictorSize &&
-           local_history_idx < localHistoryTableSize &&
-           local_predictor_idx < localPredictorSize);
+    assert(local_history_idx < localHistoryTableSize);
 
 
 }