tournament.cc (9327:07a22ace275d) tournament.cc (9360:515891d9057a)
1/*
2 * Copyright (c) 2011 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software

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

35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 */
42
1/*
2 * Copyright (c) 2011 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software

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

35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 */
42
43#include "base/bitfield.hh"
43#include "base/intmath.hh"
44#include "cpu/pred/tournament.hh"
45
44#include "base/intmath.hh"
45#include "cpu/pred/tournament.hh"
46
46TournamentBP::TournamentBP(unsigned _localPredictorSize,
47 unsigned _localCtrBits,
47TournamentBP::TournamentBP(unsigned _localCtrBits,
48 unsigned _localHistoryTableSize,
49 unsigned _localHistoryBits,
50 unsigned _globalPredictorSize,
51 unsigned _globalHistoryBits,
52 unsigned _globalCtrBits,
53 unsigned _choicePredictorSize,
54 unsigned _choiceCtrBits,
55 unsigned _instShiftAmt)
48 unsigned _localHistoryTableSize,
49 unsigned _localHistoryBits,
50 unsigned _globalPredictorSize,
51 unsigned _globalHistoryBits,
52 unsigned _globalCtrBits,
53 unsigned _choicePredictorSize,
54 unsigned _choiceCtrBits,
55 unsigned _instShiftAmt)
56 : localPredictorSize(_localPredictorSize),
57 localCtrBits(_localCtrBits),
56 : localCtrBits(_localCtrBits),
58 localHistoryTableSize(_localHistoryTableSize),
59 localHistoryBits(_localHistoryBits),
60 globalPredictorSize(_globalPredictorSize),
61 globalCtrBits(_globalCtrBits),
62 globalHistoryBits(_globalHistoryBits),
57 localHistoryTableSize(_localHistoryTableSize),
58 localHistoryBits(_localHistoryBits),
59 globalPredictorSize(_globalPredictorSize),
60 globalCtrBits(_globalCtrBits),
61 globalHistoryBits(_globalHistoryBits),
63 choicePredictorSize(_globalPredictorSize),
62 choicePredictorSize(_choicePredictorSize),
64 choiceCtrBits(_choiceCtrBits),
65 instShiftAmt(_instShiftAmt)
66{
63 choiceCtrBits(_choiceCtrBits),
64 instShiftAmt(_instShiftAmt)
65{
67 if (!isPowerOf2(localPredictorSize)) {
68 fatal("Invalid local predictor size!\n");
69 }
66 localPredictorSize = ULL(1) << localHistoryBits;
70
67
71 //Setup the array of counters for the local predictor
68 //Set up the array of counters for the local predictor
72 localCtrs.resize(localPredictorSize);
73
74 for (int i = 0; i < localPredictorSize; ++i)
75 localCtrs[i].setBits(localCtrBits);
76
69 localCtrs.resize(localPredictorSize);
70
71 for (int i = 0; i < localPredictorSize; ++i)
72 localCtrs[i].setBits(localCtrBits);
73
77 localPredictorMask = floorPow2(localPredictorSize) - 1;
74 localPredictorMask = mask(localHistoryBits);
78
79 if (!isPowerOf2(localHistoryTableSize)) {
80 fatal("Invalid local history table size!\n");
81 }
82
83 //Setup the history table for the local table
84 localHistoryTable.resize(localHistoryTableSize);
85
86 for (int i = 0; i < localHistoryTableSize; ++i)
87 localHistoryTable[i] = 0;
88
75
76 if (!isPowerOf2(localHistoryTableSize)) {
77 fatal("Invalid local history table size!\n");
78 }
79
80 //Setup the history table for the local table
81 localHistoryTable.resize(localHistoryTableSize);
82
83 for (int i = 0; i < localHistoryTableSize; ++i)
84 localHistoryTable[i] = 0;
85
89 // Setup the local history mask
90 localHistoryMask = (1 << localHistoryBits) - 1;
91
92 if (!isPowerOf2(globalPredictorSize)) {
93 fatal("Invalid global predictor size!\n");
94 }
95
96 //Setup the array of counters for the global predictor
97 globalCtrs.resize(globalPredictorSize);
98
99 for (int i = 0; i < globalPredictorSize; ++i)
100 globalCtrs[i].setBits(globalCtrBits);
101
102 //Clear the global history
103 globalHistory = 0;
86 if (!isPowerOf2(globalPredictorSize)) {
87 fatal("Invalid global predictor size!\n");
88 }
89
90 //Setup the array of counters for the global predictor
91 globalCtrs.resize(globalPredictorSize);
92
93 for (int i = 0; i < globalPredictorSize; ++i)
94 globalCtrs[i].setBits(globalCtrBits);
95
96 //Clear the global history
97 globalHistory = 0;
104 // Setup the global history mask
105 globalHistoryMask = (1 << globalHistoryBits) - 1;
98 // Set up the global history mask
99 // this is equivalent to mask(log2(globalPredictorSize)
100 globalHistoryMask = globalPredictorSize - 1;
106
107 if (!isPowerOf2(choicePredictorSize)) {
108 fatal("Invalid choice predictor size!\n");
109 }
110
101
102 if (!isPowerOf2(choicePredictorSize)) {
103 fatal("Invalid choice predictor size!\n");
104 }
105
106 // Set up choiceHistoryMask
107 // this is equivalent to mask(log2(choicePredictorSize)
108 choiceHistoryMask = choicePredictorSize - 1;
109
111 //Setup the array of counters for the choice predictor
112 choiceCtrs.resize(choicePredictorSize);
113
114 for (int i = 0; i < choicePredictorSize; ++i)
115 choiceCtrs[i].setBits(choiceCtrBits);
116
110 //Setup the array of counters for the choice predictor
111 choiceCtrs.resize(choicePredictorSize);
112
113 for (int i = 0; i < choicePredictorSize; ++i)
114 choiceCtrs[i].setBits(choiceCtrBits);
115
117 // @todo: Allow for different thresholds between the predictors.
118 threshold = (1 << (localCtrBits - 1)) - 1;
116 //Set up historyRegisterMask
117 historyRegisterMask = mask(globalHistoryBits);
118
119 //Check that predictors don't use more bits than they have available
120 if (globalHistoryMask > historyRegisterMask) {
121 fatal("Global predictor too large for global history bits!\n");
122 }
123 if (choiceHistoryMask > historyRegisterMask) {
124 fatal("Choice predictor too large for global history bits!\n");
125 }
126
127 if (globalHistoryMask < historyRegisterMask &&
128 choiceHistoryMask < historyRegisterMask) {
129 inform("More global history bits than required by predictors\n");
130 }
131
132 // Set thresholds for the three predictors' counters
133 // This is equivalent to (2^(Ctr))/2 - 1
134 localThreshold = (ULL(1) << (localCtrBits - 1)) - 1;
135 globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
136 choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
119}
120
121inline
122unsigned
123TournamentBP::calcLocHistIdx(Addr &branch_addr)
124{
125 // Get low order bits after removing instruction offset.
126 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
127}
128
129inline
130void
131TournamentBP::updateGlobalHistTaken()
132{
133 globalHistory = (globalHistory << 1) | 1;
137}
138
139inline
140unsigned
141TournamentBP::calcLocHistIdx(Addr &branch_addr)
142{
143 // Get low order bits after removing instruction offset.
144 return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
145}
146
147inline
148void
149TournamentBP::updateGlobalHistTaken()
150{
151 globalHistory = (globalHistory << 1) | 1;
134 globalHistory = globalHistory & globalHistoryMask;
152 globalHistory = globalHistory & historyRegisterMask;
135}
136
137inline
138void
139TournamentBP::updateGlobalHistNotTaken()
140{
141 globalHistory = (globalHistory << 1);
153}
154
155inline
156void
157TournamentBP::updateGlobalHistNotTaken()
158{
159 globalHistory = (globalHistory << 1);
142 globalHistory = globalHistory & globalHistoryMask;
160 globalHistory = globalHistory & historyRegisterMask;
143}
144
145inline
146void
147TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
148{
149 localHistoryTable[local_history_idx] =
150 (localHistoryTable[local_history_idx] << 1) | 1;

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

158 (localHistoryTable[local_history_idx] << 1);
159}
160
161
162void
163TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
164{
165 unsigned local_history_idx = calcLocHistIdx(branch_addr);
161}
162
163inline
164void
165TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
166{
167 localHistoryTable[local_history_idx] =
168 (localHistoryTable[local_history_idx] << 1) | 1;

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

176 (localHistoryTable[local_history_idx] << 1);
177}
178
179
180void
181TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
182{
183 unsigned local_history_idx = calcLocHistIdx(branch_addr);
166 //Update Global History to Not Taken
167 globalHistory = globalHistory & (globalHistoryMask - 1);
184 //Update Global History to Not Taken (clear LSB)
185 globalHistory &= (historyRegisterMask & ~ULL(1));
168 //Update Local History to Not Taken
169 localHistoryTable[local_history_idx] =
170 localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
171}
172
173bool
174TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
175{
176 bool local_prediction;
177 unsigned local_history_idx;
178 unsigned local_predictor_idx;
179
180 bool global_prediction;
181 bool choice_prediction;
182
183 //Lookup in the local predictor to get its branch prediction
184 local_history_idx = calcLocHistIdx(branch_addr);
185 local_predictor_idx = localHistoryTable[local_history_idx]
186 & localPredictorMask;
186 //Update Local History to Not Taken
187 localHistoryTable[local_history_idx] =
188 localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
189}
190
191bool
192TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
193{
194 bool local_prediction;
195 unsigned local_history_idx;
196 unsigned local_predictor_idx;
197
198 bool global_prediction;
199 bool choice_prediction;
200
201 //Lookup in the local predictor to get its branch prediction
202 local_history_idx = calcLocHistIdx(branch_addr);
203 local_predictor_idx = localHistoryTable[local_history_idx]
204 & localPredictorMask;
187 local_prediction = localCtrs[local_predictor_idx].read() > threshold;
205 local_prediction = localCtrs[local_predictor_idx].read() > localThreshold;
188
189 //Lookup in the global predictor to get its branch prediction
206
207 //Lookup in the global predictor to get its branch prediction
190 global_prediction = globalCtrs[globalHistory].read() > threshold;
208 global_prediction =
209 globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold;
191
192 //Lookup in the choice predictor to see which one to use
210
211 //Lookup in the choice predictor to see which one to use
193 choice_prediction = choiceCtrs[globalHistory].read() > threshold;
212 choice_prediction =
213 choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold;
194
195 // Create BPHistory and pass it back to be recorded.
196 BPHistory *history = new BPHistory;
197 history->globalHistory = globalHistory;
198 history->localPredTaken = local_prediction;
199 history->globalPredTaken = global_prediction;
200 history->globalUsed = choice_prediction;
201 history->localHistory = local_predictor_idx;
202 bp_history = (void *)history;
203
214
215 // Create BPHistory and pass it back to be recorded.
216 BPHistory *history = new BPHistory;
217 history->globalHistory = globalHistory;
218 history->localPredTaken = local_prediction;
219 history->globalPredTaken = global_prediction;
220 history->globalUsed = choice_prediction;
221 history->localHistory = local_predictor_idx;
222 bp_history = (void *)history;
223
204 assert(globalHistory < globalPredictorSize &&
205 local_history_idx < localHistoryTableSize &&
206 local_predictor_idx < localPredictorSize);
224 assert(local_history_idx < localHistoryTableSize);
207
208 // Commented code is for doing speculative update of counters and
209 // all histories.
210 if (choice_prediction) {
211 if (global_prediction) {
212 updateGlobalHistTaken();
213 updateLocalHistTaken(local_history_idx);
214 return true;

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

278 }
279 if (historyPred != taken || !squashed) {
280 // Update the choice predictor to tell it which one was correct if
281 // there was a prediction.
282 if (history->localPredTaken != history->globalPredTaken) {
283 // If the local prediction matches the actual outcome,
284 // decerement the counter. Otherwise increment the
285 // counter.
225
226 // Commented code is for doing speculative update of counters and
227 // all histories.
228 if (choice_prediction) {
229 if (global_prediction) {
230 updateGlobalHistTaken();
231 updateLocalHistTaken(local_history_idx);
232 return true;

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

296 }
297 if (historyPred != taken || !squashed) {
298 // Update the choice predictor to tell it which one was correct if
299 // there was a prediction.
300 if (history->localPredTaken != history->globalPredTaken) {
301 // If the local prediction matches the actual outcome,
302 // decerement the counter. Otherwise increment the
303 // counter.
304 unsigned choice_predictor_idx =
305 history->globalHistory & choiceHistoryMask;
286 if (history->localPredTaken == taken) {
306 if (history->localPredTaken == taken) {
287 choiceCtrs[history->globalHistory].decrement();
307 choiceCtrs[choice_predictor_idx].decrement();
288 } else if (history->globalPredTaken == taken) {
308 } else if (history->globalPredTaken == taken) {
289 choiceCtrs[history->globalHistory].increment();
309 choiceCtrs[choice_predictor_idx].increment();
290 }
291
292 }
293
294 // Update the counters and local history with the proper
295 // resolution of the branch. Global history is updated
296 // speculatively and restored upon squash() calls, so it does not
297 // need to be updated.
310 }
311
312 }
313
314 // Update the counters and local history with the proper
315 // resolution of the branch. Global history is updated
316 // speculatively and restored upon squash() calls, so it does not
317 // need to be updated.
318 unsigned global_predictor_idx =
319 history->globalHistory & globalHistoryMask;
298 if (taken) {
320 if (taken) {
299 globalCtrs[history->globalHistory].increment();
321 globalCtrs[global_predictor_idx].increment();
300 if (old_local_pred_valid) {
301 localCtrs[old_local_pred_index].increment();
302 }
303 } else {
322 if (old_local_pred_valid) {
323 localCtrs[old_local_pred_index].increment();
324 }
325 } else {
304 globalCtrs[history->globalHistory].decrement();
326 globalCtrs[global_predictor_idx].decrement();
305 if (old_local_pred_valid) {
306 localCtrs[old_local_pred_index].decrement();
307 }
308 }
309 }
310 if (squashed) {
311 if (taken) {
312 globalHistory = (history->globalHistory << 1) | 1;
327 if (old_local_pred_valid) {
328 localCtrs[old_local_pred_index].decrement();
329 }
330 }
331 }
332 if (squashed) {
333 if (taken) {
334 globalHistory = (history->globalHistory << 1) | 1;
313 globalHistory = globalHistory & globalHistoryMask;
335 globalHistory = globalHistory & historyRegisterMask;
314 if (old_local_pred_valid) {
315 localHistoryTable[local_history_idx] =
316 (history->localHistory << 1) | 1;
317 }
318 } else {
319 globalHistory = (history->globalHistory << 1);
336 if (old_local_pred_valid) {
337 localHistoryTable[local_history_idx] =
338 (history->localHistory << 1) | 1;
339 }
340 } else {
341 globalHistory = (history->globalHistory << 1);
320 globalHistory = globalHistory & globalHistoryMask;
342 globalHistory = globalHistory & historyRegisterMask;
321 if (old_local_pred_valid) {
322 localHistoryTable[local_history_idx] =
323 history->localHistory << 1;
324 }
325 }
326
327 }
328 // We're done with this history, now delete it.
329 delete history;
330
331 }
332
343 if (old_local_pred_valid) {
344 localHistoryTable[local_history_idx] =
345 history->localHistory << 1;
346 }
347 }
348
349 }
350 // We're done with this history, now delete it.
351 delete history;
352
353 }
354
333 assert(globalHistory < globalPredictorSize &&
334 local_history_idx < localHistoryTableSize &&
335 local_predictor_idx < localPredictorSize);
355 assert(local_history_idx < localHistoryTableSize);
336
337
338}
339
340void
341TournamentBP::squash(void *bp_history)
342{
343 BPHistory *history = static_cast<BPHistory *>(bp_history);

--- 12 unchanged lines hidden --- 		356
357
358}
359
360void
361TournamentBP::squash(void *bp_history)
362{
363 BPHistory *history = static_cast<BPHistory *>(bp_history);

--- 12 unchanged lines hidden ---