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