ltage.hh (13444:26f81be73cb7) ltage.hh (13454:19a5b4fb1f1f)
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.

--- 38 unchanged lines hidden (view full) ---

47 * history that matches provides the prediction (some exceptions apply).
48 * Entries are allocated in components using a longer history than the
49 * one that predicted when the prediction is incorrect.
50 */
51
52#ifndef __CPU_PRED_LTAGE
53#define __CPU_PRED_LTAGE
54
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.

--- 38 unchanged lines hidden (view full) ---

47 * history that matches provides the prediction (some exceptions apply).
48 * Entries are allocated in components using a longer history than the
49 * one that predicted when the prediction is incorrect.
50 */
51
52#ifndef __CPU_PRED_LTAGE
53#define __CPU_PRED_LTAGE
54
55
55#include <vector>
56
57#include "base/types.hh"
56#include <vector>
57
58#include "base/types.hh"
58#include "cpu/pred/bpred_unit.hh"
59#include "cpu/pred/tage.hh"
59#include "params/LTAGE.hh"
60
60#include "params/LTAGE.hh"
61
61class LTAGE: public BPredUnit
62class LTAGE: public TAGE
62{
63 public:
64 LTAGE(const LTAGEParams *params);
65
66 // Base class methods.
63{
64 public:
65 LTAGE(const LTAGEParams *params);
66
67 // Base class methods.
67 void uncondBranch(ThreadID tid, Addr br_pc, void* &bp_history) override;
68 bool lookup(ThreadID tid, Addr branch_addr, void* &bp_history) override;
69 void btbUpdate(ThreadID tid, Addr branch_addr, void* &bp_history) override;
70 void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
71 bool squashed) override;
72 void squash(ThreadID tid, void *bp_history) override;
68 void squash(ThreadID tid, void *bp_history) override;
73 unsigned getGHR(ThreadID tid, void *bp_history) const override;
74
75 private:
76 // Prediction Structures
77 // Loop Predictor Entry
78 struct LoopEntry
79 {
80 uint16_t numIter;
81 uint16_t currentIter;
82 uint16_t currentIterSpec;
83 uint8_t confidence;
84 uint16_t tag;
85 uint8_t age;
86 bool dir;
87
88 LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
89 confidence(0), tag(0), age(0), dir(0) { }
90 };
91
69
70 private:
71 // Prediction Structures
72 // Loop Predictor Entry
73 struct LoopEntry
74 {
75 uint16_t numIter;
76 uint16_t currentIter;
77 uint16_t currentIterSpec;
78 uint8_t confidence;
79 uint16_t tag;
80 uint8_t age;
81 bool dir;
82
83 LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
84 confidence(0), tag(0), age(0), dir(0) { }
85 };
86
92 // Tage Entry
93 struct TageEntry
94 {
95 int8_t ctr;
96 uint16_t tag;
97 uint8_t u;
98 TageEntry() : ctr(0), tag(0), u(0) { }
99 };
100
101 // Folded History Table - compressed history
102 // to mix with instruction PC to index partially
103 // tagged tables.
104 struct FoldedHistory
105 {
106 unsigned comp;
107 int compLength;
108 int origLength;
109 int outpoint;
110
111 void init(int original_length, int compressed_length)
112 {
113 comp = 0;
114 origLength = original_length;
115 compLength = compressed_length;
116 outpoint = original_length % compressed_length;
117 }
118
119 void update(uint8_t * h)
120 {
121 comp = (comp << 1) | h[0];
122 comp ^= h[origLength] << outpoint;
123 comp ^= (comp >> compLength);
124 comp &= (ULL(1) << compLength) - 1;
125 }
126 };
127
128 // Primary branch history entry
87 // Primary branch history entry
129 struct BranchInfo
88 struct LTageBranchInfo : public TageBranchInfo
130 {
89 {
131 int pathHist;
132 int ptGhist;
133 int hitBank;
134 int hitBankIndex;
135 int altBank;
136 int altBankIndex;
137 int bimodalIndex;
138 uint16_t loopTag;
139 uint16_t currentIter;
140
90 uint16_t loopTag;
91 uint16_t currentIter;
92
141 bool tagePred;
142 bool altTaken;
143 bool loopPred;
144 bool loopPredValid;
145 int loopIndex;
146 int loopHit;
93 bool loopPred;
94 bool loopPredValid;
95 int loopIndex;
96 int loopHit;
147 bool condBranch;
148 bool longestMatchPred;
149 bool pseudoNewAlloc;
150 Addr branchPC;
151
97
152 // Pointer to dynamically allocated storage
153 // to save table indices and folded histories.
154 // To do one call to new instead of five.
155 int *storage;
156
157 // Pointers to actual saved array within the dynamically
158 // allocated storage.
159 int *tableIndices;
160 int *tableTags;
161 int *ci;
162 int *ct0;
163 int *ct1;
164
165 BranchInfo(int sz)
166 : pathHist(0), ptGhist(0),
167 hitBank(0), hitBankIndex(0),
168 altBank(0), altBankIndex(0),
169 bimodalIndex(0), loopTag(0), currentIter(0),
170 tagePred(false), altTaken(false), loopPred(false),
171 loopPredValid(false), loopIndex(0), loopHit(0),
172 condBranch(false), longestMatchPred(false),
173 pseudoNewAlloc(false), branchPC(0)
174 {
175 storage = new int [sz * 5];
176 tableIndices = storage;
177 tableTags = storage + sz;
178 ci = tableTags + sz;
179 ct0 = ci + sz;
180 ct1 = ct0 + sz;
181 }
182
183 ~BranchInfo()
184 {
185 delete[] storage;
186 }
98 LTageBranchInfo(int sz)
99 : TageBranchInfo(sz),
100 loopTag(0), currentIter(0),
101 loopPred(false),
102 loopPredValid(false), loopIndex(0), loopHit(0)
103 {}
187 };
188
189 /**
190 * Computes the index used to access the
104 };
105
106 /**
107 * Computes the index used to access the
191 * bimodal table.
192 * @param pc_in The unshifted branch PC.
193 */
194 int bindex(Addr pc_in) const;
195
196 /**
197 * Computes the index used to access the
198 * loop predictor.
199 * @param pc_in The unshifted branch PC.
200 */
201 int lindex(Addr pc_in) const;
202
203 /**
108 * loop predictor.
109 * @param pc_in The unshifted branch PC.
110 */
111 int lindex(Addr pc_in) const;
112
113 /**
204 * Computes the index used to access a
205 * partially tagged table.
206 * @param tid The thread ID used to select the
207 * global histories to use.
208 * @param pc The unshifted branch PC.
209 * @param bank The partially tagged table to access.
210 */
211 inline int gindex(ThreadID tid, Addr pc, int bank) const;
212
213 /**
214 * Utility function to shuffle the path history
215 * depending on which tagged table we are accessing.
216 * @param phist The path history.
217 * @param size Number of path history bits to use.
218 * @param bank The partially tagged table to access.
219 */
220 int F(int phist, int size, int bank) const;
221
222 /**
223 * Computes the partial tag of a tagged table.
224 * @param tid the thread ID used to select the
225 * global histories to use.
226 * @param pc The unshifted branch PC.
227 * @param bank The partially tagged table to access.
228 */
229 inline uint16_t gtag(ThreadID tid, Addr pc, int bank) const;
230
231 /**
232 * Updates a direction counter based on the actual
233 * branch outcome.
234 * @param ctr Reference to counter to update.
235 * @param taken Actual branch outcome.
236 * @param nbits Counter width.
237 */
238 void ctrUpdate(int8_t & ctr, bool taken, int nbits);
239
240 /**
241 * Updates an unsigned counter based on up/down parameter
242 * @param ctr Reference to counter to update.
243 * @param up Boolean indicating if the counter is incremented/decremented
244 * If true it is incremented, if false it is decremented
245 * @param nbits Counter width.
246 */
247 void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);
248
249 /**
250 * Get a branch prediction from the bimodal
251 * predictor.
252 * @param pc The unshifted branch PC.
253 * @param bi Pointer to information on the
254 * prediction.
255 */
256 bool getBimodePred(Addr pc, BranchInfo* bi) const;
257
258 /**
259 * Updates the bimodal predictor.
260 * @param pc The unshifted branch PC.
261 * @param taken The actual branch outcome.
262 * @param bi Pointer to information on the prediction
263 * recorded at prediction time.
264 */
265 void baseUpdate(Addr pc, bool taken, BranchInfo* bi);
266
267 /**
268 * Get a branch prediction from the loop
269 * predictor.
270 * @param pc The unshifted branch PC.
271 * @param bi Pointer to information on the
272 * prediction.
273 */
114 * Get a branch prediction from the loop
115 * predictor.
116 * @param pc The unshifted branch PC.
117 * @param bi Pointer to information on the
118 * prediction.
119 */
274 bool getLoop(Addr pc, BranchInfo* bi) const;
120 bool getLoop(Addr pc, LTageBranchInfo* bi) const;
275
276 /**
277 * Updates the loop predictor.
278 * @param pc The unshifted branch PC.
279 * @param taken The actual branch outcome.
280 * @param bi Pointer to information on the
281 * prediction recorded at prediction time.
282 */
121
122 /**
123 * Updates the loop predictor.
124 * @param pc The unshifted branch PC.
125 * @param taken The actual branch outcome.
126 * @param bi Pointer to information on the
127 * prediction recorded at prediction time.
128 */
283 void loopUpdate(Addr pc, bool Taken, BranchInfo* bi);
129 void loopUpdate(Addr pc, bool Taken, LTageBranchInfo* bi);
284
130
285 /**
286 * (Speculatively) updates the global branch history.
287 * @param h Reference to pointer to global branch history.
288 * @param dir (Predicted) outcome to update the histories
289 * with.
290 * @param tab
291 * @param PT Reference to path history.
292 */
293 void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT);
131 /**
132 * Speculatively updates the loop predictor
133 * iteration count.
134 * @param pc The unshifted branch PC.
135 * @param taken The predicted branch outcome.
136 * @param bi Pointer to information on the prediction
137 * recorded at prediction time.
138 */
139 void specLoopUpdate(Addr pc, bool taken, LTageBranchInfo* bi);
294
295 /**
140
141 /**
296 * Get a branch prediction from L-TAGE. *NOT* an override of
142 * Update LTAGE for conditional branches.
143 * @param branch_pc The unshifted branch PC.
144 * @param taken Actual branch outcome.
145 * @param bi Pointer to information on the prediction
146 * recorded at prediction time.
147 * @nrand Random int number from 0 to 3
148 */
149 void condBranchUpdate(
150 Addr branch_pc, bool taken, TageBranchInfo* bi, int nrand) override;
151
152 /**
153 * Get a branch prediction from LTAGE. *NOT* an override of
297 * BpredUnit::predict().
298 * @param tid The thread ID to select the global
299 * histories to use.
300 * @param branch_pc The unshifted branch PC.
301 * @param cond_branch True if the branch is conditional.
302 * @param b Reference to wrapping pointer to allow storing
303 * derived class prediction information in the base class.
304 */
154 * BpredUnit::predict().
155 * @param tid The thread ID to select the global
156 * histories to use.
157 * @param branch_pc The unshifted branch PC.
158 * @param cond_branch True if the branch is conditional.
159 * @param b Reference to wrapping pointer to allow storing
160 * derived class prediction information in the base class.
161 */
305 bool predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b);
162 bool predict(
163 ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override;
306
307 /**
164
165 /**
308 * Update L-TAGE. Called at execute to repair histories on a misprediction
309 * and at commit to update the tables.
310 * @param tid The thread ID to select the global
311 * histories to use.
312 * @param branch_pc The unshifted branch PC.
313 * @param taken Actual branch outcome.
314 * @param bi Pointer to information on the prediction
315 * recorded at prediction time.
316 */
317 void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);
318
319 /**
320 * (Speculatively) updates global histories (path and direction).
321 * Also recomputes compressed (folded) histories based on the
322 * branch direction.
323 * @param tid The thread ID to select the histories
324 * to update.
325 * @param branch_pc The unshifted branch PC.
326 * @param taken (Predicted) branch direction.
327 * @param b Wrapping pointer to BranchInfo (to allow
328 * storing derived class prediction information in the
329 * base class).
330 */
331 void updateHistories(ThreadID tid, Addr branch_pc, bool taken, void* b);
332
333 /**
334 * Restores speculatively updated path and direction histories.
335 * Also recomputes compressed (folded) histories based on the
336 * correct branch outcome.
337 * This version of squash() is called once on a branch misprediction.
338 * @param tid The Thread ID to select the histories to rollback.
339 * @param taken The correct branch outcome.
166 * Restores speculatively updated path and direction histories.
167 * Also recomputes compressed (folded) histories based on the
168 * correct branch outcome.
169 * This version of squash() is called once on a branch misprediction.
170 * @param tid The Thread ID to select the histories to rollback.
171 * @param taken The correct branch outcome.
340 * @param bp_history Wrapping pointer to BranchInfo (to allow
172 * @param bp_history Wrapping pointer to TageBranchInfo (to allow
341 * storing derived class prediction information in the
342 * base class).
343 * @post bp_history points to valid memory.
344 */
173 * storing derived class prediction information in the
174 * base class).
175 * @post bp_history points to valid memory.
176 */
345 void squash(ThreadID tid, bool taken, void *bp_history);
177 void squash(
178 ThreadID tid, bool taken, void *bp_history) override;
346
179
347 /**
348 * Speculatively updates the loop predictor
349 * iteration count.
350 * @param pc The unshifted branch PC.
351 * @param taken The predicted branch outcome.
352 * @param bi Pointer to information on the prediction
353 * recorded at prediction time.
354 */
355 void specLoopUpdate(Addr pc, bool taken, BranchInfo* bi);
356
357 const unsigned logRatioBiModalHystEntries;
358 const unsigned logSizeLoopPred;
180 const unsigned logSizeLoopPred;
359 const unsigned nHistoryTables;
360 const unsigned tagTableCounterBits;
361 const unsigned tagTableUBits;
362 const unsigned histBufferSize;
363 const unsigned minHist;
364 const unsigned maxHist;
365 const unsigned pathHistBits;
366 const unsigned loopTableAgeBits;
367 const unsigned loopTableConfidenceBits;
368 const unsigned loopTableTagBits;
369 const unsigned loopTableIterBits;
370 const unsigned logLoopTableAssoc;
371 const uint8_t confidenceThreshold;
372 const uint16_t loopTagMask;
373 const uint16_t loopNumIterMask;
374
181 const unsigned loopTableAgeBits;
182 const unsigned loopTableConfidenceBits;
183 const unsigned loopTableTagBits;
184 const unsigned loopTableIterBits;
185 const unsigned logLoopTableAssoc;
186 const uint8_t confidenceThreshold;
187 const uint16_t loopTagMask;
188 const uint16_t loopNumIterMask;
189
375 const std::vector<unsigned> tagTableTagWidths;
376 const std::vector<int> logTagTableSizes;
377
378 std::vector<bool> btablePrediction;
379 std::vector<bool> btableHysteresis;
380 TageEntry **gtable;
381 LoopEntry *ltable;
382
190 LoopEntry *ltable;
191
383 // Keep per-thread histories to
384 // support SMT.
385 struct ThreadHistory {
386 // Speculative path history
387 // (LSB of branch address)
388 int pathHist;
389
390 // Speculative branch direction
391 // history (circular buffer)
392 // @TODO Convert to std::vector<bool>
393 uint8_t *globalHistory;
394
395 // Pointer to most recent branch outcome
396 uint8_t* gHist;
397
398 // Index to most recent branch outcome
399 int ptGhist;
400
401 // Speculative folded histories.
402 FoldedHistory *computeIndices;
403 FoldedHistory *computeTags[2];
404 };
405
406 std::vector<ThreadHistory> threadHistory;
407
408 int *histLengths;
409 int *tableIndices;
410 int *tableTags;
411
412 int8_t loopUseCounter;
192 int8_t loopUseCounter;
413 int8_t useAltPredForNewlyAllocated;
414 uint64_t tCounter;
415 uint64_t logUResetPeriod;
416 unsigned useAltOnNaBits;
417 unsigned withLoopBits;
418};
419
420#endif // __CPU_PRED_LTAGE
193 unsigned withLoopBits;
194};
195
196#endif // __CPU_PRED_LTAGE