tournament.cc revision 9480
1/* 2 * Copyright (c) 2011 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2004-2006 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Kevin Lim 41 */ 42 43#include "base/bitfield.hh" 44#include "base/intmath.hh" 45#include "cpu/pred/tournament.hh" 46 47TournamentBP::TournamentBP(const Params *params) 48 : BPredUnit(params), 49 localCtrBits(params->localCtrBits), 50 localHistoryTableSize(params->localHistoryTableSize), 51 localHistoryBits(params->localHistoryBits), 52 globalPredictorSize(params->globalPredictorSize), 53 globalCtrBits(params->globalCtrBits), 54 globalHistoryBits(params->globalHistoryBits), 55 choicePredictorSize(params->choicePredictorSize), 56 choiceCtrBits(params->choiceCtrBits), 57 instShiftAmt(params->instShiftAmt) 58{ 59 localPredictorSize = ULL(1) << localHistoryBits; 60 61 //Set up the array of counters for the local predictor 62 localCtrs.resize(localPredictorSize); 63 64 for (int i = 0; i < localPredictorSize; ++i) 65 localCtrs[i].setBits(localCtrBits); 66 67 localPredictorMask = mask(localHistoryBits); 68 69 if (!isPowerOf2(localHistoryTableSize)) { 70 fatal("Invalid local history table size!\n"); 71 } 72 73 //Setup the history table for the local table 74 localHistoryTable.resize(localHistoryTableSize); 75 76 for (int i = 0; i < localHistoryTableSize; ++i) 77 localHistoryTable[i] = 0; 78 79 if (!isPowerOf2(globalPredictorSize)) { 80 fatal("Invalid global predictor size!\n"); 81 } 82 83 //Setup the array of counters for the global predictor 84 globalCtrs.resize(globalPredictorSize); 85 86 for (int i = 0; i < globalPredictorSize; ++i) 87 globalCtrs[i].setBits(globalCtrBits); 88 89 //Clear the global history 90 globalHistory = 0; 91 // Set up the global history mask 92 // this is equivalent to mask(log2(globalPredictorSize) 93 globalHistoryMask = globalPredictorSize - 1; 94 95 if (!isPowerOf2(choicePredictorSize)) { 96 fatal("Invalid choice predictor size!\n"); 97 } 98 99 // Set up choiceHistoryMask 100 // this is equivalent to mask(log2(choicePredictorSize) 101 choiceHistoryMask = choicePredictorSize - 1; 102 103 //Setup the array of counters for the choice predictor 104 choiceCtrs.resize(choicePredictorSize); 105 106 for (int i = 0; i < choicePredictorSize; ++i) 107 choiceCtrs[i].setBits(choiceCtrBits); 108 109 //Set up historyRegisterMask 110 historyRegisterMask = mask(globalHistoryBits); 111 112 //Check that predictors don't use more bits than they have available 113 if (globalHistoryMask > historyRegisterMask) { 114 fatal("Global predictor too large for global history bits!\n"); 115 } 116 if (choiceHistoryMask > historyRegisterMask) { 117 fatal("Choice predictor too large for global history bits!\n"); 118 } 119 120 if (globalHistoryMask < historyRegisterMask && 121 choiceHistoryMask < historyRegisterMask) { 122 inform("More global history bits than required by predictors\n"); 123 } 124 125 // Set thresholds for the three predictors' counters 126 // This is equivalent to (2^(Ctr))/2 - 1 127 localThreshold = (ULL(1) << (localCtrBits - 1)) - 1; 128 globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 129 choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 130} 131 132inline 133unsigned 134TournamentBP::calcLocHistIdx(Addr &branch_addr) 135{ 136 // Get low order bits after removing instruction offset. 137 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 138} 139 140inline 141void 142TournamentBP::updateGlobalHistTaken() 143{ 144 globalHistory = (globalHistory << 1) | 1; 145 globalHistory = globalHistory & historyRegisterMask; 146} 147 148inline 149void 150TournamentBP::updateGlobalHistNotTaken() 151{ 152 globalHistory = (globalHistory << 1); 153 globalHistory = globalHistory & historyRegisterMask; 154} 155 156inline 157void 158TournamentBP::updateLocalHistTaken(unsigned local_history_idx) 159{ 160 localHistoryTable[local_history_idx] = 161 (localHistoryTable[local_history_idx] << 1) | 1; 162} 163 164inline 165void 166TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 167{ 168 localHistoryTable[local_history_idx] = 169 (localHistoryTable[local_history_idx] << 1); 170} 171 172 173void 174TournamentBP::btbUpdate(Addr branch_addr, void * &bp_history) 175{ 176 unsigned local_history_idx = calcLocHistIdx(branch_addr); 177 //Update Global History to Not Taken (clear LSB) 178 globalHistory &= (historyRegisterMask & ~ULL(1)); 179 //Update Local History to Not Taken 180 localHistoryTable[local_history_idx] = 181 localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 182} 183 184bool 185TournamentBP::lookup(Addr branch_addr, void * &bp_history) 186{ 187 bool local_prediction; 188 unsigned local_history_idx; 189 unsigned local_predictor_idx; 190 191 bool global_prediction; 192 bool choice_prediction; 193 194 //Lookup in the local predictor to get its branch prediction 195 local_history_idx = calcLocHistIdx(branch_addr); 196 local_predictor_idx = localHistoryTable[local_history_idx] 197 & localPredictorMask; 198 local_prediction = localCtrs[local_predictor_idx].read() > localThreshold; 199 200 //Lookup in the global predictor to get its branch prediction 201 global_prediction = 202 globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold; 203 204 //Lookup in the choice predictor to see which one to use 205 choice_prediction = 206 choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold; 207 208 // Create BPHistory and pass it back to be recorded. 209 BPHistory *history = new BPHistory; 210 history->globalHistory = globalHistory; 211 history->localPredTaken = local_prediction; 212 history->globalPredTaken = global_prediction; 213 history->globalUsed = choice_prediction; 214 history->localHistory = local_predictor_idx; 215 bp_history = (void *)history; 216 217 assert(local_history_idx < localHistoryTableSize); 218 219 // Commented code is for doing speculative update of counters and 220 // all histories. 221 if (choice_prediction) { 222 if (global_prediction) { 223 updateGlobalHistTaken(); 224 updateLocalHistTaken(local_history_idx); 225 return true; 226 } else { 227 updateGlobalHistNotTaken(); 228 updateLocalHistNotTaken(local_history_idx); 229 return false; 230 } 231 } else { 232 if (local_prediction) { 233 updateGlobalHistTaken(); 234 updateLocalHistTaken(local_history_idx); 235 return true; 236 } else { 237 updateGlobalHistNotTaken(); 238 updateLocalHistNotTaken(local_history_idx); 239 return false; 240 } 241 } 242} 243 244void 245TournamentBP::uncondBranch(void * &bp_history) 246{ 247 // Create BPHistory and pass it back to be recorded. 248 BPHistory *history = new BPHistory; 249 history->globalHistory = globalHistory; 250 history->localPredTaken = true; 251 history->globalPredTaken = true; 252 history->globalUsed = true; 253 history->localHistory = invalidPredictorIndex; 254 bp_history = static_cast<void *>(history); 255 256 updateGlobalHistTaken(); 257} 258 259void 260TournamentBP::update(Addr branch_addr, bool taken, void *bp_history, 261 bool squashed) 262{ 263 unsigned local_history_idx; 264 unsigned local_predictor_idx M5_VAR_USED; 265 unsigned local_predictor_hist; 266 267 // Get the local predictor's current prediction 268 local_history_idx = calcLocHistIdx(branch_addr); 269 local_predictor_hist = localHistoryTable[local_history_idx]; 270 local_predictor_idx = local_predictor_hist & localPredictorMask; 271 272 if (bp_history) { 273 BPHistory *history = static_cast<BPHistory *>(bp_history); 274 // Update may also be called if the Branch target is incorrect even if 275 // the prediction is correct. In that case do not update the counters. 276 bool historyPred = false; 277 unsigned old_local_pred_index = history->localHistory & 278 localPredictorMask; 279 280 bool old_local_pred_valid = history->localHistory != 281 invalidPredictorIndex; 282 283 assert(old_local_pred_index < localPredictorSize); 284 285 if (history->globalUsed) { 286 historyPred = history->globalPredTaken; 287 } else { 288 historyPred = history->localPredTaken; 289 } 290 if (historyPred != taken || !squashed) { 291 // Update the choice predictor to tell it which one was correct if 292 // there was a prediction. 293 if (history->localPredTaken != history->globalPredTaken) { 294 // If the local prediction matches the actual outcome, 295 // decerement the counter. Otherwise increment the 296 // counter. 297 unsigned choice_predictor_idx = 298 history->globalHistory & choiceHistoryMask; 299 if (history->localPredTaken == taken) { 300 choiceCtrs[choice_predictor_idx].decrement(); 301 } else if (history->globalPredTaken == taken) { 302 choiceCtrs[choice_predictor_idx].increment(); 303 } 304 305 } 306 307 // Update the counters and local history with the proper 308 // resolution of the branch. Global history is updated 309 // speculatively and restored upon squash() calls, so it does not 310 // need to be updated. 311 unsigned global_predictor_idx = 312 history->globalHistory & globalHistoryMask; 313 if (taken) { 314 globalCtrs[global_predictor_idx].increment(); 315 if (old_local_pred_valid) { 316 localCtrs[old_local_pred_index].increment(); 317 } 318 } else { 319 globalCtrs[global_predictor_idx].decrement(); 320 if (old_local_pred_valid) { 321 localCtrs[old_local_pred_index].decrement(); 322 } 323 } 324 } 325 if (squashed) { 326 if (taken) { 327 globalHistory = (history->globalHistory << 1) | 1; 328 globalHistory = globalHistory & historyRegisterMask; 329 if (old_local_pred_valid) { 330 localHistoryTable[local_history_idx] = 331 (history->localHistory << 1) | 1; 332 } 333 } else { 334 globalHistory = (history->globalHistory << 1); 335 globalHistory = globalHistory & historyRegisterMask; 336 if (old_local_pred_valid) { 337 localHistoryTable[local_history_idx] = 338 history->localHistory << 1; 339 } 340 } 341 342 } 343 // We're done with this history, now delete it. 344 delete history; 345 346 } 347 348 assert(local_history_idx < localHistoryTableSize); 349 350 351} 352 353void 354TournamentBP::squash(void *bp_history) 355{ 356 BPHistory *history = static_cast<BPHistory *>(bp_history); 357 358 // Restore global history to state prior to this branch. 359 globalHistory = history->globalHistory; 360 361 // Delete this BPHistory now that we're done with it. 362 delete history; 363} 364 365#ifdef DEBUG 366int 367TournamentBP::BPHistory::newCount = 0; 368#endif 369