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