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 * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec)
40 */
41
42#include "cpu/pred/tage_sc_l_64KB.hh"
43
44TAGE_SC_L_64KB_StatisticalCorrector::TAGE_SC_L_64KB_StatisticalCorrector(
45    TAGE_SC_L_64KB_StatisticalCorrectorParams *p)
46  : StatisticalCorrector(p),
47    numEntriesSecondLocalHistories(p->numEntriesSecondLocalHistories),
48    numEntriesThirdLocalHistories(p->numEntriesThirdLocalHistories),
49    pnb(p->pnb),
50    logPnb(p->logPnb),
51    pm(p->pm),
52    snb(p->snb),
53    logSnb(p->logSnb),
54    sm(p->sm),
55    tnb(p->tnb),
56    logTnb(p->logTnb),
57    tm(p->tm),
58    imnb(p->imnb),
59    logImnb(p->logImnb),
60    imm(p->imm)
61{
62    initGEHLTable(pnb, pm, pgehl, logPnb, wp, 7);
63    initGEHLTable(snb, sm, sgehl, logSnb, ws, 7);
64    initGEHLTable(tnb, tm, tgehl, logTnb, wt, 7);
65    initGEHLTable(imnb, imm, imgehl, logImnb, wim, 0);
66
67}
68
69TAGE_SC_L_64KB_StatisticalCorrector::SCThreadHistory*
70TAGE_SC_L_64KB_StatisticalCorrector::makeThreadHistory()
71{
72    SC_64KB_ThreadHistory *sh = new SC_64KB_ThreadHistory();
73
74    sh->setNumOrdinalHistories(3);
75    sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2);
76    sh->initLocalHistory(2, numEntriesSecondLocalHistories, 5);
77    sh->initLocalHistory(3, numEntriesThirdLocalHistories, logTnb);
78
79    sh->imHist.resize(1 << im[0]);
80    return sh;
81}
82
83unsigned
84TAGE_SC_L_64KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc,
85        BranchInfo* bi, int hitBank, int altBank) const
86{
87    return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) +
88            (bi->lowConf <<2) + ((altBank!=0)<<3) +
89            ((branch_pc^(branch_pc>>2))<<7)) & ((1<<logBias) -1);
90}
91
92int
93TAGE_SC_L_64KB_StatisticalCorrector::gPredictions(ThreadID tid, Addr branch_pc,
94        BranchInfo* bi, int & lsum, int64_t pathHist)
95{
96    SC_64KB_ThreadHistory *sh =
97        static_cast<SC_64KB_ThreadHistory *>(scHistory);
98
99    lsum += gPredict(
100        (branch_pc << 1) + bi->predBeforeSC, sh->bwHist, bwm,
101        bwgehl, bwnb, logBwnb, wbw);
102
103    lsum += gPredict(
104        branch_pc, pathHist, pm, pgehl, pnb, logPnb, wp);
105
106    lsum += gPredict(
107        branch_pc, sh->getLocalHistory(1, branch_pc), lm,
108        lgehl, lnb, logLnb, wl);
109
110    lsum += gPredict(
111        branch_pc, sh->getLocalHistory(2, branch_pc), sm,
112        sgehl, snb, logSnb, ws);
113
114    lsum += gPredict(
115        branch_pc, sh->getLocalHistory(3, branch_pc), tm,
116        tgehl, tnb, logTnb, wt);
117
118    lsum += gPredict(
119        branch_pc, sh->imHist[scHistory->imliCount], imm,
120        imgehl, imnb, logImnb, wim);
121
122    lsum += gPredict(
123        branch_pc, sh->imliCount, im, igehl, inb, logInb, wi);
124
125    int thres = (updateThreshold>>3) + pUpdateThreshold[getIndUpd(branch_pc)]
126      + 12*((wb[getIndUpds(branch_pc)] >= 0) + (wp[getIndUpds(branch_pc)] >= 0)
127      + (ws[getIndUpds(branch_pc)] >= 0) + (wt[getIndUpds(branch_pc)] >= 0)
128      + (wl[getIndUpds(branch_pc)] >= 0) + (wbw[getIndUpds(branch_pc)] >= 0)
129      + (wi[getIndUpds(branch_pc)] >= 0));
130
131    return thres;
132}
133
134int
135TAGE_SC_L_64KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
136{
137    return (i >= (nbr - 2)) ? 1 : 0;
138}
139
140void
141TAGE_SC_L_64KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc,
142        const StaticInstPtr &inst, bool taken, BranchInfo* tage_bi,
143        Addr corrTarget)
144{
145    int brtype = inst->isDirectCtrl() ? 0 : 2;
146    if (! inst->isUncondCtrl()) {
147        ++brtype;
148    }
149    // Non speculative SC histories update
150    if (brtype & 1) {
151        SC_64KB_ThreadHistory *sh =
152            static_cast<SC_64KB_ThreadHistory *>(scHistory);
153        int64_t imliCount = sh->imliCount;
154        sh->imHist[imliCount] = (sh->imHist[imliCount] << 1)
155                                + taken;
156        sh->updateLocalHistory(2, branch_pc, taken, branch_pc & 15);
157        sh->updateLocalHistory(3, branch_pc, taken);
158    }
159
160    StatisticalCorrector::scHistoryUpdate(branch_pc, inst, taken, tage_bi,
161                                          corrTarget);
162}
163
164void
165TAGE_SC_L_64KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc,
166        bool taken, BranchInfo* bi, int64_t phist)
167{
168    SC_64KB_ThreadHistory *sh =
169        static_cast<SC_64KB_ThreadHistory *>(scHistory);
170
171    gUpdate((pc << 1) + bi->predBeforeSC, taken, sh->bwHist, bwm,
172            bwgehl, bwnb, logBwnb, wbw, bi);
173
174    gUpdate(pc, taken, phist, pm,
175            pgehl, pnb, logPnb, wp, bi);
176
177    gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm,
178            lgehl, lnb, logLnb, wl, bi);
179
180    gUpdate(pc, taken, sh->getLocalHistory(2, pc), sm,
181            sgehl, snb, logSnb, ws, bi);
182
183    gUpdate(pc, taken, sh->getLocalHistory(3, pc), tm,
184            tgehl, tnb, logTnb, wt, bi);
185
186    gUpdate(pc, taken, sh->imHist[scHistory->imliCount], imm,
187            imgehl, imnb, logImnb, wim, bi);
188
189    gUpdate(pc, taken, sh->imliCount, im,
190            igehl, inb, logInb, wi, bi);
191}
192
193TAGE_SC_L_64KB_StatisticalCorrector*
194TAGE_SC_L_64KB_StatisticalCorrectorParams::create()
195{
196    return new TAGE_SC_L_64KB_StatisticalCorrector(this);
197}
198
199int
200TAGE_SC_L_TAGE_64KB::gindex_ext(int index, int bank) const
201{
202    return index;
203}
204
205uint16_t
206TAGE_SC_L_TAGE_64KB::gtag(ThreadID tid, Addr pc, int bank) const
207{
208    // very similar to the TAGE implementation, but w/o shifting the pc
209    int tag = pc ^ threadHistory[tid].computeTags[0][bank].comp ^
210              (threadHistory[tid].computeTags[1][bank].comp << 1);
211
212    return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1));
213}
214
215void
216TAGE_SC_L_TAGE_64KB::handleAllocAndUReset(
217    bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
218{
219    if (! alloc) {
220        return;
221    }
222
223    int penalty = 0;
224    int numAllocated = 0;
225    bool maxAllocReached = false;
226
227    for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
228        // Handle the 2-way associativity for allocation
229        for (int j = 0; j < 2; ++j) {
230            int i = ((j == 0) ? I : (I ^ 1)) + 1;
231            if (noSkip[i]) {
232                if (gtable[i][bi->tableIndices[i]].u == 0) {
233                    int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
234                    if (abs (2 * ctr + 1) <= 3) {
235                        gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
236                        gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
237                        numAllocated++;
238                        maxAllocReached = (numAllocated == maxNumAlloc);
239                        I += 2;
240                        break;
241                    } else {
242                        if (gtable[i][bi->tableIndices[i]].ctr > 0) {
243                            gtable[i][bi->tableIndices[i]].ctr--;
244                        } else {
245                            gtable[i][bi->tableIndices[i]].ctr++;
246                        }
247                    }
248                } else {
249                    penalty++;
250                }
251            }
252        }
253        if (maxAllocReached) {
254            break;
255        }
256    }
257
258    tCounter += (penalty - 2 * numAllocated);
259
260    handleUReset();
261}
262
263void
264TAGE_SC_L_TAGE_64KB::handleTAGEUpdate(Addr branch_pc, bool taken,
265                                 TAGEBase::BranchInfo* bi)
266{
267    if (bi->hitBank > 0) {
268        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
269            if (bi->longestMatchPred != taken) {
270                // acts as a protection
271                if (bi->altBank > 0) {
272                    ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
273                              tagTableCounterBits);
274                }
275                if (bi->altBank == 0){
276                    baseUpdate(branch_pc, taken, bi);
277                }
278            }
279        }
280
281        ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
282                  tagTableCounterBits);
283
284        //sign changes: no way it can have been useful
285        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
286            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
287        }
288
289        if (bi->altTaken == taken) {
290            if (bi->altBank > 0) {
291                int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
292                if (abs (2 * ctr + 1) == 7) {
293                    if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
294                        if (bi->longestMatchPred == taken) {
295                          gtable[bi->hitBank][bi->hitBankIndex].u = 0;
296                        }
297                    }
298                }
299            }
300        }
301    } else {
302        baseUpdate(branch_pc, taken, bi);
303    }
304
305    if ((bi->longestMatchPred != bi->altTaken) &&
306        (bi->longestMatchPred == taken) &&
307        (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
308            gtable[bi->hitBank][bi->hitBankIndex].u++;
309    }
310}
311
312TAGE_SC_L_TAGE_64KB*
313TAGE_SC_L_TAGE_64KBParams::create()
314{
315    return new TAGE_SC_L_TAGE_64KB(this);
316}
317
318TAGE_SC_L_64KB::TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params)
319  : TAGE_SC_L(params)
320{
321}
322
323TAGE_SC_L_64KB*
324TAGE_SC_L_64KBParams::create()
325{
326    return new TAGE_SC_L_64KB(this);
327}
328