tage.hh (13455:56e25a5f9603) tage.hh (13626:d6a6358aa6db)
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.

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

50
51#ifndef __CPU_PRED_TAGE
52#define __CPU_PRED_TAGE
53
54#include <vector>
55
56#include "base/types.hh"
57#include "cpu/pred/bpred_unit.hh"
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.

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

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