src/cpu/o3/tournament_pred.cc

   1 /*
   2  * Copyright (c) 2004-2006 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Kevin Lim
  29  */
  30
  31 #include "base/intmath.hh"
  32 #include "cpu/o3/tournament_pred.hh"
  33
  34 TournamentBP::TournamentBP(unsigned _localPredictorSize,
  35                            unsigned _localCtrBits,
  36                            unsigned _localHistoryTableSize,
  37                            unsigned _localHistoryBits,
  38                            unsigned _globalPredictorSize,
  39                            unsigned _globalCtrBits,
  40                            unsigned _globalHistoryBits,
  41                            unsigned _choicePredictorSize,
  42                            unsigned _choiceCtrBits,
  43                            unsigned _instShiftAmt)
  44     : localPredictorSize(_localPredictorSize),
  45       localCtrBits(_localCtrBits),
  46       localHistoryTableSize(_localHistoryTableSize),
  47       localHistoryBits(_localHistoryBits),
  48       globalPredictorSize(_globalPredictorSize),
  49       globalCtrBits(_globalCtrBits),
  50       globalHistoryBits(_globalHistoryBits),
  51       choicePredictorSize(_globalPredictorSize),
  52       choiceCtrBits(_choiceCtrBits),
  53       instShiftAmt(_instShiftAmt)
  54 {
  55     if (!isPowerOf2(localPredictorSize)) {
  56         fatal("Invalid local predictor size!\n");
  57     }
  58
  59     //Setup the array of counters for the local predictor
  60     localCtrs.resize(localPredictorSize);
  61
  62     for (int i = 0; i < localPredictorSize; ++i)
  63         localCtrs[i].setBits(localCtrBits);
  64
  65     if (!isPowerOf2(localHistoryTableSize)) {
  66         fatal("Invalid local history table size!\n");
  67     }
  68
  69     //Setup the history table for the local table
  70     localHistoryTable.resize(localHistoryTableSize);
  71
  72     for (int i = 0; i < localHistoryTableSize; ++i)
  73         localHistoryTable[i] = 0;
  74
  75     // Setup the local history mask
  76     localHistoryMask = (1 << localHistoryBits) - 1;
  77
  78     if (!isPowerOf2(globalPredictorSize)) {
  79         fatal("Invalid global predictor size!\n");
  80     }
  81
  82     //Setup the array of counters for the global predictor
  83     globalCtrs.resize(globalPredictorSize);
  84
  85     for (int i = 0; i < globalPredictorSize; ++i)
  86         globalCtrs[i].setBits(globalCtrBits);
  87
  88     //Clear the global history
  89     globalHistory = 0;
  90     // Setup the global history mask
  91     globalHistoryMask = (1 << globalHistoryBits) - 1;
  92
  93     if (!isPowerOf2(choicePredictorSize)) {
  94         fatal("Invalid choice predictor size!\n");
  95     }
  96
  97     //Setup the array of counters for the choice predictor
  98     choiceCtrs.resize(choicePredictorSize);
  99
 100     for (int i = 0; i < choicePredictorSize; ++i)
 101         choiceCtrs[i].setBits(choiceCtrBits);
 102
 103     // @todo: Allow for different thresholds between the predictors.
 104     threshold = (1 << (localCtrBits - 1)) - 1;
 105     threshold = threshold / 2;
 106 }
 107
 108 inline
 109 unsigned
 110 TournamentBP::calcLocHistIdx(Addr &branch_addr)
 111 {
 112     // Get low order bits after removing instruction offset.
 113     return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
 114 }
 115
 116 inline
 117 void
 118 TournamentBP::updateGlobalHistTaken()
 119 {
 120     globalHistory = (globalHistory << 1) | 1;
 121     globalHistory = globalHistory & globalHistoryMask;
 122 }
 123
 124 inline
 125 void
 126 TournamentBP::updateGlobalHistNotTaken()
 127 {
 128     globalHistory = (globalHistory << 1);
 129     globalHistory = globalHistory & globalHistoryMask;
 130 }
 131
 132 inline
 133 void
 134 TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
 135 {
 136     localHistoryTable[local_history_idx] =
 137         (localHistoryTable[local_history_idx] << 1) | 1;
 138 }
 139
 140 inline
 141 void
 142 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
 143 {
 144     localHistoryTable[local_history_idx] =
 145         (localHistoryTable[local_history_idx] << 1);
 146 }
 147
 148 bool
 149 TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
 150 {
 151     bool local_prediction;
 152     unsigned local_history_idx;
 153     unsigned local_predictor_idx;
 154
 155     bool global_prediction;
 156     bool choice_prediction;
 157
 158     //Lookup in the local predictor to get its branch prediction
 159     local_history_idx = calcLocHistIdx(branch_addr);
 160     local_predictor_idx = localHistoryTable[local_history_idx]
 161         & localHistoryMask;
 162     local_prediction = localCtrs[local_predictor_idx].read() > threshold;
 163
 164     //Lookup in the global predictor to get its branch prediction
 165     global_prediction = globalCtrs[globalHistory].read() > threshold;
 166
 167     //Lookup in the choice predictor to see which one to use
 168     choice_prediction = choiceCtrs[globalHistory].read() > threshold;
 169
 170     // Create BPHistory and pass it back to be recorded.
 171     BPHistory *history = new BPHistory;
 172     history->globalHistory = globalHistory;
 173     history->localPredTaken = local_prediction;
 174     history->globalPredTaken = global_prediction;
 175     history->globalUsed = choice_prediction;
 176     bp_history = (void *)history;
 177
 178     assert(globalHistory < globalPredictorSize &&
 179            local_history_idx < localPredictorSize);
 180
 181     // Commented code is for doing speculative update of counters and
 182     // all histories.
 183     if (choice_prediction) {
 184         if (global_prediction) {
 185 //            updateHistoriesTaken(local_history_idx);
 186 //            globalCtrs[globalHistory].increment();
 187 //            localCtrs[local_history_idx].increment();
 188             updateGlobalHistTaken();
 189             return true;
 190         } else {
 191 //            updateHistoriesNotTaken(local_history_idx);
 192 //            globalCtrs[globalHistory].decrement();
 193 //            localCtrs[local_history_idx].decrement();
 194             updateGlobalHistNotTaken();
 195             return false;
 196         }
 197     } else {
 198         if (local_prediction) {
 199 //            updateHistoriesTaken(local_history_idx);
 200 //            globalCtrs[globalHistory].increment();
 201 //            localCtrs[local_history_idx].increment();
 202             updateGlobalHistTaken();
 203             return true;
 204         } else {
 205 //            updateHistoriesNotTaken(local_history_idx);
 206 //            globalCtrs[globalHistory].decrement();
 207 //            localCtrs[local_history_idx].decrement();
 208             updateGlobalHistNotTaken();
 209             return false;
 210         }
 211     }
 212 }
 213
 214 void
 215 TournamentBP::uncondBr(void * &bp_history)
 216 {
 217     // Create BPHistory and pass it back to be recorded.
 218     BPHistory *history = new BPHistory;
 219     history->globalHistory = globalHistory;
 220     history->localPredTaken = true;
 221     history->globalPredTaken = true;
 222     bp_history = static_cast<void *>(history);
 223
 224     updateGlobalHistTaken();
 225 }
 226
 227 void
 228 TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
 229 {
 230     unsigned local_history_idx;
 231     unsigned local_predictor_idx;
 232     unsigned local_predictor_hist;
 233
 234     // Get the local predictor's current prediction
 235     local_history_idx = calcLocHistIdx(branch_addr);
 236     local_predictor_hist = localHistoryTable[local_history_idx];
 237     local_predictor_idx = local_predictor_hist & localHistoryMask;
 238
 239     // Update the choice predictor to tell it which one was correct if
 240     // there was a prediction.
 241     if (bp_history) {
 242         BPHistory *history = static_cast<BPHistory *>(bp_history);
 243         if (history->localPredTaken != history->globalPredTaken) {
 244             // If the local prediction matches the actual outcome,
 245             // decerement the counter.  Otherwise increment the
 246             // counter.
 247             if (history->localPredTaken == taken) {
 248                 choiceCtrs[globalHistory].decrement();
 249             } else if (history->globalPredTaken == taken){
 250                 choiceCtrs[globalHistory].increment();
 251             }
 252         }
 253
 254         // We're done with this history, now delete it.
 255         delete history;
 256     }
 257
 258     assert(globalHistory < globalPredictorSize &&
 259            local_predictor_idx < localPredictorSize);
 260
 261     // Update the counters and local history with the proper
 262     // resolution of the branch.  Global history is updated
 263     // speculatively and restored upon squash() calls, so it does not
 264     // need to be updated.
 265     if (taken) {
 266         localCtrs[local_predictor_idx].increment();
 267         globalCtrs[globalHistory].increment();
 268
 269         updateLocalHistTaken(local_history_idx);
 270     } else {
 271         localCtrs[local_predictor_idx].decrement();
 272         globalCtrs[globalHistory].decrement();
 273
 274         updateLocalHistNotTaken(local_history_idx);
 275     }
 276 }
 277
 278 void
 279 TournamentBP::squash(void *bp_history)
 280 {
 281     BPHistory *history = static_cast<BPHistory *>(bp_history);
 282
 283     // Restore global history to state prior to this branch.
 284     globalHistory = history->globalHistory;
 285
 286     // Delete this BPHistory now that we're done with it.
 287     delete history;
 288 }
 289
 290 #ifdef DEBUG
 291 int
 292 TournamentBP::BPHistory::newCount = 0;
 293 #endif