tage_sc_l_8KB.cc revision 13685:bb3377c81303 
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, int brtype,
105    bool taken, BranchInfo * tage_bi, Addr corrTarget)
106{
107    // Non speculative SC histories update
108    if (brtype & 1) {
109        SC_8KB_ThreadHistory *sh =
110            static_cast<SC_8KB_ThreadHistory *>(scHistory);
111        sh->globalHist = (sh->globalHist << 1) + taken;
112    }
113
114    StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi,
115                                          corrTarget);
116}
117
118void
119TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken,
120        BranchInfo* bi, int64_t phist)
121{
122    SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
123    gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi);
124    gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi);
125    gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl,
126            bi);
127    gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi);
128}
129
130TAGE_SC_L_8KB_StatisticalCorrector*
131TAGE_SC_L_8KB_StatisticalCorrectorParams::create()
132{
133    return new TAGE_SC_L_8KB_StatisticalCorrector(this);
134}
135
136TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params)
137  : TAGE_SC_L(params)
138{
139}
140
141void
142TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history)
143{
144    // Some hardcoded values are used here
145    // (they do not seem to depend on any parameter)
146    for (int i = 1; i <= nHistoryTables; i++) {
147        history.computeIndices[i].init(
148            histLengths[i], 17 + (2 * ((i - 1) / 2) % 4));
149        history.computeTags[0][i].init(
150            history.computeIndices[i].origLength, 13);
151        history.computeTags[1][i].init(
152            history.computeIndices[i].origLength, 11);
153        DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
154                histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]);
155    }
156}
157
158int
159TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const
160{
161    return (index ^ (index >> logTagTableSizes[bank])
162                  ^ (index >> 2 * logTagTableSizes[bank]));
163}
164
165uint16_t
166TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const
167{
168    int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^
169              (pc >> instShiftAmt) ^
170              threadHistory[tid].computeIndices[bank].comp;
171    int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
172                                                    histLengths[bank];
173
174    tag = (tag >> 1) ^ ((tag & 1) << 10) ^
175           F(threadHistory[tid].pathHist, hlen, bank);
176    tag ^= threadHistory[tid].computeTags[0][bank].comp ^
177           (threadHistory[tid].computeTags[1][bank].comp << 1);
178
179    return ((tag ^ (tag >> tagTableTagWidths[bank]))
180            & ((ULL(1) << tagTableTagWidths[bank]) - 1));
181}
182
183void
184TAGE_SC_L_TAGE_8KB::handleAllocAndUReset(
185    bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
186{
187    if (!alloc) {
188        return;
189    }
190
191    int penalty = 0;
192    int truePen = 0;
193    int numAllocated = 0;
194    bool maxAllocReached = false;
195
196    for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
197        // Handle the 2-way associativity for allocation
198        for (int j = 0; j < 2; ++j) {
199            int i = ((j == 0) ? I : (I ^ 1)) + 1;
200            if (i > nHistoryTables) {
201                break;
202            }
203            if (noSkip[i]) {
204                if (gtable[i][bi->tableIndices[i]].u == 0) {
205                    gtable[i][bi->tableIndices[i]].u =
206                        ((random_mt.random<int>() & 31) == 0);
207                    // protect randomly from fast replacement
208                    gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
209                    gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
210                    numAllocated++;
211
212                    if (numAllocated == maxNumAlloc) {
213                        maxAllocReached = true;
214                        break;
215                    }
216                    I += 2;
217                } else {
218                    int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
219                    if ((gtable[i][bi->tableIndices[i]].u == 1) &
220                        (abs (2 * ctr + 1) == 1)) {
221                        if ((random_mt.random<int>() & 7) == 0) {
222                            gtable[i][bi->tableIndices[i]].u = 0;
223                        }
224                    } else {
225                        truePen++;
226                    }
227                    penalty++;
228                }
229            } else {
230                break;
231            }
232        }
233        if (maxAllocReached) {
234            break;
235        }
236    }
237
238    tCounter += (truePen + penalty - 5 * numAllocated);
239
240    handleUReset();
241}
242
243void
244TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u)
245{
246    // On real HW it should be u >>= 1 instead of if > 0 then u--
247    if (u > 0) {
248        u--;
249    }
250}
251
252void
253TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken,
254                                     TAGEBase::BranchInfo* bi)
255{
256    if (bi->hitBank > 0) {
257        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
258            if (bi->longestMatchPred != taken) { // acts as a protection
259                if (bi->altBank > 0) {
260                    int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
261                    if (abs (2 * ctr + 1) == 1) {
262                        gtable[bi->altBank][bi->altBankIndex].u = 0;
263                    }
264
265                    //just mute from protected to unprotected
266                    ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
267                              tagTableCounterBits);
268                    ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
269                    if (abs (2 * ctr + 1) == 1) {
270                        gtable[bi->altBank][bi->altBankIndex].u = 0;
271                    }
272                }
273                if (bi->altBank == 0) {
274                    baseUpdate(branch_pc, taken, bi);
275                }
276            }
277        }
278
279        //just mute from protected to unprotected
280        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
281            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
282        }
283
284        ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
285                  tagTableCounterBits);
286
287        //sign changes: no way it can have been useful
288        if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
289            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
290        }
291
292        if (bi->altTaken == taken) {
293            if (bi->altBank > 0) {
294                int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
295                if (abs (2*ctr + 1) == 7) {
296                    if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
297                        if (bi->longestMatchPred == taken) {
298                            gtable[bi->hitBank][bi->hitBankIndex].u = 0;
299                        }
300                    }
301                }
302            }
303        }
304    } else {
305        baseUpdate(branch_pc, taken, bi);
306    }
307
308    if ((bi->longestMatchPred != bi->altTaken) &&
309        (bi->longestMatchPred == taken) &&
310        (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
311            gtable[bi->hitBank][bi->hitBankIndex].u++;
312    }
313}
314
315TAGE_SC_L_TAGE_8KB*
316TAGE_SC_L_TAGE_8KBParams::create()
317{
318    return new TAGE_SC_L_TAGE_8KB(this);
319}
320
321TAGE_SC_L_8KB*
322TAGE_SC_L_8KBParams::create()
323{
324    return new TAGE_SC_L_8KB(this);
325}
326