src/cpu/pred/tage_sc_l.cc

   1 /*
   2  * Copyright (c) 2018 Metempsy Technology Consulting
   3  * All rights reserved.
   4  *
   5  * Copyright (c) 2006 INRIA (Institut National de Recherche en
   6  * Informatique et en Automatique  / French National Research Institute
   7  * for Computer Science and Applied Mathematics)
   8  *
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions are
  13  * met: redistributions of source code must retain the above copyright
  14  * notice, this list of conditions and the following disclaimer;
  15  * redistributions in binary form must reproduce the above copyright
  16  * notice, this list of conditions and the following disclaimer in the
  17  * documentation and/or other materials provided with the distribution;
  18  * neither the name of the copyright holders nor the names of its
  19  * contributors may be used to endorse or promote products derived from
  20  * this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  25  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  26  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Author: André Seznec, Pau Cabre, Javier Bueno
  35  *
  36  */
  37
  38 /*
  39  * TAGE-SC-L branch predictor base class (devised by Andre Seznec)
  40  * It consits of a TAGE + a statistical corrector (SC) + a loop predictor (L)
  41  */
  42
  43 #include "cpu/pred/tage_sc_l.hh"
  44
  45 #include "base/random.hh"
  46 #include "debug/TageSCL.hh"
  47
  48 bool
  49 TAGE_SC_L_LoopPredictor::calcConf(int index) const
  50 {
  51     return LoopPredictor::calcConf(index) ||
  52            (ltable[index].confidence * ltable[index].numIter > 128);
  53 }
  54
  55 bool
  56 TAGE_SC_L_LoopPredictor::optionalAgeInc() const
  57 {
  58     return (random_mt.random<int>() & 7) == 0;
  59 }
  60
  61 TAGE_SC_L::TAGE_SC_L(const TAGE_SC_LParams &p)
  62   : LTAGE(p), statisticalCorrector(p.statistical_corrector)
  63 {
  64 }
  65
  66 TAGEBase::BranchInfo*
  67 TAGE_SC_L_TAGE::makeBranchInfo()
  68 {
  69     return new BranchInfo(*this);
  70 }
  71 void
  72 TAGE_SC_L_TAGE::calculateParameters()
  73 {
  74     unsigned numHistLengths = nHistoryTables/2;
  75     histLengths[1] = minHist;
  76     histLengths[numHistLengths] = maxHist;
  77
  78     // This calculates the different history lenghts
  79     // there are only numHistLengths different lengths
  80     // They are initially set to the lower half of histLengths
  81     for (int i = 2; i <= numHistLengths; i++) {
  82         histLengths[i] = (int) (((double) minHist *
  83                        pow ((double) (maxHist) / (double) minHist,
  84                            (double) (i - 1) / (double) ((numHistLengths - 1))))
  85                        + 0.5);
  86     }
  87
  88     // This copies and duplicates the values from the lower half of the table
  89     // Ex: 4, 6, 9, 13 would get exanded to 4, 4, 6, 6, 9, 9, 13, 13
  90     for (int i = nHistoryTables; i > 1; i--)
  91     {
  92         histLengths[i] = histLengths[(i + 1) / 2];
  93     }
  94
  95     for (int i = 1; i <= nHistoryTables; i++)
  96     {
  97         tagTableTagWidths.push_back(
  98             (i < firstLongTagTable) ? shortTagsSize : longTagsSize);
  99
 100         logTagTableSizes.push_back(logTagTableSize);
 101     }
 102 }
 103
 104 void
 105 TAGE_SC_L_TAGE::buildTageTables()
 106 {
 107     // Trick! We only allocate entries for tables 1 and firstLongTagTable and
 108     // make the other tables point to these allocated entries
 109
 110     gtable[1] = new TageEntry[shortTagsTageFactor * (1 << logTagTableSize)];
 111     gtable[firstLongTagTable] =
 112         new TageEntry[longTagsTageFactor * (1 << logTagTableSize)];
 113     for (int i = 2; i < firstLongTagTable; ++i) {
 114         gtable[i] = gtable[1];
 115     }
 116     for (int i = firstLongTagTable + 1; i <= nHistoryTables; ++i) {
 117         gtable[i] = gtable[firstLongTagTable];
 118     }
 119 }
 120
 121 void
 122 TAGE_SC_L_TAGE::calculateIndicesAndTags(
 123     ThreadID tid, Addr pc, TAGEBase::BranchInfo* bi)
 124 {
 125     // computes the table addresses and the partial tags
 126
 127     for (int i = 1; i <= nHistoryTables; i += 2) {
 128         tableIndices[i] = gindex(tid, pc, i);
 129         tableTags[i] = gtag(tid, pc, i);
 130         tableTags[i + 1] = tableTags[i];
 131         tableIndices[i + 1] = tableIndices[i] ^
 132                              (tableTags[i] & ((1 << logTagTableSizes[i]) - 1));
 133
 134         bi->tableTags[i] = tableTags[i];
 135         bi->tableTags[i+1] = tableTags[i+1];
 136     }
 137
 138     Addr t = (pc ^ (threadHistory[tid].pathHist &
 139                     ((1 << histLengths[firstLongTagTable]) - 1)))
 140              % longTagsTageFactor;
 141
 142     for (int i = firstLongTagTable; i <= nHistoryTables; i++) {
 143         if (noSkip[i]) {
 144             tableIndices[i] += (t << logTagTableSizes[i]);
 145             bi->tableIndices[i] = tableIndices[i];
 146             t++;
 147             t = t % longTagsTageFactor;
 148         }
 149     }
 150
 151     t = (pc ^ (threadHistory[tid].pathHist & ((1 << histLengths[1]) - 1)))
 152         % shortTagsTageFactor;
 153
 154     for (int i = 1; i <= firstLongTagTable - 1; i++) {
 155         if (noSkip[i]) {
 156             tableIndices[i] += (t << logTagTableSizes[i]);
 157             bi->tableIndices[i] = tableIndices[i];
 158             t++;
 159             t = t % shortTagsTageFactor;
 160         }
 161     }
 162 }
 163
 164 unsigned
 165 TAGE_SC_L_TAGE::getUseAltIdx(TAGEBase::BranchInfo* bi, Addr branch_pc)
 166 {
 167     BranchInfo *tbi = static_cast<BranchInfo *>(bi);
 168     unsigned idx;
 169     idx = ((((bi->hitBank-1)/8)<<1)+tbi->altConf) % (numUseAltOnNa-1);
 170     return idx;
 171 }
 172
 173 int
 174 TAGE_SC_L_TAGE::gindex(ThreadID tid, Addr pc, int bank) const
 175 {
 176     int index;
 177     int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
 178                                                     histLengths[bank];
 179     unsigned int shortPc = pc;
 180
 181     // pc is not shifted by instShiftAmt in this implementation
 182     index = shortPc ^
 183             (shortPc >> ((int) abs(logTagTableSizes[bank] - bank) + 1)) ^
 184             threadHistory[tid].computeIndices[bank].comp ^
 185             F(threadHistory[tid].pathHist, hlen, bank);
 186
 187     index = gindex_ext(index, bank);
 188
 189     return (index & ((ULL(1) << (logTagTableSizes[bank])) - 1));
 190 }
 191
 192 int
 193 TAGE_SC_L_TAGE::F(int a, int size, int bank) const
 194 {
 195     int a1, a2;
 196
 197     a = a & ((ULL(1) << size) - 1);
 198     a1 = (a & ((ULL(1) << logTagTableSizes[bank]) - 1));
 199     a2 = (a >> logTagTableSizes[bank]);
 200
 201     if (bank < logTagTableSizes[bank]) {
 202         a2 = ((a2 << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
 203              + (a2 >> (logTagTableSizes[bank] - bank));
 204     }
 205
 206     a = a1 ^ a2;
 207
 208     if (bank < logTagTableSizes[bank]) {
 209         a = ((a << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
 210             + (a >> (logTagTableSizes[bank] - bank));
 211     }
 212
 213     return a;
 214 }
 215
 216 int
 217 TAGE_SC_L_TAGE::bindex(Addr pc) const
 218 {
 219     return ((pc ^ (pc >> instShiftAmt)) &
 220             ((ULL(1) << (logTagTableSizes[0])) - 1));
 221 }
 222
 223 void
 224 TAGE_SC_L_TAGE::updatePathAndGlobalHistory(
 225     ThreadHistory& tHist, int brtype, bool taken, Addr branch_pc, Addr target)
 226 {
 227     // TAGE update
 228     int tmp = ((branch_pc ^ (branch_pc >> instShiftAmt))) ^ taken;
 229     int path = branch_pc ^ (branch_pc >> instShiftAmt)
 230                          ^ (branch_pc >> (instShiftAmt+2));
 231     if ((brtype == 3) & taken) {
 232          tmp = (tmp ^ (target >> instShiftAmt));
 233          path = path ^ (target >> instShiftAmt) ^ (target >> (instShiftAmt+2));
 234     }
 235
 236     // some branch types use 3 bits in global history, the others just 2
 237     int maxt = (brtype == 2) ? 3 : 2;
 238
 239     for (int t = 0; t < maxt; t++) {
 240         bool dir = (tmp & 1);
 241         tmp >>= 1;
 242         int pathbit = (path & 127);
 243         path >>= 1;
 244         updateGHist(tHist.gHist, dir, tHist.globalHistory, tHist.ptGhist);
 245         tHist.pathHist = (tHist.pathHist << 1) ^ pathbit;
 246         if (truncatePathHist) {
 247             // The 8KB implementation does not do this truncation
 248             tHist.pathHist = (tHist.pathHist & ((ULL(1) << pathHistBits) - 1));
 249         }
 250         for (int i = 1; i <= nHistoryTables; i++) {
 251             tHist.computeIndices[i].update(tHist.gHist);
 252             tHist.computeTags[0][i].update(tHist.gHist);
 253             tHist.computeTags[1][i].update(tHist.gHist);
 254         }
 255     }
 256 }
 257
 258 void
 259 TAGE_SC_L_TAGE::updateHistories(
 260     ThreadID tid, Addr branch_pc, bool taken, TAGEBase::BranchInfo* b,
 261     bool speculative, const StaticInstPtr &inst, Addr target)
 262 {
 263     if (speculative != speculativeHistUpdate) {
 264         return;
 265     }
 266     // speculation is not implemented
 267     assert(! speculative);
 268
 269     ThreadHistory& tHist = threadHistory[tid];
 270
 271     int brtype = inst->isDirectCtrl() ? 0 : 2;
 272     if (! inst->isUncondCtrl()) {
 273         ++brtype;
 274     }
 275     updatePathAndGlobalHistory(tHist, brtype, taken, branch_pc, target);
 276
 277     DPRINTF(TageSCL, "Updating global histories with branch:%lx; taken?:%d, "
 278             "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist,
 279             tHist.ptGhist);
 280 }
 281
 282 void
 283 TAGE_SC_L_TAGE::squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi,
 284                        Addr target)
 285 {
 286     fatal("Speculation is not implemented");
 287 }
 288
 289 void
 290 TAGE_SC_L_TAGE::adjustAlloc(bool & alloc, bool taken, bool pred_taken)
 291 {
 292     // Do not allocate too often if the prediction is ok
 293     if ((taken == pred_taken) && ((random_mt.random<int>() & 31) != 0)) {
 294         alloc = false;
 295     }
 296 }
 297
 298 int
 299 TAGE_SC_L_TAGE::calcDep(TAGEBase::BranchInfo* bi)
 300 {
 301     int a = 1;
 302     if ((random_mt.random<int>() & 127) < 32) {
 303         a = 2;
 304     }
 305     return ((((bi->hitBank - 1 + 2 * a) & 0xffe)) ^
 306             (random_mt.random<int>() & 1));
 307 }
 308
 309 void
 310 TAGE_SC_L_TAGE::handleUReset()
 311 {
 312     //just the best formula for the Championship:
 313     //In practice when one out of two entries are useful
 314     if (tCounter < 0) {
 315         tCounter = 0;
 316     }
 317
 318     if (tCounter >= ((ULL(1) << logUResetPeriod))) {
 319         // Update the u bits for the short tags table
 320         for (int j = 0; j < (shortTagsTageFactor*(1<<logTagTableSize)); j++) {
 321             resetUctr(gtable[1][j].u);
 322         }
 323
 324         // Update the u bits for the long tags table
 325         for (int j = 0; j < (longTagsTageFactor*(1<<logTagTableSize)); j++) {
 326             resetUctr(gtable[firstLongTagTable][j].u);
 327         }
 328
 329         tCounter = 0;
 330     }
 331 }
 332
 333 bool
 334 TAGE_SC_L_TAGE::getBimodePred(Addr pc, TAGEBase::BranchInfo* tage_bi) const
 335 {
 336     TAGE_SC_L_TAGE::BranchInfo *bi =
 337         static_cast<TAGE_SC_L_TAGE::BranchInfo *>(tage_bi);
 338
 339     int bim = (btablePrediction[bi->bimodalIndex] << 1)
 340         + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries];
 341
 342     bi->highConf = (bim == 0) || (bim == 3);
 343     bi->lowConf = ! bi->highConf;
 344     bi->altConf = bi->highConf;
 345     bi->medConf = false;
 346     return TAGEBase::getBimodePred(pc, tage_bi);
 347 }
 348
 349 void
 350 TAGE_SC_L_TAGE::extraAltCalc(TAGEBase::BranchInfo* bi)
 351 {
 352     TAGE_SC_L_TAGE::BranchInfo *tage_scl_bi =
 353         static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi);
 354     int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
 355     tage_scl_bi->altConf = (abs(2*ctr + 1) > 1);
 356 }
 357
 358 bool
 359 TAGE_SC_L::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
 360 {
 361     TageSCLBranchInfo *bi = new TageSCLBranchInfo(*tage,
 362                                                   *statisticalCorrector,
 363                                                   *loopPredictor);
 364     b = (void*)(bi);
 365
 366     bool pred_taken = tage->tagePredict(tid, branch_pc, cond_branch,
 367                                         bi->tageBranchInfo);
 368     pred_taken = loopPredictor->loopPredict(tid, branch_pc, cond_branch,
 369                                             bi->lpBranchInfo, pred_taken,
 370                                             instShiftAmt);
 371
 372     if (bi->lpBranchInfo->loopPredUsed) {
 373         bi->tageBranchInfo->provider = LOOP;
 374     }
 375
 376     TAGE_SC_L_TAGE::BranchInfo* tage_scl_bi =
 377         static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi->tageBranchInfo);
 378
 379     // Copy the confidences computed by TAGE
 380     bi->scBranchInfo->lowConf = tage_scl_bi->lowConf;
 381     bi->scBranchInfo->highConf = tage_scl_bi->highConf;
 382     bi->scBranchInfo->altConf = tage_scl_bi->altConf;
 383     bi->scBranchInfo->medConf = tage_scl_bi->medConf;
 384
 385     bool use_tage_ctr = bi->tageBranchInfo->hitBank > 0;
 386     int8_t tage_ctr = use_tage_ctr ?
 387         tage->getCtr(tage_scl_bi->hitBank, tage_scl_bi->hitBankIndex) : 0;
 388     bool bias = (bi->tageBranchInfo->longestMatchPred !=
 389                  bi->tageBranchInfo->altTaken);
 390
 391     pred_taken = statisticalCorrector->scPredict(tid, branch_pc, cond_branch,
 392             bi->scBranchInfo, pred_taken, bias, use_tage_ctr, tage_ctr,
 393             tage->getTageCtrBits(), bi->tageBranchInfo->hitBank,
 394             bi->tageBranchInfo->altBank, tage->getPathHist(tid));
 395
 396     if (bi->scBranchInfo->usedScPred) {
 397         bi->tageBranchInfo->provider = SC;
 398     }
 399
 400     // record final prediction
 401     bi->lpBranchInfo->predTaken = pred_taken;
 402
 403     return pred_taken;
 404 }
 405
 406 void
 407 TAGE_SC_L::update(ThreadID tid, Addr branch_pc, bool taken, void *bp_history,
 408         bool squashed, const StaticInstPtr & inst, Addr corrTarget)
 409 {
 410     assert(bp_history);
 411
 412     TageSCLBranchInfo* bi = static_cast<TageSCLBranchInfo*>(bp_history);
 413     TAGE_SC_L_TAGE::BranchInfo* tage_bi =
 414         static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi->tageBranchInfo);
 415
 416     if (squashed) {
 417         if (tage->isSpeculativeUpdateEnabled()) {
 418             // This restores the global history, then update it
 419             // and recomputes the folded histories.
 420             tage->squash(tid, taken, tage_bi, corrTarget);
 421             if (bi->tageBranchInfo->condBranch) {
 422                 loopPredictor->squashLoop(bi->lpBranchInfo);
 423             }
 424         }
 425         return;
 426     }
 427
 428     int nrand = random_mt.random<int>() & 3;
 429     if (tage_bi->condBranch) {
 430         DPRINTF(TageSCL, "Updating tables for branch:%lx; taken?:%d\n",
 431                 branch_pc, taken);
 432         tage->updateStats(taken, bi->tageBranchInfo);
 433
 434         loopPredictor->updateStats(taken, bi->lpBranchInfo);
 435
 436         statisticalCorrector->updateStats(taken, bi->scBranchInfo);
 437
 438         bool bias = (bi->tageBranchInfo->longestMatchPred !=
 439                      bi->tageBranchInfo->altTaken);
 440         statisticalCorrector->condBranchUpdate(tid, branch_pc, taken,
 441             bi->scBranchInfo, corrTarget, bias, bi->tageBranchInfo->hitBank,
 442             bi->tageBranchInfo->altBank, tage->getPathHist(tid));
 443
 444         loopPredictor->condBranchUpdate(tid, branch_pc, taken,
 445                 bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt);
 446
 447         tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo,
 448                                nrand, corrTarget, bi->lpBranchInfo->predTaken);
 449     }
 450
 451     if (!tage->isSpeculativeUpdateEnabled()) {
 452         statisticalCorrector->scHistoryUpdate(branch_pc, inst, taken,
 453                                               bi->scBranchInfo, corrTarget);
 454
 455         tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
 456                               inst, corrTarget);
 457     }
 458
 459     delete bi;
 460 }
 461
 462 void
 463 TAGE_SC_L::regStats()
 464 {
 465     LTAGE::regStats();
 466 }