1/*
2 * Copyright (c) 2014 The Regents of The University of Michigan
3 * All rights reserved.
4 *
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.
15 *
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.
27 *
28 * Authors: Anthony Gutierrez
29 */
30
31/* @file
32 * Implementation of a bi-mode branch predictor
33 */
34
35#include "cpu/pred/bi_mode.hh"
36
37#include "base/bitfield.hh"
38#include "base/intmath.hh"
39
40BiModeBP::BiModeBP(const BiModeBPParams *params)
41 : BPredUnit(params),
42 globalHistoryReg(params->numThreads, 0),
43 globalHistoryBits(ceilLog2(params->globalPredictorSize)),
44 choicePredictorSize(params->choicePredictorSize),
45 choiceCtrBits(params->choiceCtrBits),
46 globalPredictorSize(params->globalPredictorSize),
47 globalCtrBits(params->globalCtrBits),
48 choiceCounters(choicePredictorSize, SatCounter(choiceCtrBits)),
49 takenCounters(globalPredictorSize, SatCounter(globalCtrBits)),
50 notTakenCounters(globalPredictorSize, SatCounter(globalCtrBits))
51{
52 if (!isPowerOf2(choicePredictorSize))
53 fatal("Invalid choice predictor size.\n");
54 if (!isPowerOf2(globalPredictorSize))
55 fatal("Invalid global history predictor size.\n");
56
57 historyRegisterMask = mask(globalHistoryBits);
58 choiceHistoryMask = choicePredictorSize - 1;
59 globalHistoryMask = globalPredictorSize - 1;
60
61 choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
62 takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
63 notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
64}
65
66/*
67 * For an unconditional branch we set its history such that
68 * everything is set to taken. I.e., its choice predictor
69 * chooses the taken array and the taken array predicts taken.
70 */
71void
72BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory)
73{
74 BPHistory *history = new BPHistory;
75 history->globalHistoryReg = globalHistoryReg[tid];
76 history->takenUsed = true;
77 history->takenPred = true;
78 history->notTakenPred = true;
79 history->finalPred = true;
80 bpHistory = static_cast<void*>(history);
81 updateGlobalHistReg(tid, true);
82}
83
84void
85BiModeBP::squash(ThreadID tid, void *bpHistory)
86{
87 BPHistory *history = static_cast<BPHistory*>(bpHistory);
88 globalHistoryReg[tid] = history->globalHistoryReg;
89
90 delete history;
91}
92
93/*
94 * Here we lookup the actual branch prediction. We use the PC to
95 * identify the bias of a particular branch, which is based on the
96 * prediction in the choice array. A hash of the global history
97 * register and a branch's PC is used to index into both the taken
98 * and not-taken predictors, which both present a prediction. The
99 * choice array's prediction is used to select between the two
100 * direction predictors for the final branch prediction.
101 */
102bool
103BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory)
104{
105 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
106 & choiceHistoryMask);
107 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
108 ^ globalHistoryReg[tid])
109 & globalHistoryMask);
110
111 assert(choiceHistoryIdx < choicePredictorSize);
112 assert(globalHistoryIdx < globalPredictorSize);
113
114 bool choicePrediction = choiceCounters[choiceHistoryIdx]
115 > choiceThreshold;
116 bool takenGHBPrediction = takenCounters[globalHistoryIdx]
117 > takenThreshold;
118 bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx]
119 > notTakenThreshold;
120 bool finalPrediction;
121
122 BPHistory *history = new BPHistory;
123 history->globalHistoryReg = globalHistoryReg[tid];
124 history->takenUsed = choicePrediction;
125 history->takenPred = takenGHBPrediction;
126 history->notTakenPred = notTakenGHBPrediction;
127
128 if (choicePrediction) {
129 finalPrediction = takenGHBPrediction;
130 } else {
131 finalPrediction = notTakenGHBPrediction;
132 }
133
134 history->finalPred = finalPrediction;
135 bpHistory = static_cast<void*>(history);
136 updateGlobalHistReg(tid, finalPrediction);
137
138 return finalPrediction;
139}
140
141void
142BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory)
143{
144 globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1));
145}
146
147/* Only the selected direction predictor will be updated with the final
148 * outcome; the status of the unselected one will not be altered. The choice
149 * predictor is always updated with the branch outcome, except when the
150 * choice is opposite to the branch outcome but the selected counter of
151 * the direction predictors makes a correct final prediction.
152 */
153void
154BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory,
155 bool squashed, const StaticInstPtr & inst, Addr corrTarget)
156{
157 assert(bpHistory);
158
159 BPHistory *history = static_cast<BPHistory*>(bpHistory);
160
161 // We do not update the counters speculatively on a squash.
162 // We just restore the global history register.
163 if (squashed) {
164 globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken;
165 return;
166 }
167
168 unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
169 & choiceHistoryMask);
170 unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
171 ^ history->globalHistoryReg)
172 & globalHistoryMask);
173
174 assert(choiceHistoryIdx < choicePredictorSize);
175 assert(globalHistoryIdx < globalPredictorSize);
176
177 if (history->takenUsed) {
178 // if the taken array's prediction was used, update it
179 if (taken) {
180 takenCounters[globalHistoryIdx]++;
181 } else {
182 takenCounters[globalHistoryIdx]--;
183 }
184 } else {
185 // if the not-taken array's prediction was used, update it
186 if (taken) {
187 notTakenCounters[globalHistoryIdx]++;
188 } else {
189 notTakenCounters[globalHistoryIdx]--;
190 }
191 }
192
193 if (history->finalPred == taken) {
194 /* If the final prediction matches the actual branch's
195 * outcome and the choice predictor matches the final
196 * outcome, we update the choice predictor, otherwise it
197 * is not updated. While the designers of the bi-mode
198 * predictor don't explicity say why this is done, one
199 * can infer that it is to preserve the choice predictor's
200 * bias with respect to the branch being predicted; afterall,
201 * the whole point of the bi-mode predictor is to identify the
202 * atypical case when a branch deviates from its bias.
203 */
204 if (history->finalPred == history->takenUsed) {
205 if (taken) {
206 choiceCounters[choiceHistoryIdx]++;
207 } else {
208 choiceCounters[choiceHistoryIdx]--;
209 }
210 }
211 } else {
212 // always update the choice predictor on an incorrect prediction
213 if (taken) {
214 choiceCounters[choiceHistoryIdx]++;
215 } else {
216 choiceCounters[choiceHistoryIdx]--;
217 }
218 }
219
220 delete history;
221}
222
223void
224BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken)
225{
226 globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 :
227 (globalHistoryReg[tid] << 1);
228 globalHistoryReg[tid] &= historyRegisterMask;
229}
230
231BiModeBP*
232BiModeBPParams::create()
233{
234 return new BiModeBP(this);
235}