1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Kevin Lim
29 */
30
31#include "base/intmath.hh"
32#include "cpu/pred/tournament.hh"
33
34TournamentBP::TournamentBP(unsigned _localPredictorSize,
35 unsigned _localCtrBits,
36 unsigned _localHistoryTableSize,
37 unsigned _localHistoryBits,
38 unsigned _globalPredictorSize,
| 1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Kevin Lim
29 */
30
31#include "base/intmath.hh"
32#include "cpu/pred/tournament.hh"
33
34TournamentBP::TournamentBP(unsigned _localPredictorSize,
35 unsigned _localCtrBits,
36 unsigned _localHistoryTableSize,
37 unsigned _localHistoryBits,
38 unsigned _globalPredictorSize,
|
39 unsigned _globalCtrBits,
| |
40 unsigned _globalHistoryBits,
| 39 unsigned _globalHistoryBits,
|
| 40 unsigned _globalCtrBits,
|
41 unsigned _choicePredictorSize,
42 unsigned _choiceCtrBits,
43 unsigned _instShiftAmt)
44 : localPredictorSize(_localPredictorSize),
45 localCtrBits(_localCtrBits),
46 localHistoryTableSize(_localHistoryTableSize),
47 localHistoryBits(_localHistoryBits),
48 globalPredictorSize(_globalPredictorSize),
49 globalCtrBits(_globalCtrBits),
50 globalHistoryBits(_globalHistoryBits),
51 choicePredictorSize(_globalPredictorSize),
52 choiceCtrBits(_choiceCtrBits),
53 instShiftAmt(_instShiftAmt)
54{
55 if (!isPowerOf2(localPredictorSize)) {
56 fatal("Invalid local predictor size!\n");
57 }
58
59 //Setup the array of counters for the local predictor
60 localCtrs.resize(localPredictorSize);
61
62 for (int i = 0; i < localPredictorSize; ++i)
63 localCtrs[i].setBits(localCtrBits);
64
65 localPredictorMask = floorPow2(localPredictorSize) - 1;
66
67 if (!isPowerOf2(localHistoryTableSize)) {
68 fatal("Invalid local history table size!\n");
69 }
70
71 //Setup the history table for the local table
72 localHistoryTable.resize(localHistoryTableSize);
73
74 for (int i = 0; i < localHistoryTableSize; ++i)
75 localHistoryTable[i] = 0;
76
77 // Setup the local history mask
78 localHistoryMask = (1 << localHistoryBits) - 1;
79
80 if (!isPowerOf2(globalPredictorSize)) {
81 fatal("Invalid global predictor size!\n");
82 }
83
84 //Setup the array of counters for the global predictor
85 globalCtrs.resize(globalPredictorSize);
86
87 for (int i = 0; i < globalPredictorSize; ++i)
88 globalCtrs[i].setBits(globalCtrBits);
89
90 //Clear the global history
91 globalHistory = 0;
92 // Setup the global history mask
93 globalHistoryMask = (1 << globalHistoryBits) - 1;
94
95 if (!isPowerOf2(choicePredictorSize)) {
96 fatal("Invalid choice predictor size!\n");
97 }
98
99 //Setup the array of counters for the choice predictor
100 choiceCtrs.resize(choicePredictorSize);
101
102 for (int i = 0; i < choicePredictorSize; ++i)
103 choiceCtrs[i].setBits(choiceCtrBits);
104
105 // @todo: Allow for different thresholds between the predictors.
106 threshold = (1 << (localCtrBits - 1)) - 1;
107}
108
109inline
110unsigned
111TournamentBP::calcLocHistIdx(Addr &branch_addr)
112{
113 // Get low order bits after removing instruction offset.
114 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
115}
116
117inline
118void
119TournamentBP::updateGlobalHistTaken()
120{
121 globalHistory = (globalHistory << 1) | 1;
122 globalHistory = globalHistory & globalHistoryMask;
123}
124
125inline
126void
127TournamentBP::updateGlobalHistNotTaken()
128{
129 globalHistory = (globalHistory << 1);
130 globalHistory = globalHistory & globalHistoryMask;
131}
132
133inline
134void
135TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
136{
137 localHistoryTable[local_history_idx] =
138 (localHistoryTable[local_history_idx] << 1) | 1;
139}
140
141inline
142void
143TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
144{
145 localHistoryTable[local_history_idx] =
146 (localHistoryTable[local_history_idx] << 1);
147}
148
149bool
150TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
151{
152 bool local_prediction;
153 unsigned local_history_idx;
154 unsigned local_predictor_idx;
155
156 bool global_prediction;
157 bool choice_prediction;
158
159 //Lookup in the local predictor to get its branch prediction
160 local_history_idx = calcLocHistIdx(branch_addr);
161 local_predictor_idx = localHistoryTable[local_history_idx]
162 & localPredictorMask;
163 local_prediction = localCtrs[local_predictor_idx].read() > threshold;
164
165 //Lookup in the global predictor to get its branch prediction
166 global_prediction = globalCtrs[globalHistory].read() > threshold;
167
168 //Lookup in the choice predictor to see which one to use
169 choice_prediction = choiceCtrs[globalHistory].read() > threshold;
170
171 // Create BPHistory and pass it back to be recorded.
172 BPHistory *history = new BPHistory;
173 history->globalHistory = globalHistory;
174 history->localPredTaken = local_prediction;
175 history->globalPredTaken = global_prediction;
176 history->globalUsed = choice_prediction;
177 bp_history = (void *)history;
178
179 assert(globalHistory < globalPredictorSize &&
180 local_history_idx < localHistoryTableSize &&
181 local_predictor_idx < localPredictorSize);
182
183 // Commented code is for doing speculative update of counters and
184 // all histories.
185 if (choice_prediction) {
186 if (global_prediction) {
187// updateHistoriesTaken(local_history_idx);
188// globalCtrs[globalHistory].increment();
189// localCtrs[local_history_idx].increment();
190 updateGlobalHistTaken();
191 return true;
192 } else {
193// updateHistoriesNotTaken(local_history_idx);
194// globalCtrs[globalHistory].decrement();
195// localCtrs[local_history_idx].decrement();
196 updateGlobalHistNotTaken();
197 return false;
198 }
199 } else {
200 if (local_prediction) {
201// updateHistoriesTaken(local_history_idx);
202// globalCtrs[globalHistory].increment();
203// localCtrs[local_history_idx].increment();
204 updateGlobalHistTaken();
205 return true;
206 } else {
207// updateHistoriesNotTaken(local_history_idx);
208// globalCtrs[globalHistory].decrement();
209// localCtrs[local_history_idx].decrement();
210 updateGlobalHistNotTaken();
211 return false;
212 }
213 }
214}
215
216void
217TournamentBP::uncondBr(void * &bp_history)
218{
219 // Create BPHistory and pass it back to be recorded.
220 BPHistory *history = new BPHistory;
221 history->globalHistory = globalHistory;
222 history->localPredTaken = true;
223 history->globalPredTaken = true;
224 bp_history = static_cast<void *>(history);
225
226 updateGlobalHistTaken();
227}
228
229void
230TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
231{
232 unsigned local_history_idx;
233 unsigned local_predictor_idx;
234 unsigned local_predictor_hist;
235
236 // Get the local predictor's current prediction
237 local_history_idx = calcLocHistIdx(branch_addr);
238 local_predictor_hist = localHistoryTable[local_history_idx];
239 local_predictor_idx = local_predictor_hist & localPredictorMask;
240
241 // Update the choice predictor to tell it which one was correct if
242 // there was a prediction.
243 if (bp_history) {
244 BPHistory *history = static_cast<BPHistory *>(bp_history);
245 if (history->localPredTaken != history->globalPredTaken) {
246 // If the local prediction matches the actual outcome,
247 // decerement the counter. Otherwise increment the
248 // counter.
249 if (history->localPredTaken == taken) {
| 41 unsigned _choicePredictorSize,
42 unsigned _choiceCtrBits,
43 unsigned _instShiftAmt)
44 : localPredictorSize(_localPredictorSize),
45 localCtrBits(_localCtrBits),
46 localHistoryTableSize(_localHistoryTableSize),
47 localHistoryBits(_localHistoryBits),
48 globalPredictorSize(_globalPredictorSize),
49 globalCtrBits(_globalCtrBits),
50 globalHistoryBits(_globalHistoryBits),
51 choicePredictorSize(_globalPredictorSize),
52 choiceCtrBits(_choiceCtrBits),
53 instShiftAmt(_instShiftAmt)
54{
55 if (!isPowerOf2(localPredictorSize)) {
56 fatal("Invalid local predictor size!\n");
57 }
58
59 //Setup the array of counters for the local predictor
60 localCtrs.resize(localPredictorSize);
61
62 for (int i = 0; i < localPredictorSize; ++i)
63 localCtrs[i].setBits(localCtrBits);
64
65 localPredictorMask = floorPow2(localPredictorSize) - 1;
66
67 if (!isPowerOf2(localHistoryTableSize)) {
68 fatal("Invalid local history table size!\n");
69 }
70
71 //Setup the history table for the local table
72 localHistoryTable.resize(localHistoryTableSize);
73
74 for (int i = 0; i < localHistoryTableSize; ++i)
75 localHistoryTable[i] = 0;
76
77 // Setup the local history mask
78 localHistoryMask = (1 << localHistoryBits) - 1;
79
80 if (!isPowerOf2(globalPredictorSize)) {
81 fatal("Invalid global predictor size!\n");
82 }
83
84 //Setup the array of counters for the global predictor
85 globalCtrs.resize(globalPredictorSize);
86
87 for (int i = 0; i < globalPredictorSize; ++i)
88 globalCtrs[i].setBits(globalCtrBits);
89
90 //Clear the global history
91 globalHistory = 0;
92 // Setup the global history mask
93 globalHistoryMask = (1 << globalHistoryBits) - 1;
94
95 if (!isPowerOf2(choicePredictorSize)) {
96 fatal("Invalid choice predictor size!\n");
97 }
98
99 //Setup the array of counters for the choice predictor
100 choiceCtrs.resize(choicePredictorSize);
101
102 for (int i = 0; i < choicePredictorSize; ++i)
103 choiceCtrs[i].setBits(choiceCtrBits);
104
105 // @todo: Allow for different thresholds between the predictors.
106 threshold = (1 << (localCtrBits - 1)) - 1;
107}
108
109inline
110unsigned
111TournamentBP::calcLocHistIdx(Addr &branch_addr)
112{
113 // Get low order bits after removing instruction offset.
114 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
115}
116
117inline
118void
119TournamentBP::updateGlobalHistTaken()
120{
121 globalHistory = (globalHistory << 1) | 1;
122 globalHistory = globalHistory & globalHistoryMask;
123}
124
125inline
126void
127TournamentBP::updateGlobalHistNotTaken()
128{
129 globalHistory = (globalHistory << 1);
130 globalHistory = globalHistory & globalHistoryMask;
131}
132
133inline
134void
135TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
136{
137 localHistoryTable[local_history_idx] =
138 (localHistoryTable[local_history_idx] << 1) | 1;
139}
140
141inline
142void
143TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
144{
145 localHistoryTable[local_history_idx] =
146 (localHistoryTable[local_history_idx] << 1);
147}
148
149bool
150TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
151{
152 bool local_prediction;
153 unsigned local_history_idx;
154 unsigned local_predictor_idx;
155
156 bool global_prediction;
157 bool choice_prediction;
158
159 //Lookup in the local predictor to get its branch prediction
160 local_history_idx = calcLocHistIdx(branch_addr);
161 local_predictor_idx = localHistoryTable[local_history_idx]
162 & localPredictorMask;
163 local_prediction = localCtrs[local_predictor_idx].read() > threshold;
164
165 //Lookup in the global predictor to get its branch prediction
166 global_prediction = globalCtrs[globalHistory].read() > threshold;
167
168 //Lookup in the choice predictor to see which one to use
169 choice_prediction = choiceCtrs[globalHistory].read() > threshold;
170
171 // Create BPHistory and pass it back to be recorded.
172 BPHistory *history = new BPHistory;
173 history->globalHistory = globalHistory;
174 history->localPredTaken = local_prediction;
175 history->globalPredTaken = global_prediction;
176 history->globalUsed = choice_prediction;
177 bp_history = (void *)history;
178
179 assert(globalHistory < globalPredictorSize &&
180 local_history_idx < localHistoryTableSize &&
181 local_predictor_idx < localPredictorSize);
182
183 // Commented code is for doing speculative update of counters and
184 // all histories.
185 if (choice_prediction) {
186 if (global_prediction) {
187// updateHistoriesTaken(local_history_idx);
188// globalCtrs[globalHistory].increment();
189// localCtrs[local_history_idx].increment();
190 updateGlobalHistTaken();
191 return true;
192 } else {
193// updateHistoriesNotTaken(local_history_idx);
194// globalCtrs[globalHistory].decrement();
195// localCtrs[local_history_idx].decrement();
196 updateGlobalHistNotTaken();
197 return false;
198 }
199 } else {
200 if (local_prediction) {
201// updateHistoriesTaken(local_history_idx);
202// globalCtrs[globalHistory].increment();
203// localCtrs[local_history_idx].increment();
204 updateGlobalHistTaken();
205 return true;
206 } else {
207// updateHistoriesNotTaken(local_history_idx);
208// globalCtrs[globalHistory].decrement();
209// localCtrs[local_history_idx].decrement();
210 updateGlobalHistNotTaken();
211 return false;
212 }
213 }
214}
215
216void
217TournamentBP::uncondBr(void * &bp_history)
218{
219 // Create BPHistory and pass it back to be recorded.
220 BPHistory *history = new BPHistory;
221 history->globalHistory = globalHistory;
222 history->localPredTaken = true;
223 history->globalPredTaken = true;
224 bp_history = static_cast<void *>(history);
225
226 updateGlobalHistTaken();
227}
228
229void
230TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
231{
232 unsigned local_history_idx;
233 unsigned local_predictor_idx;
234 unsigned local_predictor_hist;
235
236 // Get the local predictor's current prediction
237 local_history_idx = calcLocHistIdx(branch_addr);
238 local_predictor_hist = localHistoryTable[local_history_idx];
239 local_predictor_idx = local_predictor_hist & localPredictorMask;
240
241 // Update the choice predictor to tell it which one was correct if
242 // there was a prediction.
243 if (bp_history) {
244 BPHistory *history = static_cast<BPHistory *>(bp_history);
245 if (history->localPredTaken != history->globalPredTaken) {
246 // If the local prediction matches the actual outcome,
247 // decerement the counter. Otherwise increment the
248 // counter.
249 if (history->localPredTaken == taken) {
|
250 choiceCtrs[globalHistory].decrement();
| 250 choiceCtrs[history->globalHistory].decrement();
|
251 } else if (history->globalPredTaken == taken){
| 251 } else if (history->globalPredTaken == taken){
|
252 choiceCtrs[globalHistory].increment();
| 252 choiceCtrs[history->globalHistory].increment();
|
253 }
| 253 }
|
| 254
|
254 }
255
| 255 }
256
|
| 257 // Update the counters and local history with the proper
258 // resolution of the branch. Global history is updated
259 // speculatively and restored upon squash() calls, so it does not
260 // need to be updated.
261 if (taken) {
262 localCtrs[local_predictor_idx].increment();
263 globalCtrs[history->globalHistory].increment();
264
265 updateLocalHistTaken(local_history_idx);
266 } else {
267 localCtrs[local_predictor_idx].decrement();
268 globalCtrs[history->globalHistory].decrement();
269
270 updateLocalHistNotTaken(local_history_idx);
271 }
272
273 bool mispredict = false;
274
275 //global predictor used and mispredicted
276 if (history->globalUsed && history->globalPredTaken != taken)
277 mispredict = true;
278 //local predictor used and mispredicted
279 else if (!history->globalUsed && history->localPredTaken != taken)
280 mispredict = true;
281
282 if (mispredict) {
283 if (taken) {
284 globalHistory = globalHistory | 1;
285 } else {
286 unsigned mask = globalHistoryMask - 1;
287 globalHistory = globalHistory & mask;
288 }
289
290 }
|
256 // We're done with this history, now delete it.
257 delete history;
258 }
259
260 assert(globalHistory < globalPredictorSize &&
261 local_history_idx < localHistoryTableSize &&
262 local_predictor_idx < localPredictorSize);
263
| 291 // We're done with this history, now delete it.
292 delete history;
293 }
294
295 assert(globalHistory < globalPredictorSize &&
296 local_history_idx < localHistoryTableSize &&
297 local_predictor_idx < localPredictorSize);
298
|
264 // Update the counters and local history with the proper
265 // resolution of the branch. Global history is updated
266 // speculatively and restored upon squash() calls, so it does not
267 // need to be updated.
268 if (taken) {
269 localCtrs[local_predictor_idx].increment();
270 globalCtrs[globalHistory].increment();
| |
271
| 299
|
272 updateLocalHistTaken(local_history_idx);
273 } else {
274 localCtrs[local_predictor_idx].decrement();
275 globalCtrs[globalHistory].decrement();
276
277 updateLocalHistNotTaken(local_history_idx);
278 }
| |
279}
280
281void
282TournamentBP::squash(void *bp_history)
283{
284 BPHistory *history = static_cast<BPHistory *>(bp_history);
285
286 // Restore global history to state prior to this branch.
287 globalHistory = history->globalHistory;
288
289 // Delete this BPHistory now that we're done with it.
290 delete history;
291}
292
293#ifdef DEBUG
294int
295TournamentBP::BPHistory::newCount = 0;
296#endif
| 300}
301
302void
303TournamentBP::squash(void *bp_history)
304{
305 BPHistory *history = static_cast<BPHistory *>(bp_history);
306
307 // Restore global history to state prior to this branch.
308 globalHistory = history->globalHistory;
309
310 // Delete this BPHistory now that we're done with it.
311 delete history;
312}
313
314#ifdef DEBUG
315int
316TournamentBP::BPHistory::newCount = 0;
317#endif
|