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/* @file
38 * Implementation of a TAGE branch predictor. TAGE is a global-history based
39 * branch predictor. It features a PC-indexed bimodal predictor and N
40 * partially tagged tables, indexed with a hash of the PC and the global
41 * branch history. The different lengths of global branch history used to
42 * index the partially tagged tables grow geometrically. A small path history
43 * is also used in the hash.
44 *
45 * All TAGE tables are accessed in parallel, and the one using the longest
46 * history that matches provides the prediction (some exceptions apply).
47 * Entries are allocated in components using a longer history than the
48 * one that predicted when the prediction is incorrect.
49 */
50
51#ifndef __CPU_PRED_TAGE_BASE
52#define __CPU_PRED_TAGE_BASE
53
54#include <vector>
55
56#include "base/statistics.hh"
57#include "cpu/static_inst.hh"
58#include "params/TAGEBase.hh"
59#include "sim/sim_object.hh"
60
61class TAGEBase : public SimObject
62{
63 public:
64 TAGEBase(const TAGEBaseParams *p);
65 void regStats() override;
66 void init() override;
67
68 protected:
69 // Prediction Structures
70
71 // Tage Entry
72 struct TageEntry
73 {
74 int8_t ctr;
75 uint16_t tag;
76 uint8_t u;
77 TageEntry() : ctr(0), tag(0), u(0) { }
78 };
79
80 // Folded History Table - compressed history
81 // to mix with instruction PC to index partially
82 // tagged tables.
83 struct FoldedHistory
84 {
85 unsigned comp;
86 int compLength;
87 int origLength;
88 int outpoint;
89 int bufferSize;
90
91 FoldedHistory()
92 {
93 comp = 0;
94 }
95
96 void init(int original_length, int compressed_length)
97 {
98 origLength = original_length;
99 compLength = compressed_length;
100 outpoint = original_length % compressed_length;
101 }
102
103 void update(uint8_t * h)
104 {
105 comp = (comp << 1) | h[0];
106 comp ^= h[origLength] << outpoint;
107 comp ^= (comp >> compLength);
108 comp &= (ULL(1) << compLength) - 1;
109 }
110 };
111
112 public:
113
114 // provider type
115 enum {
116 BIMODAL_ONLY = 0,
117 TAGE_LONGEST_MATCH,
118 BIMODAL_ALT_MATCH,
119 TAGE_ALT_MATCH,
120 LAST_TAGE_PROVIDER_TYPE = TAGE_ALT_MATCH
121 };
122
123 // Primary branch history entry
124 struct BranchInfo
125 {
126 int pathHist;
127 int ptGhist;
128 int hitBank;
129 int hitBankIndex;
130 int altBank;
131 int altBankIndex;
132 int bimodalIndex;
133
134 bool tagePred;
135 bool altTaken;
136 bool condBranch;
137 bool longestMatchPred;
138 bool pseudoNewAlloc;
139 Addr branchPC;
140
141 // Pointer to dynamically allocated storage
142 // to save table indices and folded histories.
143 // To do one call to new instead of five.
144 int *storage;
145
146 // Pointers to actual saved array within the dynamically
147 // allocated storage.
148 int *tableIndices;
149 int *tableTags;
150 int *ci;
151 int *ct0;
152 int *ct1;
153
154 // for stats purposes
155 unsigned provider;
156
157 BranchInfo(const TAGEBase &tage)
158 : pathHist(0), ptGhist(0),
159 hitBank(0), hitBankIndex(0),
160 altBank(0), altBankIndex(0),
161 bimodalIndex(0),
162 tagePred(false), altTaken(false),
163 condBranch(false), longestMatchPred(false),
164 pseudoNewAlloc(false), branchPC(0),
165 provider(-1)
166 {
167 int sz = tage.nHistoryTables + 1;
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 ~BranchInfo()
177 {
178 delete[] storage;
179 }
180 };
181
182 virtual BranchInfo *makeBranchInfo();
183
184 /**
185 * Computes the index used to access the
186 * bimodal table.
187 * @param pc_in The unshifted branch PC.
188 */
189 virtual int bindex(Addr pc_in) const;
190
191 /**
192 * Computes the index used to access a
193 * partially tagged table.
194 * @param tid The thread ID used to select the
195 * global histories to use.
196 * @param pc The unshifted branch PC.
197 * @param bank The partially tagged table to access.
198 */
199 virtual int gindex(ThreadID tid, Addr pc, int bank) const;
200
201 /**
202 * Utility function to shuffle the path history
203 * depending on which tagged table we are accessing.
204 * @param phist The path history.
205 * @param size Number of path history bits to use.
206 * @param bank The partially tagged table to access.
207 */
208 virtual int F(int phist, int size, int bank) const;
209
210 /**
211 * Computes the partial tag of a tagged table.
212 * @param tid the thread ID used to select the
213 * global histories to use.
214 * @param pc The unshifted branch PC.
215 * @param bank The partially tagged table to access.
216 */
217 virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const;
218
219 /**
220 * Updates a direction counter based on the actual
221 * branch outcome.
222 * @param ctr Reference to counter to update.
223 * @param taken Actual branch outcome.
224 * @param nbits Counter width.
225 */
226 template<typename T>
227 static void ctrUpdate(T & ctr, bool taken, int nbits);
228
229 /**
230 * Updates an unsigned counter based on up/down parameter
231 * @param ctr Reference to counter to update.
232 * @param up Boolean indicating if the counter is incremented/decremented
233 * If true it is incremented, if false it is decremented
234 * @param nbits Counter width.
235 */
236 static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);
237
238 /**
239 * Get a branch prediction from the bimodal
240 * predictor.
241 * @param pc The unshifted branch PC.
242 * @param bi Pointer to information on the
243 * prediction.
244 */
245 virtual bool getBimodePred(Addr pc, BranchInfo* bi) const;
246
247 /**
248 * Updates the bimodal predictor.
249 * @param pc The unshifted branch PC.
250 * @param taken The actual branch outcome.
251 * @param bi Pointer to information on the prediction
252 * recorded at prediction time.
253 */
254 void baseUpdate(Addr pc, bool taken, BranchInfo* bi);
255
256 /**
257 * (Speculatively) updates the global branch history.
258 * @param h Reference to pointer to global branch history.
259 * @param dir (Predicted) outcome to update the histories
260 * with.
261 * @param tab
262 * @param PT Reference to path history.
263 */
264 void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT);
265
266 /**
267 * Update TAGE. Called at execute to repair histories on a misprediction
268 * and at commit to update the tables.
269 * @param tid The thread ID to select the global
270 * histories to use.
271 * @param branch_pc The unshifted branch PC.
272 * @param taken Actual branch outcome.
273 * @param bi Pointer to information on the prediction
274 * recorded at prediction time.
275 */
276 void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);
277
278 /**
279 * (Speculatively) updates global histories (path and direction).
280 * Also recomputes compressed (folded) histories based on the
281 * branch direction.
282 * @param tid The thread ID to select the histories
283 * to update.
284 * @param branch_pc The unshifted branch PC.
285 * @param taken (Predicted) branch direction.
286 * @param b Wrapping pointer to BranchInfo (to allow
287 * storing derived class prediction information in the
288 * base class).
289 */
290 virtual void updateHistories(
291 ThreadID tid, Addr branch_pc, bool taken, BranchInfo* b,
292 bool speculative,
293 const StaticInstPtr & inst = StaticInst::nullStaticInstPtr,
294 Addr target = MaxAddr);
295
296 /**
297 * Restores speculatively updated path and direction histories.
298 * Also recomputes compressed (folded) histories based on the
299 * correct branch outcome.
300 * This version of squash() is called once on a branch misprediction.
301 * @param tid The Thread ID to select the histories to rollback.
302 * @param taken The correct branch outcome.
303 * @param bp_history Wrapping pointer to BranchInfo (to allow
304 * storing derived class prediction information in the
305 * base class).
306 * @param target The correct branch target
307 * @post bp_history points to valid memory.
308 */
309 virtual void squash(
310 ThreadID tid, bool taken, BranchInfo *bi, Addr target);
311
312 /**
313 * Update TAGE for conditional branches.
314 * @param branch_pc The unshifted branch PC.
315 * @param taken Actual branch outcome.
316 * @param bi Pointer to information on the prediction
317 * recorded at prediction time.
318 * @nrand Random int number from 0 to 3
319 * @param corrTarget The correct branch target
| 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/* @file
38 * Implementation of a TAGE branch predictor. TAGE is a global-history based
39 * branch predictor. It features a PC-indexed bimodal predictor and N
40 * partially tagged tables, indexed with a hash of the PC and the global
41 * branch history. The different lengths of global branch history used to
42 * index the partially tagged tables grow geometrically. A small path history
43 * is also used in the hash.
44 *
45 * All TAGE tables are accessed in parallel, and the one using the longest
46 * history that matches provides the prediction (some exceptions apply).
47 * Entries are allocated in components using a longer history than the
48 * one that predicted when the prediction is incorrect.
49 */
50
51#ifndef __CPU_PRED_TAGE_BASE
52#define __CPU_PRED_TAGE_BASE
53
54#include <vector>
55
56#include "base/statistics.hh"
57#include "cpu/static_inst.hh"
58#include "params/TAGEBase.hh"
59#include "sim/sim_object.hh"
60
61class TAGEBase : public SimObject
62{
63 public:
64 TAGEBase(const TAGEBaseParams *p);
65 void regStats() override;
66 void init() override;
67
68 protected:
69 // Prediction Structures
70
71 // Tage Entry
72 struct TageEntry
73 {
74 int8_t ctr;
75 uint16_t tag;
76 uint8_t u;
77 TageEntry() : ctr(0), tag(0), u(0) { }
78 };
79
80 // Folded History Table - compressed history
81 // to mix with instruction PC to index partially
82 // tagged tables.
83 struct FoldedHistory
84 {
85 unsigned comp;
86 int compLength;
87 int origLength;
88 int outpoint;
89 int bufferSize;
90
91 FoldedHistory()
92 {
93 comp = 0;
94 }
95
96 void init(int original_length, int compressed_length)
97 {
98 origLength = original_length;
99 compLength = compressed_length;
100 outpoint = original_length % compressed_length;
101 }
102
103 void update(uint8_t * h)
104 {
105 comp = (comp << 1) | h[0];
106 comp ^= h[origLength] << outpoint;
107 comp ^= (comp >> compLength);
108 comp &= (ULL(1) << compLength) - 1;
109 }
110 };
111
112 public:
113
114 // provider type
115 enum {
116 BIMODAL_ONLY = 0,
117 TAGE_LONGEST_MATCH,
118 BIMODAL_ALT_MATCH,
119 TAGE_ALT_MATCH,
120 LAST_TAGE_PROVIDER_TYPE = TAGE_ALT_MATCH
121 };
122
123 // Primary branch history entry
124 struct BranchInfo
125 {
126 int pathHist;
127 int ptGhist;
128 int hitBank;
129 int hitBankIndex;
130 int altBank;
131 int altBankIndex;
132 int bimodalIndex;
133
134 bool tagePred;
135 bool altTaken;
136 bool condBranch;
137 bool longestMatchPred;
138 bool pseudoNewAlloc;
139 Addr branchPC;
140
141 // Pointer to dynamically allocated storage
142 // to save table indices and folded histories.
143 // To do one call to new instead of five.
144 int *storage;
145
146 // Pointers to actual saved array within the dynamically
147 // allocated storage.
148 int *tableIndices;
149 int *tableTags;
150 int *ci;
151 int *ct0;
152 int *ct1;
153
154 // for stats purposes
155 unsigned provider;
156
157 BranchInfo(const TAGEBase &tage)
158 : pathHist(0), ptGhist(0),
159 hitBank(0), hitBankIndex(0),
160 altBank(0), altBankIndex(0),
161 bimodalIndex(0),
162 tagePred(false), altTaken(false),
163 condBranch(false), longestMatchPred(false),
164 pseudoNewAlloc(false), branchPC(0),
165 provider(-1)
166 {
167 int sz = tage.nHistoryTables + 1;
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 ~BranchInfo()
177 {
178 delete[] storage;
179 }
180 };
181
182 virtual BranchInfo *makeBranchInfo();
183
184 /**
185 * Computes the index used to access the
186 * bimodal table.
187 * @param pc_in The unshifted branch PC.
188 */
189 virtual int bindex(Addr pc_in) const;
190
191 /**
192 * Computes the index used to access a
193 * partially tagged table.
194 * @param tid The thread ID used to select the
195 * global histories to use.
196 * @param pc The unshifted branch PC.
197 * @param bank The partially tagged table to access.
198 */
199 virtual int gindex(ThreadID tid, Addr pc, int bank) const;
200
201 /**
202 * Utility function to shuffle the path history
203 * depending on which tagged table we are accessing.
204 * @param phist The path history.
205 * @param size Number of path history bits to use.
206 * @param bank The partially tagged table to access.
207 */
208 virtual int F(int phist, int size, int bank) const;
209
210 /**
211 * Computes the partial tag of a tagged table.
212 * @param tid the thread ID used to select the
213 * global histories to use.
214 * @param pc The unshifted branch PC.
215 * @param bank The partially tagged table to access.
216 */
217 virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const;
218
219 /**
220 * Updates a direction counter based on the actual
221 * branch outcome.
222 * @param ctr Reference to counter to update.
223 * @param taken Actual branch outcome.
224 * @param nbits Counter width.
225 */
226 template<typename T>
227 static void ctrUpdate(T & ctr, bool taken, int nbits);
228
229 /**
230 * Updates an unsigned counter based on up/down parameter
231 * @param ctr Reference to counter to update.
232 * @param up Boolean indicating if the counter is incremented/decremented
233 * If true it is incremented, if false it is decremented
234 * @param nbits Counter width.
235 */
236 static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);
237
238 /**
239 * Get a branch prediction from the bimodal
240 * predictor.
241 * @param pc The unshifted branch PC.
242 * @param bi Pointer to information on the
243 * prediction.
244 */
245 virtual bool getBimodePred(Addr pc, BranchInfo* bi) const;
246
247 /**
248 * Updates the bimodal predictor.
249 * @param pc The unshifted branch PC.
250 * @param taken The actual branch outcome.
251 * @param bi Pointer to information on the prediction
252 * recorded at prediction time.
253 */
254 void baseUpdate(Addr pc, bool taken, BranchInfo* bi);
255
256 /**
257 * (Speculatively) updates the global branch history.
258 * @param h Reference to pointer to global branch history.
259 * @param dir (Predicted) outcome to update the histories
260 * with.
261 * @param tab
262 * @param PT Reference to path history.
263 */
264 void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT);
265
266 /**
267 * Update TAGE. Called at execute to repair histories on a misprediction
268 * and at commit to update the tables.
269 * @param tid The thread ID to select the global
270 * histories to use.
271 * @param branch_pc The unshifted branch PC.
272 * @param taken Actual branch outcome.
273 * @param bi Pointer to information on the prediction
274 * recorded at prediction time.
275 */
276 void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);
277
278 /**
279 * (Speculatively) updates global histories (path and direction).
280 * Also recomputes compressed (folded) histories based on the
281 * branch direction.
282 * @param tid The thread ID to select the histories
283 * to update.
284 * @param branch_pc The unshifted branch PC.
285 * @param taken (Predicted) branch direction.
286 * @param b Wrapping pointer to BranchInfo (to allow
287 * storing derived class prediction information in the
288 * base class).
289 */
290 virtual void updateHistories(
291 ThreadID tid, Addr branch_pc, bool taken, BranchInfo* b,
292 bool speculative,
293 const StaticInstPtr & inst = StaticInst::nullStaticInstPtr,
294 Addr target = MaxAddr);
295
296 /**
297 * Restores speculatively updated path and direction histories.
298 * Also recomputes compressed (folded) histories based on the
299 * correct branch outcome.
300 * This version of squash() is called once on a branch misprediction.
301 * @param tid The Thread ID to select the histories to rollback.
302 * @param taken The correct branch outcome.
303 * @param bp_history Wrapping pointer to BranchInfo (to allow
304 * storing derived class prediction information in the
305 * base class).
306 * @param target The correct branch target
307 * @post bp_history points to valid memory.
308 */
309 virtual void squash(
310 ThreadID tid, bool taken, BranchInfo *bi, Addr target);
311
312 /**
313 * Update TAGE for conditional branches.
314 * @param branch_pc The unshifted branch PC.
315 * @param taken Actual branch outcome.
316 * @param bi Pointer to information on the prediction
317 * recorded at prediction time.
318 * @nrand Random int number from 0 to 3
319 * @param corrTarget The correct branch target
|