loop_predictor.cc revision 13627:ec1395943cd2
1/* 2 * Copyright (c) 2014 The University of Wisconsin 3 * 4 * Copyright (c) 2006 INRIA (Institut National de Recherche en 5 * Informatique et en Automatique / French National Research Institute 6 * for Computer Science and Applied Mathematics) 7 * 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions are 12 * met: redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer; 14 * redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution; 17 * neither the name of the copyright holders nor the names of its 18 * contributors may be used to endorse or promote products derived from 19 * this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 * 33 * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 34 * from André Seznec's code. 35 */ 36 37#include "cpu/pred/loop_predictor.hh" 38 39#include "params/LoopPredictor.hh" 40 41LoopPredictor::LoopPredictor(LoopPredictorParams *p) 42 : SimObject(p), logSizeLoopPred(p->logSizeLoopPred), 43 loopTableAgeBits(p->loopTableAgeBits), 44 loopTableConfidenceBits(p->loopTableConfidenceBits), 45 loopTableTagBits(p->loopTableTagBits), 46 loopTableIterBits(p->loopTableIterBits), 47 logLoopTableAssoc(p->logLoopTableAssoc), 48 confidenceThreshold((1 << loopTableConfidenceBits) - 1), 49 loopTagMask((1 << loopTableTagBits) - 1), 50 loopNumIterMask((1 << loopTableIterBits) - 1), 51 loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1), 52 loopUseCounter(-1), 53 withLoopBits(p->withLoopBits), 54 useDirectionBit(p->useDirectionBit), 55 useSpeculation(p->useSpeculation), 56 useHashing(p->useHashing), 57 restrictAllocation(p->restrictAllocation), 58 initialLoopIter(p->initialLoopIter), 59 initialLoopAge(p->initialLoopAge), 60 optionalAgeReset(p->optionalAgeReset) 61{ 62 assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1)); 63} 64 65void 66LoopPredictor::init() 67{ 68 // we use uint16_t type for these vales, so they cannot be more than 69 // 16 bits 70 assert(loopTableTagBits <= 16); 71 assert(loopTableIterBits <= 16); 72 73 assert(logSizeLoopPred >= logLoopTableAssoc); 74 75 ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; 76} 77 78LoopPredictor::BranchInfo* 79LoopPredictor::makeBranchInfo() 80{ 81 return new BranchInfo(); 82} 83 84int 85LoopPredictor::lindex(Addr pc_in, unsigned instShiftAmt) const 86{ 87 // The loop table is implemented as a linear table 88 // If associativity is N (N being 1 << logLoopTableAssoc), 89 // the first N entries are for set 0, the next N entries are for set 1, 90 // and so on. 91 // Thus, this function calculates the set and then it gets left shifted 92 // by logLoopTableAssoc in order to return the index of the first of the 93 // N entries of the set 94 Addr pc = pc_in >> instShiftAmt; 95 if (useHashing) { 96 pc ^= pc_in; 97 } 98 return ((pc & loopSetMask) << logLoopTableAssoc); 99} 100 101int 102LoopPredictor::finallindex(int index, int lowPcBits, int way) const 103{ 104 return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) : 105 (index)) 106 + way; 107} 108 109//loop prediction: only used if high confidence 110bool 111LoopPredictor::getLoop(Addr pc, BranchInfo* bi, bool speculative, 112 unsigned instShiftAmt) const 113{ 114 bi->loopHit = -1; 115 bi->loopPredValid = false; 116 bi->loopIndex = lindex(pc, instShiftAmt); 117 118 if (useHashing) { 119 unsigned pcShift = logSizeLoopPred - logLoopTableAssoc; 120 bi->loopIndexB = (pc >> pcShift) & loopSetMask; 121 bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift + loopTableTagBits)); 122 bi->loopTag &= loopTagMask; 123 } else { 124 unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc; 125 bi->loopTag = (pc >> pcShift) & loopTagMask; 126 // bi->loopIndexB is not used without hash 127 } 128 129 for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 130 int idx = finallindex(bi->loopIndex, bi->loopIndexB, i); 131 if (ltable[idx].tag == bi->loopTag) { 132 bi->loopHit = i; 133 bi->loopPredValid = calcConf(idx); 134 135 uint16_t iter = speculative ? ltable[idx].currentIterSpec 136 : ltable[idx].currentIter; 137 138 if ((iter + 1) == ltable[idx].numIter) { 139 return useDirectionBit ? !(ltable[idx].dir) : false; 140 } else { 141 return useDirectionBit ? (ltable[idx].dir) : true; 142 } 143 } 144 } 145 return false; 146} 147 148bool 149LoopPredictor::calcConf(int index) const 150{ 151 return ltable[index].confidence == confidenceThreshold; 152} 153 154void 155LoopPredictor::specLoopUpdate(bool taken, BranchInfo* bi) 156{ 157 if (bi->loopHit>=0) { 158 int index = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit); 159 if (taken != ltable[index].dir) { 160 ltable[index].currentIterSpec = 0; 161 } else { 162 ltable[index].currentIterSpec = 163 (ltable[index].currentIterSpec + 1) & loopNumIterMask; 164 } 165 } 166} 167 168bool 169LoopPredictor::optionalAgeInc(int nrand) const 170{ 171 return false; 172} 173 174void 175LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, 176 int random0, int random1, int random2) 177{ 178 int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit); 179 if (bi->loopHit >= 0) { 180 //already a hit 181 if (bi->loopPredValid) { 182 if (taken != bi->loopPred) { 183 // free the entry 184 ltable[idx].numIter = 0; 185 ltable[idx].age = 0; 186 ltable[idx].confidence = 0; 187 ltable[idx].currentIter = 0; 188 return; 189 } else if (bi->loopPred != tage_pred || optionalAgeInc(random0)) { 190 unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits); 191 } 192 } 193 194 ltable[idx].currentIter = 195 (ltable[idx].currentIter + 1) & loopNumIterMask; 196 if (ltable[idx].currentIter > ltable[idx].numIter) { 197 ltable[idx].confidence = 0; 198 if (ltable[idx].numIter != 0) { 199 // free the entry 200 ltable[idx].numIter = 0; 201 if (optionalAgeReset) { 202 ltable[idx].age = 0; 203 } 204 } 205 } 206 207 if (taken != (useDirectionBit ? ltable[idx].dir : true)) { 208 if (ltable[idx].currentIter == ltable[idx].numIter) { 209 unsignedCtrUpdate(ltable[idx].confidence, true, 210 loopTableConfidenceBits); 211 //just do not predict when the loop count is 1 or 2 212 if (ltable[idx].numIter < 3) { 213 // free the entry 214 ltable[idx].dir = taken; // ignored if no useDirectionBit 215 ltable[idx].numIter = 0; 216 ltable[idx].age = 0; 217 ltable[idx].confidence = 0; 218 } 219 } else { 220 if (ltable[idx].numIter == 0) { 221 // first complete nest; 222 ltable[idx].confidence = 0; 223 ltable[idx].numIter = ltable[idx].currentIter; 224 } else { 225 //not the same number of iterations as last time: free the 226 //entry 227 ltable[idx].numIter = 0; 228 if (optionalAgeReset) { 229 ltable[idx].age = 0; 230 } 231 ltable[idx].confidence = 0; 232 } 233 } 234 ltable[idx].currentIter = 0; 235 } 236 237 } else if (useDirectionBit ? (bi->predTaken != taken) : taken) { 238 if ((random2 & 3) == 0 || !restrictAllocation) { 239 //try to allocate an entry on taken branch 240 int nrand = random1; 241 for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 242 int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); 243 idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit); 244 if (ltable[idx].age == 0) { 245 ltable[idx].dir = !taken; // ignored if no useDirectionBit 246 ltable[idx].tag = bi->loopTag; 247 ltable[idx].numIter = 0; 248 ltable[idx].age = initialLoopAge; 249 ltable[idx].confidence = 0; 250 ltable[idx].currentIter = initialLoopIter; 251 break; 252 253 } else { 254 ltable[idx].age--; 255 } 256 if (restrictAllocation) { 257 break; 258 } 259 } 260 } 261 } 262} 263 264bool 265LoopPredictor::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch, 266 BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt) 267{ 268 bool pred_taken = prev_pred_taken; 269 if (cond_branch) { 270 // loop prediction 271 bi->loopPred = getLoop(branch_pc, bi, useSpeculation, instShiftAmt); 272 273 if ((loopUseCounter >= 0) && bi->loopPredValid) { 274 pred_taken = bi->loopPred; 275 bi->loopPredUsed = true; 276 } 277 278 if (useSpeculation) { 279 specLoopUpdate(pred_taken, bi); 280 } 281 } 282 283 return pred_taken; 284} 285 286void 287LoopPredictor::squash(ThreadID tid, BranchInfo *bi) 288{ 289 if (bi->loopHit >= 0) { 290 int idx = finallindex(bi->loopIndex, 291 bi->loopIndexB, 292 bi->loopHit); 293 ltable[idx].currentIterSpec = bi->currentIter; 294 } 295} 296 297void 298LoopPredictor::squashLoop(BranchInfo* bi) 299{ 300 if (bi->loopHit >= 0) { 301 int idx = finallindex(bi->loopIndex, 302 bi->loopIndexB, 303 bi->loopHit); 304 ltable[idx].currentIterSpec = bi->currentIter; 305 } 306} 307 308void 309LoopPredictor::updateStats(bool taken, BranchInfo* bi) 310{ 311 if (taken == bi->loopPred) { 312 loopPredictorCorrect++; 313 } else { 314 loopPredictorWrong++; 315 } 316} 317 318void 319LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, 320 bool tage_pred, BranchInfo* bi, 321 unsigned instShiftAmt, int rand0, int rand1, 322 int rand2) 323{ 324 if (useSpeculation) { 325 // recalculate loop prediction without speculation 326 // It is ok to overwrite the loop prediction fields in bi 327 // as the stats have already been updated with the previous 328 // values 329 bi->loopPred = getLoop(branch_pc, bi, false, instShiftAmt); 330 } 331 332 if (bi->loopPredValid) { 333 if (bi->predTaken != bi->loopPred) { 334 signedCtrUpdate(loopUseCounter, 335 (bi->loopPred == taken), 336 withLoopBits); 337 } 338 } 339 340 loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1, rand2); 341} 342 343void 344LoopPredictor::regStats() 345{ 346 loopPredictorCorrect 347 .name(name() + ".loopPredictorCorrect") 348 .desc("Number of times the loop predictor is the provider and " 349 "the prediction is correct"); 350 351 loopPredictorWrong 352 .name(name() + ".loopPredictorWrong") 353 .desc("Number of times the loop predictor is the provider and " 354 "the prediction is wrong"); 355} 356 357LoopPredictor * 358LoopPredictorParams::create() 359{ 360 return new LoopPredictor(this); 361} 362