cpu/o3/tournament_pred.cc

   1 /*
   2  * Copyright (c) 2004-2005 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 "cpu/o3/tournament_pred.hh"
  30
  31 TournamentBP::TournamentBP(unsigned _local_predictor_size,
  32                            unsigned _local_ctr_bits,
  33                            unsigned _local_history_table_size,
  34                            unsigned _local_history_bits,
  35                            unsigned _global_predictor_size,
  36                            unsigned _global_ctr_bits,
  37                            unsigned _global_history_bits,
  38                            unsigned _choice_predictor_size,
  39                            unsigned _choice_ctr_bits,
  40                            unsigned _instShiftAmt)
  41     : localPredictorSize(_local_predictor_size),
  42       localCtrBits(_local_ctr_bits),
  43       localHistoryTableSize(_local_history_table_size),
  44       localHistoryBits(_local_history_bits),
  45       globalPredictorSize(_global_predictor_size),
  46       globalCtrBits(_global_ctr_bits),
  47       globalHistoryBits(_global_history_bits),
  48       choicePredictorSize(_global_predictor_size),
  49       choiceCtrBits(_choice_ctr_bits),
  50       instShiftAmt(_instShiftAmt)
  51 {
  52     //Should do checks here to make sure sizes are correct (powers of 2)
  53
  54     //Setup the array of counters for the local predictor
  55     localCtrs = new SatCounter[localPredictorSize];
  56
  57     for (int i = 0; i < localPredictorSize; ++i)
  58         localCtrs[i].setBits(localCtrBits);
  59
  60     //Setup the history table for the local table
  61     localHistoryTable = new unsigned[localHistoryTableSize];
  62
  63     for (int i = 0; i < localHistoryTableSize; ++i)
  64         localHistoryTable[i] = 0;
  65
  66     // Setup the local history mask
  67     localHistoryMask = (1 << localHistoryBits) - 1;
  68
  69     //Setup the array of counters for the global predictor
  70     globalCtrs = new SatCounter[globalPredictorSize];
  71
  72     for (int i = 0; i < globalPredictorSize; ++i)
  73         globalCtrs[i].setBits(globalCtrBits);
  74
  75     //Clear the global history
  76     globalHistory = 0;
  77     // Setup the global history mask
  78     globalHistoryMask = (1 << globalHistoryBits) - 1;
  79
  80     //Setup the array of counters for the choice predictor
  81     choiceCtrs = new SatCounter[choicePredictorSize];
  82
  83     for (int i = 0; i < choicePredictorSize; ++i)
  84         choiceCtrs[i].setBits(choiceCtrBits);
  85
  86     threshold = (1 << (localCtrBits - 1)) - 1;
  87     threshold = threshold / 2;
  88 }
  89
  90 inline
  91 unsigned
  92 TournamentBP::calcLocHistIdx(Addr &branch_addr)
  93 {
  94     return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
  95 }
  96
  97 inline
  98 void
  99 TournamentBP::updateHistoriesTaken(unsigned local_history_idx)
 100 {
 101     globalHistory = (globalHistory << 1) | 1;
 102     globalHistory = globalHistory & globalHistoryMask;
 103
 104     localHistoryTable[local_history_idx] =
 105         (localHistoryTable[local_history_idx] << 1) | 1;
 106 }
 107
 108 inline
 109 void
 110 TournamentBP::updateHistoriesNotTaken(unsigned local_history_idx)
 111 {
 112     globalHistory = (globalHistory << 1);
 113     globalHistory = globalHistory & globalHistoryMask;
 114
 115     localHistoryTable[local_history_idx] =
 116         (localHistoryTable[local_history_idx] << 1);
 117 }
 118
 119 bool
 120 TournamentBP::lookup(Addr &branch_addr)
 121 {
 122     uint8_t local_prediction;
 123     unsigned local_history_idx;
 124     unsigned local_predictor_idx;
 125
 126     uint8_t global_prediction;
 127     uint8_t choice_prediction;
 128
 129     //Lookup in the local predictor to get its branch prediction
 130     local_history_idx = calcLocHistIdx(branch_addr);
 131     local_predictor_idx = localHistoryTable[local_history_idx]
 132         & localHistoryMask;
 133     local_prediction = localCtrs[local_predictor_idx].read();
 134
 135     //Lookup in the global predictor to get its branch prediction
 136     global_prediction = globalCtrs[globalHistory].read();
 137
 138     //Lookup in the choice predictor to see which one to use
 139     choice_prediction = choiceCtrs[globalHistory].read();
 140
 141     //@todo Put a threshold value in for the three predictors that can
 142     // be set through the constructor (so this isn't hard coded).
 143     //Also should put some of this code into functions.
 144     if (choice_prediction > threshold) {
 145         if (global_prediction > threshold) {
 146             updateHistoriesTaken(local_history_idx);
 147
 148             assert(globalHistory < globalPredictorSize &&
 149                    local_history_idx < localPredictorSize);
 150
 151             globalCtrs[globalHistory].increment();
 152             localCtrs[local_history_idx].increment();
 153
 154             return true;
 155         } else {
 156             updateHistoriesNotTaken(local_history_idx);
 157
 158             assert(globalHistory < globalPredictorSize &&
 159                    local_history_idx < localPredictorSize);
 160
 161             globalCtrs[globalHistory].decrement();
 162             localCtrs[local_history_idx].decrement();
 163
 164             return false;
 165         }
 166     } else {
 167         if (local_prediction > threshold) {
 168             updateHistoriesTaken(local_history_idx);
 169
 170             assert(globalHistory < globalPredictorSize &&
 171                    local_history_idx < localPredictorSize);
 172
 173             globalCtrs[globalHistory].increment();
 174             localCtrs[local_history_idx].increment();
 175
 176             return true;
 177         } else {
 178             updateHistoriesNotTaken(local_history_idx);
 179
 180             assert(globalHistory < globalPredictorSize &&
 181                    local_history_idx < localPredictorSize);
 182
 183             globalCtrs[globalHistory].decrement();
 184             localCtrs[local_history_idx].decrement();
 185
 186             return false;
 187         }
 188     }
 189 }
 190
 191 // Update the branch predictor if it predicted a branch wrong.
 192 void
 193 TournamentBP::update(Addr &branch_addr, unsigned correct_gh, bool taken)
 194 {
 195
 196     uint8_t local_prediction;
 197     unsigned local_history_idx;
 198     unsigned local_predictor_idx;
 199     bool local_pred_taken;
 200
 201     uint8_t global_prediction;
 202     bool global_pred_taken;
 203
 204     // Load the correct global history into the register.
 205     globalHistory = correct_gh;
 206
 207     // Get the local predictor's current prediction, remove the incorrect
 208     // update, and update the local predictor
 209     local_history_idx = calcLocHistIdx(branch_addr);
 210     local_predictor_idx = localHistoryTable[local_history_idx];
 211     local_predictor_idx = (local_predictor_idx >> 1) & localHistoryMask;
 212
 213     local_prediction = localCtrs[local_predictor_idx].read();
 214     local_pred_taken = local_prediction > threshold;
 215
 216     //Get the global predictor's current prediction, and update the
 217     //global predictor
 218     global_prediction = globalCtrs[globalHistory].read();
 219     global_pred_taken = global_prediction > threshold;
 220
 221     //Update the choice predictor to tell it which one was correct
 222     if (local_pred_taken != global_pred_taken) {
 223         //If the local prediction matches the actual outcome, decerement
 224         //the counter.  Otherwise increment the counter.
 225         if (local_pred_taken == taken) {
 226             choiceCtrs[globalHistory].decrement();
 227         } else {
 228             choiceCtrs[globalHistory].increment();
 229         }
 230     }
 231
 232     if (taken) {
 233         assert(globalHistory < globalPredictorSize &&
 234                local_predictor_idx < localPredictorSize);
 235
 236         localCtrs[local_predictor_idx].increment();
 237         globalCtrs[globalHistory].increment();
 238
 239         globalHistory = (globalHistory << 1) | 1;
 240         globalHistory = globalHistory & globalHistoryMask;
 241
 242         localHistoryTable[local_history_idx] |= 1;
 243     }
 244     else {
 245         assert(globalHistory < globalPredictorSize &&
 246                local_predictor_idx < localPredictorSize);
 247
 248         localCtrs[local_predictor_idx].decrement();
 249         globalCtrs[globalHistory].decrement();
 250
 251         globalHistory = (globalHistory << 1);
 252         globalHistory = globalHistory & globalHistoryMask;
 253
 254         localHistoryTable[local_history_idx] &= ~1;
 255     }
 256 }