src/cpu/pred/tournament.cc

   1 /*
   2  * Copyright (c) 2011 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Kevin Lim
  41  */
  42
  43 #include "base/bitfield.hh"
  44 #include "base/intmath.hh"
  45 #include "cpu/pred/tournament.hh"
  46
  47 TournamentBP::TournamentBP(const Params *params)
  48     : BPredUnit(params),
  49       localCtrBits(params->localCtrBits),
  50       localHistoryTableSize(params->localHistoryTableSize),
  51       localHistoryBits(params->localHistoryBits),
  52       globalPredictorSize(params->globalPredictorSize),
  53       globalCtrBits(params->globalCtrBits),
  54       globalHistoryBits(params->globalHistoryBits),
  55       choicePredictorSize(params->choicePredictorSize),
  56       choiceCtrBits(params->choiceCtrBits),
  57       instShiftAmt(params->instShiftAmt)
  58 {
  59     localPredictorSize = ULL(1) << localHistoryBits;
  60
  61     //Set up the array of counters for the local predictor
  62     localCtrs.resize(localPredictorSize);
  63
  64     for (int i = 0; i < localPredictorSize; ++i)
  65         localCtrs[i].setBits(localCtrBits);
  66
  67     localPredictorMask = mask(localHistoryBits);
  68
  69     if (!isPowerOf2(localHistoryTableSize)) {
  70         fatal("Invalid local history table size!\n");
  71     }
  72
  73     //Setup the history table for the local table
  74     localHistoryTable.resize(localHistoryTableSize);
  75
  76     for (int i = 0; i < localHistoryTableSize; ++i)
  77         localHistoryTable[i] = 0;
  78
  79     if (!isPowerOf2(globalPredictorSize)) {
  80         fatal("Invalid global predictor size!\n");
  81     }
  82
  83     //Setup the array of counters for the global predictor
  84     globalCtrs.resize(globalPredictorSize);
  85
  86     for (int i = 0; i < globalPredictorSize; ++i)
  87         globalCtrs[i].setBits(globalCtrBits);
  88
  89     //Clear the global history
  90     globalHistory = 0;
  91     // Set up the global history mask
  92     // this is equivalent to mask(log2(globalPredictorSize)
  93     globalHistoryMask = globalPredictorSize - 1;
  94
  95     if (!isPowerOf2(choicePredictorSize)) {
  96         fatal("Invalid choice predictor size!\n");
  97     }
  98
  99     // Set up choiceHistoryMask
 100     // this is equivalent to mask(log2(choicePredictorSize)
 101     choiceHistoryMask = choicePredictorSize - 1;
 102
 103     //Setup the array of counters for the choice predictor
 104     choiceCtrs.resize(choicePredictorSize);
 105
 106     for (int i = 0; i < choicePredictorSize; ++i)
 107         choiceCtrs[i].setBits(choiceCtrBits);
 108
 109     //Set up historyRegisterMask
 110     historyRegisterMask = mask(globalHistoryBits);
 111
 112     //Check that predictors don't use more bits than they have available
 113     if (globalHistoryMask > historyRegisterMask) {
 114         fatal("Global predictor too large for global history bits!\n");
 115     }
 116     if (choiceHistoryMask > historyRegisterMask) {
 117         fatal("Choice predictor too large for global history bits!\n");
 118     }
 119
 120     if (globalHistoryMask < historyRegisterMask &&
 121         choiceHistoryMask < historyRegisterMask) {
 122         inform("More global history bits than required by predictors\n");
 123     }
 124
 125     // Set thresholds for the three predictors' counters
 126     // This is equivalent to (2^(Ctr))/2 - 1
 127     localThreshold  = (ULL(1) << (localCtrBits  - 1)) - 1;
 128     globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
 129     choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
 130 }
 131
 132 inline
 133 unsigned
 134 TournamentBP::calcLocHistIdx(Addr &branch_addr)
 135 {
 136     // Get low order bits after removing instruction offset.
 137     return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
 138 }
 139
 140 inline
 141 void
 142 TournamentBP::updateGlobalHistTaken()
 143 {
 144     globalHistory = (globalHistory << 1) | 1;
 145     globalHistory = globalHistory & historyRegisterMask;
 146 }
 147
 148 inline
 149 void
 150 TournamentBP::updateGlobalHistNotTaken()
 151 {
 152     globalHistory = (globalHistory << 1);
 153     globalHistory = globalHistory & historyRegisterMask;
 154 }
 155
 156 inline
 157 void
 158 TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
 159 {
 160     localHistoryTable[local_history_idx] =
 161         (localHistoryTable[local_history_idx] << 1) | 1;
 162 }
 163
 164 inline
 165 void
 166 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
 167 {
 168     localHistoryTable[local_history_idx] =
 169         (localHistoryTable[local_history_idx] << 1);
 170 }
 171
 172
 173 void
 174 TournamentBP::btbUpdate(Addr branch_addr, void * &bp_history)
 175 {
 176     unsigned local_history_idx = calcLocHistIdx(branch_addr);
 177     //Update Global History to Not Taken (clear LSB)
 178     globalHistory &= (historyRegisterMask & ~ULL(1));
 179     //Update Local History to Not Taken
 180     localHistoryTable[local_history_idx] =
 181        localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
 182 }
 183
 184 bool
 185 TournamentBP::lookup(Addr branch_addr, void * &bp_history)
 186 {
 187     bool local_prediction;
 188     unsigned local_history_idx;
 189     unsigned local_predictor_idx;
 190
 191     bool global_prediction;
 192     bool choice_prediction;
 193
 194     //Lookup in the local predictor to get its branch prediction
 195     local_history_idx = calcLocHistIdx(branch_addr);
 196     local_predictor_idx = localHistoryTable[local_history_idx]
 197         & localPredictorMask;
 198     local_prediction = localCtrs[local_predictor_idx].read() > localThreshold;
 199
 200     //Lookup in the global predictor to get its branch prediction
 201     global_prediction =
 202       globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold;
 203
 204     //Lookup in the choice predictor to see which one to use
 205     choice_prediction =
 206       choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold;
 207
 208     // Create BPHistory and pass it back to be recorded.
 209     BPHistory *history = new BPHistory;
 210     history->globalHistory = globalHistory;
 211     history->localPredTaken = local_prediction;
 212     history->globalPredTaken = global_prediction;
 213     history->globalUsed = choice_prediction;
 214     history->localHistory = local_predictor_idx;
 215     bp_history = (void *)history;
 216
 217     assert(local_history_idx < localHistoryTableSize);
 218
 219     // Commented code is for doing speculative update of counters and
 220     // all histories.
 221     if (choice_prediction) {
 222         if (global_prediction) {
 223             updateGlobalHistTaken();
 224             updateLocalHistTaken(local_history_idx);
 225             return true;
 226         } else {
 227             updateGlobalHistNotTaken();
 228             updateLocalHistNotTaken(local_history_idx);
 229             return false;
 230         }
 231     } else {
 232         if (local_prediction) {
 233             updateGlobalHistTaken();
 234             updateLocalHistTaken(local_history_idx);
 235             return true;
 236         } else {
 237             updateGlobalHistNotTaken();
 238             updateLocalHistNotTaken(local_history_idx);
 239             return false;
 240         }
 241     }
 242 }
 243
 244 void
 245 TournamentBP::uncondBranch(void * &bp_history)
 246 {
 247     // Create BPHistory and pass it back to be recorded.
 248     BPHistory *history = new BPHistory;
 249     history->globalHistory = globalHistory;
 250     history->localPredTaken = true;
 251     history->globalPredTaken = true;
 252     history->globalUsed = true;
 253     history->localHistory = invalidPredictorIndex;
 254     bp_history = static_cast<void *>(history);
 255
 256     updateGlobalHistTaken();
 257 }
 258
 259 void
 260 TournamentBP::update(Addr branch_addr, bool taken, void *bp_history,
 261                      bool squashed)
 262 {
 263     unsigned local_history_idx;
 264     unsigned local_predictor_idx M5_VAR_USED;
 265     unsigned local_predictor_hist;
 266
 267     // Get the local predictor's current prediction
 268     local_history_idx = calcLocHistIdx(branch_addr);
 269     local_predictor_hist = localHistoryTable[local_history_idx];
 270     local_predictor_idx = local_predictor_hist & localPredictorMask;
 271
 272     if (bp_history) {
 273         BPHistory *history = static_cast<BPHistory *>(bp_history);
 274         // Update may also be called if the Branch target is incorrect even if
 275         // the prediction is correct. In that case do not update the counters.
 276         bool historyPred = false;
 277         unsigned old_local_pred_index = history->localHistory &
 278                 localPredictorMask;
 279
 280         bool old_local_pred_valid = history->localHistory !=
 281             invalidPredictorIndex;
 282
 283         assert(old_local_pred_index < localPredictorSize);
 284
 285         if (history->globalUsed) {
 286            historyPred = history->globalPredTaken;
 287         } else {
 288            historyPred = history->localPredTaken;
 289         }
 290         if (historyPred != taken || !squashed) {
 291             // Update the choice predictor to tell it which one was correct if
 292             // there was a prediction.
 293             if (history->localPredTaken != history->globalPredTaken) {
 294                  // If the local prediction matches the actual outcome,
 295                  // decerement the counter.  Otherwise increment the
 296                  // counter.
 297                  unsigned choice_predictor_idx =
 298                    history->globalHistory & choiceHistoryMask;
 299                  if (history->localPredTaken == taken) {
 300                      choiceCtrs[choice_predictor_idx].decrement();
 301                  } else if (history->globalPredTaken == taken) {
 302                      choiceCtrs[choice_predictor_idx].increment();
 303                  }
 304
 305              }
 306
 307              // Update the counters and local history with the proper
 308              // resolution of the branch.  Global history is updated
 309              // speculatively and restored upon squash() calls, so it does not
 310              // need to be updated.
 311              unsigned global_predictor_idx =
 312                history->globalHistory & globalHistoryMask;
 313              if (taken) {
 314                   globalCtrs[global_predictor_idx].increment();
 315                   if (old_local_pred_valid) {
 316                           localCtrs[old_local_pred_index].increment();
 317                   }
 318              } else {
 319                   globalCtrs[global_predictor_idx].decrement();
 320                   if (old_local_pred_valid) {
 321                           localCtrs[old_local_pred_index].decrement();
 322                   }
 323              }
 324         }
 325         if (squashed) {
 326              if (taken) {
 327                 globalHistory = (history->globalHistory << 1) | 1;
 328                 globalHistory = globalHistory & historyRegisterMask;
 329                 if (old_local_pred_valid) {
 330                     localHistoryTable[local_history_idx] =
 331                      (history->localHistory << 1) | 1;
 332                 }
 333              } else {
 334                 globalHistory = (history->globalHistory << 1);
 335                 globalHistory = globalHistory & historyRegisterMask;
 336                 if (old_local_pred_valid) {
 337                      localHistoryTable[local_history_idx] =
 338                      history->localHistory << 1;
 339                 }
 340              }
 341
 342         }
 343         // We're done with this history, now delete it.
 344         delete history;
 345
 346     }
 347
 348     assert(local_history_idx < localHistoryTableSize);
 349
 350
 351 }
 352
 353 void
 354 TournamentBP::squash(void *bp_history)
 355 {
 356     BPHistory *history = static_cast<BPHistory *>(bp_history);
 357
 358     // Restore global history to state prior to this branch.
 359     globalHistory = history->globalHistory;
 360
 361     // Delete this BPHistory now that we're done with it.
 362     delete history;
 363 }
 364
 365 #ifdef DEBUG
 366 int
 367 TournamentBP::BPHistory::newCount = 0;
 368 #endif