tournament.cc revision 8842:a02932e2e73d
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/intmath.hh" 44#include "cpu/pred/tournament.hh" 45 46TournamentBP::TournamentBP(unsigned _localPredictorSize, 47 unsigned _localCtrBits, 48 unsigned _localHistoryTableSize, 49 unsigned _localHistoryBits, 50 unsigned _globalPredictorSize, 51 unsigned _globalHistoryBits, 52 unsigned _globalCtrBits, 53 unsigned _choicePredictorSize, 54 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 - 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 // Update the choice predictor to tell it which one was correct if 262 // there was a prediction. 263 if (bp_history) { 264 BPHistory *history = static_cast<BPHistory *>(bp_history); 265 if (history->localPredTaken != history->globalPredTaken) { 266 // If the local prediction matches the actual outcome, 267 // decerement the counter. Otherwise increment the 268 // counter. 269 if (history->localPredTaken == taken) { 270 choiceCtrs[history->globalHistory].decrement(); 271 } else if (history->globalPredTaken == taken){ 272 choiceCtrs[history->globalHistory].increment(); 273 } 274 275 } 276 277 // Update the counters and local history with the proper 278 // resolution of the branch. Global history is updated 279 // speculatively and restored upon squash() calls, so it does not 280 // need to be updated. 281 unsigned old_local_pred_index = history->localHistory 282 & localPredictorMask; 283 if (taken) { 284 globalCtrs[history->globalHistory].increment(); 285 if (old_local_pred_index != invalidPredictorIndex) { 286 localCtrs[old_local_pred_index].increment(); 287 } 288 } else { 289 globalCtrs[history->globalHistory].decrement(); 290 if (old_local_pred_index != invalidPredictorIndex) { 291 localCtrs[old_local_pred_index].decrement(); 292 } 293 } 294 295 if (squashed) { 296 if (taken) { 297 globalHistory = (history->globalHistory << 1) | 1; 298 globalHistory = globalHistory & globalHistoryMask; 299 if (history->localHistory != invalidPredictorIndex) 300 localHistoryTable[local_history_idx] = 301 (history->localHistory << 1) | 1; 302 } else { 303 globalHistory = (history->globalHistory << 1); 304 globalHistory = globalHistory & globalHistoryMask; 305 if (history->localHistory != invalidPredictorIndex) { 306 localHistoryTable[local_history_idx] = 307 history->localHistory << 1; 308 } 309 } 310 311 } 312 // We're done with this history, now delete it. 313 delete history; 314 } 315 316 assert(globalHistory < globalPredictorSize && 317 local_history_idx < localHistoryTableSize && 318 local_predictor_idx < localPredictorSize); 319 320 321} 322 323void 324TournamentBP::squash(void *bp_history) 325{ 326 BPHistory *history = static_cast<BPHistory *>(bp_history); 327 328 // Restore global history to state prior to this branch. 329 globalHistory = history->globalHistory; 330 331 // Delete this BPHistory now that we're done with it. 332 delete history; 333} 334 335#ifdef DEBUG 336int 337TournamentBP::BPHistory::newCount = 0; 338#endif 339