tournament.cc revision 8843
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 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 if (history->globalUsed) { 269 historyPred = history->globalPredTaken; 270 } else { 271 historyPred = history->localPredTaken; 272 } 273 if (historyPred != taken || !squashed) { 274 // Update the choice predictor to tell it which one was correct if 275 // there was a prediction. 276 if (history->localPredTaken != history->globalPredTaken) { 277 // If the local prediction matches the actual outcome, 278 // decerement the counter. Otherwise increment the 279 // counter. 280 if (history->localPredTaken == taken) { 281 choiceCtrs[history->globalHistory].decrement(); 282 } else if (history->globalPredTaken == taken) { 283 choiceCtrs[history->globalHistory].increment(); 284 } 285 286 } 287 288 // Update the counters and local history with the proper 289 // resolution of the branch. Global history is updated 290 // speculatively and restored upon squash() calls, so it does not 291 // need to be updated. 292 if (taken) { 293 globalCtrs[history->globalHistory].increment(); 294 if (old_local_pred_index != invalidPredictorIndex) { 295 localCtrs[old_local_pred_index].increment(); 296 } 297 } else { 298 globalCtrs[history->globalHistory].decrement(); 299 if (old_local_pred_index != invalidPredictorIndex) { 300 localCtrs[old_local_pred_index].decrement(); 301 } 302 } 303 } 304 if (squashed) { 305 if (taken) { 306 globalHistory = (history->globalHistory << 1) | 1; 307 globalHistory = globalHistory & globalHistoryMask; 308 if (old_local_pred_index != invalidPredictorIndex) { 309 localHistoryTable[old_local_pred_index] = 310 (history->localHistory << 1) | 1; 311 } 312 } else { 313 globalHistory = (history->globalHistory << 1); 314 globalHistory = globalHistory & globalHistoryMask; 315 if (old_local_pred_index != invalidPredictorIndex) { 316 localHistoryTable[old_local_pred_index] = 317 history->localHistory << 1; 318 } 319 } 320 321 } 322 // We're done with this history, now delete it. 323 delete history; 324 325 } 326 327 assert(globalHistory < globalPredictorSize && 328 local_history_idx < localHistoryTableSize && 329 local_predictor_idx < localPredictorSize); 330 331 332} 333 334void 335TournamentBP::squash(void *bp_history) 336{ 337 BPHistory *history = static_cast<BPHistory *>(bp_history); 338 339 // Restore global history to state prior to this branch. 340 globalHistory = history->globalHistory; 341 342 // Delete this BPHistory now that we're done with it. 343 delete history; 344} 345 346#ifdef DEBUG 347int 348TournamentBP::BPHistory::newCount = 0; 349#endif 350