ltage.cc revision 11784
12623SN/A/* 22623SN/A * Copyright (c) 2014 The University of Wisconsin 32623SN/A * 42623SN/A * Copyright (c) 2006 INRIA (Institut National de Recherche en 52623SN/A * Informatique et en Automatique / French National Research Institute 62623SN/A * for Computer Science and Applied Mathematics) 72623SN/A * 82623SN/A * All rights reserved. 92623SN/A * 102623SN/A * Redistribution and use in source and binary forms, with or without 112623SN/A * modification, are permitted provided that the following conditions are 122623SN/A * met: redistributions of source code must retain the above copyright 132623SN/A * notice, this list of conditions and the following disclaimer; 142623SN/A * redistributions in binary form must reproduce the above copyright 152623SN/A * notice, this list of conditions and the following disclaimer in the 162623SN/A * documentation and/or other materials provided with the distribution; 172623SN/A * neither the name of the copyright holders nor the names of its 182623SN/A * contributors may be used to endorse or promote products derived from 192623SN/A * this software without specific prior written permission. 202623SN/A * 212623SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 222623SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 232623SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 242623SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 252623SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 262623SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 272665Ssaidi@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 282665Ssaidi@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 292623SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 302623SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 313170Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 323806Ssaidi@eecs.umich.edu * 332623SN/A * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 344040Ssaidi@eecs.umich.edu * from André Seznec's code. 352623SN/A */ 362623SN/A 373348Sbinkertn@umich.edu/* @file 383348Sbinkertn@umich.edu * Implementation of a L-TAGE branch predictor 394762Snate@binkert.org */ 402901Ssaidi@eecs.umich.edu 412623SN/A#include "cpu/pred/ltage.hh" 422623SN/A 432623SN/A#include "base/intmath.hh" 442623SN/A#include "base/misc.hh" 452623SN/A#include "base/random.hh" 462623SN/A#include "base/trace.hh" 472623SN/A#include "debug/Fetch.hh" 482623SN/A#include "debug/LTage.hh" 492623SN/A 502623SN/ALTAGE::LTAGE(const LTAGEParams *params) 512623SN/A : BPredUnit(params), 522623SN/A logSizeBiMP(params->logSizeBiMP), 532623SN/A logSizeTagTables(params->logSizeTagTables), 542623SN/A logSizeLoopPred(params->logSizeLoopPred), 552623SN/A nHistoryTables(params->nHistoryTables), 562623SN/A tagTableCounterBits(params->tagTableCounterBits), 572623SN/A histBufferSize(params->histBufferSize), 582623SN/A minHist(params->minHist), 592623SN/A maxHist(params->maxHist), 602623SN/A minTagWidth(params->minTagWidth), 612623SN/A threadHistory(params->numThreads) 622623SN/A{ 632856Srdreslin@umich.edu assert(params->histBufferSize > params->maxHist * 2); 642856Srdreslin@umich.edu useAltPredForNewlyAllocated = 0; 652856Srdreslin@umich.edu logTick = 19; 662856Srdreslin@umich.edu tCounter = ULL(1) << (logTick - 1); 672856Srdreslin@umich.edu 682856Srdreslin@umich.edu for (auto& history : threadHistory) { 692856Srdreslin@umich.edu history.pathHist = 0; 702856Srdreslin@umich.edu history.globalHistory = new uint8_t[histBufferSize]; 712856Srdreslin@umich.edu history.gHist = history.globalHistory; 722856Srdreslin@umich.edu memset(history.gHist, 0, histBufferSize); 732623SN/A history.ptGhist = 0; 742623SN/A } 752623SN/A 762623SN/A histLengths = new int [nHistoryTables+1]; 772623SN/A histLengths[1] = minHist; 782623SN/A histLengths[nHistoryTables] = maxHist; 792680Sktlim@umich.edu 802680Sktlim@umich.edu for (int i = 2; i <= nHistoryTables; i++) { 812623SN/A histLengths[i] = (int) (((double) minHist * 822623SN/A pow ((double) (maxHist) / (double) minHist, 832680Sktlim@umich.edu (double) (i - 1) / (double) ((nHistoryTables- 1)))) 842623SN/A + 0.5); 852623SN/A } 862623SN/A 872623SN/A tagWidths[1] = minTagWidth; 882623SN/A tagWidths[2] = minTagWidth; 893349Sbinkertn@umich.edu tagWidths[3] = minTagWidth + 1; 902623SN/A tagWidths[4] = minTagWidth + 1; 913184Srdreslin@umich.edu tagWidths[5] = minTagWidth + 2; 922623SN/A tagWidths[6] = minTagWidth + 3; 932623SN/A tagWidths[7] = minTagWidth + 4; 942623SN/A tagWidths[8] = minTagWidth + 5; 952623SN/A tagWidths[9] = minTagWidth + 5; 963349Sbinkertn@umich.edu tagWidths[10] = minTagWidth + 6; 972623SN/A tagWidths[11] = minTagWidth + 7; 983310Srdreslin@umich.edu tagWidths[12] = minTagWidth + 8; 993649Srdreslin@umich.edu 1002623SN/A for (int i = 1; i <= 2; i++) 1012623SN/A tagTableSizes[i] = logSizeTagTables - 1; 1022623SN/A for (int i = 3; i <= 6; i++) 1033349Sbinkertn@umich.edu tagTableSizes[i] = logSizeTagTables; 1042623SN/A for (int i = 7; i <= 10; i++) 1053184Srdreslin@umich.edu tagTableSizes[i] = logSizeTagTables - 1; 1063184Srdreslin@umich.edu for (int i = 11; i <= 12; i++) 1072623SN/A tagTableSizes[i] = logSizeTagTables - 2; 1082623SN/A 1092623SN/A for (auto& history : threadHistory) { 1102623SN/A history.computeIndices = new FoldedHistory[nHistoryTables+1]; 1112623SN/A history.computeTags[0] = new FoldedHistory[nHistoryTables+1]; 1123647Srdreslin@umich.edu history.computeTags[1] = new FoldedHistory[nHistoryTables+1]; 1133647Srdreslin@umich.edu 1143647Srdreslin@umich.edu for (int i = 1; i <= nHistoryTables; i++) { 1153647Srdreslin@umich.edu history.computeIndices[i].init(histLengths[i], (tagTableSizes[i])); 1163647Srdreslin@umich.edu history.computeTags[0][i].init( 1172626SN/A history.computeIndices[i].origLength, tagWidths[i]); 1183647Srdreslin@umich.edu history.computeTags[1][i].init( 1192626SN/A history.computeIndices[i].origLength, tagWidths[i] - 1); 1202623SN/A DPRINTF(LTage, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", 1212623SN/A histLengths[i], tagTableSizes[i], tagWidths[i]); 1222623SN/A } 1232657Ssaidi@eecs.umich.edu } 1242623SN/A 1252623SN/A btable = new BimodalEntry[ULL(1) << logSizeBiMP]; 1262623SN/A ltable = new LoopEntry[ULL(1) << logSizeLoopPred]; 1272623SN/A gtable = new TageEntry*[nHistoryTables + 1]; 1282623SN/A for (int i = 1; i <= nHistoryTables; i++) { 1294192Sktlim@umich.edu gtable[i] = new TageEntry[1<<(tagTableSizes[i])]; 1304192Sktlim@umich.edu } 1314192Sktlim@umich.edu 1324192Sktlim@umich.edu tableIndices = new int [nHistoryTables+1]; 1334192Sktlim@umich.edu tableTags = new int [nHistoryTables+1]; 1344192Sktlim@umich.edu 1354192Sktlim@umich.edu loopUseCounter = 0; 1364192Sktlim@umich.edu} 1374192Sktlim@umich.edu 1384192Sktlim@umich.eduint 1394192Sktlim@umich.eduLTAGE::bindex(Addr pc_in) const 1402623SN/A{ 1412623SN/A return ((pc_in) & ((ULL(1) << (logSizeBiMP)) - 1)); 1422623SN/A} 1432623SN/A 1442640Sstever@eecs.umich.eduint 1452623SN/ALTAGE::lindex(Addr pc_in) const 1462623SN/A{ 1472623SN/A return (((pc_in) & ((ULL(1) << (logSizeLoopPred - 2)) - 1)) << 2); 1483647Srdreslin@umich.edu} 1493647Srdreslin@umich.edu 1503647Srdreslin@umich.eduint 1512663Sstever@eecs.umich.eduLTAGE::F(int A, int size, int bank) const 1523170Sstever@eecs.umich.edu{ 1534022Sstever@eecs.umich.edu int A1, A2; 1542623SN/A 1552623SN/A A = A & ((ULL(1) << size) - 1); 1562663Sstever@eecs.umich.edu A1 = (A & ((ULL(1) << tagTableSizes[bank]) - 1)); 1573170Sstever@eecs.umich.edu A2 = (A >> tagTableSizes[bank]); 1584022Sstever@eecs.umich.edu A2 = ((A2 << bank) & ((ULL(1) << tagTableSizes[bank]) - 1)) 1592641Sstever@eecs.umich.edu + (A2 >> (tagTableSizes[bank] - bank)); 1602623SN/A A = A1 ^ A2; 1612623SN/A A = ((A << bank) & ((ULL(1) << tagTableSizes[bank]) - 1)) 1622663Sstever@eecs.umich.edu + (A >> (tagTableSizes[bank] - bank)); 1633170Sstever@eecs.umich.edu return (A); 1644022Sstever@eecs.umich.edu} 1652641Sstever@eecs.umich.edu 1664040Ssaidi@eecs.umich.edu 1674040Ssaidi@eecs.umich.edu// gindex computes a full hash of pc, ghist and pathHist 1682623SN/Aint 1692623SN/ALTAGE::gindex(ThreadID tid, Addr pc, int bank) const 1702623SN/A{ 1712623SN/A int index; 1722623SN/A int hlen = (histLengths[bank] > 16) ? 16 : histLengths[bank]; 1732623SN/A index = 1742623SN/A (pc) ^ ((pc) >> ((int) abs(tagTableSizes[bank] - bank) + 1)) ^ 1752623SN/A threadHistory[tid].computeIndices[bank].comp ^ 1762623SN/A F(threadHistory[tid].pathHist, hlen, bank); 1772623SN/A 1782915Sktlim@umich.edu return (index & ((ULL(1) << (tagTableSizes[bank])) - 1)); 1792915Sktlim@umich.edu} 1803177Shsul@eecs.umich.edu 1813177Shsul@eecs.umich.edu 1823145Shsul@eecs.umich.edu// Tag computation 1832623SN/Auint16_t 1842623SN/ALTAGE::gtag(ThreadID tid, Addr pc, int bank) const 1852623SN/A{ 1862623SN/A int tag = (pc) ^ threadHistory[tid].computeTags[0][bank].comp 1872623SN/A ^ (threadHistory[tid].computeTags[1][bank].comp << 1); 1882623SN/A 1892623SN/A return (tag & ((ULL(1) << tagWidths[bank]) - 1)); 1902915Sktlim@umich.edu} 1912915Sktlim@umich.edu 1923177Shsul@eecs.umich.edu 1933145Shsul@eecs.umich.edu// Up-down saturating counter 1942915Sktlim@umich.eduvoid 1952915Sktlim@umich.eduLTAGE::ctrUpdate(int8_t & ctr, bool taken, int nbits) 1962915Sktlim@umich.edu{ 1972915Sktlim@umich.edu assert(nbits <= sizeof(int8_t) << 3); 1982915Sktlim@umich.edu if (taken) { 1992915Sktlim@umich.edu if (ctr < ((1 << (nbits - 1)) - 1)) 2003324Shsul@eecs.umich.edu ctr++; 2014762Snate@binkert.org } else { 2023324Shsul@eecs.umich.edu if (ctr > -(1 << (nbits - 1))) 2033324Shsul@eecs.umich.edu ctr--; 2043324Shsul@eecs.umich.edu } 2053431Sgblack@eecs.umich.edu} 2063495Sktlim@umich.edu 2073431Sgblack@eecs.umich.edu// Bimodal prediction 2083324Shsul@eecs.umich.edubool 2092915Sktlim@umich.eduLTAGE::getBimodePred(Addr pc, BranchInfo* bi) const 2102623SN/A{ 2112623SN/A return (btable[bi->bimodalIndex].pred > 0); 2122623SN/A} 2132798Sktlim@umich.edu 2142623SN/A 2152798Sktlim@umich.edu// Update the bimodal predictor: a hysteresis bit is shared among 4 prediction 2162798Sktlim@umich.edu// bits 2172623SN/Avoid 2182798Sktlim@umich.eduLTAGE::baseUpdate(Addr pc, bool taken, BranchInfo* bi) 2192623SN/A{ 2202623SN/A int inter = (btable[bi->bimodalIndex].pred << 1) 2212623SN/A + btable[bi->bimodalIndex ].hyst; 2222623SN/A if (taken) { 2232623SN/A if (inter < 3) 2242623SN/A inter++; 2254192Sktlim@umich.edu } else if (inter > 0) { 2262623SN/A inter--; 2272623SN/A } 2282623SN/A btable[bi->bimodalIndex].pred = inter >> 1; 2292680Sktlim@umich.edu btable[bi->bimodalIndex].hyst = (inter & 1); 2302623SN/A DPRINTF(LTage, "Updating branch %lx, pred:%d, hyst:%d\n", 2312680Sktlim@umich.edu pc, btable[bi->bimodalIndex].pred,btable[bi->bimodalIndex].hyst); 2322680Sktlim@umich.edu} 2332680Sktlim@umich.edu 2342623SN/A 2353495Sktlim@umich.edu//loop prediction: only used if high confidence 2362623SN/Abool 2372623SN/ALTAGE::getLoop(Addr pc, BranchInfo* bi) const 2382623SN/A{ 2393512Sktlim@umich.edu bi->loopHit = -1; 2403512Sktlim@umich.edu bi->loopPredValid = false; 2413512Sktlim@umich.edu bi->loopIndex = lindex(pc); 2422623SN/A bi->loopTag = ((pc) >> (logSizeLoopPred - 2)); 2432623SN/A 2442623SN/A for (int i = 0; i < 4; i++) { 2452623SN/A if (ltable[bi->loopIndex + i].tag == bi->loopTag) { 2462623SN/A bi->loopHit = i; 2472623SN/A bi->loopPredValid = (ltable[bi->loopIndex + i].confidence >= 3); 2482623SN/A bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec; 2492683Sktlim@umich.edu if (ltable[bi->loopIndex + i].currentIterSpec + 1 == 2502623SN/A ltable[bi->loopIndex + i].numIter) { 2512623SN/A return !(ltable[bi->loopIndex + i].dir); 2522623SN/A }else { 2532623SN/A return (ltable[bi->loopIndex + i].dir); 2542623SN/A } 2553686Sktlim@umich.edu } 2563430Sgblack@eecs.umich.edu } 2573495Sktlim@umich.edu return false; 2582623SN/A} 2592623SN/A 2602623SN/Avoid 2612623SN/ALTAGE::specLoopUpdate(Addr pc, bool taken, BranchInfo* bi) 2622623SN/A{ 2632623SN/A if (bi->loopHit>=0) { 2642623SN/A int index = lindex(pc); 2652623SN/A if (taken != ltable[index].dir) { 2662683Sktlim@umich.edu ltable[index].currentIterSpec = 0; 2672623SN/A } else { 2682623SN/A ltable[index].currentIterSpec++; 2692626SN/A } 2702626SN/A } 2712626SN/A} 2722626SN/A 2732626SN/Avoid 2742623SN/ALTAGE::loopUpdate(Addr pc, bool taken, BranchInfo* bi) 2752623SN/A{ 2762623SN/A int idx = bi->loopIndex + bi->loopHit; 2772623SN/A if (bi->loopHit >= 0) { 2782623SN/A //already a hit 2792623SN/A if (bi->loopPredValid) { 2802623SN/A if (taken != bi->loopPred) { 2812623SN/A // free the entry 2822623SN/A ltable[idx].numIter = 0; 2832623SN/A ltable[idx].age = 0; 2843169Sstever@eecs.umich.edu ltable[idx].confidence = 0; 2853169Sstever@eecs.umich.edu ltable[idx].currentIter = 0; 2863349Sbinkertn@umich.edu return; 2873169Sstever@eecs.umich.edu } else if (bi->loopPred != bi->tagePred) { 2883169Sstever@eecs.umich.edu DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); 2892623SN/A if (ltable[idx].age < 7) 2902623SN/A ltable[idx].age++; 2912623SN/A } 2922623SN/A } 2932623SN/A 2942623SN/A ltable[idx].currentIter++; 2953169Sstever@eecs.umich.edu if (ltable[idx].currentIter > ltable[idx].numIter) { 2962623SN/A ltable[idx].confidence = 0; 2972623SN/A if (ltable[idx].numIter != 0) { 2982623SN/A // free the entry 2993169Sstever@eecs.umich.edu ltable[idx].numIter = 0; 3002623SN/A ltable[idx].age = 0; 3013806Ssaidi@eecs.umich.edu ltable[idx].confidence = 0; 3023806Ssaidi@eecs.umich.edu } 3033806Ssaidi@eecs.umich.edu } 3043806Ssaidi@eecs.umich.edu 3052623SN/A if (taken != ltable[idx].dir) { 3063814Ssaidi@eecs.umich.edu if (ltable[idx].currentIter == ltable[idx].numIter) { 3073814Ssaidi@eecs.umich.edu DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); 3083814Ssaidi@eecs.umich.edu 3093814Ssaidi@eecs.umich.edu if (ltable[idx].confidence < 7) { 3103814Ssaidi@eecs.umich.edu ltable[idx].confidence++; 3113169Sstever@eecs.umich.edu } 3123170Sstever@eecs.umich.edu //just do not predict when the loop count is 1 or 2 3133170Sstever@eecs.umich.edu if (ltable[idx].numIter < 3) { 3143170Sstever@eecs.umich.edu // free the entry 3153170Sstever@eecs.umich.edu ltable[idx].dir = taken; 3162623SN/A ltable[idx].numIter = 0; 3172623SN/A ltable[idx].age = 0; 3182623SN/A ltable[idx].confidence = 0; 3193172Sstever@eecs.umich.edu } 3202623SN/A } else { 3212623SN/A DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); 3222623SN/A if (ltable[idx].numIter == 0) { 3232623SN/A // first complete nest; 3242623SN/A ltable[idx].confidence = 0; 3252623SN/A ltable[idx].numIter = ltable[idx].currentIter; 3262623SN/A } else { 3272623SN/A //not the same number of iterations as last time: free the 3282623SN/A //entry 3294115Ssaidi@eecs.umich.edu ltable[idx].numIter = 0; 3304115Ssaidi@eecs.umich.edu ltable[idx].age = 0; 3314115Ssaidi@eecs.umich.edu ltable[idx].confidence = 0; 3324115Ssaidi@eecs.umich.edu } 3334040Ssaidi@eecs.umich.edu } 3344040Ssaidi@eecs.umich.edu ltable[idx].currentIter = 0; 3354040Ssaidi@eecs.umich.edu } 3364040Ssaidi@eecs.umich.edu 3372623SN/A } else if (taken) { 3382623SN/A //try to allocate an entry on taken branch 3392623SN/A int nrand = random_mt.random<int>(); 3402623SN/A for (int i = 0; i < 4; i++) { 3412623SN/A int loop_hit = (nrand + i) & 3; 3422623SN/A idx = bi->loopIndex + loop_hit; 3432623SN/A if (ltable[idx].age == 0) { 3442623SN/A DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n", 3452623SN/A pc); 3462623SN/A ltable[idx].dir = !taken; 3472623SN/A ltable[idx].tag = bi->loopTag; 3482623SN/A ltable[idx].numIter = 0; 3492623SN/A ltable[idx].age = 7; 3502623SN/A ltable[idx].confidence = 0; 3512623SN/A ltable[idx].currentIter = 1; 3522623SN/A break; 3532623SN/A 3542623SN/A } 3552623SN/A else 3562623SN/A ltable[idx].age--; 3572623SN/A } 3582623SN/A } 3592623SN/A 3602623SN/A} 3612623SN/A 3622623SN/A// shifting the global history: we manage the history in a big table in order 3632623SN/A// to reduce simulation time 3642623SN/Avoid 3652623SN/ALTAGE::updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &pt) 3662623SN/A{ 3672623SN/A if (pt == 0) { 3682623SN/A DPRINTF(LTage, "Rolling over the histories\n"); 3692623SN/A // Copy beginning of globalHistoryBuffer to end, such that 3702623SN/A // the last maxHist outcomes are still reachable 3712623SN/A // through pt[0 .. maxHist - 1]. 3722623SN/A for (int i = 0; i < maxHist; i++) 3732623SN/A tab[histBufferSize - maxHist + i] = tab[i]; 3742623SN/A pt = histBufferSize - maxHist; 3752623SN/A h = &tab[pt]; 3762623SN/A } 3772623SN/A pt--; 3782623SN/A h--; 3792623SN/A h[0] = (dir) ? 1 : 0; 3803169Sstever@eecs.umich.edu} 3813169Sstever@eecs.umich.edu 3824040Ssaidi@eecs.umich.edu// Get GHR for hashing indirect predictor 3833169Sstever@eecs.umich.edu// Build history backwards from pointer in 3843169Sstever@eecs.umich.edu// bp_history. 3852623SN/Aunsigned 3864040Ssaidi@eecs.umich.eduLTAGE::getGHR(ThreadID tid, void *bp_history) const 3874040Ssaidi@eecs.umich.edu{ 3884040Ssaidi@eecs.umich.edu BranchInfo* bi = static_cast<BranchInfo*>(bp_history); 3894040Ssaidi@eecs.umich.edu unsigned val = 0; 3904040Ssaidi@eecs.umich.edu for (unsigned i = 0; i < 32; i++) { 3912623SN/A // Make sure we don't go out of bounds 3922623SN/A int gh_offset = bi->ptGhist + i; 3932623SN/A assert(&(threadHistory[tid].globalHistory[gh_offset]) < 3942623SN/A threadHistory[tid].globalHistory + histBufferSize); 3952623SN/A val |= ((threadHistory[tid].globalHistory[gh_offset] & 0x1) << i); 3963169Sstever@eecs.umich.edu } 3972623SN/A 3982623SN/A return val; 3992623SN/A} 4003170Sstever@eecs.umich.edu 4012623SN/A//prediction 4023170Sstever@eecs.umich.edubool 4033170Sstever@eecs.umich.eduLTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) 4043170Sstever@eecs.umich.edu{ 4054040Ssaidi@eecs.umich.edu BranchInfo *bi = new BranchInfo(nHistoryTables+1); 4064040Ssaidi@eecs.umich.edu b = (void*)(bi); 4074040Ssaidi@eecs.umich.edu Addr pc = branch_pc; 4084040Ssaidi@eecs.umich.edu bool pred_taken = true; 4094040Ssaidi@eecs.umich.edu bi->loopHit = -1; 4102623SN/A 4113170Sstever@eecs.umich.edu if (cond_branch) { 4123170Sstever@eecs.umich.edu // TAGE prediction 4133170Sstever@eecs.umich.edu 4142631SN/A // computes the table addresses and the partial tags 4153806Ssaidi@eecs.umich.edu for (int i = 1; i <= nHistoryTables; i++) { 4163806Ssaidi@eecs.umich.edu tableIndices[i] = gindex(tid, pc, i); 4173806Ssaidi@eecs.umich.edu bi->tableIndices[i] = tableIndices[i]; 4183806Ssaidi@eecs.umich.edu tableTags[i] = gtag(tid, pc, i); 4193806Ssaidi@eecs.umich.edu bi->tableTags[i] = tableTags[i]; 4203806Ssaidi@eecs.umich.edu } 4213170Sstever@eecs.umich.edu 4223170Sstever@eecs.umich.edu bi->bimodalIndex = bindex(pc); 4233814Ssaidi@eecs.umich.edu 4243814Ssaidi@eecs.umich.edu bi->hitBank = 0; 4253814Ssaidi@eecs.umich.edu bi->altBank = 0; 4263814Ssaidi@eecs.umich.edu //Look for the bank with longest matching history 4273814Ssaidi@eecs.umich.edu for (int i = nHistoryTables; i > 0; i--) { 4283170Sstever@eecs.umich.edu if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 4293170Sstever@eecs.umich.edu bi->hitBank = i; 4304040Ssaidi@eecs.umich.edu bi->hitBankIndex = tableIndices[bi->hitBank]; 4314040Ssaidi@eecs.umich.edu break; 4324040Ssaidi@eecs.umich.edu } 4334050Ssaidi@eecs.umich.edu } 4344052Ssaidi@eecs.umich.edu //Look for the alternate bank 4352631SN/A for (int i = bi->hitBank - 1; i > 0; i--) { 4362623SN/A if (gtable[i][tableIndices[i]].tag == tableTags[i]) { 4372623SN/A bi->altBank = i; 4382623SN/A bi->altBankIndex = tableIndices[bi->altBank]; 4393172Sstever@eecs.umich.edu break; 4402623SN/A } 4412623SN/A } 4422623SN/A //computes the prediction and the alternate prediction 4432623SN/A if (bi->hitBank > 0) { 4442623SN/A if (bi->altBank > 0) { 4452623SN/A bi->altTaken = 4462623SN/A gtable[bi->altBank][tableIndices[bi->altBank]].ctr >= 0; 4472623SN/A }else { 4482623SN/A bi->altTaken = getBimodePred(pc, bi); 4494224Sgblack@eecs.umich.edu } 4504224Sgblack@eecs.umich.edu 4514224Sgblack@eecs.umich.edu bi->longestMatchPred = 4524224Sgblack@eecs.umich.edu gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr >= 0; 4534224Sgblack@eecs.umich.edu bi->pseudoNewAlloc = 4544224Sgblack@eecs.umich.edu abs(2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) <= 1; 4554224Sgblack@eecs.umich.edu 4564224Sgblack@eecs.umich.edu //if the entry is recognized as a newly allocated entry and 4574224Sgblack@eecs.umich.edu //useAltPredForNewlyAllocated is positive use the alternate 4584224Sgblack@eecs.umich.edu //prediction 4594224Sgblack@eecs.umich.edu if ((useAltPredForNewlyAllocated < 0) 4602623SN/A || abs(2 * 4612623SN/A gtable[bi->hitBank][tableIndices[bi->hitBank]].ctr + 1) > 1) 4622623SN/A bi->tagePred = bi->longestMatchPred; 4632623SN/A else 4642623SN/A bi->tagePred = bi->altTaken; 4652623SN/A } else { 4662623SN/A bi->altTaken = getBimodePred(pc, bi); 4672623SN/A bi->tagePred = bi->altTaken; 4682623SN/A bi->longestMatchPred = bi->altTaken; 4692623SN/A } 4702623SN/A //end TAGE prediction 4712623SN/A 4722623SN/A bi->loopPred = getLoop(pc, bi); // loop prediction 4732623SN/A 4742623SN/A pred_taken = (((loopUseCounter >= 0) && bi->loopPredValid)) ? 4752623SN/A (bi->loopPred): (bi->tagePred); 4762623SN/A DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, " 4772623SN/A "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n", 4782623SN/A branch_pc, pred_taken, bi->loopPred, bi->loopPredValid, 4792623SN/A loopUseCounter, bi->tagePred, bi->altTaken); 4802623SN/A } 4812623SN/A bi->branchPC = branch_pc; 4822623SN/A bi->condBranch = cond_branch; 4832623SN/A specLoopUpdate(branch_pc, pred_taken, bi); 4842623SN/A return pred_taken; 4852623SN/A} 4862623SN/A 4872623SN/A// PREDICTOR UPDATE 4882623SN/Avoid 4892623SN/ALTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, 4902623SN/A bool squashed) 4912623SN/A{ 4922623SN/A assert(bp_history); 4932623SN/A 4942623SN/A BranchInfo *bi = static_cast<BranchInfo*>(bp_history); 4952623SN/A 4962623SN/A if (squashed) { 4972623SN/A // This restores the global history, then update it 4982623SN/A // and recomputes the folded histories. 4992623SN/A squash(tid, taken, bp_history); 5002623SN/A return; 5012623SN/A } 5022623SN/A 5032623SN/A int nrand = random_mt.random<int>(0,3); 5042623SN/A Addr pc = branch_pc; 5052623SN/A if (bi->condBranch) { 5062623SN/A DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n", 5072623SN/A branch_pc, taken); 5082623SN/A // first update the loop predictor 5092623SN/A loopUpdate(pc, taken, bi); 5102623SN/A 5112623SN/A if (bi->loopPredValid) { 5122623SN/A if (bi->tagePred != bi->loopPred) { 5133387Sgblack@eecs.umich.edu ctrUpdate(loopUseCounter, (bi->loopPred== taken), 7); 5143387Sgblack@eecs.umich.edu } 5152626SN/A } 5162662Sstever@eecs.umich.edu 5172623SN/A // TAGE UPDATE 5182623SN/A // try to allocate a new entries only if prediction was wrong 5194182Sgblack@eecs.umich.edu bool longest_match_pred = false; 5204182Sgblack@eecs.umich.edu bool alloc = (bi->tagePred != taken) && (bi->hitBank < nHistoryTables); 5214182Sgblack@eecs.umich.edu if (bi->hitBank > 0) { 5222662Sstever@eecs.umich.edu // Manage the selection between longest matching and alternate 5234182Sgblack@eecs.umich.edu // matching for "pseudo"-newly allocated longest matching entry 5244593Sgblack@eecs.umich.edu longest_match_pred = bi->longestMatchPred; 5254593Sgblack@eecs.umich.edu bool PseudoNewAlloc = bi->pseudoNewAlloc; 5264182Sgblack@eecs.umich.edu // an entry is considered as newly allocated if its prediction 5274182Sgblack@eecs.umich.edu // counter is weak 5282623SN/A if (PseudoNewAlloc) { 5294182Sgblack@eecs.umich.edu if (longest_match_pred == taken) { 5304182Sgblack@eecs.umich.edu alloc = false; 5314182Sgblack@eecs.umich.edu } 5324593Sgblack@eecs.umich.edu // if it was delivering the correct prediction, no need to 5334182Sgblack@eecs.umich.edu // allocate new entry even if the overall prediction was false 5342623SN/A if (longest_match_pred != bi->altTaken) { 5353814Ssaidi@eecs.umich.edu ctrUpdate(useAltPredForNewlyAllocated, 5364182Sgblack@eecs.umich.edu bi->altTaken == taken, 4); 5374182Sgblack@eecs.umich.edu } 5384182Sgblack@eecs.umich.edu } 5394182Sgblack@eecs.umich.edu } 5404182Sgblack@eecs.umich.edu 5412623SN/A if (alloc) { 5423814Ssaidi@eecs.umich.edu // is there some "unuseful" entry to allocate 5434539Sgblack@eecs.umich.edu int8_t min = 1; 5444539Sgblack@eecs.umich.edu for (int i = nHistoryTables; i > bi->hitBank; i--) { 5453814Ssaidi@eecs.umich.edu if (gtable[i][bi->tableIndices[i]].u < min) { 5463814Ssaidi@eecs.umich.edu min = gtable[i][bi->tableIndices[i]].u; 5472623SN/A } 5484182Sgblack@eecs.umich.edu } 5494182Sgblack@eecs.umich.edu 5502623SN/A // we allocate an entry with a longer history 5512662Sstever@eecs.umich.edu // to avoid ping-pong, we do not choose systematically the next 5522803Ssaidi@eecs.umich.edu // entry, but among the 3 next entries 5532803Ssaidi@eecs.umich.edu int Y = nrand & 5542803Ssaidi@eecs.umich.edu ((ULL(1) << (nHistoryTables - bi->hitBank - 1)) - 1); 5552803Ssaidi@eecs.umich.edu int X = bi->hitBank + 1; 5562803Ssaidi@eecs.umich.edu if (Y & 1) { 5572623SN/A X++; 5582623SN/A if (Y & 2) 5592623SN/A X++; 5604377Sgblack@eecs.umich.edu } 5614182Sgblack@eecs.umich.edu // No entry available, forces one to be available 5622623SN/A if (min > 0) { 5632623SN/A gtable[X][bi->tableIndices[X]].u = 0; 5642626SN/A } 5652626SN/A 5662623SN/A 5672623SN/A //Allocate only one entry 5682623SN/A for (int i = X; i <= nHistoryTables; i++) { 5692623SN/A if ((gtable[i][bi->tableIndices[i]].u == 0)) { 5702623SN/A gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; 5712623SN/A gtable[i][bi->tableIndices[i]].ctr = (taken) ? 0 : -1; 5722623SN/A gtable[i][bi->tableIndices[i]].u = 0; //? 5734762Snate@binkert.org } 5744762Snate@binkert.org } 5752623SN/A } 5762623SN/A //periodic reset of u: reset is not complete but bit by bit 5774762Snate@binkert.org tCounter++; 5782623SN/A if ((tCounter & ((ULL(1) << logTick) - 1)) == 0) { 5792623SN/A // reset least significant bit 5802623SN/A // most significant bit becomes least significant bit 5812623SN/A for (int i = 1; i <= nHistoryTables; i++) { 5822623SN/A for (int j = 0; j < (ULL(1) << tagTableSizes[i]); j++) { 5833119Sktlim@umich.edu gtable[i][j].u = gtable[i][j].u >> 1; 5842623SN/A } 5853661Srdreslin@umich.edu } 5862623SN/A } 5872623SN/A 5882623SN/A if (bi->hitBank > 0) { 5892623SN/A DPRINTF(LTage, "Updating tag table entry (%d,%d) for branch %lx\n", 5902623SN/A bi->hitBank, bi->hitBankIndex, branch_pc); 5912901Ssaidi@eecs.umich.edu ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, 5923170Sstever@eecs.umich.edu tagTableCounterBits); 5932623SN/A // if the provider entry is not certified to be useful also update 5942623SN/A // the alternate prediction 5952623SN/A if (gtable[bi->hitBank][bi->hitBankIndex].u == 0) { 5962623SN/A if (bi->altBank > 0) { 5972623SN/A ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, 5983617Sbinkertn@umich.edu tagTableCounterBits); 5993617Sbinkertn@umich.edu DPRINTF(LTage, "Updating tag table entry (%d,%d) for" 6003617Sbinkertn@umich.edu " branch %lx\n", bi->hitBank, bi->hitBankIndex, 6012623SN/A branch_pc); 6024762Snate@binkert.org } 6034762Snate@binkert.org if (bi->altBank == 0) { 6044762Snate@binkert.org baseUpdate(pc, taken, bi); 6052623SN/A } 6062623SN/A } 6072623SN/A 6082623SN/A // update the u counter 6092623SN/A if (longest_match_pred != bi->altTaken) { 610 if (longest_match_pred == taken) { 611 if (gtable[bi->hitBank][bi->hitBankIndex].u < 1) { 612 gtable[bi->hitBank][bi->hitBankIndex].u++; 613 } 614 } 615 } 616 } else { 617 baseUpdate(pc, taken, bi); 618 } 619 620 //END PREDICTOR UPDATE 621 } 622 if (!squashed) { 623 delete bi; 624 } 625} 626 627void 628LTAGE::updateHistories(ThreadID tid, Addr branch_pc, bool taken, void* b) 629{ 630 BranchInfo* bi = (BranchInfo*)(b); 631 ThreadHistory& tHist = threadHistory[tid]; 632 // UPDATE HISTORIES 633 bool pathbit = ((branch_pc) & 1); 634 //on a squash, return pointers to this and recompute indices. 635 //update user history 636 updateGHist(tHist.gHist, taken, tHist.globalHistory, tHist.ptGhist); 637 tHist.pathHist = (tHist.pathHist << 1) + pathbit; 638 tHist.pathHist = (tHist.pathHist & ((ULL(1) << 16) - 1)); 639 640 bi->ptGhist = tHist.ptGhist; 641 bi->pathHist = tHist.pathHist; 642 //prepare next index and tag computations for user branchs 643 for (int i = 1; i <= nHistoryTables; i++) 644 { 645 bi->ci[i] = tHist.computeIndices[i].comp; 646 bi->ct0[i] = tHist.computeTags[0][i].comp; 647 bi->ct1[i] = tHist.computeTags[1][i].comp; 648 tHist.computeIndices[i].update(tHist.gHist); 649 tHist.computeTags[0][i].update(tHist.gHist); 650 tHist.computeTags[1][i].update(tHist.gHist); 651 } 652 DPRINTF(LTage, "Updating global histories with branch:%lx; taken?:%d, " 653 "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist, 654 tHist.ptGhist); 655} 656 657void 658LTAGE::squash(ThreadID tid, bool taken, void *bp_history) 659{ 660 BranchInfo* bi = (BranchInfo*)(bp_history); 661 ThreadHistory& tHist = threadHistory[tid]; 662 DPRINTF(LTage, "Restoring branch info: %lx; taken? %d; PathHistory:%x, " 663 "pointer:%d\n", bi->branchPC,taken, bi->pathHist, bi->ptGhist); 664 tHist.pathHist = bi->pathHist; 665 tHist.ptGhist = bi->ptGhist; 666 tHist.gHist = &(tHist.globalHistory[tHist.ptGhist]); 667 tHist.gHist[0] = (taken ? 1 : 0); 668 for (int i = 1; i <= nHistoryTables; i++) { 669 tHist.computeIndices[i].comp = bi->ci[i]; 670 tHist.computeTags[0][i].comp = bi->ct0[i]; 671 tHist.computeTags[1][i].comp = bi->ct1[i]; 672 tHist.computeIndices[i].update(tHist.gHist); 673 tHist.computeTags[0][i].update(tHist.gHist); 674 tHist.computeTags[1][i].update(tHist.gHist); 675 } 676 677 if (bi->condBranch) { 678 if (bi->loopHit >= 0) { 679 int idx = bi->loopIndex + bi->loopHit; 680 ltable[idx].currentIterSpec = bi->currentIter; 681 } 682 } 683 684} 685 686void 687LTAGE::squash(ThreadID tid, void *bp_history) 688{ 689 BranchInfo* bi = (BranchInfo*)(bp_history); 690 DPRINTF(LTage, "Deleting branch info: %lx\n", bi->branchPC); 691 if (bi->condBranch) { 692 if (bi->loopHit >= 0) { 693 int idx = bi->loopIndex + bi->loopHit; 694 ltable[idx].currentIterSpec = bi->currentIter; 695 } 696 } 697 698 delete bi; 699} 700 701bool 702LTAGE::lookup(ThreadID tid, Addr branch_pc, void* &bp_history) 703{ 704 bool retval = predict(tid, branch_pc, true, bp_history); 705 706 DPRINTF(LTage, "Lookup branch: %lx; predict:%d\n", branch_pc, retval); 707 updateHistories(tid, branch_pc, retval, bp_history); 708 assert(threadHistory[tid].gHist == 709 &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 710 711 return retval; 712} 713 714void 715LTAGE::btbUpdate(ThreadID tid, Addr branch_pc, void* &bp_history) 716{ 717 BranchInfo* bi = (BranchInfo*) bp_history; 718 ThreadHistory& tHist = threadHistory[tid]; 719 DPRINTF(LTage, "BTB miss resets prediction: %lx\n", branch_pc); 720 assert(tHist.gHist == &tHist.globalHistory[tHist.ptGhist]); 721 tHist.gHist[0] = 0; 722 for (int i = 1; i <= nHistoryTables; i++) { 723 tHist.computeIndices[i].comp = bi->ci[i]; 724 tHist.computeTags[0][i].comp = bi->ct0[i]; 725 tHist.computeTags[1][i].comp = bi->ct1[i]; 726 tHist.computeIndices[i].update(tHist.gHist); 727 tHist.computeTags[0][i].update(tHist.gHist); 728 tHist.computeTags[1][i].update(tHist.gHist); 729 } 730} 731 732void 733LTAGE::uncondBranch(ThreadID tid, Addr br_pc, void* &bp_history) 734{ 735 DPRINTF(LTage, "UnConditionalBranch: %lx\n", br_pc); 736 predict(tid, br_pc, false, bp_history); 737 updateHistories(tid, br_pc, true, bp_history); 738 assert(threadHistory[tid].gHist == 739 &threadHistory[tid].globalHistory[threadHistory[tid].ptGhist]); 740} 741 742LTAGE* 743LTAGEParams::create() 744{ 745 return new LTAGE(this); 746} 747