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