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