tournament.cc revision 8463
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/pred/tournament.hh" 33 34TournamentBP::TournamentBP(unsigned _localPredictorSize, 35 unsigned _localCtrBits, 36 unsigned _localHistoryTableSize, 37 unsigned _localHistoryBits, 38 unsigned _globalPredictorSize, 39 unsigned _globalHistoryBits, 40 unsigned _globalCtrBits, 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} 108 109inline 110unsigned 111TournamentBP::calcLocHistIdx(Addr &branch_addr) 112{ 113 // Get low order bits after removing instruction offset. 114 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 115} 116 117inline 118void 119TournamentBP::updateGlobalHistTaken() 120{ 121 globalHistory = (globalHistory << 1) | 1; 122 globalHistory = globalHistory & globalHistoryMask; 123} 124 125inline 126void 127TournamentBP::updateGlobalHistNotTaken() 128{ 129 globalHistory = (globalHistory << 1); 130 globalHistory = globalHistory & globalHistoryMask; 131} 132 133inline 134void 135TournamentBP::updateLocalHistTaken(unsigned local_history_idx) 136{ 137 localHistoryTable[local_history_idx] = 138 (localHistoryTable[local_history_idx] << 1) | 1; 139} 140 141inline 142void 143TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 144{ 145 localHistoryTable[local_history_idx] = 146 (localHistoryTable[local_history_idx] << 1); 147} 148 149bool 150TournamentBP::lookup(Addr &branch_addr, void * &bp_history) 151{ 152 bool local_prediction; 153 unsigned local_history_idx; 154 unsigned local_predictor_idx; 155 156 bool global_prediction; 157 bool choice_prediction; 158 159 //Lookup in the local predictor to get its branch prediction 160 local_history_idx = calcLocHistIdx(branch_addr); 161 local_predictor_idx = localHistoryTable[local_history_idx] 162 & localPredictorMask; 163 local_prediction = localCtrs[local_predictor_idx].read() > threshold; 164 165 //Lookup in the global predictor to get its branch prediction 166 global_prediction = globalCtrs[globalHistory].read() > threshold; 167 168 //Lookup in the choice predictor to see which one to use 169 choice_prediction = choiceCtrs[globalHistory].read() > threshold; 170 171 // Create BPHistory and pass it back to be recorded. 172 BPHistory *history = new BPHistory; 173 history->globalHistory = globalHistory; 174 history->localPredTaken = local_prediction; 175 history->globalPredTaken = global_prediction; 176 history->globalUsed = choice_prediction; 177 bp_history = (void *)history; 178 179 assert(globalHistory < globalPredictorSize && 180 local_history_idx < localHistoryTableSize && 181 local_predictor_idx < localPredictorSize); 182 183 // Commented code is for doing speculative update of counters and 184 // all histories. 185 if (choice_prediction) { 186 if (global_prediction) { 187// updateHistoriesTaken(local_history_idx); 188// globalCtrs[globalHistory].increment(); 189// localCtrs[local_history_idx].increment(); 190 updateGlobalHistTaken(); 191 return true; 192 } else { 193// updateHistoriesNotTaken(local_history_idx); 194// globalCtrs[globalHistory].decrement(); 195// localCtrs[local_history_idx].decrement(); 196 updateGlobalHistNotTaken(); 197 return false; 198 } 199 } else { 200 if (local_prediction) { 201// updateHistoriesTaken(local_history_idx); 202// globalCtrs[globalHistory].increment(); 203// localCtrs[local_history_idx].increment(); 204 updateGlobalHistTaken(); 205 return true; 206 } else { 207// updateHistoriesNotTaken(local_history_idx); 208// globalCtrs[globalHistory].decrement(); 209// localCtrs[local_history_idx].decrement(); 210 updateGlobalHistNotTaken(); 211 return false; 212 } 213 } 214} 215 216void 217TournamentBP::uncondBr(void * &bp_history) 218{ 219 // Create BPHistory and pass it back to be recorded. 220 BPHistory *history = new BPHistory; 221 history->globalHistory = globalHistory; 222 history->localPredTaken = true; 223 history->globalPredTaken = true; 224 bp_history = static_cast<void *>(history); 225 226 updateGlobalHistTaken(); 227} 228 229void 230TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history) 231{ 232 unsigned local_history_idx; 233 unsigned local_predictor_idx; 234 unsigned local_predictor_hist; 235 236 // Get the local predictor's current prediction 237 local_history_idx = calcLocHistIdx(branch_addr); 238 local_predictor_hist = localHistoryTable[local_history_idx]; 239 local_predictor_idx = local_predictor_hist & localPredictorMask; 240 241 // Update the choice predictor to tell it which one was correct if 242 // there was a prediction. 243 if (bp_history) { 244 BPHistory *history = static_cast<BPHistory *>(bp_history); 245 if (history->localPredTaken != history->globalPredTaken) { 246 // If the local prediction matches the actual outcome, 247 // decerement the counter. Otherwise increment the 248 // counter. 249 if (history->localPredTaken == taken) { 250 choiceCtrs[history->globalHistory].decrement(); 251 } else if (history->globalPredTaken == taken){ 252 choiceCtrs[history->globalHistory].increment(); 253 } 254 255 } 256 257 // Update the counters and local history with the proper 258 // resolution of the branch. Global history is updated 259 // speculatively and restored upon squash() calls, so it does not 260 // need to be updated. 261 if (taken) { 262 localCtrs[local_predictor_idx].increment(); 263 globalCtrs[history->globalHistory].increment(); 264 265 updateLocalHistTaken(local_history_idx); 266 } else { 267 localCtrs[local_predictor_idx].decrement(); 268 globalCtrs[history->globalHistory].decrement(); 269 270 updateLocalHistNotTaken(local_history_idx); 271 } 272 273 bool mispredict = false; 274 275 //global predictor used and mispredicted 276 if (history->globalUsed && history->globalPredTaken != taken) 277 mispredict = true; 278 //local predictor used and mispredicted 279 else if (!history->globalUsed && history->localPredTaken != taken) 280 mispredict = true; 281 282 if (mispredict) { 283 if (taken) { 284 globalHistory = globalHistory | 1; 285 } else { 286 unsigned mask = globalHistoryMask - 1; 287 globalHistory = globalHistory & mask; 288 } 289 290 } 291 // We're done with this history, now delete it. 292 delete history; 293 } 294 295 assert(globalHistory < globalPredictorSize && 296 local_history_idx < localHistoryTableSize && 297 local_predictor_idx < localPredictorSize); 298 299 300} 301 302void 303TournamentBP::squash(void *bp_history) 304{ 305 BPHistory *history = static_cast<BPHistory *>(bp_history); 306 307 // Restore global history to state prior to this branch. 308 globalHistory = history->globalHistory; 309 310 // Delete this BPHistory now that we're done with it. 311 delete history; 312} 313 314#ifdef DEBUG 315int 316TournamentBP::BPHistory::newCount = 0; 317#endif 318