tournament.cc revision 13654:dc3878f03a0c
1/* 2 * Copyright (c) 2011, 2014 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 "cpu/pred/tournament.hh" 44 45#include "base/bitfield.hh" 46#include "base/intmath.hh" 47 48TournamentBP::TournamentBP(const TournamentBPParams *params) 49 : BPredUnit(params), 50 localPredictorSize(params->localPredictorSize), 51 localCtrBits(params->localCtrBits), 52 localHistoryTableSize(params->localHistoryTableSize), 53 localHistoryBits(ceilLog2(params->localPredictorSize)), 54 globalPredictorSize(params->globalPredictorSize), 55 globalCtrBits(params->globalCtrBits), 56 globalHistory(params->numThreads, 0), 57 globalHistoryBits( 58 ceilLog2(params->globalPredictorSize) > 59 ceilLog2(params->choicePredictorSize) ? 60 ceilLog2(params->globalPredictorSize) : 61 ceilLog2(params->choicePredictorSize)), 62 choicePredictorSize(params->choicePredictorSize), 63 choiceCtrBits(params->choiceCtrBits) 64{ 65 if (!isPowerOf2(localPredictorSize)) { 66 fatal("Invalid local predictor size!\n"); 67 } 68 69 if (!isPowerOf2(globalPredictorSize)) { 70 fatal("Invalid global predictor size!\n"); 71 } 72 73 //Set up the array of counters for the local predictor 74 localCtrs.resize(localPredictorSize); 75 76 for (int i = 0; i < localPredictorSize; ++i) 77 localCtrs[i].setBits(localCtrBits); 78 79 localPredictorMask = mask(localHistoryBits); 80 81 if (!isPowerOf2(localHistoryTableSize)) { 82 fatal("Invalid local history table size!\n"); 83 } 84 85 //Setup the history table for the local table 86 localHistoryTable.resize(localHistoryTableSize); 87 88 for (int i = 0; i < localHistoryTableSize; ++i) 89 localHistoryTable[i] = 0; 90 91 //Setup the array of counters for the global predictor 92 globalCtrs.resize(globalPredictorSize); 93 94 for (int i = 0; i < globalPredictorSize; ++i) 95 globalCtrs[i].setBits(globalCtrBits); 96 97 // Set up the global history mask 98 // this is equivalent to mask(log2(globalPredictorSize) 99 globalHistoryMask = globalPredictorSize - 1; 100 101 if (!isPowerOf2(choicePredictorSize)) { 102 fatal("Invalid choice predictor size!\n"); 103 } 104 105 // Set up choiceHistoryMask 106 // this is equivalent to mask(log2(choicePredictorSize) 107 choiceHistoryMask = choicePredictorSize - 1; 108 109 //Setup the array of counters for the choice predictor 110 choiceCtrs.resize(choicePredictorSize); 111 112 for (int i = 0; i < choicePredictorSize; ++i) 113 choiceCtrs[i].setBits(choiceCtrBits); 114 115 //Set up historyRegisterMask 116 historyRegisterMask = mask(globalHistoryBits); 117 118 //Check that predictors don't use more bits than they have available 119 if (globalHistoryMask > historyRegisterMask) { 120 fatal("Global predictor too large for global history bits!\n"); 121 } 122 if (choiceHistoryMask > historyRegisterMask) { 123 fatal("Choice predictor too large for global history bits!\n"); 124 } 125 126 if (globalHistoryMask < historyRegisterMask && 127 choiceHistoryMask < historyRegisterMask) { 128 inform("More global history bits than required by predictors\n"); 129 } 130 131 // Set thresholds for the three predictors' counters 132 // This is equivalent to (2^(Ctr))/2 - 1 133 localThreshold = (ULL(1) << (localCtrBits - 1)) - 1; 134 globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 135 choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 136} 137 138inline 139unsigned 140TournamentBP::calcLocHistIdx(Addr &branch_addr) 141{ 142 // Get low order bits after removing instruction offset. 143 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 144} 145 146inline 147void 148TournamentBP::updateGlobalHistTaken(ThreadID tid) 149{ 150 globalHistory[tid] = (globalHistory[tid] << 1) | 1; 151 globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 152} 153 154inline 155void 156TournamentBP::updateGlobalHistNotTaken(ThreadID tid) 157{ 158 globalHistory[tid] = (globalHistory[tid] << 1); 159 globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 160} 161 162inline 163void 164TournamentBP::updateLocalHistTaken(unsigned local_history_idx) 165{ 166 localHistoryTable[local_history_idx] = 167 (localHistoryTable[local_history_idx] << 1) | 1; 168} 169 170inline 171void 172TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 173{ 174 localHistoryTable[local_history_idx] = 175 (localHistoryTable[local_history_idx] << 1); 176} 177 178 179void 180TournamentBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history) 181{ 182 unsigned local_history_idx = calcLocHistIdx(branch_addr); 183 //Update Global History to Not Taken (clear LSB) 184 globalHistory[tid] &= (historyRegisterMask & ~ULL(1)); 185 //Update Local History to Not Taken 186 localHistoryTable[local_history_idx] = 187 localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 188} 189 190bool 191TournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) 192{ 193 bool local_prediction; 194 unsigned local_history_idx; 195 unsigned local_predictor_idx; 196 197 bool global_prediction; 198 bool choice_prediction; 199 200 //Lookup in the local predictor to get its branch prediction 201 local_history_idx = calcLocHistIdx(branch_addr); 202 local_predictor_idx = localHistoryTable[local_history_idx] 203 & localPredictorMask; 204 local_prediction = localCtrs[local_predictor_idx].read() > localThreshold; 205 206 //Lookup in the global predictor to get its branch prediction 207 global_prediction = globalThreshold < 208 globalCtrs[globalHistory[tid] & globalHistoryMask].read(); 209 210 //Lookup in the choice predictor to see which one to use 211 choice_prediction = choiceThreshold < 212 choiceCtrs[globalHistory[tid] & choiceHistoryMask].read(); 213 214 // Create BPHistory and pass it back to be recorded. 215 BPHistory *history = new BPHistory; 216 history->globalHistory = globalHistory[tid]; 217 history->localPredTaken = local_prediction; 218 history->globalPredTaken = global_prediction; 219 history->globalUsed = choice_prediction; 220 history->localHistoryIdx = local_history_idx; 221 history->localHistory = local_predictor_idx; 222 bp_history = (void *)history; 223 224 assert(local_history_idx < localHistoryTableSize); 225 226 // Speculative update of the global history and the 227 // selected local history. 228 if (choice_prediction) { 229 if (global_prediction) { 230 updateGlobalHistTaken(tid); 231 updateLocalHistTaken(local_history_idx); 232 return true; 233 } else { 234 updateGlobalHistNotTaken(tid); 235 updateLocalHistNotTaken(local_history_idx); 236 return false; 237 } 238 } else { 239 if (local_prediction) { 240 updateGlobalHistTaken(tid); 241 updateLocalHistTaken(local_history_idx); 242 return true; 243 } else { 244 updateGlobalHistNotTaken(tid); 245 updateLocalHistNotTaken(local_history_idx); 246 return false; 247 } 248 } 249} 250 251void 252TournamentBP::uncondBranch(ThreadID tid, Addr pc, void * &bp_history) 253{ 254 // Create BPHistory and pass it back to be recorded. 255 BPHistory *history = new BPHistory; 256 history->globalHistory = globalHistory[tid]; 257 history->localPredTaken = true; 258 history->globalPredTaken = true; 259 history->globalUsed = true; 260 history->localHistoryIdx = invalidPredictorIndex; 261 history->localHistory = invalidPredictorIndex; 262 bp_history = static_cast<void *>(history); 263 264 updateGlobalHistTaken(tid); 265} 266 267void 268TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken, 269 void *bp_history, bool squashed, 270 const StaticInstPtr & inst, Addr corrTarget) 271{ 272 assert(bp_history); 273 274 BPHistory *history = static_cast<BPHistory *>(bp_history); 275 276 unsigned local_history_idx = calcLocHistIdx(branch_addr); 277 278 assert(local_history_idx < localHistoryTableSize); 279 280 // Unconditional branches do not use local history. 281 bool old_local_pred_valid = history->localHistory != 282 invalidPredictorIndex; 283 284 // If this is a misprediction, restore the speculatively 285 // updated state (global history register and local history) 286 // and update again. 287 if (squashed) { 288 // Global history restore and update 289 globalHistory[tid] = (history->globalHistory << 1) | taken; 290 globalHistory[tid] &= historyRegisterMask; 291 292 // Local history restore and update. 293 if (old_local_pred_valid) { 294 localHistoryTable[local_history_idx] = 295 (history->localHistory << 1) | taken; 296 } 297 298 return; 299 } 300 301 unsigned old_local_pred_index = history->localHistory & 302 localPredictorMask; 303 304 assert(old_local_pred_index < localPredictorSize); 305 306 // Update the choice predictor to tell it which one was correct if 307 // there was a prediction. 308 if (history->localPredTaken != history->globalPredTaken && 309 old_local_pred_valid) 310 { 311 // If the local prediction matches the actual outcome, 312 // decrement the counter. Otherwise increment the 313 // counter. 314 unsigned choice_predictor_idx = 315 history->globalHistory & choiceHistoryMask; 316 if (history->localPredTaken == taken) { 317 choiceCtrs[choice_predictor_idx].decrement(); 318 } else if (history->globalPredTaken == taken) { 319 choiceCtrs[choice_predictor_idx].increment(); 320 } 321 } 322 323 // Update the counters with the proper 324 // resolution of the branch. Histories are updated 325 // speculatively, restored upon squash() calls, and 326 // recomputed upon update(squash = true) calls, 327 // so they do not need to be updated. 328 unsigned global_predictor_idx = 329 history->globalHistory & globalHistoryMask; 330 if (taken) { 331 globalCtrs[global_predictor_idx].increment(); 332 if (old_local_pred_valid) { 333 localCtrs[old_local_pred_index].increment(); 334 } 335 } else { 336 globalCtrs[global_predictor_idx].decrement(); 337 if (old_local_pred_valid) { 338 localCtrs[old_local_pred_index].decrement(); 339 } 340 } 341 342 // We're done with this history, now delete it. 343 delete history; 344} 345 346void 347TournamentBP::squash(ThreadID tid, void *bp_history) 348{ 349 BPHistory *history = static_cast<BPHistory *>(bp_history); 350 351 // Restore global history to state prior to this branch. 352 globalHistory[tid] = history->globalHistory; 353 354 // Restore local history 355 if (history->localHistoryIdx != invalidPredictorIndex) { 356 localHistoryTable[history->localHistoryIdx] = history->localHistory; 357 } 358 359 // Delete this BPHistory now that we're done with it. 360 delete history; 361} 362 363TournamentBP* 364TournamentBPParams::create() 365{ 366 return new TournamentBP(this); 367} 368 369#ifdef DEBUG 370int 371TournamentBP::BPHistory::newCount = 0; 372#endif 373