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/intmath.hh"
44 #include "cpu/pred/tournament.hh"
46 TournamentBP::TournamentBP(unsigned _localPredictorSize
,
47 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
)
56 : localPredictorSize(_localPredictorSize
),
57 localCtrBits(_localCtrBits
),
58 localHistoryTableSize(_localHistoryTableSize
),
59 localHistoryBits(_localHistoryBits
),
60 globalPredictorSize(_globalPredictorSize
),
61 globalCtrBits(_globalCtrBits
),
62 globalHistoryBits(_globalHistoryBits
),
63 choicePredictorSize(_globalPredictorSize
),
64 choiceCtrBits(_choiceCtrBits
),
65 instShiftAmt(_instShiftAmt
)
67 if (!isPowerOf2(localPredictorSize
)) {
68 fatal("Invalid local predictor size!\n");
71 //Setup the array of counters for the local predictor
72 localCtrs
.resize(localPredictorSize
);
74 for (int i
= 0; i
< localPredictorSize
; ++i
)
75 localCtrs
[i
].setBits(localCtrBits
);
77 localPredictorMask
= floorPow2(localPredictorSize
) - 1;
79 if (!isPowerOf2(localHistoryTableSize
)) {
80 fatal("Invalid local history table size!\n");
83 //Setup the history table for the local table
84 localHistoryTable
.resize(localHistoryTableSize
);
86 for (int i
= 0; i
< localHistoryTableSize
; ++i
)
87 localHistoryTable
[i
] = 0;
89 // Setup the local history mask
90 localHistoryMask
= (1 << localHistoryBits
) - 1;
92 if (!isPowerOf2(globalPredictorSize
)) {
93 fatal("Invalid global predictor size!\n");
96 //Setup the array of counters for the global predictor
97 globalCtrs
.resize(globalPredictorSize
);
99 for (int i
= 0; i
< globalPredictorSize
; ++i
)
100 globalCtrs
[i
].setBits(globalCtrBits
);
102 //Clear the global history
104 // Setup the global history mask
105 globalHistoryMask
= (1 << globalHistoryBits
) - 1;
107 if (!isPowerOf2(choicePredictorSize
)) {
108 fatal("Invalid choice predictor size!\n");
111 //Setup the array of counters for the choice predictor
112 choiceCtrs
.resize(choicePredictorSize
);
114 for (int i
= 0; i
< choicePredictorSize
; ++i
)
115 choiceCtrs
[i
].setBits(choiceCtrBits
);
117 // @todo: Allow for different thresholds between the predictors.
118 threshold
= (1 << (localCtrBits
- 1)) - 1;
123 TournamentBP::calcLocHistIdx(Addr
&branch_addr
)
125 // Get low order bits after removing instruction offset.
126 return (branch_addr
>> instShiftAmt
) & (localHistoryTableSize
- 1);
131 TournamentBP::updateGlobalHistTaken()
133 globalHistory
= (globalHistory
<< 1) | 1;
134 globalHistory
= globalHistory
& globalHistoryMask
;
139 TournamentBP::updateGlobalHistNotTaken()
141 globalHistory
= (globalHistory
<< 1);
142 globalHistory
= globalHistory
& globalHistoryMask
;
147 TournamentBP::updateLocalHistTaken(unsigned local_history_idx
)
149 localHistoryTable
[local_history_idx
] =
150 (localHistoryTable
[local_history_idx
] << 1) | 1;
155 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx
)
157 localHistoryTable
[local_history_idx
] =
158 (localHistoryTable
[local_history_idx
] << 1);
163 TournamentBP::BTBUpdate(Addr
&branch_addr
, void * &bp_history
)
165 unsigned local_history_idx
= calcLocHistIdx(branch_addr
);
166 //Update Global History to Not Taken
167 globalHistory
= globalHistory
& (globalHistoryMask
- 1);
168 //Update Local History to Not Taken
169 localHistoryTable
[local_history_idx
] =
170 localHistoryTable
[local_history_idx
] & (localPredictorMask
- 1);
174 TournamentBP::lookup(Addr
&branch_addr
, void * &bp_history
)
176 bool local_prediction
;
177 unsigned local_history_idx
;
178 unsigned local_predictor_idx
;
180 bool global_prediction
;
181 bool choice_prediction
;
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
;
187 local_prediction
= localCtrs
[local_predictor_idx
].read() > threshold
;
189 //Lookup in the global predictor to get its branch prediction
190 global_prediction
= globalCtrs
[globalHistory
].read() > threshold
;
192 //Lookup in the choice predictor to see which one to use
193 choice_prediction
= choiceCtrs
[globalHistory
].read() > threshold
;
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
;
204 assert(globalHistory
< globalPredictorSize
&&
205 local_history_idx
< localHistoryTableSize
&&
206 local_predictor_idx
< localPredictorSize
);
208 // Commented code is for doing speculative update of counters and
210 if (choice_prediction
) {
211 if (global_prediction
) {
212 updateGlobalHistTaken();
213 updateLocalHistTaken(local_history_idx
);
216 updateGlobalHistNotTaken();
217 updateLocalHistNotTaken(local_history_idx
);
221 if (local_prediction
) {
222 updateGlobalHistTaken();
223 updateLocalHistTaken(local_history_idx
);
226 updateGlobalHistNotTaken();
227 updateLocalHistNotTaken(local_history_idx
);
234 TournamentBP::uncondBr(void * &bp_history
)
236 // Create BPHistory and pass it back to be recorded.
237 BPHistory
*history
= new BPHistory
;
238 history
->globalHistory
= globalHistory
;
239 history
->localPredTaken
= true;
240 history
->globalPredTaken
= true;
241 history
->globalUsed
= true;
242 history
->localHistory
= invalidPredictorIndex
;
243 bp_history
= static_cast<void *>(history
);
245 updateGlobalHistTaken();
249 TournamentBP::update(Addr
&branch_addr
, bool taken
, void *bp_history
,
252 unsigned local_history_idx
;
253 unsigned local_predictor_idx M5_VAR_USED
;
254 unsigned local_predictor_hist
;
256 // Get the local predictor's current prediction
257 local_history_idx
= calcLocHistIdx(branch_addr
);
258 local_predictor_hist
= localHistoryTable
[local_history_idx
];
259 local_predictor_idx
= local_predictor_hist
& localPredictorMask
;
262 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
263 // Update may also be called if the Branch target is incorrect even if
264 // the prediction is correct. In that case do not update the counters.
265 bool historyPred
= false;
266 unsigned old_local_pred_index
= history
->localHistory
267 & localPredictorMask
;
268 if (history
->globalUsed
) {
269 historyPred
= history
->globalPredTaken
;
271 historyPred
= history
->localPredTaken
;
273 if (historyPred
!= taken
|| !squashed
) {
274 // Update the choice predictor to tell it which one was correct if
275 // there was a prediction.
276 if (history
->localPredTaken
!= history
->globalPredTaken
) {
277 // If the local prediction matches the actual outcome,
278 // decerement the counter. Otherwise increment the
280 if (history
->localPredTaken
== taken
) {
281 choiceCtrs
[history
->globalHistory
].decrement();
282 } else if (history
->globalPredTaken
== taken
) {
283 choiceCtrs
[history
->globalHistory
].increment();
288 // Update the counters and local history with the proper
289 // resolution of the branch. Global history is updated
290 // speculatively and restored upon squash() calls, so it does not
291 // need to be updated.
293 globalCtrs
[history
->globalHistory
].increment();
294 if (old_local_pred_index
!= invalidPredictorIndex
) {
295 localCtrs
[old_local_pred_index
].increment();
298 globalCtrs
[history
->globalHistory
].decrement();
299 if (old_local_pred_index
!= invalidPredictorIndex
) {
300 localCtrs
[old_local_pred_index
].decrement();
306 globalHistory
= (history
->globalHistory
<< 1) | 1;
307 globalHistory
= globalHistory
& globalHistoryMask
;
308 if (old_local_pred_index
!= invalidPredictorIndex
) {
309 localHistoryTable
[old_local_pred_index
] =
310 (history
->localHistory
<< 1) | 1;
313 globalHistory
= (history
->globalHistory
<< 1);
314 globalHistory
= globalHistory
& globalHistoryMask
;
315 if (old_local_pred_index
!= invalidPredictorIndex
) {
316 localHistoryTable
[old_local_pred_index
] =
317 history
->localHistory
<< 1;
322 // We're done with this history, now delete it.
327 assert(globalHistory
< globalPredictorSize
&&
328 local_history_idx
< localHistoryTableSize
&&
329 local_predictor_idx
< localPredictorSize
);
335 TournamentBP::squash(void *bp_history
)
337 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
339 // Restore global history to state prior to this branch.
340 globalHistory
= history
->globalHistory
;
342 // Delete this BPHistory now that we're done with it.
348 TournamentBP::BPHistory::newCount
= 0;