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
| 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
|
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
| 206
207 /**
208 * Get the loop prediction
209 * @param tid The thread ID to select the global
210 * histories to use.
211 * @param branch_pc The unshifted branch PC.
212 * @param cond_branch True if the branch is conditional.
213 * @param bi Reference to wrapping pointer to allow storing
214 * derived class prediction information in the base class.
215 * @param prev_pred_taken Result of the TAGE prediction
216 * @param instShiftAmt Shift the pc by as many bits
217 * @param instShiftAmt Shift the pc by as many bits
218 * @result the prediction, true if taken
219 */
220 bool loopPredict(
221 ThreadID tid, Addr branch_pc, bool cond_branch,
222 BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt);
223
224 /**
225 * Update the stats
226 * @param taken Actual branch outcome
227 * @param bi Pointer to information on the prediction
228 * recorded at prediction time.
229 */
230 void updateStats(bool taken, BranchInfo* bi);
231
232 void squashLoop(BranchInfo * bi);
233
234 void squash(ThreadID tid, BranchInfo *bi);
235
236 virtual bool calcConf(int index) const;
237
|