ltage.cc revision 13455:56e25a5f9603
112954Sgabeblack@google.com/* 212954Sgabeblack@google.com * Copyright (c) 2014 The University of Wisconsin 312954Sgabeblack@google.com * 412954Sgabeblack@google.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 512954Sgabeblack@google.com * Informatique et en Automatique / French National Research Institute 612954Sgabeblack@google.com * for Computer Science and Applied Mathematics) 712954Sgabeblack@google.com * 812954Sgabeblack@google.com * All rights reserved. 912954Sgabeblack@google.com * 1012954Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 1112954Sgabeblack@google.com * modification, are permitted provided that the following conditions are 1212954Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 1312954Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 1412954Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1512954Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1612954Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1712954Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1812954Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1912954Sgabeblack@google.com * this software without specific prior written permission. 2012954Sgabeblack@google.com * 2112954Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2212954Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2312954Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2412954Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2512954Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2612954Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2712954Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2812954Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2912954Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3012954Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3112954Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3212954Sgabeblack@google.com * 3312954Sgabeblack@google.com * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3412954Sgabeblack@google.com * from André Seznec's code. 3512954Sgabeblack@google.com */ 3612954Sgabeblack@google.com 3712954Sgabeblack@google.com/* @file 3812954Sgabeblack@google.com * Implementation of a L-TAGE branch predictor 3912954Sgabeblack@google.com */ 4012954Sgabeblack@google.com 4112954Sgabeblack@google.com#include "cpu/pred/ltage.hh" 4212954Sgabeblack@google.com 4312954Sgabeblack@google.com#include "base/intmath.hh" 4412954Sgabeblack@google.com#include "base/logging.hh" 4512954Sgabeblack@google.com#include "base/random.hh" 4612954Sgabeblack@google.com#include "base/trace.hh" 4712954Sgabeblack@google.com#include "debug/Fetch.hh" 4812954Sgabeblack@google.com#include "debug/LTage.hh" 4912954Sgabeblack@google.com 5012954Sgabeblack@google.comLTAGE::LTAGE(const LTAGEParams *params) 5112954Sgabeblack@google.com : TAGE(params), 5212954Sgabeblack@google.com logSizeLoopPred(params->logSizeLoopPred), 5312954Sgabeblack@google.com loopTableAgeBits(params->loopTableAgeBits), 5412954Sgabeblack@google.com loopTableConfidenceBits(params->loopTableConfidenceBits), 5512954Sgabeblack@google.com loopTableTagBits(params->loopTableTagBits), 5612954Sgabeblack@google.com loopTableIterBits(params->loopTableIterBits), 5712954Sgabeblack@google.com logLoopTableAssoc(params->logLoopTableAssoc), 5812954Sgabeblack@google.com confidenceThreshold((1 << loopTableConfidenceBits) - 1), 59 loopTagMask((1 << loopTableTagBits) - 1), 60 loopNumIterMask((1 << loopTableIterBits) - 1), 61 loopUseCounter(0), 62 withLoopBits(params->withLoopBits) 63{ 64 // we use uint16_t type for these vales, so they cannot be more than 65 // 16 bits 66 assert(loopTableTagBits <= 16); 67 assert(loopTableIterBits <= 16); 68 69 assert(logSizeLoopPred >= logLoopTableAssoc); 70 71 ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; 72} 73 74int 75LTAGE::lindex(Addr pc_in) const 76{ 77 // The loop table is implemented as a linear table 78 // If associativity is N (N being 1 << logLoopTableAssoc), 79 // the first N entries are for set 0, the next N entries are for set 1, 80 // and so on. 81 // Thus, this function calculates the set and then it gets left shifted 82 // by logLoopTableAssoc in order to return the index of the first of the 83 // N entries of the set 84 Addr mask = (ULL(1) << (logSizeLoopPred - logLoopTableAssoc)) - 1; 85 return (((pc_in >> instShiftAmt) & mask) << logLoopTableAssoc); 86} 87 88//loop prediction: only used if high confidence 89bool 90LTAGE::getLoop(Addr pc, LTageBranchInfo* bi) const 91{ 92 bi->loopHit = -1; 93 bi->loopPredValid = false; 94 bi->loopIndex = lindex(pc); 95 unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc; 96 bi->loopTag = ((pc) >> pcShift) & loopTagMask; 97 98 for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 99 if (ltable[bi->loopIndex + i].tag == bi->loopTag) { 100 bi->loopHit = i; 101 bi->loopPredValid = 102 ltable[bi->loopIndex + i].confidence == confidenceThreshold; 103 bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec; 104 if (ltable[bi->loopIndex + i].currentIterSpec + 1 == 105 ltable[bi->loopIndex + i].numIter) { 106 return !(ltable[bi->loopIndex + i].dir); 107 }else { 108 return (ltable[bi->loopIndex + i].dir); 109 } 110 } 111 } 112 return false; 113} 114 115void 116LTAGE::specLoopUpdate(Addr pc, bool taken, LTageBranchInfo* bi) 117{ 118 if (bi->loopHit>=0) { 119 int index = lindex(pc); 120 if (taken != ltable[index].dir) { 121 ltable[index].currentIterSpec = 0; 122 } else { 123 ltable[index].currentIterSpec = 124 (ltable[index].currentIterSpec + 1) & loopNumIterMask; 125 } 126 } 127} 128 129void 130LTAGE::loopUpdate(Addr pc, bool taken, LTageBranchInfo* bi) 131{ 132 int idx = bi->loopIndex + bi->loopHit; 133 if (bi->loopHit >= 0) { 134 //already a hit 135 if (bi->loopPredValid) { 136 if (taken != bi->loopPred) { 137 // free the entry 138 ltable[idx].numIter = 0; 139 ltable[idx].age = 0; 140 ltable[idx].confidence = 0; 141 ltable[idx].currentIter = 0; 142 return; 143 } else if (bi->loopPred != bi->tagePred) { 144 DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); 145 unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits); 146 } 147 } 148 149 ltable[idx].currentIter = 150 (ltable[idx].currentIter + 1) & loopNumIterMask; 151 if (ltable[idx].currentIter > ltable[idx].numIter) { 152 ltable[idx].confidence = 0; 153 if (ltable[idx].numIter != 0) { 154 // free the entry 155 ltable[idx].numIter = 0; 156 ltable[idx].age = 0; 157 ltable[idx].confidence = 0; 158 } 159 } 160 161 if (taken != ltable[idx].dir) { 162 if (ltable[idx].currentIter == ltable[idx].numIter) { 163 DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); 164 165 unsignedCtrUpdate(ltable[idx].confidence, true, 166 loopTableConfidenceBits); 167 //just do not predict when the loop count is 1 or 2 168 if (ltable[idx].numIter < 3) { 169 // free the entry 170 ltable[idx].dir = taken; 171 ltable[idx].numIter = 0; 172 ltable[idx].age = 0; 173 ltable[idx].confidence = 0; 174 } 175 } else { 176 DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); 177 if (ltable[idx].numIter == 0) { 178 // first complete nest; 179 ltable[idx].confidence = 0; 180 ltable[idx].numIter = ltable[idx].currentIter; 181 } else { 182 //not the same number of iterations as last time: free the 183 //entry 184 ltable[idx].numIter = 0; 185 ltable[idx].age = 0; 186 ltable[idx].confidence = 0; 187 } 188 } 189 ltable[idx].currentIter = 0; 190 } 191 192 } else if (taken) { 193 //try to allocate an entry on taken branch 194 int nrand = random_mt.random<int>(); 195 for (int i = 0; i < (1 << logLoopTableAssoc); i++) { 196 int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); 197 idx = bi->loopIndex + loop_hit; 198 if (ltable[idx].age == 0) { 199 DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n", 200 pc); 201 ltable[idx].dir = !taken; 202 ltable[idx].tag = bi->loopTag; 203 ltable[idx].numIter = 0; 204 ltable[idx].age = (1 << loopTableAgeBits) - 1; 205 ltable[idx].confidence = 0; 206 ltable[idx].currentIter = 1; 207 break; 208 209 } 210 else 211 ltable[idx].age--; 212 } 213 } 214 215} 216 217//prediction 218bool 219LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) 220{ 221 LTageBranchInfo *bi = new LTageBranchInfo(nHistoryTables+1); 222 b = (void*)(bi); 223 224 bool pred_taken = tagePredict(tid, branch_pc, cond_branch, bi); 225 226 if (cond_branch) { 227 bi->loopPred = getLoop(branch_pc, bi); // loop prediction 228 229 if ((loopUseCounter >= 0) && bi->loopPredValid) { 230 pred_taken = bi->loopPred; 231 bi->provider = LOOP; 232 } 233 DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, " 234 "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n", 235 branch_pc, pred_taken, bi->loopPred, bi->loopPredValid, 236 loopUseCounter, bi->tagePred, bi->altTaken); 237 } 238 239 specLoopUpdate(branch_pc, pred_taken, bi); 240 return pred_taken; 241} 242 243void 244LTAGE::condBranchUpdate(Addr branch_pc, bool taken, 245 TageBranchInfo* tage_bi, int nrand) 246{ 247 LTageBranchInfo* bi = static_cast<LTageBranchInfo*>(tage_bi); 248 249 // first update the loop predictor 250 loopUpdate(branch_pc, taken, bi); 251 252 if (bi->loopPredValid) { 253 if (bi->tagePred != bi->loopPred) { 254 ctrUpdate(loopUseCounter, 255 (bi->loopPred == taken), 256 withLoopBits); 257 } 258 } 259 260 TAGE::condBranchUpdate(branch_pc, taken, bi, nrand); 261} 262 263void 264LTAGE::squash(ThreadID tid, bool taken, void *bp_history) 265{ 266 TAGE::squash(tid, taken, bp_history); 267 268 LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history); 269 270 if (bi->condBranch) { 271 if (bi->loopHit >= 0) { 272 int idx = bi->loopIndex + bi->loopHit; 273 ltable[idx].currentIterSpec = bi->currentIter; 274 } 275 } 276} 277 278void 279LTAGE::squash(ThreadID tid, void *bp_history) 280{ 281 LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history); 282 if (bi->condBranch) { 283 if (bi->loopHit >= 0) { 284 int idx = bi->loopIndex + bi->loopHit; 285 ltable[idx].currentIterSpec = bi->currentIter; 286 } 287 } 288 289 TAGE::squash(tid, bp_history); 290} 291 292 293void 294LTAGE::updateStats(bool taken, TageBranchInfo* bi) 295{ 296 TAGE::updateStats(taken, bi); 297 298 LTageBranchInfo * ltage_bi = static_cast<LTageBranchInfo *>(bi); 299 300 if (ltage_bi->provider == LOOP) { 301 if (taken == ltage_bi->loopPred) { 302 loopPredictorCorrect++; 303 } else { 304 loopPredictorWrong++; 305 } 306 } 307} 308 309 310 311void 312LTAGE::regStats() 313{ 314 TAGE::regStats(); 315 316 loopPredictorCorrect 317 .name(name() + ".loopPredictorCorrect") 318 .desc("Number of times the loop predictor is the provider and " 319 "the prediction is correct"); 320 321 loopPredictorWrong 322 .name(name() + ".loopPredictorWrong") 323 .desc("Number of times the loop predictor is the provier and " 324 "the prediction is wrong"); 325} 326 327 328 329LTAGE* 330LTAGEParams::create() 331{ 332 return new LTAGE(this); 333} 334