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     localPredictorMask = floorPow2(localPredictorSize) - 1;
  66
  67     if (!isPowerOf2(localHistoryTableSize)) {
  68         fatal("Invalid local history table size!\n");
  69     }
  70
  71     //Setup the history table for the local table
  72     localHistoryTable.resize(localHistoryTableSize);
  73
  74     for (int i = 0; i < localHistoryTableSize; ++i)
  75         localHistoryTable[i] = 0;
  76
  77     // Setup the local history mask
  78     localHistoryMask = (1 << localHistoryBits) - 1;
  79
  80     if (!isPowerOf2(globalPredictorSize)) {
  81         fatal("Invalid global predictor size!\n");
  82     }
  83
  84     //Setup the array of counters for the global predictor
  85     globalCtrs.resize(globalPredictorSize);
  86
  87     for (int i = 0; i < globalPredictorSize; ++i)
  88         globalCtrs[i].setBits(globalCtrBits);
  89
  90     //Clear the global history
  91     globalHistory = 0;
  92     // Setup the global history mask
  93     globalHistoryMask = (1 << globalHistoryBits) - 1;
  94
  95     if (!isPowerOf2(choicePredictorSize)) {
  96         fatal("Invalid choice predictor size!\n");
  97     }
  98
  99     //Setup the array of counters for the choice predictor
 100     choiceCtrs.resize(choicePredictorSize);
 101
 102     for (int i = 0; i < choicePredictorSize; ++i)
 103         choiceCtrs[i].setBits(choiceCtrBits);
 104
 105     // @todo: Allow for different thresholds between the predictors.
 106     threshold = (1 << (localCtrBits - 1)) - 1;
 107     threshold = threshold / 2;
 108 }
 109
 110 inline
 111 unsigned
 112 TournamentBP::calcLocHistIdx(Addr &branch_addr)
 113 {
 114     // Get low order bits after removing instruction offset.
 115     return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
 116 }
 117
 118 inline
 119 void
 120 TournamentBP::updateGlobalHistTaken()
 121 {
 122     globalHistory = (globalHistory << 1) | 1;
 123     globalHistory = globalHistory & globalHistoryMask;
 124 }
 125
 126 inline
 127 void
 128 TournamentBP::updateGlobalHistNotTaken()
 129 {
 130     globalHistory = (globalHistory << 1);
 131     globalHistory = globalHistory & globalHistoryMask;
 132 }
 133
 134 inline
 135 void
 136 TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
 137 {
 138     localHistoryTable[local_history_idx] =
 139         (localHistoryTable[local_history_idx] << 1) | 1;
 140 }
 141
 142 inline
 143 void
 144 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
 145 {
 146     localHistoryTable[local_history_idx] =
 147         (localHistoryTable[local_history_idx] << 1);
 148 }
 149
 150 bool
 151 TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
 152 {
 153     bool local_prediction;
 154     unsigned local_history_idx;
 155     unsigned local_predictor_idx;
 156
 157     bool global_prediction;
 158     bool choice_prediction;
 159
 160     //Lookup in the local predictor to get its branch prediction
 161     local_history_idx = calcLocHistIdx(branch_addr);
 162     local_predictor_idx = localHistoryTable[local_history_idx]
 163         & localPredictorMask;
 164     local_prediction = localCtrs[local_predictor_idx].read() > threshold;
 165
 166     //Lookup in the global predictor to get its branch prediction
 167     global_prediction = globalCtrs[globalHistory].read() > threshold;
 168
 169     //Lookup in the choice predictor to see which one to use
 170     choice_prediction = choiceCtrs[globalHistory].read() > threshold;
 171
 172     // Create BPHistory and pass it back to be recorded.
 173     BPHistory *history = new BPHistory;
 174     history->globalHistory = globalHistory;
 175     history->localPredTaken = local_prediction;
 176     history->globalPredTaken = global_prediction;
 177     history->globalUsed = choice_prediction;
 178     bp_history = (void *)history;
 179
 180     assert(globalHistory < globalPredictorSize &&
 181            local_history_idx < localHistoryTableSize &&
 182            local_predictor_idx < localPredictorSize);
 183
 184     // Commented code is for doing speculative update of counters and
 185     // all histories.
 186     if (choice_prediction) {
 187         if (global_prediction) {
 188 //            updateHistoriesTaken(local_history_idx);
 189 //            globalCtrs[globalHistory].increment();
 190 //            localCtrs[local_history_idx].increment();
 191             updateGlobalHistTaken();
 192             return true;
 193         } else {
 194 //            updateHistoriesNotTaken(local_history_idx);
 195 //            globalCtrs[globalHistory].decrement();
 196 //            localCtrs[local_history_idx].decrement();
 197             updateGlobalHistNotTaken();
 198             return false;
 199         }
 200     } else {
 201         if (local_prediction) {
 202 //            updateHistoriesTaken(local_history_idx);
 203 //            globalCtrs[globalHistory].increment();
 204 //            localCtrs[local_history_idx].increment();
 205             updateGlobalHistTaken();
 206             return true;
 207         } else {
 208 //            updateHistoriesNotTaken(local_history_idx);
 209 //            globalCtrs[globalHistory].decrement();
 210 //            localCtrs[local_history_idx].decrement();
 211             updateGlobalHistNotTaken();
 212             return false;
 213         }
 214     }
 215 }
 216
 217 void
 218 TournamentBP::uncondBr(void * &bp_history)
 219 {
 220     // Create BPHistory and pass it back to be recorded.
 221     BPHistory *history = new BPHistory;
 222     history->globalHistory = globalHistory;
 223     history->localPredTaken = true;
 224     history->globalPredTaken = true;
 225     bp_history = static_cast<void *>(history);
 226
 227     updateGlobalHistTaken();
 228 }
 229
 230 void
 231 TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
 232 {
 233     unsigned local_history_idx;
 234     unsigned local_predictor_idx;
 235     unsigned local_predictor_hist;
 236
 237     // Get the local predictor's current prediction
 238     local_history_idx = calcLocHistIdx(branch_addr);
 239     local_predictor_hist = localHistoryTable[local_history_idx];
 240     local_predictor_idx = local_predictor_hist & localPredictorMask;
 241
 242     // Update the choice predictor to tell it which one was correct if
 243     // there was a prediction.
 244     if (bp_history) {
 245         BPHistory *history = static_cast<BPHistory *>(bp_history);
 246         if (history->localPredTaken != history->globalPredTaken) {
 247             // If the local prediction matches the actual outcome,
 248             // decerement the counter.  Otherwise increment the
 249             // counter.
 250             if (history->localPredTaken == taken) {
 251                 choiceCtrs[globalHistory].decrement();
 252             } else if (history->globalPredTaken == taken){
 253                 choiceCtrs[globalHistory].increment();
 254             }
 255         }
 256
 257         // We're done with this history, now delete it.
 258         delete history;
 259     }
 260
 261     assert(globalHistory < globalPredictorSize &&
 262            local_history_idx < localHistoryTableSize &&
 263            local_predictor_idx < localPredictorSize);
 264
 265     // Update the counters and local history with the proper
 266     // resolution of the branch.  Global history is updated
 267     // speculatively and restored upon squash() calls, so it does not
 268     // need to be updated.
 269     if (taken) {
 270         localCtrs[local_predictor_idx].increment();
 271         globalCtrs[globalHistory].increment();
 272
 273         updateLocalHistTaken(local_history_idx);
 274     } else {
 275         localCtrs[local_predictor_idx].decrement();
 276         globalCtrs[globalHistory].decrement();
 277
 278         updateLocalHistNotTaken(local_history_idx);
 279     }
 280 }
 281
 282 void
 283 TournamentBP::squash(void *bp_history)
 284 {
 285     BPHistory *history = static_cast<BPHistory *>(bp_history);
 286
 287     // Restore global history to state prior to this branch.
 288     globalHistory = history->globalHistory;
 289
 290     // Delete this BPHistory now that we're done with it.
 291     delete history;
 292 }
 293
 294 #ifdef DEBUG
 295 int
 296 TournamentBP::BPHistory::newCount = 0;
 297 #endif