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 |
56#include <vector> 57 58#include "base/types.hh"
|
58#include "cpu/pred/bpred_unit.hh"
|
59#include "cpu/pred/tage.hh" |
60#include "params/LTAGE.hh" 61
|
61class LTAGE: public BPredUnit
|
62class LTAGE: public TAGE |
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;
|
68 void squash(ThreadID tid, void *bp_history) override;
|
73 unsigned getGHR(ThreadID tid, void *bp_history) const override;
|
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
|
87 // Primary branch history entry
|
129 struct BranchInfo
|
88 struct LTageBranchInfo : public TageBranchInfo |
89 {
|
131 int pathHist;
132 int ptGhist;
133 int hitBank;
134 int hitBankIndex;
135 int altBank;
136 int altBankIndex;
137 int bimodalIndex;
|
90 uint16_t loopTag; 91 uint16_t currentIter; 92
|
141 bool tagePred;
142 bool altTaken;
|
93 bool loopPred; 94 bool loopPredValid; 95 int loopIndex; 96 int loopHit;
|
147 bool condBranch;
148 bool longestMatchPred;
149 bool pseudoNewAlloc;
150 Addr branchPC;
|
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 {} |
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
|
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 /**
|
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; |
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); |
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); |
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 |
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; |
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 /**
|
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 |
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; |
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;
|
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;
|
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;
|
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
|
192 int8_t loopUseCounter;
|
413 int8_t useAltPredForNewlyAllocated;
414 uint64_t tCounter;
415 uint64_t logUResetPeriod;
416 unsigned useAltOnNaBits;
|
193 unsigned withLoopBits; 194}; 195 196#endif // __CPU_PRED_LTAGE
|