2 * Copyright (c) 2014 The Regents of The University of Michigan
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.
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.
28 * Authors: Anthony Gutierrez
32 * Implementation of a bi-mode branch predictor
35 #include "base/bitfield.hh"
36 #include "base/intmath.hh"
37 #include "cpu/pred/bi_mode.hh"
39 BiModeBP::BiModeBP(const BiModeBPParams
*params
)
42 globalHistoryBits(ceilLog2(params
->globalPredictorSize
)),
43 choicePredictorSize(params
->choicePredictorSize
),
44 choiceCtrBits(params
->choiceCtrBits
),
45 globalPredictorSize(params
->globalPredictorSize
),
46 globalCtrBits(params
->globalCtrBits
)
48 if (!isPowerOf2(choicePredictorSize
))
49 fatal("Invalid choice predictor size.\n");
50 if (!isPowerOf2(globalPredictorSize
))
51 fatal("Invalid global history predictor size.\n");
53 choiceCounters
.resize(choicePredictorSize
);
54 takenCounters
.resize(globalPredictorSize
);
55 notTakenCounters
.resize(globalPredictorSize
);
57 for (int i
= 0; i
< choicePredictorSize
; ++i
) {
58 choiceCounters
[i
].setBits(choiceCtrBits
);
60 for (int i
= 0; i
< globalPredictorSize
; ++i
) {
61 takenCounters
[i
].setBits(globalCtrBits
);
62 notTakenCounters
[i
].setBits(globalCtrBits
);
65 historyRegisterMask
= mask(globalHistoryBits
);
66 choiceHistoryMask
= choicePredictorSize
- 1;
67 globalHistoryMask
= globalPredictorSize
- 1;
69 choiceThreshold
= (ULL(1) << (choiceCtrBits
- 1)) - 1;
70 takenThreshold
= (ULL(1) << (choiceCtrBits
- 1)) - 1;
71 notTakenThreshold
= (ULL(1) << (choiceCtrBits
- 1)) - 1;
75 * For an unconditional branch we set its history such that
76 * everything is set to taken. I.e., its choice predictor
77 * chooses the taken array and the taken array predicts taken.
80 BiModeBP::uncondBranch(Addr pc
, void * &bpHistory
)
82 BPHistory
*history
= new BPHistory
;
83 history
->globalHistoryReg
= globalHistoryReg
;
84 history
->takenUsed
= true;
85 history
->takenPred
= true;
86 history
->notTakenPred
= true;
87 history
->finalPred
= true;
88 bpHistory
= static_cast<void*>(history
);
89 updateGlobalHistReg(true);
93 BiModeBP::squash(void *bpHistory
)
95 BPHistory
*history
= static_cast<BPHistory
*>(bpHistory
);
96 globalHistoryReg
= history
->globalHistoryReg
;
102 * Here we lookup the actual branch prediction. We use the PC to
103 * identify the bias of a particular branch, which is based on the
104 * prediction in the choice array. A hash of the global history
105 * register and a branch's PC is used to index into both the taken
106 * and not-taken predictors, which both present a prediction. The
107 * choice array's prediction is used to select between the two
108 * direction predictors for the final branch prediction.
111 BiModeBP::lookup(Addr branchAddr
, void * &bpHistory
)
113 unsigned choiceHistoryIdx
= ((branchAddr
>> instShiftAmt
)
114 & choiceHistoryMask
);
115 unsigned globalHistoryIdx
= (((branchAddr
>> instShiftAmt
)
117 & globalHistoryMask
);
119 assert(choiceHistoryIdx
< choicePredictorSize
);
120 assert(globalHistoryIdx
< globalPredictorSize
);
122 bool choicePrediction
= choiceCounters
[choiceHistoryIdx
].read()
124 bool takenGHBPrediction
= takenCounters
[globalHistoryIdx
].read()
126 bool notTakenGHBPrediction
= notTakenCounters
[globalHistoryIdx
].read()
128 bool finalPrediction
;
130 BPHistory
*history
= new BPHistory
;
131 history
->globalHistoryReg
= globalHistoryReg
;
132 history
->takenUsed
= choicePrediction
;
133 history
->takenPred
= takenGHBPrediction
;
134 history
->notTakenPred
= notTakenGHBPrediction
;
136 if (choicePrediction
) {
137 finalPrediction
= takenGHBPrediction
;
139 finalPrediction
= notTakenGHBPrediction
;
142 history
->finalPred
= finalPrediction
;
143 bpHistory
= static_cast<void*>(history
);
144 updateGlobalHistReg(finalPrediction
);
146 return finalPrediction
;
150 BiModeBP::btbUpdate(Addr branchAddr
, void * &bpHistory
)
152 globalHistoryReg
&= (historyRegisterMask
& ~ULL(1));
155 /* Only the selected direction predictor will be updated with the final
156 * outcome; the status of the unselected one will not be altered. The choice
157 * predictor is always updated with the branch outcome, except when the
158 * choice is opposite to the branch outcome but the selected counter of
159 * the direction predictors makes a correct final prediction.
162 BiModeBP::update(Addr branchAddr
, bool taken
, void *bpHistory
, bool squashed
)
165 BPHistory
*history
= static_cast<BPHistory
*>(bpHistory
);
167 unsigned choiceHistoryIdx
= ((branchAddr
>> instShiftAmt
)
168 & choiceHistoryMask
);
169 unsigned globalHistoryIdx
= (((branchAddr
>> instShiftAmt
)
170 ^ history
->globalHistoryReg
)
171 & globalHistoryMask
);
173 assert(choiceHistoryIdx
< choicePredictorSize
);
174 assert(globalHistoryIdx
< globalPredictorSize
);
176 if (history
->takenUsed
) {
177 // if the taken array's prediction was used, update it
179 takenCounters
[globalHistoryIdx
].increment();
181 takenCounters
[globalHistoryIdx
].decrement();
184 // if the not-taken array's prediction was used, update it
186 notTakenCounters
[globalHistoryIdx
].increment();
188 notTakenCounters
[globalHistoryIdx
].decrement();
192 if (history
->finalPred
== taken
) {
193 /* If the final prediction matches the actual branch's
194 * outcome and the choice predictor matches the final
195 * outcome, we update the choice predictor, otherwise it
196 * is not updated. While the designers of the bi-mode
197 * predictor don't explicity say why this is done, one
198 * can infer that it is to preserve the choice predictor's
199 * bias with respect to the branch being predicted; afterall,
200 * the whole point of the bi-mode predictor is to identify the
201 * atypical case when a branch deviates from its bias.
203 if (history
->finalPred
== history
->takenUsed
) {
205 choiceCounters
[choiceHistoryIdx
].increment();
207 choiceCounters
[choiceHistoryIdx
].decrement();
211 // always update the choice predictor on an incorrect prediction
213 choiceCounters
[choiceHistoryIdx
].increment();
215 choiceCounters
[choiceHistoryIdx
].decrement();
221 globalHistoryReg
= (history
->globalHistoryReg
<< 1) | 1;
223 globalHistoryReg
= (history
->globalHistoryReg
<< 1);
225 globalHistoryReg
&= historyRegisterMask
;
233 BiModeBP::retireSquashed(void *bp_history
)
235 BPHistory
*history
= static_cast<BPHistory
*>(bp_history
);
240 BiModeBP::getGHR(void *bp_history
) const
242 return static_cast<BPHistory
*>(bp_history
)->globalHistoryReg
;
246 BiModeBP::updateGlobalHistReg(bool taken
)
248 globalHistoryReg
= taken
? (globalHistoryReg
<< 1) | 1 :
249 (globalHistoryReg
<< 1);
250 globalHistoryReg
&= historyRegisterMask
;
254 BiModeBPParams::create()
256 return new BiModeBP(this);