2 * Copyright (c) 2011, 2014 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.
41 #include "cpu/pred/tournament.hh"
43 #include "base/bitfield.hh"
44 #include "base/intmath.hh"
46 TournamentBP::TournamentBP(const TournamentBPParams
¶ms
)
48 localPredictorSize(params
.localPredictorSize
),
49 localCtrBits(params
.localCtrBits
),
50 localCtrs(localPredictorSize
, SatCounter8(localCtrBits
)),
51 localHistoryTableSize(params
.localHistoryTableSize
),
52 localHistoryBits(ceilLog2(params
.localPredictorSize
)),
53 globalPredictorSize(params
.globalPredictorSize
),
54 globalCtrBits(params
.globalCtrBits
),
55 globalCtrs(globalPredictorSize
, SatCounter8(globalCtrBits
)),
56 globalHistory(params
.numThreads
, 0),
58 ceilLog2(params
.globalPredictorSize
) >
59 ceilLog2(params
.choicePredictorSize
) ?
60 ceilLog2(params
.globalPredictorSize
) :
61 ceilLog2(params
.choicePredictorSize
)),
62 choicePredictorSize(params
.choicePredictorSize
),
63 choiceCtrBits(params
.choiceCtrBits
),
64 choiceCtrs(choicePredictorSize
, SatCounter8(choiceCtrBits
))
66 if (!isPowerOf2(localPredictorSize
)) {
67 fatal("Invalid local predictor size!\n");
70 if (!isPowerOf2(globalPredictorSize
)) {
71 fatal("Invalid global predictor size!\n");
74 localPredictorMask
= mask(localHistoryBits
);
76 if (!isPowerOf2(localHistoryTableSize
)) {
77 fatal("Invalid local history table size!\n");
80 //Setup the history table for the local table
81 localHistoryTable
.resize(localHistoryTableSize
);
83 for (int i
= 0; i
< localHistoryTableSize
; ++i
)
84 localHistoryTable
[i
] = 0;
86 // Set up the global history mask
87 // this is equivalent to mask(log2(globalPredictorSize)
88 globalHistoryMask
= globalPredictorSize
- 1;
90 if (!isPowerOf2(choicePredictorSize
)) {
91 fatal("Invalid choice predictor size!\n");
94 // Set up choiceHistoryMask
95 // this is equivalent to mask(log2(choicePredictorSize)
96 choiceHistoryMask
= choicePredictorSize
- 1;
98 //Set up historyRegisterMask
99 historyRegisterMask
= mask(globalHistoryBits
);
101 //Check that predictors don't use more bits than they have available
102 if (globalHistoryMask
> historyRegisterMask
) {
103 fatal("Global predictor too large for global history bits!\n");
105 if (choiceHistoryMask
> historyRegisterMask
) {
106 fatal("Choice predictor too large for global history bits!\n");
109 if (globalHistoryMask
< historyRegisterMask
&&
110 choiceHistoryMask
< historyRegisterMask
) {
111 inform("More global history bits than required by predictors\n");
114 // Set thresholds for the three predictors' counters
115 // This is equivalent to (2^(Ctr))/2 - 1
116 localThreshold
= (ULL(1) << (localCtrBits
- 1)) - 1;
117 globalThreshold
= (ULL(1) << (globalCtrBits
- 1)) - 1;
118 choiceThreshold
= (ULL(1) << (choiceCtrBits
- 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(ThreadID tid
)
133 globalHistory
[tid
] = (globalHistory
[tid
] << 1) | 1;
134 globalHistory
[tid
] = globalHistory
[tid
] & historyRegisterMask
;
139 TournamentBP::updateGlobalHistNotTaken(ThreadID tid
)
141 globalHistory
[tid
] = (globalHistory
[tid
] << 1);
142 globalHistory
[tid
] = globalHistory
[tid
] & historyRegisterMask
;
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(ThreadID tid
, Addr branch_addr
, void * &bp_history
)
165 unsigned local_history_idx
= calcLocHistIdx(branch_addr
);
166 //Update Global History to Not Taken (clear LSB)
167 globalHistory
[tid
] &= (historyRegisterMask
& ~ULL(1));
168 //Update Local History to Not Taken
169 localHistoryTable
[local_history_idx
] =
170 localHistoryTable
[local_history_idx
] & (localPredictorMask
& ~ULL(1));
174 TournamentBP::lookup(ThreadID tid
, 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
] > localThreshold
;
189 //Lookup in the global predictor to get its branch prediction
190 global_prediction
= globalThreshold
<
191 globalCtrs
[globalHistory
[tid
] & globalHistoryMask
];
193 //Lookup in the choice predictor to see which one to use
194 choice_prediction
= choiceThreshold
<
195 choiceCtrs
[globalHistory
[tid
] & choiceHistoryMask
];
197 // Create BPHistory and pass it back to be recorded.
198 BPHistory
*history
= new BPHistory
;
199 history
->globalHistory
= globalHistory
[tid
];
200 history
->localPredTaken
= local_prediction
;
201 history
->globalPredTaken
= global_prediction
;
202 history
->globalUsed
= choice_prediction
;
203 history
->localHistoryIdx
= local_history_idx
;
204 history
->localHistory
= local_predictor_idx
;
205 bp_history
= (void *)history
;
207 assert(local_history_idx
< localHistoryTableSize
);
209 // Speculative update of the global history and the
210 // selected local history.
211 if (choice_prediction
) {
212 if (global_prediction
) {
213 updateGlobalHistTaken(tid
);
214 updateLocalHistTaken(local_history_idx
);
217 updateGlobalHistNotTaken(tid
);
218 updateLocalHistNotTaken(local_history_idx
);
222 if (local_prediction
) {
223 updateGlobalHistTaken(tid
);
224 updateLocalHistTaken(local_history_idx
);
227 updateGlobalHistNotTaken(tid
);
228 updateLocalHistNotTaken(local_history_idx
);
235 TournamentBP::uncondBranch(ThreadID tid
, Addr pc
, void * &bp_history
)
237 // Create BPHistory and pass it back to be recorded.
238 BPHistory
*history
= new BPHistory
;
239 history
->globalHistory
= globalHistory
[tid
];
240 history
->localPredTaken
= true;
241 history
->globalPredTaken
= true;
242 history
->globalUsed
= true;
243 history
->localHistoryIdx
= invalidPredictorIndex
;
244 history
->localHistory
= invalidPredictorIndex
;
245 bp_history
= static_cast<void *>(history
);
247 updateGlobalHistTaken(tid
);
251 TournamentBP::update(ThreadID tid
, Addr branch_addr
, bool taken
,
252 void *bp_history
, bool squashed
,
253 const StaticInstPtr
& inst
, Addr corrTarget
)
257 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
259 unsigned local_history_idx
= calcLocHistIdx(branch_addr
);
261 assert(local_history_idx
< localHistoryTableSize
);
263 // Unconditional branches do not use local history.
264 bool old_local_pred_valid
= history
->localHistory
!=
265 invalidPredictorIndex
;
267 // If this is a misprediction, restore the speculatively
268 // updated state (global history register and local history)
271 // Global history restore and update
272 globalHistory
[tid
] = (history
->globalHistory
<< 1) | taken
;
273 globalHistory
[tid
] &= historyRegisterMask
;
275 // Local history restore and update.
276 if (old_local_pred_valid
) {
277 localHistoryTable
[local_history_idx
] =
278 (history
->localHistory
<< 1) | taken
;
284 unsigned old_local_pred_index
= history
->localHistory
&
287 assert(old_local_pred_index
< localPredictorSize
);
289 // Update the choice predictor to tell it which one was correct if
290 // there was a prediction.
291 if (history
->localPredTaken
!= history
->globalPredTaken
&&
292 old_local_pred_valid
)
294 // If the local prediction matches the actual outcome,
295 // decrement the counter. Otherwise increment the
297 unsigned choice_predictor_idx
=
298 history
->globalHistory
& choiceHistoryMask
;
299 if (history
->localPredTaken
== taken
) {
300 choiceCtrs
[choice_predictor_idx
]--;
301 } else if (history
->globalPredTaken
== taken
) {
302 choiceCtrs
[choice_predictor_idx
]++;
306 // Update the counters with the proper
307 // resolution of the branch. Histories are updated
308 // speculatively, restored upon squash() calls, and
309 // recomputed upon update(squash = true) calls,
310 // so they do not need to be updated.
311 unsigned global_predictor_idx
=
312 history
->globalHistory
& globalHistoryMask
;
314 globalCtrs
[global_predictor_idx
]++;
315 if (old_local_pred_valid
) {
316 localCtrs
[old_local_pred_index
]++;
319 globalCtrs
[global_predictor_idx
]--;
320 if (old_local_pred_valid
) {
321 localCtrs
[old_local_pred_index
]--;
325 // We're done with this history, now delete it.
330 TournamentBP::squash(ThreadID tid
, void *bp_history
)
332 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
334 // Restore global history to state prior to this branch.
335 globalHistory
[tid
] = history
->globalHistory
;
337 // Restore local history
338 if (history
->localHistoryIdx
!= invalidPredictorIndex
) {
339 localHistoryTable
[history
->localHistoryIdx
] = history
->localHistory
;
342 // Delete this BPHistory now that we're done with it.
348 TournamentBP::BPHistory::newCount
= 0;