tournament.cc revision 9327:07a22ace275d
16657Snate@binkert.org/* 26657Snate@binkert.org * Copyright (c) 2011 ARM Limited 36657Snate@binkert.org * All rights reserved 46657Snate@binkert.org * 56657Snate@binkert.org * The license below extends only to copyright in the software and shall 66657Snate@binkert.org * not be construed as granting a license to any other intellectual 76657Snate@binkert.org * property including but not limited to intellectual property relating 86657Snate@binkert.org * to a hardware implementation of the functionality of the software 96657Snate@binkert.org * licensed hereunder. You may use the software subject to the license 106657Snate@binkert.org * terms below provided that you ensure that this notice is replicated 116657Snate@binkert.org * unmodified and in its entirety in all distributions of the software, 126657Snate@binkert.org * modified or unmodified, in source code or in binary form. 136657Snate@binkert.org * 146657Snate@binkert.org * Copyright (c) 2004-2006 The Regents of The University of Michigan 156657Snate@binkert.org * All rights reserved. 166657Snate@binkert.org * 176657Snate@binkert.org * Redistribution and use in source and binary forms, with or without 186657Snate@binkert.org * modification, are permitted provided that the following conditions are 196657Snate@binkert.org * met: redistributions of source code must retain the above copyright 206657Snate@binkert.org * notice, this list of conditions and the following disclaimer; 216657Snate@binkert.org * redistributions in binary form must reproduce the above copyright 226657Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 236657Snate@binkert.org * documentation and/or other materials provided with the distribution; 246657Snate@binkert.org * neither the name of the copyright holders nor the names of its 256657Snate@binkert.org * contributors may be used to endorse or promote products derived from 266657Snate@binkert.org * this software without specific prior written permission. 276657Snate@binkert.org * 286657Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 296657Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 306657Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 316657Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 326882SBrad.Beckmann@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 336657Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 346657Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 356657Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 366877Ssteve.reinhardt@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 376882SBrad.Beckmann@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 386657Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 396657Snate@binkert.org * 406657Snate@binkert.org * Authors: Kevin Lim 416657Snate@binkert.org */ 426657Snate@binkert.org 436657Snate@binkert.org#include "base/intmath.hh" 446657Snate@binkert.org#include "cpu/pred/tournament.hh" 456657Snate@binkert.org 466657Snate@binkert.orgTournamentBP::TournamentBP(unsigned _localPredictorSize, 476657Snate@binkert.org unsigned _localCtrBits, 486657Snate@binkert.org unsigned _localHistoryTableSize, 496657Snate@binkert.org unsigned _localHistoryBits, 506657Snate@binkert.org unsigned _globalPredictorSize, 516657Snate@binkert.org unsigned _globalHistoryBits, 526657Snate@binkert.org unsigned _globalCtrBits, 536657Snate@binkert.org unsigned _choicePredictorSize, 546657Snate@binkert.org unsigned _choiceCtrBits, 55 unsigned _instShiftAmt) 56 : localPredictorSize(_localPredictorSize), 57 localCtrBits(_localCtrBits), 58 localHistoryTableSize(_localHistoryTableSize), 59 localHistoryBits(_localHistoryBits), 60 globalPredictorSize(_globalPredictorSize), 61 globalCtrBits(_globalCtrBits), 62 globalHistoryBits(_globalHistoryBits), 63 choicePredictorSize(_globalPredictorSize), 64 choiceCtrBits(_choiceCtrBits), 65 instShiftAmt(_instShiftAmt) 66{ 67 if (!isPowerOf2(localPredictorSize)) { 68 fatal("Invalid local predictor size!\n"); 69 } 70 71 //Setup the array of counters for the local predictor 72 localCtrs.resize(localPredictorSize); 73 74 for (int i = 0; i < localPredictorSize; ++i) 75 localCtrs[i].setBits(localCtrBits); 76 77 localPredictorMask = floorPow2(localPredictorSize) - 1; 78 79 if (!isPowerOf2(localHistoryTableSize)) { 80 fatal("Invalid local history table size!\n"); 81 } 82 83 //Setup the history table for the local table 84 localHistoryTable.resize(localHistoryTableSize); 85 86 for (int i = 0; i < localHistoryTableSize; ++i) 87 localHistoryTable[i] = 0; 88 89 // Setup the local history mask 90 localHistoryMask = (1 << localHistoryBits) - 1; 91 92 if (!isPowerOf2(globalPredictorSize)) { 93 fatal("Invalid global predictor size!\n"); 94 } 95 96 //Setup the array of counters for the global predictor 97 globalCtrs.resize(globalPredictorSize); 98 99 for (int i = 0; i < globalPredictorSize; ++i) 100 globalCtrs[i].setBits(globalCtrBits); 101 102 //Clear the global history 103 globalHistory = 0; 104 // Setup the global history mask 105 globalHistoryMask = (1 << globalHistoryBits) - 1; 106 107 if (!isPowerOf2(choicePredictorSize)) { 108 fatal("Invalid choice predictor size!\n"); 109 } 110 111 //Setup the array of counters for the choice predictor 112 choiceCtrs.resize(choicePredictorSize); 113 114 for (int i = 0; i < choicePredictorSize; ++i) 115 choiceCtrs[i].setBits(choiceCtrBits); 116 117 // @todo: Allow for different thresholds between the predictors. 118 threshold = (1 << (localCtrBits - 1)) - 1; 119} 120 121inline 122unsigned 123TournamentBP::calcLocHistIdx(Addr &branch_addr) 124{ 125 // Get low order bits after removing instruction offset. 126 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 127} 128 129inline 130void 131TournamentBP::updateGlobalHistTaken() 132{ 133 globalHistory = (globalHistory << 1) | 1; 134 globalHistory = globalHistory & globalHistoryMask; 135} 136 137inline 138void 139TournamentBP::updateGlobalHistNotTaken() 140{ 141 globalHistory = (globalHistory << 1); 142 globalHistory = globalHistory & globalHistoryMask; 143} 144 145inline 146void 147TournamentBP::updateLocalHistTaken(unsigned local_history_idx) 148{ 149 localHistoryTable[local_history_idx] = 150 (localHistoryTable[local_history_idx] << 1) | 1; 151} 152 153inline 154void 155TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 156{ 157 localHistoryTable[local_history_idx] = 158 (localHistoryTable[local_history_idx] << 1); 159} 160 161 162void 163TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history) 164{ 165 unsigned local_history_idx = calcLocHistIdx(branch_addr); 166 //Update Global History to Not Taken 167 globalHistory = globalHistory & (globalHistoryMask - 1); 168 //Update Local History to Not Taken 169 localHistoryTable[local_history_idx] = 170 localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 171} 172 173bool 174TournamentBP::lookup(Addr &branch_addr, void * &bp_history) 175{ 176 bool local_prediction; 177 unsigned local_history_idx; 178 unsigned local_predictor_idx; 179 180 bool global_prediction; 181 bool choice_prediction; 182 183 //Lookup in the local predictor to get its branch prediction 184 local_history_idx = calcLocHistIdx(branch_addr); 185 local_predictor_idx = localHistoryTable[local_history_idx] 186 & localPredictorMask; 187 local_prediction = localCtrs[local_predictor_idx].read() > threshold; 188 189 //Lookup in the global predictor to get its branch prediction 190 global_prediction = globalCtrs[globalHistory].read() > threshold; 191 192 //Lookup in the choice predictor to see which one to use 193 choice_prediction = choiceCtrs[globalHistory].read() > threshold; 194 195 // Create BPHistory and pass it back to be recorded. 196 BPHistory *history = new BPHistory; 197 history->globalHistory = globalHistory; 198 history->localPredTaken = local_prediction; 199 history->globalPredTaken = global_prediction; 200 history->globalUsed = choice_prediction; 201 history->localHistory = local_predictor_idx; 202 bp_history = (void *)history; 203 204 assert(globalHistory < globalPredictorSize && 205 local_history_idx < localHistoryTableSize && 206 local_predictor_idx < localPredictorSize); 207 208 // Commented code is for doing speculative update of counters and 209 // all histories. 210 if (choice_prediction) { 211 if (global_prediction) { 212 updateGlobalHistTaken(); 213 updateLocalHistTaken(local_history_idx); 214 return true; 215 } else { 216 updateGlobalHistNotTaken(); 217 updateLocalHistNotTaken(local_history_idx); 218 return false; 219 } 220 } else { 221 if (local_prediction) { 222 updateGlobalHistTaken(); 223 updateLocalHistTaken(local_history_idx); 224 return true; 225 } else { 226 updateGlobalHistNotTaken(); 227 updateLocalHistNotTaken(local_history_idx); 228 return false; 229 } 230 } 231} 232 233void 234TournamentBP::uncondBr(void * &bp_history) 235{ 236 // Create BPHistory and pass it back to be recorded. 237 BPHistory *history = new BPHistory; 238 history->globalHistory = globalHistory; 239 history->localPredTaken = true; 240 history->globalPredTaken = true; 241 history->globalUsed = true; 242 history->localHistory = invalidPredictorIndex; 243 bp_history = static_cast<void *>(history); 244 245 updateGlobalHistTaken(); 246} 247 248void 249TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history, 250 bool squashed) 251{ 252 unsigned local_history_idx; 253 unsigned local_predictor_idx M5_VAR_USED; 254 unsigned local_predictor_hist; 255 256 // Get the local predictor's current prediction 257 local_history_idx = calcLocHistIdx(branch_addr); 258 local_predictor_hist = localHistoryTable[local_history_idx]; 259 local_predictor_idx = local_predictor_hist & localPredictorMask; 260 261 if (bp_history) { 262 BPHistory *history = static_cast<BPHistory *>(bp_history); 263 // Update may also be called if the Branch target is incorrect even if 264 // the prediction is correct. In that case do not update the counters. 265 bool historyPred = false; 266 unsigned old_local_pred_index = history->localHistory & 267 localPredictorMask; 268 269 bool old_local_pred_valid = history->localHistory != 270 invalidPredictorIndex; 271 272 assert(old_local_pred_index < localPredictorSize); 273 274 if (history->globalUsed) { 275 historyPred = history->globalPredTaken; 276 } else { 277 historyPred = history->localPredTaken; 278 } 279 if (historyPred != taken || !squashed) { 280 // Update the choice predictor to tell it which one was correct if 281 // there was a prediction. 282 if (history->localPredTaken != history->globalPredTaken) { 283 // If the local prediction matches the actual outcome, 284 // decerement the counter. Otherwise increment the 285 // counter. 286 if (history->localPredTaken == taken) { 287 choiceCtrs[history->globalHistory].decrement(); 288 } else if (history->globalPredTaken == taken) { 289 choiceCtrs[history->globalHistory].increment(); 290 } 291 292 } 293 294 // Update the counters and local history with the proper 295 // resolution of the branch. Global history is updated 296 // speculatively and restored upon squash() calls, so it does not 297 // need to be updated. 298 if (taken) { 299 globalCtrs[history->globalHistory].increment(); 300 if (old_local_pred_valid) { 301 localCtrs[old_local_pred_index].increment(); 302 } 303 } else { 304 globalCtrs[history->globalHistory].decrement(); 305 if (old_local_pred_valid) { 306 localCtrs[old_local_pred_index].decrement(); 307 } 308 } 309 } 310 if (squashed) { 311 if (taken) { 312 globalHistory = (history->globalHistory << 1) | 1; 313 globalHistory = globalHistory & globalHistoryMask; 314 if (old_local_pred_valid) { 315 localHistoryTable[local_history_idx] = 316 (history->localHistory << 1) | 1; 317 } 318 } else { 319 globalHistory = (history->globalHistory << 1); 320 globalHistory = globalHistory & globalHistoryMask; 321 if (old_local_pred_valid) { 322 localHistoryTable[local_history_idx] = 323 history->localHistory << 1; 324 } 325 } 326 327 } 328 // We're done with this history, now delete it. 329 delete history; 330 331 } 332 333 assert(globalHistory < globalPredictorSize && 334 local_history_idx < localHistoryTableSize && 335 local_predictor_idx < localPredictorSize); 336 337 338} 339 340void 341TournamentBP::squash(void *bp_history) 342{ 343 BPHistory *history = static_cast<BPHistory *>(bp_history); 344 345 // Restore global history to state prior to this branch. 346 globalHistory = history->globalHistory; 347 348 // Delete this BPHistory now that we're done with it. 349 delete history; 350} 351 352#ifdef DEBUG 353int 354TournamentBP::BPHistory::newCount = 0; 355#endif 356