src/cpu/pred/tage_base.cc

   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 /* @file
  38  * Implementation of a TAGE branch predictor
  39  */
  40
  41 #include "cpu/pred/tage_base.hh"
  42
  43 #include "base/intmath.hh"
  44 #include "base/logging.hh"
  45 #include "debug/Fetch.hh"
  46 #include "debug/Tage.hh"
  47
  48 TAGEBase::TAGEBase(const TAGEBaseParams *p)
  49    : SimObject(p),
  50      logRatioBiModalHystEntries(p->logRatioBiModalHystEntries),
  51      nHistoryTables(p->nHistoryTables),
  52      tagTableCounterBits(p->tagTableCounterBits),
  53      tagTableUBits(p->tagTableUBits),
  54      histBufferSize(p->histBufferSize),
  55      minHist(p->minHist),
  56      maxHist(p->maxHist),
  57      pathHistBits(p->pathHistBits),
  58      tagTableTagWidths(p->tagTableTagWidths),
  59      logTagTableSizes(p->logTagTableSizes),
  60      threadHistory(p->numThreads),
  61      logUResetPeriod(p->logUResetPeriod),
  62      numUseAltOnNa(p->numUseAltOnNa),
  63      useAltOnNaBits(p->useAltOnNaBits),
  64      maxNumAlloc(p->maxNumAlloc),
  65      noSkip(p->noSkip),
  66      speculativeHistUpdate(p->speculativeHistUpdate),
  67      instShiftAmt(p->instShiftAmt)
  68 {
  69     if (noSkip.empty()) {
  70         // Set all the table to enabled by default
  71         noSkip.resize(nHistoryTables + 1, true);
  72     }
  73 }
  74
  75 TAGEBase::BranchInfo*
  76 TAGEBase::makeBranchInfo() {
  77     return new BranchInfo(*this);
  78 }
  79
  80 void
  81 TAGEBase::init()
  82 {
  83     // Current method for periodically resetting the u counter bits only
  84     // works for 1 or 2 bits
  85     // Also make sure that it is not 0
  86     assert(tagTableUBits <= 2 && (tagTableUBits > 0));
  87
  88     // we use int type for the path history, so it cannot be more than
  89     // its size
  90     assert(pathHistBits <= (sizeof(int)*8));
  91
  92     // initialize the counter to half of the period
  93     assert(logUResetPeriod != 0);
  94     tCounter = ULL(1) << (logUResetPeriod - 1);
  95
  96     assert(histBufferSize > maxHist * 2);
  97
  98     useAltPredForNewlyAllocated.resize(numUseAltOnNa, 0);
  99
 100     for (auto& history : threadHistory) {
 101         history.pathHist = 0;
 102         history.globalHistory = new uint8_t[histBufferSize];
 103         history.gHist = history.globalHistory;
 104         memset(history.gHist, 0, histBufferSize);
 105         history.ptGhist = 0;
 106     }
 107
 108     histLengths = new int [nHistoryTables+1];
 109
 110     calculateParameters();
 111
 112     assert(tagTableTagWidths.size() == (nHistoryTables+1));
 113     assert(logTagTableSizes.size() == (nHistoryTables+1));
 114
 115     // First entry is for the Bimodal table and it is untagged in this
 116     // implementation
 117     assert(tagTableTagWidths[0] == 0);
 118
 119     for (auto& history : threadHistory) {
 120         history.computeIndices = new FoldedHistory[nHistoryTables+1];
 121         history.computeTags[0] = new FoldedHistory[nHistoryTables+1];
 122         history.computeTags[1] = new FoldedHistory[nHistoryTables+1];
 123
 124         initFoldedHistories(history);
 125     }
 126
 127     const uint64_t bimodalTableSize = ULL(1) << logTagTableSizes[0];
 128     btablePrediction.resize(bimodalTableSize, false);
 129     btableHysteresis.resize(bimodalTableSize >> logRatioBiModalHystEntries,
 130                             true);
 131
 132     gtable = new TageEntry*[nHistoryTables + 1];
 133     buildTageTables();
 134
 135     tableIndices = new int [nHistoryTables+1];
 136     tableTags = new int [nHistoryTables+1];
 137 }
 138
 139 void
 140 TAGEBase::initFoldedHistories(ThreadHistory & history)
 141 {
 142     for (int i = 1; i <= nHistoryTables; i++) {
 143         history.computeIndices[i].init(
 144             histLengths[i], (logTagTableSizes[i]));
 145         history.computeTags[0][i].init(
 146             history.computeIndices[i].origLength, tagTableTagWidths[i]);
 147         history.computeTags[1][i].init(
 148             history.computeIndices[i].origLength, tagTableTagWidths[i]-1);
 149         DPRINTF(Tage, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
 150                 histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]);
 151     }
 152 }
 153
 154 void
 155 TAGEBase::buildTageTables()
 156 {
 157     for (int i = 1; i <= nHistoryTables; i++) {
 158         gtable[i] = new TageEntry[1<<(logTagTableSizes[i])];
 159     }
 160 }
 161
 162 void
 163 TAGEBase::calculateParameters()
 164 {
 165     histLengths[1] = minHist;
 166     histLengths[nHistoryTables] = maxHist;
 167
 168     for (int i = 2; i <= nHistoryTables; i++) {
 169         histLengths[i] = (int) (((double) minHist *
 170                        pow ((double) (maxHist) / (double) minHist,
 171                            (double) (i - 1) / (double) ((nHistoryTables- 1))))
 172                        + 0.5);
 173     }
 174 }
 175
 176 void
 177 TAGEBase::btbUpdate(ThreadID tid, Addr branch_pc, BranchInfo* &bi)
 178 {
 179     if (speculativeHistUpdate) {
 180         ThreadHistory& tHist = threadHistory[tid];
 181         DPRINTF(Tage, "BTB miss resets prediction: %lx\n", branch_pc);
 182         assert(tHist.gHist == &tHist.globalHistory[tHist.ptGhist]);
 183         tHist.gHist[0] = 0;
 184         for (int i = 1; i <= nHistoryTables; i++) {
 185             tHist.computeIndices[i].comp = bi->ci[i];
 186             tHist.computeTags[0][i].comp = bi->ct0[i];
 187             tHist.computeTags[1][i].comp = bi->ct1[i];
 188             tHist.computeIndices[i].update(tHist.gHist);
 189             tHist.computeTags[0][i].update(tHist.gHist);
 190             tHist.computeTags[1][i].update(tHist.gHist);
 191         }
 192     }
 193 }
 194
 195 int
 196 TAGEBase::bindex(Addr pc_in) const
 197 {
 198     return ((pc_in >> instShiftAmt) & ((ULL(1) << (logTagTableSizes[0])) - 1));
 199 }
 200
 201 int
 202 TAGEBase::F(int A, int size, int bank) const
 203 {
 204     int A1, A2;
 205
 206     A = A & ((ULL(1) << size) - 1);
 207     A1 = (A & ((ULL(1) << logTagTableSizes[bank]) - 1));
 208     A2 = (A >> logTagTableSizes[bank]);
 209     A2 = ((A2 << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
 210        + (A2 >> (logTagTableSizes[bank] - bank));
 211     A = A1 ^ A2;
 212     A = ((A << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
 213       + (A >> (logTagTableSizes[bank] - bank));
 214     return (A);
 215 }
 216
 217 // gindex computes a full hash of pc, ghist and pathHist
 218 int
 219 TAGEBase::gindex(ThreadID tid, Addr pc, int bank) const
 220 {
 221     int index;
 222     int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
 223                                                     histLengths[bank];
 224     const unsigned int shiftedPc = pc >> instShiftAmt;
 225     index =
 226         shiftedPc ^
 227         (shiftedPc >> ((int) abs(logTagTableSizes[bank] - bank) + 1)) ^
 228         threadHistory[tid].computeIndices[bank].comp ^
 229         F(threadHistory[tid].pathHist, hlen, bank);
 230
 231     return (index & ((ULL(1) << (logTagTableSizes[bank])) - 1));
 232 }
 233
 234
 235 // Tag computation
 236 uint16_t
 237 TAGEBase::gtag(ThreadID tid, Addr pc, int bank) const
 238 {
 239     int tag = (pc >> instShiftAmt) ^
 240               threadHistory[tid].computeTags[0][bank].comp ^
 241               (threadHistory[tid].computeTags[1][bank].comp << 1);
 242
 243     return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1));
 244 }
 245
 246
 247 // Up-down saturating counter
 248 template<typename T>
 249 void
 250 TAGEBase::ctrUpdate(T & ctr, bool taken, int nbits)
 251 {
 252     assert(nbits <= sizeof(T) << 3);
 253     if (taken) {
 254         if (ctr < ((1 << (nbits - 1)) - 1))
 255             ctr++;
 256     } else {
 257         if (ctr > -(1 << (nbits - 1)))
 258             ctr--;
 259     }
 260 }
 261
 262 // int8_t and int versions of this function may be needed
 263 template void TAGEBase::ctrUpdate(int8_t & ctr, bool taken, int nbits);
 264 template void TAGEBase::ctrUpdate(int & ctr, bool taken, int nbits);
 265
 266 // Up-down unsigned saturating counter
 267 void
 268 TAGEBase::unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits)
 269 {
 270     assert(nbits <= sizeof(uint8_t) << 3);
 271     if (up) {
 272         if (ctr < ((1 << nbits) - 1))
 273             ctr++;
 274     } else {
 275         if (ctr)
 276             ctr--;
 277     }
 278 }
 279
 280 // Bimodal prediction
 281 bool
 282 TAGEBase::getBimodePred(Addr pc, BranchInfo* bi) const
 283 {
 284     return btablePrediction[bi->bimodalIndex];
 285 }
 286
 287
 288 // Update the bimodal predictor: a hysteresis bit is shared among N prediction
 289 // bits (N = 2 ^ logRatioBiModalHystEntries)
 290 void
 291 TAGEBase::baseUpdate(Addr pc, bool taken, BranchInfo* bi)
 292 {
 293     int inter = (btablePrediction[bi->bimodalIndex] << 1)
 294         + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries];
 295     if (taken) {
 296         if (inter < 3)
 297             inter++;
 298     } else if (inter > 0) {
 299         inter--;
 300     }
 301     const bool pred = inter >> 1;
 302     const bool hyst = inter & 1;
 303     btablePrediction[bi->bimodalIndex] = pred;
 304     btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries] = hyst;
 305     DPRINTF(Tage, "Updating branch %lx, pred:%d, hyst:%d\n", pc, pred, hyst);
 306 }
 307
 308 // shifting the global history:  we manage the history in a big table in order
 309 // to reduce simulation time
 310 void
 311 TAGEBase::updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &pt)
 312 {
 313     if (pt == 0) {
 314         DPRINTF(Tage, "Rolling over the histories\n");
 315          // Copy beginning of globalHistoryBuffer to end, such that
 316          // the last maxHist outcomes are still reachable
 317          // through pt[0 .. maxHist - 1].
 318          for (int i = 0; i < maxHist; i++)
 319              tab[histBufferSize - maxHist + i] = tab[i];
 320          pt =  histBufferSize - maxHist;
 321          h = &tab[pt];
 322     }
 323     pt--;
 324     h--;
 325     h[0] = (dir) ? 1 : 0;
 326 }
 327
 328 void
 329 TAGEBase::calculateIndicesAndTags(ThreadID tid, Addr branch_pc,
 330                                   BranchInfo* bi)
 331 {
 332     // computes the table addresses and the partial tags
 333     for (int i = 1; i <= nHistoryTables; i++) {
 334         tableIndices[i] = gindex(tid, branch_pc, i);
 335         bi->tableIndices[i] = tableIndices[i];
 336         tableTags[i] = gtag(tid, branch_pc, i);
 337         bi->tableTags[i] = tableTags[i];
 338     }
 339 }
 340
 341 unsigned
 342 TAGEBase::getUseAltIdx(BranchInfo* bi)
 343 {
 344     // There is only 1 counter on the base TAGE implementation
 345     return 0;
 346 }
 347
 348 bool
 349 TAGEBase::tagePredict(ThreadID tid, Addr branch_pc,
 350               bool cond_branch, BranchInfo* bi)
 351 {
 352     Addr pc = branch_pc;
 353     bool pred_taken = true;
 354
 355     if (cond_branch) {
 356         // TAGE prediction
 357
 358         calculateIndicesAndTags(tid, pc, bi);
 359
 360         bi->bimodalIndex = bindex(pc);
 361
 362         bi->hitBank = 0;
 363         bi->altBank = 0;
 364         //Look for the bank with longest matching history
 365         for (int i = nHistoryTables; i > 0; i--) {
 366             if (noSkip[i] &&
 367                 gtable[i][tableIndices[i]].tag == tableTags[i]) {
 368                 bi->hitBank = i;
 369                 bi->hitBankIndex = tableIndices[bi->hitBank];
 370                 break;
 371             }
 372         }
 373         //Look for the alternate bank
 374         for (int i = bi->hitBank - 1; i > 0; i--) {
 375             if (noSkip[i] &&
 376                 gtable[i][tableIndices[i]].tag == tableTags[i]) {
 377                 bi->altBank = i;
 378                 bi->altBankIndex = tableIndices[bi->altBank];
 379                 break;
 380             }
 381         }
 382         //computes the prediction and the alternate prediction
 383         if (bi->hitBank > 0) {
 384             if (bi->altBank > 0) {
 385                 bi->altTaken =
 386                     gtable[bi->altBank][tableIndices[bi->altBank]].ctr >= 0;
 387                 extraAltCalc(bi);
 388             }else {
 389                 bi->altTaken = getBimodePred(pc, bi);
 390             }
 391
 392             bi->longestMatchPred =
 393                 gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr >= 0;
 394             bi->pseudoNewAlloc =
 395                 abs(2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) <= 1;
 396
 397             //if the entry is recognized as a newly allocated entry and
 398             //useAltPredForNewlyAllocated is positive use the alternate
 399             //prediction
 400             if ((useAltPredForNewlyAllocated[getUseAltIdx(bi)] < 0) ||
 401                 ! bi->pseudoNewAlloc) {
 402                 bi->tagePred = bi->longestMatchPred;
 403                 bi->provider = TAGE_LONGEST_MATCH;
 404             } else {
 405                 bi->tagePred = bi->altTaken;
 406                 bi->provider = bi->altBank ? TAGE_ALT_MATCH
 407                                            : BIMODAL_ALT_MATCH;
 408             }
 409         } else {
 410             bi->altTaken = getBimodePred(pc, bi);
 411             bi->tagePred = bi->altTaken;
 412             bi->longestMatchPred = bi->altTaken;
 413             bi->provider = BIMODAL_ONLY;
 414         }
 415         //end TAGE prediction
 416
 417         pred_taken = (bi->tagePred);
 418         DPRINTF(Tage, "Predict for %lx: taken?:%d, tagePred:%d, altPred:%d\n",
 419                 branch_pc, pred_taken, bi->tagePred, bi->altTaken);
 420     }
 421     bi->branchPC = branch_pc;
 422     bi->condBranch = cond_branch;
 423     return pred_taken;
 424 }
 425
 426 void
 427 TAGEBase::adjustAlloc(bool & alloc, bool taken, bool pred_taken)
 428 {
 429     // Nothing for this base class implementation
 430 }
 431
 432 void
 433 TAGEBase::handleAllocAndUReset(bool alloc, bool taken, BranchInfo* bi,
 434                            int nrand)
 435 {
 436     if (alloc) {
 437         // is there some "unuseful" entry to allocate
 438         uint8_t min = 1;
 439         for (int i = nHistoryTables; i > bi->hitBank; i--) {
 440             if (gtable[i][bi->tableIndices[i]].u < min) {
 441                 min = gtable[i][bi->tableIndices[i]].u;
 442             }
 443         }
 444
 445         // we allocate an entry with a longer history
 446         // to  avoid ping-pong, we do not choose systematically the next
 447         // entry, but among the 3 next entries
 448         int Y = nrand &
 449             ((ULL(1) << (nHistoryTables - bi->hitBank - 1)) - 1);
 450         int X = bi->hitBank + 1;
 451         if (Y & 1) {
 452             X++;
 453             if (Y & 2)
 454                 X++;
 455         }
 456         // No entry available, forces one to be available
 457         if (min > 0) {
 458             gtable[X][bi->tableIndices[X]].u = 0;
 459         }
 460
 461
 462         //Allocate entries
 463         unsigned numAllocated = 0;
 464         for (int i = X; i <= nHistoryTables; i++) {
 465             if ((gtable[i][bi->tableIndices[i]].u == 0)) {
 466                 gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
 467                 gtable[i][bi->tableIndices[i]].ctr = (taken) ? 0 : -1;
 468                 ++numAllocated;
 469                 if (numAllocated == maxNumAlloc) {
 470                     break;
 471                 }
 472             }
 473         }
 474     }
 475
 476     tCounter++;
 477
 478     handleUReset();
 479 }
 480
 481 void
 482 TAGEBase::handleUReset()
 483 {
 484     //periodic reset of u: reset is not complete but bit by bit
 485     if ((tCounter & ((ULL(1) << logUResetPeriod) - 1)) == 0) {
 486         // reset least significant bit
 487         // most significant bit becomes least significant bit
 488         for (int i = 1; i <= nHistoryTables; i++) {
 489             for (int j = 0; j < (ULL(1) << logTagTableSizes[i]); j++) {
 490                 resetUctr(gtable[i][j].u);
 491             }
 492         }
 493     }
 494 }
 495
 496 void
 497 TAGEBase::resetUctr(uint8_t & u)
 498 {
 499     u >>= 1;
 500 }
 501
 502 void
 503 TAGEBase::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
 504                        BranchInfo* bi, int nrand, Addr corrTarget, bool pred)
 505 {
 506     // TAGE UPDATE
 507     // try to allocate a  new entries only if prediction was wrong
 508     bool alloc = (bi->tagePred != taken) && (bi->hitBank < nHistoryTables);
 509     if (bi->hitBank > 0) {
 510         // Manage the selection between longest matching and alternate
 511         // matching for "pseudo"-newly allocated longest matching entry
 512         bool PseudoNewAlloc = bi->pseudoNewAlloc;
 513         // an entry is considered as newly allocated if its prediction
 514         // counter is weak
 515         if (PseudoNewAlloc) {
 516             if (bi->longestMatchPred == taken) {
 517                 alloc = false;
 518             }
 519             // if it was delivering the correct prediction, no need to
 520             // allocate new entry even if the overall prediction was false
 521             if (bi->longestMatchPred != bi->altTaken) {
 522                 ctrUpdate(useAltPredForNewlyAllocated[getUseAltIdx(bi)],
 523                      bi->altTaken == taken, useAltOnNaBits);
 524             }
 525         }
 526     }
 527
 528     adjustAlloc(alloc, taken, pred);
 529
 530     handleAllocAndUReset(alloc, taken, bi, nrand);
 531
 532     handleTAGEUpdate(branch_pc, taken, bi);
 533 }
 534
 535 void
 536 TAGEBase::handleTAGEUpdate(Addr branch_pc, bool taken, BranchInfo* bi)
 537 {
 538     if (bi->hitBank > 0) {
 539         DPRINTF(Tage, "Updating tag table entry (%d,%d) for branch %lx\n",
 540                 bi->hitBank, bi->hitBankIndex, branch_pc);
 541         ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
 542                   tagTableCounterBits);
 543         // if the provider entry is not certified to be useful also update
 544         // the alternate prediction
 545         if (gtable[bi->hitBank][bi->hitBankIndex].u == 0) {
 546             if (bi->altBank > 0) {
 547                 ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
 548                           tagTableCounterBits);
 549                 DPRINTF(Tage, "Updating tag table entry (%d,%d) for"
 550                         " branch %lx\n", bi->hitBank, bi->hitBankIndex,
 551                         branch_pc);
 552             }
 553             if (bi->altBank == 0) {
 554                 baseUpdate(branch_pc, taken, bi);
 555             }
 556         }
 557
 558         // update the u counter
 559         if (bi->tagePred != bi->altTaken) {
 560             unsignedCtrUpdate(gtable[bi->hitBank][bi->hitBankIndex].u,
 561                               bi->tagePred == taken, tagTableUBits);
 562         }
 563     } else {
 564         baseUpdate(branch_pc, taken, bi);
 565     }
 566 }
 567
 568 void
 569 TAGEBase::updateHistories(ThreadID tid, Addr branch_pc, bool taken,
 570                           BranchInfo* bi, bool speculative,
 571                           const StaticInstPtr &inst, Addr target)
 572 {
 573     if (speculative != speculativeHistUpdate) {
 574         return;
 575     }
 576     ThreadHistory& tHist = threadHistory[tid];
 577     //  UPDATE HISTORIES
 578     bool pathbit = ((branch_pc >> instShiftAmt) & 1);
 579     //on a squash, return pointers to this and recompute indices.
 580     //update user history
 581     updateGHist(tHist.gHist, taken, tHist.globalHistory, tHist.ptGhist);
 582     tHist.pathHist = (tHist.pathHist << 1) + pathbit;
 583     tHist.pathHist = (tHist.pathHist & ((ULL(1) << pathHistBits) - 1));
 584
 585     if (speculative) {
 586         bi->ptGhist = tHist.ptGhist;
 587         bi->pathHist = tHist.pathHist;
 588     }
 589
 590     //prepare next index and tag computations for user branchs
 591     for (int i = 1; i <= nHistoryTables; i++)
 592     {
 593         if (speculative) {
 594             bi->ci[i]  = tHist.computeIndices[i].comp;
 595             bi->ct0[i] = tHist.computeTags[0][i].comp;
 596             bi->ct1[i] = tHist.computeTags[1][i].comp;
 597         }
 598         tHist.computeIndices[i].update(tHist.gHist);
 599         tHist.computeTags[0][i].update(tHist.gHist);
 600         tHist.computeTags[1][i].update(tHist.gHist);
 601     }
 602     DPRINTF(Tage, "Updating global histories with branch:%lx; taken?:%d, "
 603             "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist,
 604             tHist.ptGhist);
 605     assert(threadHistory[tid].gHist ==
 606             &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]);
 607 }
 608
 609 void
 610 TAGEBase::squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi,
 611                  Addr target)
 612 {
 613     if (!speculativeHistUpdate) {
 614         /* If there are no speculative updates, no actions are needed */
 615         return;
 616     }
 617
 618     ThreadHistory& tHist = threadHistory[tid];
 619     DPRINTF(Tage, "Restoring branch info: %lx; taken? %d; PathHistory:%x, "
 620             "pointer:%d\n", bi->branchPC,taken, bi->pathHist, bi->ptGhist);
 621     tHist.pathHist = bi->pathHist;
 622     tHist.ptGhist = bi->ptGhist;
 623     tHist.gHist = &(tHist.globalHistory[tHist.ptGhist]);
 624     tHist.gHist[0] = (taken ? 1 : 0);
 625     for (int i = 1; i <= nHistoryTables; i++) {
 626         tHist.computeIndices[i].comp = bi->ci[i];
 627         tHist.computeTags[0][i].comp = bi->ct0[i];
 628         tHist.computeTags[1][i].comp = bi->ct1[i];
 629         tHist.computeIndices[i].update(tHist.gHist);
 630         tHist.computeTags[0][i].update(tHist.gHist);
 631         tHist.computeTags[1][i].update(tHist.gHist);
 632     }
 633 }
 634
 635 void
 636 TAGEBase::extraAltCalc(BranchInfo* bi)
 637 {
 638     // do nothing. This is only used in some derived classes
 639     return;
 640 }
 641
 642 void
 643 TAGEBase::updateStats(bool taken, BranchInfo* bi)
 644 {
 645     if (taken == bi->tagePred) {
 646         // correct prediction
 647         switch (bi->provider) {
 648           case BIMODAL_ONLY: tageBimodalProviderCorrect++; break;
 649           case TAGE_LONGEST_MATCH: tageLongestMatchProviderCorrect++; break;
 650           case BIMODAL_ALT_MATCH: bimodalAltMatchProviderCorrect++; break;
 651           case TAGE_ALT_MATCH: tageAltMatchProviderCorrect++; break;
 652         }
 653     } else {
 654         // wrong prediction
 655         switch (bi->provider) {
 656           case BIMODAL_ONLY: tageBimodalProviderWrong++; break;
 657           case TAGE_LONGEST_MATCH:
 658             tageLongestMatchProviderWrong++;
 659             if (bi->altTaken == taken) {
 660                 tageAltMatchProviderWouldHaveHit++;
 661             }
 662             break;
 663           case BIMODAL_ALT_MATCH:
 664             bimodalAltMatchProviderWrong++;
 665             break;
 666           case TAGE_ALT_MATCH:
 667             tageAltMatchProviderWrong++;
 668             break;
 669         }
 670
 671         switch (bi->provider) {
 672           case BIMODAL_ALT_MATCH:
 673           case TAGE_ALT_MATCH:
 674             if (bi->longestMatchPred == taken) {
 675                 tageLongestMatchProviderWouldHaveHit++;
 676             }
 677         }
 678     }
 679
 680     switch (bi->provider) {
 681       case TAGE_LONGEST_MATCH:
 682       case TAGE_ALT_MATCH:
 683         tageLongestMatchProvider[bi->hitBank]++;
 684         tageAltMatchProvider[bi->altBank]++;
 685         break;
 686     }
 687 }
 688
 689 unsigned
 690 TAGEBase::getGHR(ThreadID tid, BranchInfo *bi) const
 691 {
 692     unsigned val = 0;
 693     for (unsigned i = 0; i < 32; i++) {
 694         // Make sure we don't go out of bounds
 695         int gh_offset = bi->ptGhist + i;
 696         assert(&(threadHistory[tid].globalHistory[gh_offset]) <
 697                threadHistory[tid].globalHistory + histBufferSize);
 698         val |= ((threadHistory[tid].globalHistory[gh_offset] & 0x1) << i);
 699     }
 700
 701     return val;
 702 }
 703
 704 void
 705 TAGEBase::regStats()
 706 {
 707     tageLongestMatchProviderCorrect
 708         .name(name() + ".tageLongestMatchProviderCorrect")
 709         .desc("Number of times TAGE Longest Match is the provider and "
 710               "the prediction is correct");
 711
 712     tageAltMatchProviderCorrect
 713         .name(name() + ".tageAltMatchProviderCorrect")
 714         .desc("Number of times TAGE Alt Match is the provider and "
 715               "the prediction is correct");
 716
 717     bimodalAltMatchProviderCorrect
 718         .name(name() + ".bimodalAltMatchProviderCorrect")
 719         .desc("Number of times TAGE Alt Match is the bimodal and it is the "
 720               "provider and the prediction is correct");
 721
 722     tageBimodalProviderCorrect
 723         .name(name() + ".tageBimodalProviderCorrect")
 724         .desc("Number of times there are no hits on the TAGE tables "
 725               "and the bimodal prediction is correct");
 726
 727     tageLongestMatchProviderWrong
 728         .name(name() + ".tageLongestMatchProviderWrong")
 729         .desc("Number of times TAGE Longest Match is the provider and "
 730               "the prediction is wrong");
 731
 732     tageAltMatchProviderWrong
 733         .name(name() + ".tageAltMatchProviderWrong")
 734         .desc("Number of times TAGE Alt Match is the provider and "
 735               "the prediction is wrong");
 736
 737     bimodalAltMatchProviderWrong
 738         .name(name() + ".bimodalAltMatchProviderWrong")
 739         .desc("Number of times TAGE Alt Match is the bimodal and it is the "
 740               "provider and the prediction is wrong");
 741
 742     tageBimodalProviderWrong
 743         .name(name() + ".tageBimodalProviderWrong")
 744         .desc("Number of times there are no hits on the TAGE tables "
 745               "and the bimodal prediction is wrong");
 746
 747     tageAltMatchProviderWouldHaveHit
 748         .name(name() + ".tageAltMatchProviderWouldHaveHit")
 749         .desc("Number of times TAGE Longest Match is the provider, "
 750               "the prediction is wrong and Alt Match prediction was correct");
 751
 752     tageLongestMatchProviderWouldHaveHit
 753         .name(name() + ".tageLongestMatchProviderWouldHaveHit")
 754         .desc("Number of times TAGE Alt Match is the provider, the "
 755               "prediction is wrong and Longest Match prediction was correct");
 756
 757     tageLongestMatchProvider
 758         .init(nHistoryTables + 1)
 759         .name(name() + ".tageLongestMatchProvider")
 760         .desc("TAGE provider for longest match");
 761
 762     tageAltMatchProvider
 763         .init(nHistoryTables + 1)
 764         .name(name() + ".tageAltMatchProvider")
 765         .desc("TAGE provider for alt match");
 766 }
 767
 768 int8_t
 769 TAGEBase::getCtr(int hitBank, int hitBankIndex) const
 770 {
 771     return gtable[hitBank][hitBankIndex].ctr;
 772 }
 773
 774 unsigned
 775 TAGEBase::getTageCtrBits() const
 776 {
 777     return tagTableCounterBits;
 778 }
 779
 780 int
 781 TAGEBase::getPathHist(ThreadID tid) const
 782 {
 783     return threadHistory[tid].pathHist;
 784 }
 785
 786 bool
 787 TAGEBase::isSpeculativeUpdateEnabled() const
 788 {
 789     return speculativeHistUpdate;
 790 }
 791
 792 TAGEBase*
 793 TAGEBaseParams::create()
 794 {
 795     return new TAGEBase(this);
 796 }