loop_predictor.hh revision 13627 
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#ifndef __CPU_PRED_LOOP_PREDICTOR_HH__
38#define __CPU_PRED_LOOP_PREDICTOR_HH__
39
40#include "base/statistics.hh"
41#include "base/types.hh"
42#include "sim/sim_object.hh"
43
44struct LoopPredictorParams;
45
46class LoopPredictor : public SimObject
47{
48  protected:
49    const unsigned logSizeLoopPred;
50    const unsigned loopTableAgeBits;
51    const unsigned loopTableConfidenceBits;
52    const unsigned loopTableTagBits;
53    const unsigned loopTableIterBits;
54    const unsigned logLoopTableAssoc;
55    const uint8_t confidenceThreshold;
56    const uint16_t loopTagMask;
57    const uint16_t loopNumIterMask;
58    const int loopSetMask;
59
60    // Prediction Structures
61    // Loop Predictor Entry
62    struct LoopEntry
63    {
64        uint16_t numIter;
65        uint16_t currentIter;
66        uint16_t currentIterSpec; // only for useSpeculation
67        uint8_t confidence;
68        uint16_t tag;
69        uint8_t age;
70        bool dir; // only for useDirectionBit
71
72        LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
73                      confidence(0), tag(0), age(0), dir(0) { }
74    };
75
76    LoopEntry *ltable;
77
78    int8_t loopUseCounter;
79    unsigned withLoopBits;
80
81    const bool useDirectionBit;
82    const bool useSpeculation;
83    const bool useHashing;
84    const bool restrictAllocation;
85    const unsigned initialLoopIter;
86    const unsigned initialLoopAge;
87    const bool optionalAgeReset;
88
89    // stats
90    Stats::Scalar loopPredictorCorrect;
91    Stats::Scalar loopPredictorWrong;
92
93    /**
94     * Updates an unsigned counter based on up/down parameter
95     * @param ctr Reference to counter to update.
96     * @param up Boolean indicating if the counter is incremented/decremented
97     * If true it is incremented, if false it is decremented
98     * @param nbits Counter width.
99     */
100    static inline void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned nbits)
101    {
102        assert(nbits <= sizeof(uint8_t) << 3);
103        if (up) {
104            if (ctr < ((1 << nbits) - 1))
105                ctr++;
106        } else {
107            if (ctr)
108                ctr--;
109        }
110    }
111    static inline void signedCtrUpdate(int8_t &ctr, bool up, unsigned nbits)
112    {
113        if (up) {
114            if (ctr < ((1 << (nbits - 1)) - 1))
115                ctr++;
116        } else {
117            if (ctr > -(1 << (nbits - 1)))
118                ctr--;
119        }
120    }
121  public:
122    // Primary branch history entry
123    struct BranchInfo
124    {
125        uint16_t loopTag;
126        uint16_t currentIter;
127
128        bool loopPred;
129        bool loopPredValid;
130        bool loopPredUsed;
131        int  loopIndex;
132        int  loopIndexB;  // only for useHashing
133        int loopHit;
134        bool predTaken;
135
136        BranchInfo()
137            : loopTag(0), currentIter(0),
138              loopPred(false),
139              loopPredValid(false), loopIndex(0), loopIndexB(0), loopHit(0),
140              predTaken(false)
141        {}
142    };
143
144    /**
145     * Computes the index used to access the
146     * loop predictor.
147     * @param pc_in The unshifted branch PC.
148     * @param instShiftAmt Shift the pc by as many bits
149     */
150    int lindex(Addr pc_in, unsigned instShiftAmt) const;
151
152    /**
153     * Computes the index used to access the
154     * ltable structures.
155     * It may take hashing into account
156     * @param index Result of lindex function
157     * @param lowPcBits PC bits masked with set size
158     * @param way Way to be used
159     */
160    int finallindex(int lindex, int lowPcBits, int way) const;
161
162    /**
163     * Get a branch prediction from the loop
164     * predictor.
165     * @param pc The unshifted branch PC.
166     * @param bi Pointer to information on the
167     * prediction.
168     * @param speculative Use speculative number of iterations
169     * @param instShiftAmt Shift the pc by as many bits (if hashing is not
170     * used)
171     * @result the result of the prediction, if it could be predicted
172     */
173    bool getLoop(Addr pc, BranchInfo* bi, bool speculative,
174                 unsigned instShiftAmt) const;
175
176   /**
177    * Updates the loop predictor.
178    * @param pc The unshifted branch PC.
179    * @param taken The actual branch outcome.
180    * @param bi Pointer to information on the
181    * prediction recorded at prediction time.
182    * @param tage_pred tage prediction of the branch
183    * @param random0 random value
184    * @param random1 random value
185    * @param random2 random value
186    */
187    void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred,
188                    int random0, int random1, int random2);
189
190    /**
191     * Speculatively updates the loop predictor
192     * iteration count (only for useSpeculation).
193     * @param taken The predicted branch outcome.
194     * @param bi Pointer to information on the prediction
195     * recorded at prediction time.
196     */
197    void specLoopUpdate(bool taken, BranchInfo* bi);
198
199    /**
200     * Update LTAGE for conditional branches.
201     * @param branch_pc The unshifted branch PC.
202     * @param taken Actual branch outcome.
203     * @param tage_pred Prediction from TAGE
204     * @param bi Pointer to information on the prediction
205     * recorded at prediction time.
206     * @param instShiftAmt Number of bits to shift instructions
207     * @param rand0 Random integer value
208     * @param rand1 Random integer value
209     * @param rand2 Random integer value
210     */
211    void condBranchUpdate(
212        ThreadID tid, Addr branch_pc, bool taken, bool tage_pred,
213        BranchInfo* bi, unsigned instShiftAmt, int rand0, int rand1,
214        int rand2);
215
216    /**
217     * Get the loop prediction
218     * @param tid The thread ID to select the global
219     * histories to use.
220     * @param branch_pc The unshifted branch PC.
221     * @param cond_branch True if the branch is conditional.
222     * @param bi Reference to wrapping pointer to allow storing
223     * derived class prediction information in the base class.
224     * @param prev_pred_taken Result of the TAGE prediction
225     * @param instShiftAmt Shift the pc by as many bits
226     * @param instShiftAmt Shift the pc by as many bits
227     * @result the prediction, true if taken
228     */
229    bool loopPredict(
230        ThreadID tid, Addr branch_pc, bool cond_branch,
231        BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt);
232
233    /**
234     * Update the stats
235     * @param taken Actual branch outcome
236     * @param bi Pointer to information on the prediction
237     * recorded at prediction time.
238     */
239    void updateStats(bool taken, BranchInfo* bi);
240
241    void squashLoop(BranchInfo * bi);
242
243    void squash(ThreadID tid, BranchInfo *bi);
244
245    virtual bool calcConf(int index) const;
246
247    virtual bool optionalAgeInc(int nrand) const;
248
249    virtual BranchInfo *makeBranchInfo();
250
251    /**
252     * Gets the value of the loop use counter
253     * @return the loop use counter value
254     */
255    int8_t getLoopUseCounter() const
256    {
257        return loopUseCounter;
258    }
259
260    /**
261     * Initialize the loop predictor
262     */
263    void init() override;
264
265    /**
266     * Register stats for this object
267     */
268    void regStats() override;
269
270    LoopPredictor(LoopPredictorParams *p);
271};
272#endif//__CPU_PRED_LOOP_PREDICTOR_HH__
273