2 * Copyright (c) 2011 ARM Limited
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
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
14 * Copyright (c) 2004-2006 The Regents of The University of Michigan
15 * All rights reserved.
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
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.
43 #include "base/bitfield.hh"
44 #include "base/intmath.hh"
45 #include "cpu/pred/tournament.hh"
47 TournamentBP::TournamentBP(const Params
*params
)
49 localCtrBits(params
->localCtrBits
),
50 localHistoryTableSize(params
->localHistoryTableSize
),
51 localHistoryBits(params
->localHistoryBits
),
52 globalPredictorSize(params
->globalPredictorSize
),
53 globalCtrBits(params
->globalCtrBits
),
54 globalHistoryBits(params
->globalHistoryBits
),
55 choicePredictorSize(params
->choicePredictorSize
),
56 choiceCtrBits(params
->choiceCtrBits
),
57 instShiftAmt(params
->instShiftAmt
)
59 localPredictorSize
= ULL(1) << localHistoryBits
;
61 //Set up the array of counters for the local predictor
62 localCtrs
.resize(localPredictorSize
);
64 for (int i
= 0; i
< localPredictorSize
; ++i
)
65 localCtrs
[i
].setBits(localCtrBits
);
67 localPredictorMask
= mask(localHistoryBits
);
69 if (!isPowerOf2(localHistoryTableSize
)) {
70 fatal("Invalid local history table size!\n");
73 //Setup the history table for the local table
74 localHistoryTable
.resize(localHistoryTableSize
);
76 for (int i
= 0; i
< localHistoryTableSize
; ++i
)
77 localHistoryTable
[i
] = 0;
79 if (!isPowerOf2(globalPredictorSize
)) {
80 fatal("Invalid global predictor size!\n");
83 //Setup the array of counters for the global predictor
84 globalCtrs
.resize(globalPredictorSize
);
86 for (int i
= 0; i
< globalPredictorSize
; ++i
)
87 globalCtrs
[i
].setBits(globalCtrBits
);
89 //Clear the global history
91 // Set up the global history mask
92 // this is equivalent to mask(log2(globalPredictorSize)
93 globalHistoryMask
= globalPredictorSize
- 1;
95 if (!isPowerOf2(choicePredictorSize
)) {
96 fatal("Invalid choice predictor size!\n");
99 // Set up choiceHistoryMask
100 // this is equivalent to mask(log2(choicePredictorSize)
101 choiceHistoryMask
= choicePredictorSize
- 1;
103 //Setup the array of counters for the choice predictor
104 choiceCtrs
.resize(choicePredictorSize
);
106 for (int i
= 0; i
< choicePredictorSize
; ++i
)
107 choiceCtrs
[i
].setBits(choiceCtrBits
);
109 //Set up historyRegisterMask
110 historyRegisterMask
= mask(globalHistoryBits
);
112 //Check that predictors don't use more bits than they have available
113 if (globalHistoryMask
> historyRegisterMask
) {
114 fatal("Global predictor too large for global history bits!\n");
116 if (choiceHistoryMask
> historyRegisterMask
) {
117 fatal("Choice predictor too large for global history bits!\n");
120 if (globalHistoryMask
< historyRegisterMask
&&
121 choiceHistoryMask
< historyRegisterMask
) {
122 inform("More global history bits than required by predictors\n");
125 // Set thresholds for the three predictors' counters
126 // This is equivalent to (2^(Ctr))/2 - 1
127 localThreshold
= (ULL(1) << (localCtrBits
- 1)) - 1;
128 globalThreshold
= (ULL(1) << (globalCtrBits
- 1)) - 1;
129 choiceThreshold
= (ULL(1) << (choiceCtrBits
- 1)) - 1;
134 TournamentBP::calcLocHistIdx(Addr
&branch_addr
)
136 // Get low order bits after removing instruction offset.
137 return (branch_addr
>> instShiftAmt
) & (localHistoryTableSize
- 1);
142 TournamentBP::updateGlobalHistTaken()
144 globalHistory
= (globalHistory
<< 1) | 1;
145 globalHistory
= globalHistory
& historyRegisterMask
;
150 TournamentBP::updateGlobalHistNotTaken()
152 globalHistory
= (globalHistory
<< 1);
153 globalHistory
= globalHistory
& historyRegisterMask
;
158 TournamentBP::updateLocalHistTaken(unsigned local_history_idx
)
160 localHistoryTable
[local_history_idx
] =
161 (localHistoryTable
[local_history_idx
] << 1) | 1;
166 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx
)
168 localHistoryTable
[local_history_idx
] =
169 (localHistoryTable
[local_history_idx
] << 1);
174 TournamentBP::btbUpdate(Addr branch_addr
, void * &bp_history
)
176 unsigned local_history_idx
= calcLocHistIdx(branch_addr
);
177 //Update Global History to Not Taken (clear LSB)
178 globalHistory
&= (historyRegisterMask
& ~ULL(1));
179 //Update Local History to Not Taken
180 localHistoryTable
[local_history_idx
] =
181 localHistoryTable
[local_history_idx
] & (localPredictorMask
& ~ULL(1));
185 TournamentBP::lookup(Addr branch_addr
, void * &bp_history
)
187 bool local_prediction
;
188 unsigned local_history_idx
;
189 unsigned local_predictor_idx
;
191 bool global_prediction
;
192 bool choice_prediction
;
194 //Lookup in the local predictor to get its branch prediction
195 local_history_idx
= calcLocHistIdx(branch_addr
);
196 local_predictor_idx
= localHistoryTable
[local_history_idx
]
197 & localPredictorMask
;
198 local_prediction
= localCtrs
[local_predictor_idx
].read() > localThreshold
;
200 //Lookup in the global predictor to get its branch prediction
202 globalCtrs
[globalHistory
& globalHistoryMask
].read() > globalThreshold
;
204 //Lookup in the choice predictor to see which one to use
206 choiceCtrs
[globalHistory
& choiceHistoryMask
].read() > choiceThreshold
;
208 // Create BPHistory and pass it back to be recorded.
209 BPHistory
*history
= new BPHistory
;
210 history
->globalHistory
= globalHistory
;
211 history
->localPredTaken
= local_prediction
;
212 history
->globalPredTaken
= global_prediction
;
213 history
->globalUsed
= choice_prediction
;
214 history
->localHistory
= local_predictor_idx
;
215 bp_history
= (void *)history
;
217 assert(local_history_idx
< localHistoryTableSize
);
219 // Commented code is for doing speculative update of counters and
221 if (choice_prediction
) {
222 if (global_prediction
) {
223 updateGlobalHistTaken();
224 updateLocalHistTaken(local_history_idx
);
227 updateGlobalHistNotTaken();
228 updateLocalHistNotTaken(local_history_idx
);
232 if (local_prediction
) {
233 updateGlobalHistTaken();
234 updateLocalHistTaken(local_history_idx
);
237 updateGlobalHistNotTaken();
238 updateLocalHistNotTaken(local_history_idx
);
245 TournamentBP::uncondBranch(void * &bp_history
)
247 // Create BPHistory and pass it back to be recorded.
248 BPHistory
*history
= new BPHistory
;
249 history
->globalHistory
= globalHistory
;
250 history
->localPredTaken
= true;
251 history
->globalPredTaken
= true;
252 history
->globalUsed
= true;
253 history
->localHistory
= invalidPredictorIndex
;
254 bp_history
= static_cast<void *>(history
);
256 updateGlobalHistTaken();
260 TournamentBP::update(Addr branch_addr
, bool taken
, void *bp_history
,
263 unsigned local_history_idx
;
264 unsigned local_predictor_idx M5_VAR_USED
;
265 unsigned local_predictor_hist
;
267 // Get the local predictor's current prediction
268 local_history_idx
= calcLocHistIdx(branch_addr
);
269 local_predictor_hist
= localHistoryTable
[local_history_idx
];
270 local_predictor_idx
= local_predictor_hist
& localPredictorMask
;
273 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
274 // Update may also be called if the Branch target is incorrect even if
275 // the prediction is correct. In that case do not update the counters.
276 bool historyPred
= false;
277 unsigned old_local_pred_index
= history
->localHistory
&
280 bool old_local_pred_valid
= history
->localHistory
!=
281 invalidPredictorIndex
;
283 assert(old_local_pred_index
< localPredictorSize
);
285 if (history
->globalUsed
) {
286 historyPred
= history
->globalPredTaken
;
288 historyPred
= history
->localPredTaken
;
290 if (historyPred
!= taken
|| !squashed
) {
291 // Update the choice predictor to tell it which one was correct if
292 // there was a prediction.
293 if (history
->localPredTaken
!= history
->globalPredTaken
) {
294 // If the local prediction matches the actual outcome,
295 // decerement the counter. Otherwise increment the
297 unsigned choice_predictor_idx
=
298 history
->globalHistory
& choiceHistoryMask
;
299 if (history
->localPredTaken
== taken
) {
300 choiceCtrs
[choice_predictor_idx
].decrement();
301 } else if (history
->globalPredTaken
== taken
) {
302 choiceCtrs
[choice_predictor_idx
].increment();
307 // Update the counters and local history with the proper
308 // resolution of the branch. Global history is updated
309 // speculatively and restored upon squash() calls, so it does not
310 // need to be updated.
311 unsigned global_predictor_idx
=
312 history
->globalHistory
& globalHistoryMask
;
314 globalCtrs
[global_predictor_idx
].increment();
315 if (old_local_pred_valid
) {
316 localCtrs
[old_local_pred_index
].increment();
319 globalCtrs
[global_predictor_idx
].decrement();
320 if (old_local_pred_valid
) {
321 localCtrs
[old_local_pred_index
].decrement();
327 globalHistory
= (history
->globalHistory
<< 1) | 1;
328 globalHistory
= globalHistory
& historyRegisterMask
;
329 if (old_local_pred_valid
) {
330 localHistoryTable
[local_history_idx
] =
331 (history
->localHistory
<< 1) | 1;
334 globalHistory
= (history
->globalHistory
<< 1);
335 globalHistory
= globalHistory
& historyRegisterMask
;
336 if (old_local_pred_valid
) {
337 localHistoryTable
[local_history_idx
] =
338 history
->localHistory
<< 1;
343 // We're done with this history, now delete it.
348 assert(local_history_idx
< localHistoryTableSize
);
354 TournamentBP::squash(void *bp_history
)
356 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
358 // Restore global history to state prior to this branch.
359 globalHistory
= history
->globalHistory
;
361 // Delete this BPHistory now that we're done with it.
367 TournamentBP::BPHistory::newCount
= 0;