1/*
2 * Copyright (c) 2014 The University of Wisconsin
3 *
4 * Copyright (c) 2006 INRIA (Institut National de Recherche en
5 * Informatique et en Automatique  / French National Research Institute
6 * for Computer Science and Applied Mathematics)
7 *
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions are
12 * met: redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer;
14 * redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution;
17 * neither the name of the copyright holders nor the names of its
18 * contributors may be used to endorse or promote products derived from
19 * this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais,
34 * from André Seznec's code.
35 */
36
37/* @file
38 * Implementation of a TAGE branch predictor. TAGE is a global-history based
39 * branch predictor. It features a PC-indexed bimodal predictor and N
40 * partially tagged tables, indexed with a hash of the PC and the global
41 * branch history. The different lengths of global branch history used to
42 * index the partially tagged tables grow geometrically. A small path history
43 * is also used in the hash.
44 *
45 * All TAGE tables are accessed in parallel, and the one using the longest
46 * history that matches provides the prediction (some exceptions apply).
47 * Entries are allocated in components using a longer history than the
48 * one that predicted when the prediction is incorrect.
49 */
50
51#ifndef __CPU_PRED_TAGE_BASE
52#define __CPU_PRED_TAGE_BASE
53
54#include <vector>
55
56#include "base/statistics.hh"
57#include "cpu/static_inst.hh"
58#include "params/TAGEBase.hh"
59#include "sim/sim_object.hh"
60
61class TAGEBase : public SimObject
62{
63  public:
64    TAGEBase(const TAGEBaseParams *p);
65    void regStats() override;
66    void init() override;
67
68  protected:
69    // Prediction Structures
70
71    // Tage Entry
72    struct TageEntry
73    {
74        int8_t ctr;
75        uint16_t tag;
76        uint8_t u;
77        TageEntry() : ctr(0), tag(0), u(0) { }
78    };
79
80    // Folded History Table - compressed history
81    // to mix with instruction PC to index partially
82    // tagged tables.
83    struct FoldedHistory
84    {
85        unsigned comp;
86        int compLength;
87        int origLength;
88        int outpoint;
89        int bufferSize;
90
91        FoldedHistory()
92        {
93            comp = 0;
94        }
95
96        void init(int original_length, int compressed_length)
97        {
98            origLength = original_length;
99            compLength = compressed_length;
100            outpoint = original_length % compressed_length;
101        }
102
103        void update(uint8_t * h)
104        {
105            comp = (comp << 1) | h[0];
106            comp ^= h[origLength] << outpoint;
107            comp ^= (comp >> compLength);
108            comp &= (ULL(1) << compLength) - 1;
109        }
110    };
111
112  public:
113
114    // provider type
115    enum {
116        BIMODAL_ONLY = 0,
117        TAGE_LONGEST_MATCH,
118        BIMODAL_ALT_MATCH,
119        TAGE_ALT_MATCH,
120        LAST_TAGE_PROVIDER_TYPE = TAGE_ALT_MATCH
121    };
122
123    // Primary branch history entry
124    struct BranchInfo
125    {
126        int pathHist;
127        int ptGhist;
128        int hitBank;
129        int hitBankIndex;
130        int altBank;
131        int altBankIndex;
132        int bimodalIndex;
133
134        bool tagePred;
135        bool altTaken;
136        bool condBranch;
137        bool longestMatchPred;
138        bool pseudoNewAlloc;
139        Addr branchPC;
140
141        // Pointer to dynamically allocated storage
142        // to save table indices and folded histories.
143        // To do one call to new instead of five.
144        int *storage;
145
146        // Pointers to actual saved array within the dynamically
147        // allocated storage.
148        int *tableIndices;
149        int *tableTags;
150        int *ci;
151        int *ct0;
152        int *ct1;
153
154        // for stats purposes
155        unsigned provider;
156
157        BranchInfo(const TAGEBase &tage)
158            : pathHist(0), ptGhist(0),
159              hitBank(0), hitBankIndex(0),
160              altBank(0), altBankIndex(0),
161              bimodalIndex(0),
162              tagePred(false), altTaken(false),
163              condBranch(false), longestMatchPred(false),
164              pseudoNewAlloc(false), branchPC(0),
165              provider(-1)
166        {
167            int sz = tage.nHistoryTables + 1;
168            storage = new int [sz * 5];
169            tableIndices = storage;
170            tableTags = storage + sz;
171            ci = tableTags + sz;
172            ct0 = ci + sz;
173            ct1 = ct0 + sz;
174        }
175
176        virtual ~BranchInfo()
177        {
178            delete[] storage;
179        }
180    };
181
182    virtual BranchInfo *makeBranchInfo();
183
184    /**
185     * Computes the index used to access the
186     * bimodal table.
187     * @param pc_in The unshifted branch PC.
188     */
189    virtual int bindex(Addr pc_in) const;
190
191    /**
192     * Computes the index used to access a
193     * partially tagged table.
194     * @param tid The thread ID used to select the
195     * global histories to use.
196     * @param pc The unshifted branch PC.
197     * @param bank The partially tagged table to access.
198     */
199    virtual int gindex(ThreadID tid, Addr pc, int bank) const;
200
201    /**
202     * Utility function to shuffle the path history
203     * depending on which tagged table we are accessing.
204     * @param phist The path history.
205     * @param size Number of path history bits to use.
206     * @param bank The partially tagged table to access.
207     */
208    virtual int F(int phist, int size, int bank) const;
209
210    /**
211     * Computes the partial tag of a tagged table.
212     * @param tid the thread ID used to select the
213     * global histories to use.
214     * @param pc The unshifted branch PC.
215     * @param bank The partially tagged table to access.
216     */
217    virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const;
218
219    /**
220     * Updates a direction counter based on the actual
221     * branch outcome.
222     * @param ctr Reference to counter to update.
223     * @param taken Actual branch outcome.
224     * @param nbits Counter width.
225     */
226    template<typename T>
227    static void ctrUpdate(T & ctr, bool taken, int nbits);
228
229    /**
230     * Updates an unsigned counter based on up/down parameter
231     * @param ctr Reference to counter to update.
232     * @param up Boolean indicating if the counter is incremented/decremented
233     * If true it is incremented, if false it is decremented
234     * @param nbits Counter width.
235     */
236    static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);
237
238    /**
239     * Get a branch prediction from the bimodal
240     * predictor.
241     * @param pc The unshifted branch PC.
242     * @param bi Pointer to information on the
243     * prediction.
244     */
245    virtual bool getBimodePred(Addr pc, BranchInfo* bi) const;
246
247    /**
248     * Updates the bimodal predictor.
249     * @param pc The unshifted branch PC.
250     * @param taken The actual branch outcome.
251     * @param bi Pointer to information on the prediction
252     * recorded at prediction time.
253     */
254    void baseUpdate(Addr pc, bool taken, BranchInfo* bi);
255
256   /**
257    * (Speculatively) updates the global branch history.
258    * @param h Reference to pointer to global branch history.
259    * @param dir (Predicted) outcome to update the histories
260    * with.
261    * @param tab
262    * @param PT Reference to path history.
263    */
264    void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT);
265
266    /**
267     * Update TAGE. Called at execute to repair histories on a misprediction
268     * and at commit to update the tables.
269     * @param tid The thread ID to select the global
270     * histories to use.
271     * @param branch_pc The unshifted branch PC.
272     * @param taken Actual branch outcome.
273     * @param bi Pointer to information on the prediction
274     * recorded at prediction time.
275     */
276    void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);
277
278   /**
279    * (Speculatively) updates global histories (path and direction).
280    * Also recomputes compressed (folded) histories based on the
281    * branch direction.
282    * @param tid The thread ID to select the histories
283    * to update.
284    * @param branch_pc The unshifted branch PC.
285    * @param taken (Predicted) branch direction.
286    * @param b Wrapping pointer to BranchInfo (to allow
287    * storing derived class prediction information in the
288    * base class).
289    */
290    virtual void updateHistories(
291        ThreadID tid, Addr branch_pc, bool taken, BranchInfo* b,
292        bool speculative,
293        const StaticInstPtr & inst = StaticInst::nullStaticInstPtr,
294        Addr target = MaxAddr);
295
296    /**
297     * Restores speculatively updated path and direction histories.
298     * Also recomputes compressed (folded) histories based on the
299     * correct branch outcome.
300     * This version of squash() is called once on a branch misprediction.
301     * @param tid The Thread ID to select the histories to rollback.
302     * @param taken The correct branch outcome.
303     * @param bp_history Wrapping pointer to BranchInfo (to allow
304     * storing derived class prediction information in the
305     * base class).
306     * @param target The correct branch target
307     * @post bp_history points to valid memory.
308     */
309    virtual void squash(
310        ThreadID tid, bool taken, BranchInfo *bi, Addr target);
311
312    /**
313     * Update TAGE for conditional branches.
314     * @param branch_pc The unshifted branch PC.
315     * @param taken Actual branch outcome.
316     * @param bi Pointer to information on the prediction
317     * recorded at prediction time.
318     * @nrand Random int number from 0 to 3
319     * @param corrTarget The correct branch target
320     * @param pred Final prediction for this branch
321     * @param preAdjustAlloc call adjustAlloc before checking
322     * pseudo newly allocated entries
323     */
324    virtual void condBranchUpdate(
325        ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi,
326        int nrand, Addr corrTarget, bool pred, bool preAdjustAlloc = false);
327
328    /**
329     * TAGE prediction called from TAGE::predict
330     * @param tid The thread ID to select the global
331     * histories to use.
332     * @param branch_pc The unshifted branch PC.
333     * @param cond_branch True if the branch is conditional.
334     * @param bi Pointer to the BranchInfo
335     */
336    bool tagePredict(
337        ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi);
338
339    /**
340     * Update the stats
341     * @param taken Actual branch outcome
342     * @param bi Pointer to information on the prediction
343     * recorded at prediction time.
344     */
345    virtual void updateStats(bool taken, BranchInfo* bi);
346
347    /**
348     * Instantiates the TAGE table entries
349     */
350    virtual void buildTageTables();
351
352    /**
353     * Calculates the history lengths
354     * and some other paramters in derived classes
355     */
356    virtual void calculateParameters();
357
358    /**
359     * On a prediction, calculates the TAGE indices and tags for
360     * all the different history lengths
361     */
362    virtual void calculateIndicesAndTags(
363        ThreadID tid, Addr branch_pc, BranchInfo* bi);
364
365    /**
366     * Calculation of the index for useAltPredForNewlyAllocated
367     * On this base TAGE implementation it is always 0
368     */
369    virtual unsigned getUseAltIdx(BranchInfo* bi, Addr branch_pc);
370
371    /**
372     * Extra calculation to tell whether TAGE allocaitons may happen or not
373     * on an update
374     * For this base TAGE implementation it does nothing
375     */
376    virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken);
377
378    /**
379     * Handles Allocation and U bits reset on an update
380     */
381    virtual void handleAllocAndUReset(
382        bool alloc, bool taken, BranchInfo* bi, int nrand);
383
384    /**
385     * Handles the U bits reset
386     */
387    virtual void handleUReset();
388
389    /**
390     * Handles the update of the TAGE entries
391     */
392    virtual void handleTAGEUpdate(
393        Addr branch_pc, bool taken, BranchInfo* bi);
394
395    /**
396     * Algorithm for resetting a single U counter
397     */
398    virtual void resetUctr(uint8_t & u);
399
400    /**
401     * Extra steps for calculating altTaken
402     * For this base TAGE class it does nothing
403     */
404    virtual void extraAltCalc(BranchInfo* bi);
405
406    virtual bool isHighConfidence(BranchInfo* bi) const
407    {
408        return false;
409    }
410
411    void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi);
412    unsigned getGHR(ThreadID tid, BranchInfo *bi) const;
413    int8_t getCtr(int hitBank, int hitBankIndex) const;
414    unsigned getTageCtrBits() const;
415    int getPathHist(ThreadID tid) const;
416    bool isSpeculativeUpdateEnabled() const;
417    size_t getSizeInBits() const;
418
419  protected:
420    const unsigned logRatioBiModalHystEntries;
421    const unsigned nHistoryTables;
422    const unsigned tagTableCounterBits;
423    const unsigned tagTableUBits;
424    const unsigned histBufferSize;
425    const unsigned minHist;
426    const unsigned maxHist;
427    const unsigned pathHistBits;
428
429    std::vector<unsigned> tagTableTagWidths;
430    std::vector<int> logTagTableSizes;
431
432    std::vector<bool> btablePrediction;
433    std::vector<bool> btableHysteresis;
434    TageEntry **gtable;
435
436    // Keep per-thread histories to
437    // support SMT.
438    struct ThreadHistory {
439        // Speculative path history
440        // (LSB of branch address)
441        int pathHist;
442
443        // Speculative branch direction
444        // history (circular buffer)
445        // @TODO Convert to std::vector<bool>
446        uint8_t *globalHistory;
447
448        // Pointer to most recent branch outcome
449        uint8_t* gHist;
450
451        // Index to most recent branch outcome
452        int ptGhist;
453
454        // Speculative folded histories.
455        FoldedHistory *computeIndices;
456        FoldedHistory *computeTags[2];
457    };
458
459    std::vector<ThreadHistory> threadHistory;
460
461    /**
462     * Initialization of the folded histories
463     */
464    virtual void initFoldedHistories(ThreadHistory & history);
465
466    int *histLengths;
467    int *tableIndices;
468    int *tableTags;
469
470    std::vector<int8_t> useAltPredForNewlyAllocated;
471    int64_t tCounter;
472    uint64_t logUResetPeriod;
473    const int64_t initialTCounterValue;
474    unsigned numUseAltOnNa;
475    unsigned useAltOnNaBits;
476    unsigned maxNumAlloc;
477
478    // Tells which tables are active
479    // (for the base TAGE implementation all are active)
480    // Some other classes use this for handling associativity
481    std::vector<bool> noSkip;
482
483    const bool speculativeHistUpdate;
484
485    const unsigned instShiftAmt;
486
487    bool initialized;
488
489    // stats
490    Stats::Scalar tageLongestMatchProviderCorrect;
491    Stats::Scalar tageAltMatchProviderCorrect;
492    Stats::Scalar bimodalAltMatchProviderCorrect;
493    Stats::Scalar tageBimodalProviderCorrect;
494    Stats::Scalar tageLongestMatchProviderWrong;
495    Stats::Scalar tageAltMatchProviderWrong;
496    Stats::Scalar bimodalAltMatchProviderWrong;
497    Stats::Scalar tageBimodalProviderWrong;
498    Stats::Scalar tageAltMatchProviderWouldHaveHit;
499    Stats::Scalar tageLongestMatchProviderWouldHaveHit;
500
501    Stats::Vector tageLongestMatchProvider;
502    Stats::Vector tageAltMatchProvider;
503};
504
505#endif // __CPU_PRED_TAGE_BASE
506