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 * Statistical corrector base class
40 */
41
42 #include "cpu/pred/statistical_corrector.hh"
43
44 #include "params/StatisticalCorrector.hh"
45
46 StatisticalCorrector::StatisticalCorrector(
47    const StatisticalCorrectorParams *p)
48  : SimObject(p),
49    logBias(p->logBias),
50    logSizeUp(p->logSizeUp),
51    logSizeUps(logSizeUp / 2),
52    numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories),
53    bwnb(p->bwnb),
54    logBwnb(p->logBwnb),
55    bwm(p->bwm),
56    lnb(p->lnb),
57    logLnb(p->logLnb),
58    lm(p->lm),
59    inb(p->inb),
60    logInb(p->logInb),
61    im(p->im),
62    chooserConfWidth(p->chooserConfWidth),
63    updateThresholdWidth(p->updateThresholdWidth),
64    pUpdateThresholdWidth(p->pUpdateThresholdWidth),
65    extraWeightsWidth(p->extraWeightsWidth),
66    scCountersWidth(p->scCountersWidth),
67    firstH(0),
68    secondH(0)
69{
70    wb.resize(1 << logSizeUps, 4);
71
72    initGEHLTable(lnb, lm, lgehl, logLnb, wl, p->lWeightInitValue);
73    initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, p->bwWeightInitValue);
74    initGEHLTable(inb, im, igehl, logInb, wi, p->iWeightInitValue);
75
76    updateThreshold = 35 << 3;
77
78    pUpdateThreshold.resize(1 << logSizeUp, p->initialUpdateThresholdValue);
79
80    bias.resize(1 << logBias);
81    biasSK.resize(1 << logBias);
82    biasBank.resize(1 << logBias);
83}
84
85StatisticalCorrector::BranchInfo*
86StatisticalCorrector::makeBranchInfo()
87{
88    return new BranchInfo();
89}
90
91StatisticalCorrector::SCThreadHistory*
92StatisticalCorrector::makeThreadHistory()
93{
94    return new SCThreadHistory();
95}
96
97void
98StatisticalCorrector::initBias()
99{
100    for (int j = 0; j < (1 << logBias); j++) {
101        switch (j & 3) {
102          case 0:
103            bias[j] = -32;
104            biasSK[j] = -8;
105            biasBank[j] = -32;
106            break;
107          case 1:
108            bias[j] = 31;
109            biasSK[j] = 7;
110            biasBank[j] = 31;
111            break;
112          case 2:
113            bias[j] = -1;
114            biasSK[j] = -32;
115            biasBank[j] = -1;
116            break;
117          case 3:
118            bias[j] = 0;
119            biasSK[j] = 31;
120            biasBank[j] = 0;
121            break;
122        }
123    }
124}
125
126void
127StatisticalCorrector::initGEHLTable(unsigned numLenghts,
128    std::vector<int> lengths, std::vector<int8_t> * & table,
129    unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue)
130{
131    assert(lengths.size() == numLenghts);
132    if (numLenghts == 0) {
133        return;
134    }
135    table = new std::vector<int8_t> [numLenghts];
136    for (int i = 0; i < numLenghts; ++i) {
137        table[i].resize(1 << logNumEntries, 0);
138        for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) {
139            if (! (j & 1)) {
140                table[i][j] = -1;
141            }
142        }
143    }
144
145    w.resize(1 << logSizeUps, wInitValue);
146}
147
148unsigned
149StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi,
150                                 bool bias) const
151{
152    return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1)
153            +  bi->predBeforeSC) & ((1<<logBias) -1);
154}
155
156unsigned
157StatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const
158{
159    return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^
160           (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1);
161}
162
163unsigned
164StatisticalCorrector::getIndUpd(Addr branch_pc) const
165{
166    return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1));
167}
168
169unsigned
170StatisticalCorrector::getIndUpds(Addr branch_pc) const
171{
172    return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1));
173}
174
175int64_t
176StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr,
177                             int i)
178{
179    return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^
180            (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^
181            (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) &
182           ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1);
183}
184
185int
186StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist,
187        std::vector<int> & length, std::vector<int8_t> * tab, int nbr,
188        int logs, std::vector<int8_t> & w)
189{
190    int percsum = 0;
191    for (int i = 0; i < nbr; i++) {
192        int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1));
193        int64_t index = gIndex(branch_pc, bhist, logs, nbr, i);
194        int8_t ctr = tab[i][index];
195        percsum += (2 * ctr + 1);
196    }
197    percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum;
198    return percsum;
199}
200
201void
202StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist,
203                   std::vector<int> & length, std::vector<int8_t> * tab,
204                   int nbr, int logs, std::vector<int8_t> & w,
205                   BranchInfo* bi)
206{
207    int percsum = 0;
208    for (int i = 0; i < nbr; i++) {
209        int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1));
210        int64_t index = gIndex(branch_pc, bhist, logs, nbr, i);
211        percsum += (2 * tab[i][index] + 1);
212        ctrUpdate(tab[i][index], taken, scCountersWidth);
213    }
214
215    int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum;
216    if ((xsum + percsum >= 0) != (xsum >= 0)) {
217        ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken),
218                  extraWeightsWidth);
219    }
220}
221
222bool
223StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
224                     BranchInfo* bi, bool prev_pred_taken, bool bias_bit,
225                     bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits,
226                     int hitBank, int altBank, int64_t phist, int init_lsum)
227{
228    bool pred_taken = prev_pred_taken;
229    if (cond_branch) {
230
231        bi->predBeforeSC = prev_pred_taken;
232
233        // first calc/update the confidences from the TAGE prediction
234        if (use_conf_ctr) {
235            bi->lowConf = (abs(2 * conf_ctr + 1) == 1);
236            bi->medConf = (abs(2 * conf_ctr + 1) == 5);
237            bi->highConf = (abs(2 * conf_ctr + 1) >= (1<<conf_bits) - 1);
238        }
239
240        int lsum = init_lsum;
241
242        int8_t ctr = bias[getIndBias(branch_pc, bi, bias_bit)];
243        lsum += (2 * ctr + 1);
244        ctr = biasSK[getIndBiasSK(branch_pc, bi)];
245        lsum += (2 * ctr + 1);
246        ctr = biasBank[getIndBiasBank(branch_pc, bi, hitBank, altBank)];
247        lsum += (2 * ctr + 1);
248
249        lsum = (1 + (wb[getIndUpds(branch_pc)] >= 0)) * lsum;
250
251        int thres = gPredictions(tid, branch_pc, bi, lsum, phist);
252
253        // These will be needed at update time
254        bi->lsum = lsum;
255        bi->thres = thres;
256
257        bool scPred = (lsum >= 0);
258
259        if (pred_taken != scPred) {
260            bool useScPred = true;
261            //Choser uses TAGE confidence and |LSUM|
262            if (bi->highConf) {
263                if (abs (lsum) < (thres / 4)) {
264                    useScPred = false;
265                } else if (abs (lsum) < (thres / 2)) {
266                    useScPred = (secondH < 0);
267                }
268            }
269
270            if (bi->medConf) {
271                if (abs (lsum) < (thres / 4)) {
272                    useScPred = (firstH < 0);
273                }
274            }
275
276            bi->usedScPred = useScPred;
277            if (useScPred) {
278                pred_taken = scPred;
279                bi->scPred = scPred;
280            }
281        }
282    }
283
284    return pred_taken;
285}
286
287void
288StatisticalCorrector::scHistoryUpdate(Addr branch_pc,
289        const StaticInstPtr &inst, bool taken, BranchInfo * tage_bi,
290        Addr corrTarget)
291{
292    int brtype = inst->isDirectCtrl() ? 0 : 2;
293    if (! inst->isUncondCtrl()) {
294        ++brtype;
295    }
296    // Non speculative SC histories update
297    if (brtype & 1) {
298        if (corrTarget < branch_pc) {
299            //This branch corresponds to a loop
300            if (!taken) {
301                //exit of the "loop"
302                scHistory->imliCount = 0;
303            } else {
304                if (scHistory->imliCount < ((1 << im[0]) - 1)) {
305                    scHistory->imliCount++;
306                }
307            }
308        }
309
310        scHistory->bwHist = (scHistory->bwHist << 1) +
311                                (taken & (corrTarget < branch_pc));
312        scHistory->updateLocalHistory(1, branch_pc, taken);
313    }
314}
315
316void
317StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc,
318        bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank,
319        int altBank, int64_t phist)
320{
321    bool scPred = (bi->lsum >= 0);
322
323    if (bi->predBeforeSC != scPred) {
324        if (abs(bi->lsum) < bi->thres) {
325            if (bi->highConf) {
326                if ((abs(bi->lsum) < bi->thres / 2)) {
327                    if ((abs(bi->lsum) >= bi->thres / 4)) {
328                        ctrUpdate(secondH, (bi->predBeforeSC == taken),
329                                  chooserConfWidth);
330                    }
331                }
332            }
333        }
334        if (bi->medConf) {
335            if ((abs(bi->lsum) < bi->thres / 4)) {
336                ctrUpdate(firstH, (bi->predBeforeSC == taken),
337                          chooserConfWidth);
338            }
339        }
340    }
341
342    if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) {
343        ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth);
344        ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken),
345                  pUpdateThresholdWidth);
346
347        unsigned indUpds = getIndUpds(branch_pc);
348        unsigned indBias = getIndBias(branch_pc, bi, b);
349        unsigned indBiasSK = getIndBiasSK(branch_pc, bi);
350        unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank);
351
352        int xsum = bi->lsum -
353                      ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) +
354                          (2 * biasSK[indBiasSK] + 1) +
355                          (2 * biasBank[indBiasBank] + 1)));
356
357        if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) +
358            (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0))
359        {
360            ctrUpdate(wb[indUpds],
361                      (((2 * bias[indBias] + 1) +
362                        (2 * biasSK[indBiasSK] + 1) +
363                        (2 * biasBank[indBiasBank] + 1) >= 0) == taken),
364                      extraWeightsWidth);
365        }
366
367        ctrUpdate(bias[indBias], taken, scCountersWidth);
368        ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth);
369        ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth);
370
371        gUpdates(tid, branch_pc, taken, bi, phist);
372    }
373}
374
375void
376StatisticalCorrector::updateStats(bool taken, BranchInfo *bi)
377{
378    if (taken == bi->scPred) {
379        scPredictorCorrect++;
380    } else {
381        scPredictorWrong++;
382    }
383}
384
385void
386StatisticalCorrector::init()
387{
388    scHistory = makeThreadHistory();
389    initBias();
390}
391
392size_t
393StatisticalCorrector::getSizeInBits() const
394{
395    // Not implemented
396    return 0;
397}
398
399void
400StatisticalCorrector::regStats()
401{
402    scPredictorCorrect
403        .name(name() + ".scPredictorCorrect")
404        .desc("Number of time the SC predictor is the provider and "
405              "the prediction is correct");
406
407    scPredictorWrong
408        .name(name() + ".scPredictorWrong")
409        .desc("Number of time the SC predictor is the provider and "
410              "the prediction is wrong");
411}
412