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#ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH
43#define __CPU_PRED_STATISTICAL_CORRECTOR_HH
44
45#include "base/statistics.hh"
46#include "base/types.hh"
47#include "cpu/static_inst.hh"
48#include "sim/sim_object.hh"
49
50struct StatisticalCorrectorParams;
51
52class StatisticalCorrector : public SimObject
53{
54  protected:
55    template<typename T>
56    inline void ctrUpdate(T & ctr, bool taken, int nbits) {
57        assert(nbits <= sizeof(T) << 3);
58        if (nbits > 0) {
59            if (taken) {
60                if (ctr < ((1 << (nbits - 1)) - 1))
61                    ctr++;
62            } else {
63                if (ctr > -(1 << (nbits - 1)))
64                    ctr--;
65            }
66        }
67    }
68    // histories used for the statistical corrector
69    struct SCThreadHistory {
70        SCThreadHistory() {
71            bwHist = 0;
72            numOrdinalHistories = 0;
73            imliCount = 0;
74        }
75        int64_t bwHist;  // backward global history
76        int64_t imliCount;
77
78        void setNumOrdinalHistories(unsigned num)
79        {
80            numOrdinalHistories = num;
81            assert(num > 0);
82            shifts.resize(num);
83            localHistories = new std::vector<int64_t> [num];
84        }
85
86        void initLocalHistory(int ordinal, int numHistories, int shift)
87        {
88            assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
89            shifts[ordinal - 1] = shift;
90            assert(isPowerOf2(numHistories));
91            localHistories[ordinal - 1].resize(numHistories, 0);
92        }
93
94        int64_t getLocalHistory(int ordinal, Addr pc)
95        {
96            assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
97            unsigned idx = ordinal - 1;
98            return localHistories[idx][getEntry(pc, idx)];
99        }
100
101        void updateLocalHistory(
102            int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0)
103        {
104            assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
105            unsigned idx = ordinal - 1;
106
107            unsigned entry = getEntry(branch_pc, idx);
108            int64_t hist =  (localHistories[idx][entry] << 1) + taken;
109
110            if (extraXor) {
111                hist = hist ^ extraXor;
112            }
113
114            localHistories[idx][entry] = hist;
115        }
116
117      private:
118        std::vector<int64_t> * localHistories;
119        std::vector<int> shifts;
120        unsigned numOrdinalHistories;
121
122        unsigned getEntry(Addr pc, unsigned idx)
123        {
124            return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1);
125        }
126    };
127
128    // For SC history we use global (i.e. not per thread) non speculative
129    // histories, as some of the strucures needed are quite big and it is not
130    // reasonable to make them per thread and it would be difficult to
131    // rollback on miss-predictions
132    SCThreadHistory * scHistory;
133
134    const unsigned logBias;
135
136    const unsigned logSizeUp;
137    const unsigned logSizeUps;
138
139    const unsigned numEntriesFirstLocalHistories;
140
141    // global backward branch history GEHL
142    const unsigned bwnb;
143    const unsigned logBwnb;
144    std::vector<int> bwm;
145    std::vector<int8_t> * bwgehl;
146    std::vector<int8_t> wbw;
147
148    // First local history GEHL
149    const unsigned lnb;
150    const unsigned logLnb;
151    std::vector<int> lm;
152    std::vector<int8_t> * lgehl;
153    std::vector<int8_t> wl;
154
155    // IMLI GEHL
156    const unsigned inb;
157    const unsigned logInb;
158    std::vector<int> im;
159    std::vector<int8_t> * igehl;
160    std::vector<int8_t> wi;
161
162    std::vector<int8_t> bias;
163    std::vector<int8_t> biasSK;
164    std::vector<int8_t> biasBank;
165
166    std::vector<int8_t> wb;
167
168    int updateThreshold;
169    std::vector<int> pUpdateThreshold;
170
171    // The two counters used to choose between TAGE ang SC on High Conf
172    // TAGE/Low Conf SC
173    const unsigned chooserConfWidth;
174
175    const unsigned updateThresholdWidth;
176    const unsigned pUpdateThresholdWidth;
177
178    const unsigned extraWeightsWidth;
179
180    const unsigned scCountersWidth;
181
182    int8_t firstH;
183    int8_t secondH;
184
185    // stats
186    Stats::Scalar scPredictorCorrect;
187    Stats::Scalar scPredictorWrong;
188  public:
189    struct BranchInfo
190    {
191        BranchInfo() : lowConf(false), highConf(false), altConf(false),
192              medConf(false), scPred(false), lsum(0), thres(0),
193              predBeforeSC(false), usedScPred(false)
194        {}
195
196        // confidences calculated on tage and used on the statistical
197        // correction
198        bool lowConf;
199        bool highConf;
200        bool altConf;
201        bool medConf;
202
203        bool scPred;
204        int lsum;
205        int thres;
206        bool predBeforeSC;
207        bool usedScPred;
208    };
209
210    StatisticalCorrector(const StatisticalCorrectorParams *p);
211
212    virtual BranchInfo *makeBranchInfo();
213    virtual SCThreadHistory *makeThreadHistory();
214
215    virtual void initBias();
216
217    virtual bool scPredict(
218        ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi,
219        bool prev_pred_taken, bool bias_bit, bool use_conf_ctr,
220        int8_t conf_ctr, unsigned conf_bits, int hitBank, int altBank,
221        int64_t phist, int init_lsum = 0);
222
223    virtual unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const;
224
225    virtual unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const;
226
227    virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi,
228        int hitBank, int altBank) const = 0;
229
230    virtual unsigned getIndUpd(Addr branch_pc) const;
231    unsigned getIndUpds(Addr branch_pc) const;
232
233    virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi,
234        int & lsum, int64_t phist) = 0;
235
236    int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i);
237
238    virtual int gIndexLogsSubstr(int nbr, int i) = 0;
239
240    int gPredict(
241        Addr branch_pc, int64_t hist, std::vector<int> & length,
242        std::vector<int8_t> * tab, int nbr, int logs,
243        std::vector<int8_t> & w);
244
245    virtual void gUpdate(
246        Addr branch_pc, bool taken, int64_t hist, std::vector<int> & length,
247        std::vector<int8_t> * tab, int nbr, int logs,
248        std::vector<int8_t> & w, BranchInfo* bi);
249
250    void initGEHLTable(
251        unsigned numLenghts, std::vector<int> lengths,
252        std::vector<int8_t> * & table, unsigned logNumEntries,
253        std::vector<int8_t> & w, int8_t wInitValue);
254
255    virtual void scHistoryUpdate(
256        Addr branch_pc, const StaticInstPtr &inst , bool taken,
257        BranchInfo * tage_bi, Addr corrTarget);
258
259    virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
260        int64_t phist) = 0;
261
262    void init() override;
263    void regStats() override;
264    void updateStats(bool taken, BranchInfo *bi);
265
266    virtual void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
267                          BranchInfo *bi, Addr corrTarget, bool bias_bit,
268                          int hitBank, int altBank, int64_t phist);
269
270    virtual size_t getSizeInBits() const;
271};
272#endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH
273