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
  29 #include "base/intmath.hh"
  30 #include "cpu/o3/tournament_pred.hh"
  31
  32 TournamentBP::TournamentBP(unsigned _localPredictorSize,
  33                            unsigned _localCtrBits,
  34                            unsigned _localHistoryTableSize,
  35                            unsigned _localHistoryBits,
  36                            unsigned _globalPredictorSize,
  37                            unsigned _globalCtrBits,
  38                            unsigned _globalHistoryBits,
  39                            unsigned _choicePredictorSize,
  40                            unsigned _choiceCtrBits,
  41                            unsigned _instShiftAmt)
  42     : localPredictorSize(_localPredictorSize),
  43       localCtrBits(_localCtrBits),
  44       localHistoryTableSize(_localHistoryTableSize),
  45       localHistoryBits(_localHistoryBits),
  46       globalPredictorSize(_globalPredictorSize),
  47       globalCtrBits(_globalCtrBits),
  48       globalHistoryBits(_globalHistoryBits),
  49       choicePredictorSize(_globalPredictorSize),
  50       choiceCtrBits(_choiceCtrBits),
  51       instShiftAmt(_instShiftAmt)
  52 {
  53     if (!isPowerOf2(localPredictorSize)) {
  54         fatal("Invalid local predictor size!\n");
  55     }
  56
  57     //Setup the array of counters for the local predictor
  58     localCtrs.resize(localPredictorSize);
  59
  60     for (int i = 0; i < localPredictorSize; ++i)
  61         localCtrs[i].setBits(localCtrBits);
  62
  63     localPredictorMask = floorPow2(localPredictorSize) - 1;
  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         & localPredictorMask;
 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 < localHistoryTableSize &&
 180            local_predictor_idx < localPredictorSize);
 181
 182     // Commented code is for doing speculative update of counters and
 183     // all histories.
 184     if (choice_prediction) {
 185         if (global_prediction) {
 186 //            updateHistoriesTaken(local_history_idx);
 187 //            globalCtrs[globalHistory].increment();
 188 //            localCtrs[local_history_idx].increment();
 189             updateGlobalHistTaken();
 190             return true;
 191         } else {
 192 //            updateHistoriesNotTaken(local_history_idx);
 193 //            globalCtrs[globalHistory].decrement();
 194 //            localCtrs[local_history_idx].decrement();
 195             updateGlobalHistNotTaken();
 196             return false;
 197         }
 198     } else {
 199         if (local_prediction) {
 200 //            updateHistoriesTaken(local_history_idx);
 201 //            globalCtrs[globalHistory].increment();
 202 //            localCtrs[local_history_idx].increment();
 203             updateGlobalHistTaken();
 204             return true;
 205         } else {
 206 //            updateHistoriesNotTaken(local_history_idx);
 207 //            globalCtrs[globalHistory].decrement();
 208 //            localCtrs[local_history_idx].decrement();
 209             updateGlobalHistNotTaken();
 210             return false;
 211         }
 212     }
 213 }
 214
 215 void
 216 TournamentBP::uncondBr(void * &bp_history)
 217 {
 218     // Create BPHistory and pass it back to be recorded.
 219     BPHistory *history = new BPHistory;
 220     history->globalHistory = globalHistory;
 221     history->localPredTaken = true;
 222     history->globalPredTaken = true;
 223     bp_history = static_cast<void *>(history);
 224
 225     updateGlobalHistTaken();
 226 }
 227
 228 void
 229 TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
 230 {
 231     unsigned local_history_idx;
 232     unsigned local_predictor_idx;
 233     unsigned local_predictor_hist;
 234
 235     // Get the local predictor's current prediction
 236     local_history_idx = calcLocHistIdx(branch_addr);
 237     local_predictor_hist = localHistoryTable[local_history_idx];
 238     local_predictor_idx = local_predictor_hist & localPredictorMask;
 239
 240     // Update the choice predictor to tell it which one was correct if
 241     // there was a prediction.
 242     if (bp_history) {
 243         BPHistory *history = static_cast<BPHistory *>(bp_history);
 244         if (history->localPredTaken != history->globalPredTaken) {
 245             // If the local prediction matches the actual outcome,
 246             // decerement the counter.  Otherwise increment the
 247             // counter.
 248             if (history->localPredTaken == taken) {
 249                 choiceCtrs[globalHistory].decrement();
 250             } else if (history->globalPredTaken == taken){
 251                 choiceCtrs[globalHistory].increment();
 252             }
 253         }
 254
 255         // We're done with this history, now delete it.
 256         delete history;
 257     }
 258
 259     assert(globalHistory < globalPredictorSize &&
 260            local_history_idx < localHistoryTableSize &&
 261            local_predictor_idx < localPredictorSize);
 262
 263     // Update the counters and local history with the proper
 264     // resolution of the branch.  Global history is updated
 265     // speculatively and restored upon squash() calls, so it does not
 266     // need to be updated.
 267     if (taken) {
 268         localCtrs[local_predictor_idx].increment();
 269         globalCtrs[globalHistory].increment();
 270
 271         updateLocalHistTaken(local_history_idx);
 272     } else {
 273         localCtrs[local_predictor_idx].decrement();
 274         globalCtrs[globalHistory].decrement();
 275
 276         updateLocalHistNotTaken(local_history_idx);
 277     }
 278 }
 279
 280 void
 281 TournamentBP::squash(void *bp_history)
 282 {
 283     BPHistory *history = static_cast<BPHistory *>(bp_history);
 284
 285     // Restore global history to state prior to this branch.
 286     globalHistory = history->globalHistory;
 287
 288     // Delete this BPHistory now that we're done with it.
 289     delete history;
 290 }
 291
 292 #ifdef DEBUG
 293 int
 294 TournamentBP::BPHistory::newCount = 0;
 295 #endif