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 * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec)
40 */
41
42#include "cpu/pred/tage_sc_l_8KB.hh"
43
44#include "base/random.hh"
45#include "debug/TageSCL.hh"
46
47TAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector(
48    TAGE_SC_L_8KB_StatisticalCorrectorParams *p)
49  : StatisticalCorrector(p),
50    gnb(p->gnb),
51    logGnb(p->logGnb),
52    gm(p->gm)
53{
54    initGEHLTable(gnb, gm, ggehl, logGnb, wg, 7);
55}
56
57TAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory *
58TAGE_SC_L_8KB_StatisticalCorrector::makeThreadHistory()
59{
60    SC_8KB_ThreadHistory *sh = new SC_8KB_ThreadHistory();
61    sh->setNumOrdinalHistories(1);
62    sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2);
63    return sh;
64}
65
66unsigned
67TAGE_SC_L_8KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc,
68        BranchInfo* bi, int hitBank, int altBank) const
69{
70    return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) +
71            (bi->lowConf <<2) +((altBank!=0)<<3)) & ((1<<logBias) -1);
72}
73
74int
75TAGE_SC_L_8KB_StatisticalCorrector::gPredictions(
76    ThreadID tid, Addr branch_pc, BranchInfo* bi, int & lsum, int64_t phist)
77{
78    SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
79    lsum += gPredict(
80        branch_pc, sh->globalHist, gm, ggehl, gnb, logGnb, wg);
81
82    lsum += gPredict(
83        branch_pc, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw);
84
85    // only 1 local history here
86    lsum += gPredict(
87        branch_pc, sh->getLocalHistory(1, branch_pc), lm,
88        lgehl, lnb, logLnb, wl);
89
90    lsum += gPredict(
91        branch_pc, sh->imliCount, im, igehl, inb, logInb, wi);
92
93    int thres = (updateThreshold>>3)+pUpdateThreshold[getIndUpd(branch_pc)];
94
95    return thres;
96}
97
98int TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
99{
100    return 0;
101}
102
103void
104TAGE_SC_L_8KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc,
105    const StaticInstPtr &inst, bool taken, BranchInfo *tage_bi,
106    Addr corrTarget)
107{
108    int brtype = inst->isDirectCtrl() ? 0 : 2;
109    if (! inst->isUncondCtrl()) {
110        ++brtype;
111    }
112    // Non speculative SC histories update
113    if (brtype & 1) {
114        SC_8KB_ThreadHistory *sh =
115            static_cast<SC_8KB_ThreadHistory *>(scHistory);
116        sh->globalHist = (sh->globalHist << 1) + taken;
117    }
118
119    StatisticalCorrector::scHistoryUpdate(branch_pc, inst, taken, tage_bi,
120                                          corrTarget);
121}
122
123void
124TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken,
125        BranchInfo* bi, int64_t phist)
126{
127    SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
128    gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi);
129    gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi);
130    gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl,
131            bi);
132    gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi);
133}
134
135TAGE_SC_L_8KB_StatisticalCorrector*
136TAGE_SC_L_8KB_StatisticalCorrectorParams::create()
137{
138    return new TAGE_SC_L_8KB_StatisticalCorrector(this);
139}
140
141TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params)
142  : TAGE_SC_L(params)
143{
144}
145
146void
147TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history)
148{
149    // Some hardcoded values are used here
150    // (they do not seem to depend on any parameter)
151    for (int i = 1; i <= nHistoryTables; i++) {
152        history.computeIndices[i].init(
153            histLengths[i], 17 + (2 * ((i - 1) / 2) % 4));
154        history.computeTags[0][i].init(
155            history.computeIndices[i].origLength, 13);
156        history.computeTags[1][i].init(
157            history.computeIndices[i].origLength, 11);
158        DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
159                histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]);
160    }
161}
162
163int
164TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const
165{
166    return (index ^ (index >> logTagTableSizes[bank])
167                  ^ (index >> 2 * logTagTableSizes[bank]));
168}
169
170uint16_t
171TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const
172{
173    int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^
174              (pc >> instShiftAmt) ^
175              threadHistory[tid].computeIndices[bank].comp;
176    int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
177                                                    histLengths[bank];
178
179    tag = (tag >> 1) ^ ((tag & 1) << 10) ^
180           F(threadHistory[tid].pathHist, hlen, bank);
181    tag ^= threadHistory[tid].computeTags[0][bank].comp ^
182           (threadHistory[tid].computeTags[1][bank].comp << 1);
183
184    return ((tag ^ (tag >> tagTableTagWidths[bank]))
185            & ((ULL(1) << tagTableTagWidths[bank]) - 1));
186}
187
188void
189TAGE_SC_L_TAGE_8KB::handleAllocAndUReset(
190    bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
191{
192    if (!alloc) {
193        return;
194    }
195
196    int penalty = 0;
197    int truePen = 0;
198    int numAllocated = 0;
199    bool maxAllocReached = false;
200
201    for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
202        // Handle the 2-way associativity for allocation
203        for (int j = 0; j < 2; ++j) {
204            int i = ((j == 0) ? I : (I ^ 1)) + 1;
205            if (i > nHistoryTables) {
206                break;
207            }
208            if (noSkip[i]) {
209                if (gtable[i][bi->tableIndices[i]].u == 0) {
210                    gtable[i][bi->tableIndices[i]].u =
211                        ((random_mt.random<int>() & 31) == 0);
212                    // protect randomly from fast replacement
213                    gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
214                    gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
215                    numAllocated++;
216
217                    if (numAllocated == maxNumAlloc) {
218                        maxAllocReached = true;
219                        break;
220                    }
221                    I += 2;
222                } else {
223                    int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
224                    if ((gtable[i][bi->tableIndices[i]].u == 1) &
225                        (abs (2 * ctr + 1) == 1)) {
226                        if ((random_mt.random<int>() & 7) == 0) {
227                            gtable[i][bi->tableIndices[i]].u = 0;
228                        }
229                    } else {
230                        truePen++;
231                    }
232                    penalty++;
233                }
234            } else {
235                break;
236            }
237        }
238        if (maxAllocReached) {
239            break;
240        }
241    }
242
243    tCounter += (truePen + penalty - 5 * numAllocated);
244
245    handleUReset();
246}
247
248void
249TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u)
250{
251    // On real HW it should be u >>= 1 instead of if > 0 then u--
252    if (u > 0) {
253        u--;
254    }
255}
256
257void
258TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken,
259                                     TAGEBase::BranchInfo* bi)
260{
261    if (bi->hitBank > 0) {
262        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
263            if (bi->longestMatchPred != taken) { // acts as a protection
264                if (bi->altBank > 0) {
265                    int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
266                    if (abs (2 * ctr + 1) == 1) {
267                        gtable[bi->altBank][bi->altBankIndex].u = 0;
268                    }
269
270                    //just mute from protected to unprotected
271                    ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
272                              tagTableCounterBits);
273                    ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
274                    if (abs (2 * ctr + 1) == 1) {
275                        gtable[bi->altBank][bi->altBankIndex].u = 0;
276                    }
277                }
278                if (bi->altBank == 0) {
279                    baseUpdate(branch_pc, taken, bi);
280                }
281            }
282        }
283
284        //just mute from protected to unprotected
285        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
286            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
287        }
288
289        ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
290                  tagTableCounterBits);
291
292        //sign changes: no way it can have been useful
293        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
294            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
295        }
296
297        if (bi->altTaken == taken) {
298            if (bi->altBank > 0) {
299                int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
300                if (abs (2*ctr + 1) == 7) {
301                    if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
302                        if (bi->longestMatchPred == taken) {
303                            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
304                        }
305                    }
306                }
307            }
308        }
309    } else {
310        baseUpdate(branch_pc, taken, bi);
311    }
312
313    if ((bi->longestMatchPred != bi->altTaken) &&
314        (bi->longestMatchPred == taken) &&
315        (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
316            gtable[bi->hitBank][bi->hitBankIndex].u++;
317    }
318}
319
320TAGE_SC_L_TAGE_8KB*
321TAGE_SC_L_TAGE_8KBParams::create()
322{
323    return new TAGE_SC_L_TAGE_8KB(this);
324}
325
326TAGE_SC_L_8KB*
327TAGE_SC_L_8KBParams::create()
328{
329    return new TAGE_SC_L_8KB(this);
330}
331