gem5  v22.0.0.2
bi_mode.cc
Go to the documentation of this file.
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 
29 /* @file
30  * Implementation of a bi-mode branch predictor
31  */
32 
33 #include "cpu/pred/bi_mode.hh"
34 
35 #include "base/bitfield.hh"
36 #include "base/intmath.hh"
37 
38 namespace gem5
39 {
40 
41 namespace branch_prediction
42 {
43 
44 BiModeBP::BiModeBP(const BiModeBPParams &params)
45  : BPredUnit(params),
46  globalHistoryReg(params.numThreads, 0),
47  globalHistoryBits(ceilLog2(params.globalPredictorSize)),
48  choicePredictorSize(params.choicePredictorSize),
49  choiceCtrBits(params.choiceCtrBits),
50  globalPredictorSize(params.globalPredictorSize),
51  globalCtrBits(params.globalCtrBits),
52  choiceCounters(choicePredictorSize, SatCounter8(choiceCtrBits)),
53  takenCounters(globalPredictorSize, SatCounter8(globalCtrBits)),
54  notTakenCounters(globalPredictorSize, SatCounter8(globalCtrBits))
55 {
57  fatal("Invalid choice predictor size.\n");
59  fatal("Invalid global history predictor size.\n");
60 
64 
65  choiceThreshold = (1ULL << (choiceCtrBits - 1)) - 1;
66  takenThreshold = (1ULL << (globalCtrBits - 1)) - 1;
67  notTakenThreshold = (1ULL << (globalCtrBits - 1)) - 1;
68 }
69 
70 /*
71  * For an unconditional branch we set its history such that
72  * everything is set to taken. I.e., its choice predictor
73  * chooses the taken array and the taken array predicts taken.
74  */
75 void
76 BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory)
77 {
78  BPHistory *history = new BPHistory;
79  history->globalHistoryReg = globalHistoryReg[tid];
80  history->takenUsed = true;
81  history->takenPred = true;
82  history->notTakenPred = true;
83  history->finalPred = true;
84  bpHistory = static_cast<void*>(history);
85  updateGlobalHistReg(tid, true);
86 }
87 
88 void
89 BiModeBP::squash(ThreadID tid, void *bpHistory)
90 {
91  BPHistory *history = static_cast<BPHistory*>(bpHistory);
92  globalHistoryReg[tid] = history->globalHistoryReg;
93 
94  delete history;
95 }
96 
97 /*
98  * Here we lookup the actual branch prediction. We use the PC to
99  * identify the bias of a particular branch, which is based on the
100  * prediction in the choice array. A hash of the global history
101  * register and a branch's PC is used to index into both the taken
102  * and not-taken predictors, which both present a prediction. The
103  * choice array's prediction is used to select between the two
104  * direction predictors for the final branch prediction.
105  */
106 bool
107 BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory)
108 {
109  unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
111  unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
112  ^ globalHistoryReg[tid])
114 
115  assert(choiceHistoryIdx < choicePredictorSize);
116  assert(globalHistoryIdx < globalPredictorSize);
117 
118  bool choicePrediction = choiceCounters[choiceHistoryIdx]
119  > choiceThreshold;
120  bool takenGHBPrediction = takenCounters[globalHistoryIdx]
121  > takenThreshold;
122  bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx]
124  bool finalPrediction;
125 
126  BPHistory *history = new BPHistory;
127  history->globalHistoryReg = globalHistoryReg[tid];
128  history->takenUsed = choicePrediction;
129  history->takenPred = takenGHBPrediction;
130  history->notTakenPred = notTakenGHBPrediction;
131 
132  if (choicePrediction) {
133  finalPrediction = takenGHBPrediction;
134  } else {
135  finalPrediction = notTakenGHBPrediction;
136  }
137 
138  history->finalPred = finalPrediction;
139  bpHistory = static_cast<void*>(history);
140  updateGlobalHistReg(tid, finalPrediction);
141 
142  return finalPrediction;
143 }
144 
145 void
146 BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory)
147 {
148  globalHistoryReg[tid] &= (historyRegisterMask & ~1ULL);
149 }
150 
151 /* Only the selected direction predictor will be updated with the final
152  * outcome; the status of the unselected one will not be altered. The choice
153  * predictor is always updated with the branch outcome, except when the
154  * choice is opposite to the branch outcome but the selected counter of
155  * the direction predictors makes a correct final prediction.
156  */
157 void
158 BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory,
159  bool squashed, const StaticInstPtr & inst, Addr corrTarget)
160 {
161  assert(bpHistory);
162 
163  BPHistory *history = static_cast<BPHistory*>(bpHistory);
164 
165  // We do not update the counters speculatively on a squash.
166  // We just restore the global history register.
167  if (squashed) {
168  globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken;
169  return;
170  }
171 
172  unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
174  unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
175  ^ history->globalHistoryReg)
177 
178  assert(choiceHistoryIdx < choicePredictorSize);
179  assert(globalHistoryIdx < globalPredictorSize);
180 
181  if (history->takenUsed) {
182  // if the taken array's prediction was used, update it
183  if (taken) {
184  takenCounters[globalHistoryIdx]++;
185  } else {
186  takenCounters[globalHistoryIdx]--;
187  }
188  } else {
189  // if the not-taken array's prediction was used, update it
190  if (taken) {
191  notTakenCounters[globalHistoryIdx]++;
192  } else {
193  notTakenCounters[globalHistoryIdx]--;
194  }
195  }
196 
197  if (history->finalPred == taken) {
198  /* If the final prediction matches the actual branch's
199  * outcome and the choice predictor matches the final
200  * outcome, we update the choice predictor, otherwise it
201  * is not updated. While the designers of the bi-mode
202  * predictor don't explicity say why this is done, one
203  * can infer that it is to preserve the choice predictor's
204  * bias with respect to the branch being predicted; afterall,
205  * the whole point of the bi-mode predictor is to identify the
206  * atypical case when a branch deviates from its bias.
207  */
208  if (history->finalPred == history->takenUsed) {
209  if (taken) {
210  choiceCounters[choiceHistoryIdx]++;
211  } else {
212  choiceCounters[choiceHistoryIdx]--;
213  }
214  }
215  } else {
216  // always update the choice predictor on an incorrect prediction
217  if (taken) {
218  choiceCounters[choiceHistoryIdx]++;
219  } else {
220  choiceCounters[choiceHistoryIdx]--;
221  }
222  }
223 
224  delete history;
225 }
226 
227 void
229 {
230  globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 :
231  (globalHistoryReg[tid] << 1);
233 }
234 
235 } // namespace branch_prediction
236 } // namespace gem5
fatal
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:190
gem5::branch_prediction::BiModeBP::BPHistory::notTakenPred
bool notTakenPred
Definition: bi_mode.hh:88
gem5::branch_prediction::BiModeBP::globalPredictorSize
unsigned globalPredictorSize
Definition: bi_mode.hh:102
gem5::branch_prediction::BiModeBP::globalHistoryBits
unsigned globalHistoryBits
Definition: bi_mode.hh:96
gem5::branch_prediction::BiModeBP::uncondBranch
void uncondBranch(ThreadID tid, Addr pc, void *&bp_history)
Definition: bi_mode.cc:76
gem5::branch_prediction::BiModeBP::choiceHistoryMask
unsigned choiceHistoryMask
Definition: bi_mode.hh:101
gem5::branch_prediction::BiModeBP::BPHistory::globalHistoryReg
unsigned globalHistoryReg
Definition: bi_mode.hh:76
gem5::branch_prediction::BiModeBP::choicePredictorSize
unsigned choicePredictorSize
Definition: bi_mode.hh:99
gem5::branch_prediction::BiModeBP::BPHistory::finalPred
bool finalPred
Definition: bi_mode.hh:92
gem5::isPowerOf2
static constexpr bool isPowerOf2(const T &n)
Definition: intmath.hh:98
gem5::branch_prediction::BiModeBP::takenCounters
std::vector< SatCounter8 > takenCounters
Definition: bi_mode.hh:109
gem5::RefCountingPtr< StaticInst >
gem5::mask
constexpr uint64_t mask(unsigned nbits)
Generate a 64-bit mask of 'nbits' 1s, right justified.
Definition: bitfield.hh:63
gem5::branch_prediction::BiModeBP::BiModeBP
BiModeBP(const BiModeBPParams &params)
Definition: bi_mode.cc:44
gem5::GenericSatCounter< uint8_t >
gem5::branch_prediction::BiModeBP::historyRegisterMask
unsigned historyRegisterMask
Definition: bi_mode.hh:97
gem5::branch_prediction::BiModeBP::BPHistory
Definition: bi_mode.hh:74
gem5::branch_prediction::BiModeBP::globalHistoryMask
unsigned globalHistoryMask
Definition: bi_mode.hh:104
bitfield.hh
gem5::branch_prediction::BiModeBP::btbUpdate
void btbUpdate(ThreadID tid, Addr branch_addr, void *&bp_history)
If a branch is not taken, because the BTB address is invalid or missing, this function sets the appro...
Definition: bi_mode.cc:146
gem5::branch_prediction::BiModeBP::BPHistory::takenUsed
bool takenUsed
Definition: bi_mode.hh:80
gem5::branch_prediction::BiModeBP::BPHistory::takenPred
bool takenPred
Definition: bi_mode.hh:84
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::branch_prediction::BiModeBP::notTakenCounters
std::vector< SatCounter8 > notTakenCounters
Definition: bi_mode.hh:111
gem5::branch_prediction::BiModeBP::choiceThreshold
unsigned choiceThreshold
Definition: bi_mode.hh:113
gem5::branch_prediction::BPredUnit::instShiftAmt
const unsigned instShiftAmt
Number of bits to shift instructions by for predictor addresses.
Definition: bpred_unit.hh:338
gem5::ceilLog2
static constexpr int ceilLog2(const T &n)
Definition: intmath.hh:84
gem5::branch_prediction::BiModeBP::globalHistoryReg
std::vector< unsigned > globalHistoryReg
Definition: bi_mode.hh:95
gem5::branch_prediction::BiModeBP::globalCtrBits
unsigned globalCtrBits
Definition: bi_mode.hh:103
gem5::branch_prediction::BiModeBP::updateGlobalHistReg
void updateGlobalHistReg(ThreadID tid, bool taken)
Definition: bi_mode.cc:228
gem5::branch_prediction::BiModeBP::lookup
bool lookup(ThreadID tid, Addr branch_addr, void *&bp_history)
Looks up a given PC in the BP to see if it is taken or not taken.
Definition: bi_mode.cc:107
gem5::MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:243
gem5::branch_prediction::BPredUnit
Basically a wrapper class to hold both the branch predictor and the BTB.
Definition: bpred_unit.hh:68
bi_mode.hh
gem5::branch_prediction::BiModeBP::notTakenThreshold
unsigned notTakenThreshold
Definition: bi_mode.hh:115
intmath.hh
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: gpu_translation_state.hh:37
gem5::branch_prediction::BiModeBP::update
void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, bool squashed, const StaticInstPtr &inst, Addr corrTarget)
Updates the BP with taken/not taken information.
Definition: bi_mode.cc:158
gem5::branch_prediction::BiModeBP::takenThreshold
unsigned takenThreshold
Definition: bi_mode.hh:114
gem5::branch_prediction::BiModeBP::choiceCtrBits
unsigned choiceCtrBits
Definition: bi_mode.hh:100
gem5::branch_prediction::BiModeBP::squash
void squash(ThreadID tid, void *bp_history)
Definition: bi_mode.cc:89
gem5::ThreadID
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:235
gem5::branch_prediction::BiModeBP::choiceCounters
std::vector< SatCounter8 > choiceCounters
Definition: bi_mode.hh:107

Generated on Thu Jul 28 2022 13:32:28 for gem5 by doxygen 1.8.17