4d435a82fe7f3aea14ffea5e8c07d0a3d1889e25
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.
30 * Implementation of a bi-mode branch predictor
33 #include "cpu/pred/bi_mode.hh"
35 #include "base/bitfield.hh"
36 #include "base/intmath.hh"
38 BiModeBP::BiModeBP(const BiModeBPParams
¶ms
)
40 globalHistoryReg(params
.numThreads
, 0),
41 globalHistoryBits(ceilLog2(params
.globalPredictorSize
)),
42 choicePredictorSize(params
.choicePredictorSize
),
43 choiceCtrBits(params
.choiceCtrBits
),
44 globalPredictorSize(params
.globalPredictorSize
),
45 globalCtrBits(params
.globalCtrBits
),
46 choiceCounters(choicePredictorSize
, SatCounter(choiceCtrBits
)),
47 takenCounters(globalPredictorSize
, SatCounter(globalCtrBits
)),
48 notTakenCounters(globalPredictorSize
, SatCounter(globalCtrBits
))
50 if (!isPowerOf2(choicePredictorSize
))
51 fatal("Invalid choice predictor size.\n");
52 if (!isPowerOf2(globalPredictorSize
))
53 fatal("Invalid global history predictor size.\n");
55 historyRegisterMask
= mask(globalHistoryBits
);
56 choiceHistoryMask
= choicePredictorSize
- 1;
57 globalHistoryMask
= globalPredictorSize
- 1;
59 choiceThreshold
= (ULL(1) << (choiceCtrBits
- 1)) - 1;
60 takenThreshold
= (ULL(1) << (globalCtrBits
- 1)) - 1;
61 notTakenThreshold
= (ULL(1) << (globalCtrBits
- 1)) - 1;
65 * For an unconditional branch we set its history such that
66 * everything is set to taken. I.e., its choice predictor
67 * chooses the taken array and the taken array predicts taken.
70 BiModeBP::uncondBranch(ThreadID tid
, Addr pc
, void * &bpHistory
)
72 BPHistory
*history
= new BPHistory
;
73 history
->globalHistoryReg
= globalHistoryReg
[tid
];
74 history
->takenUsed
= true;
75 history
->takenPred
= true;
76 history
->notTakenPred
= true;
77 history
->finalPred
= true;
78 bpHistory
= static_cast<void*>(history
);
79 updateGlobalHistReg(tid
, true);
83 BiModeBP::squash(ThreadID tid
, void *bpHistory
)
85 BPHistory
*history
= static_cast<BPHistory
*>(bpHistory
);
86 globalHistoryReg
[tid
] = history
->globalHistoryReg
;
92 * Here we lookup the actual branch prediction. We use the PC to
93 * identify the bias of a particular branch, which is based on the
94 * prediction in the choice array. A hash of the global history
95 * register and a branch's PC is used to index into both the taken
96 * and not-taken predictors, which both present a prediction. The
97 * choice array's prediction is used to select between the two
98 * direction predictors for the final branch prediction.
101 BiModeBP::lookup(ThreadID tid
, Addr branchAddr
, void * &bpHistory
)
103 unsigned choiceHistoryIdx
= ((branchAddr
>> instShiftAmt
)
104 & choiceHistoryMask
);
105 unsigned globalHistoryIdx
= (((branchAddr
>> instShiftAmt
)
106 ^ globalHistoryReg
[tid
])
107 & globalHistoryMask
);
109 assert(choiceHistoryIdx
< choicePredictorSize
);
110 assert(globalHistoryIdx
< globalPredictorSize
);
112 bool choicePrediction
= choiceCounters
[choiceHistoryIdx
]
114 bool takenGHBPrediction
= takenCounters
[globalHistoryIdx
]
116 bool notTakenGHBPrediction
= notTakenCounters
[globalHistoryIdx
]
118 bool finalPrediction
;
120 BPHistory
*history
= new BPHistory
;
121 history
->globalHistoryReg
= globalHistoryReg
[tid
];
122 history
->takenUsed
= choicePrediction
;
123 history
->takenPred
= takenGHBPrediction
;
124 history
->notTakenPred
= notTakenGHBPrediction
;
126 if (choicePrediction
) {
127 finalPrediction
= takenGHBPrediction
;
129 finalPrediction
= notTakenGHBPrediction
;
132 history
->finalPred
= finalPrediction
;
133 bpHistory
= static_cast<void*>(history
);
134 updateGlobalHistReg(tid
, finalPrediction
);
136 return finalPrediction
;
140 BiModeBP::btbUpdate(ThreadID tid
, Addr branchAddr
, void * &bpHistory
)
142 globalHistoryReg
[tid
] &= (historyRegisterMask
& ~ULL(1));
145 /* Only the selected direction predictor will be updated with the final
146 * outcome; the status of the unselected one will not be altered. The choice
147 * predictor is always updated with the branch outcome, except when the
148 * choice is opposite to the branch outcome but the selected counter of
149 * the direction predictors makes a correct final prediction.
152 BiModeBP::update(ThreadID tid
, Addr branchAddr
, bool taken
, void *bpHistory
,
153 bool squashed
, const StaticInstPtr
& inst
, Addr corrTarget
)
157 BPHistory
*history
= static_cast<BPHistory
*>(bpHistory
);
159 // We do not update the counters speculatively on a squash.
160 // We just restore the global history register.
162 globalHistoryReg
[tid
] = (history
->globalHistoryReg
<< 1) | taken
;
166 unsigned choiceHistoryIdx
= ((branchAddr
>> instShiftAmt
)
167 & choiceHistoryMask
);
168 unsigned globalHistoryIdx
= (((branchAddr
>> instShiftAmt
)
169 ^ history
->globalHistoryReg
)
170 & globalHistoryMask
);
172 assert(choiceHistoryIdx
< choicePredictorSize
);
173 assert(globalHistoryIdx
< globalPredictorSize
);
175 if (history
->takenUsed
) {
176 // if the taken array's prediction was used, update it
178 takenCounters
[globalHistoryIdx
]++;
180 takenCounters
[globalHistoryIdx
]--;
183 // if the not-taken array's prediction was used, update it
185 notTakenCounters
[globalHistoryIdx
]++;
187 notTakenCounters
[globalHistoryIdx
]--;
191 if (history
->finalPred
== taken
) {
192 /* If the final prediction matches the actual branch's
193 * outcome and the choice predictor matches the final
194 * outcome, we update the choice predictor, otherwise it
195 * is not updated. While the designers of the bi-mode
196 * predictor don't explicity say why this is done, one
197 * can infer that it is to preserve the choice predictor's
198 * bias with respect to the branch being predicted; afterall,
199 * the whole point of the bi-mode predictor is to identify the
200 * atypical case when a branch deviates from its bias.
202 if (history
->finalPred
== history
->takenUsed
) {
204 choiceCounters
[choiceHistoryIdx
]++;
206 choiceCounters
[choiceHistoryIdx
]--;
210 // always update the choice predictor on an incorrect prediction
212 choiceCounters
[choiceHistoryIdx
]++;
214 choiceCounters
[choiceHistoryIdx
]--;
222 BiModeBP::updateGlobalHistReg(ThreadID tid
, bool taken
)
224 globalHistoryReg
[tid
] = taken
? (globalHistoryReg
[tid
] << 1) | 1 :
225 (globalHistoryReg
[tid
] << 1);
226 globalHistoryReg
[tid
] &= historyRegisterMask
;
230 BiModeBPParams::create() const
232 return new BiModeBP(*this);