gem5  v21.2.0.0
tournament.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2011, 2014 ARM Limited
3  * All rights reserved
4  *
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.
13  *
14  * Copyright (c) 2004-2006 The Regents of The University of Michigan
15  * All rights reserved.
16  *
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.
27  *
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.
39  */
40 
41 #include "cpu/pred/tournament.hh"
42 
43 #include "base/bitfield.hh"
44 #include "base/intmath.hh"
45 
46 namespace gem5
47 {
48 
49 namespace branch_prediction
50 {
51 
52 TournamentBP::TournamentBP(const TournamentBPParams &params)
53  : BPredUnit(params),
54  localPredictorSize(params.localPredictorSize),
55  localCtrBits(params.localCtrBits),
56  localCtrs(localPredictorSize, SatCounter8(localCtrBits)),
57  localHistoryTableSize(params.localHistoryTableSize),
58  localHistoryBits(ceilLog2(params.localPredictorSize)),
59  globalPredictorSize(params.globalPredictorSize),
60  globalCtrBits(params.globalCtrBits),
61  globalCtrs(globalPredictorSize, SatCounter8(globalCtrBits)),
62  globalHistory(params.numThreads, 0),
63  globalHistoryBits(
64  ceilLog2(params.globalPredictorSize) >
65  ceilLog2(params.choicePredictorSize) ?
66  ceilLog2(params.globalPredictorSize) :
67  ceilLog2(params.choicePredictorSize)),
68  choicePredictorSize(params.choicePredictorSize),
69  choiceCtrBits(params.choiceCtrBits),
70  choiceCtrs(choicePredictorSize, SatCounter8(choiceCtrBits))
71 {
73  fatal("Invalid local predictor size!\n");
74  }
75 
77  fatal("Invalid global predictor size!\n");
78  }
79 
81 
83  fatal("Invalid local history table size!\n");
84  }
85 
86  //Setup the history table for the local table
88 
89  for (int i = 0; i < localHistoryTableSize; ++i)
90  localHistoryTable[i] = 0;
91 
92  // Set up the global history mask
93  // this is equivalent to mask(log2(globalPredictorSize)
95 
97  fatal("Invalid choice predictor size!\n");
98  }
99 
100  // Set up choiceHistoryMask
101  // this is equivalent to mask(log2(choicePredictorSize)
103 
104  //Set up historyRegisterMask
106 
107  //Check that predictors don't use more bits than they have available
109  fatal("Global predictor too large for global history bits!\n");
110  }
112  fatal("Choice predictor too large for global history bits!\n");
113  }
114 
117  inform("More global history bits than required by predictors\n");
118  }
119 
120  // Set thresholds for the three predictors' counters
121  // This is equivalent to (2^(Ctr))/2 - 1
122  localThreshold = (1ULL << (localCtrBits - 1)) - 1;
123  globalThreshold = (1ULL << (globalCtrBits - 1)) - 1;
124  choiceThreshold = (1ULL << (choiceCtrBits - 1)) - 1;
125 }
126 
127 inline
128 unsigned
130 {
131  // Get low order bits after removing instruction offset.
132  return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
133 }
134 
135 inline
136 void
138 {
139  globalHistory[tid] = (globalHistory[tid] << 1) | 1;
141 }
142 
143 inline
144 void
146 {
147  globalHistory[tid] = (globalHistory[tid] << 1);
149 }
150 
151 inline
152 void
153 TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
154 {
155  localHistoryTable[local_history_idx] =
156  (localHistoryTable[local_history_idx] << 1) | 1;
157 }
158 
159 inline
160 void
161 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
162 {
163  localHistoryTable[local_history_idx] =
164  (localHistoryTable[local_history_idx] << 1);
165 }
166 
167 
168 void
169 TournamentBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history)
170 {
171  unsigned local_history_idx = calcLocHistIdx(branch_addr);
172  //Update Global History to Not Taken (clear LSB)
173  globalHistory[tid] &= (historyRegisterMask & ~1ULL);
174  //Update Local History to Not Taken
175  localHistoryTable[local_history_idx] =
176  localHistoryTable[local_history_idx] & (localPredictorMask & ~1ULL);
177 }
178 
179 bool
180 TournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history)
181 {
182  bool local_prediction;
183  unsigned local_history_idx;
184  unsigned local_predictor_idx;
185 
186  bool global_prediction;
187  bool choice_prediction;
188 
189  //Lookup in the local predictor to get its branch prediction
190  local_history_idx = calcLocHistIdx(branch_addr);
191  local_predictor_idx = localHistoryTable[local_history_idx]
193  local_prediction = localCtrs[local_predictor_idx] > localThreshold;
194 
195  //Lookup in the global predictor to get its branch prediction
196  global_prediction = globalThreshold <
198 
199  //Lookup in the choice predictor to see which one to use
200  choice_prediction = choiceThreshold <
202 
203  // Create BPHistory and pass it back to be recorded.
204  BPHistory *history = new BPHistory;
205  history->globalHistory = globalHistory[tid];
206  history->localPredTaken = local_prediction;
207  history->globalPredTaken = global_prediction;
208  history->globalUsed = choice_prediction;
209  history->localHistoryIdx = local_history_idx;
210  history->localHistory = local_predictor_idx;
211  bp_history = (void *)history;
212 
213  assert(local_history_idx < localHistoryTableSize);
214 
215  // Speculative update of the global history and the
216  // selected local history.
217  if (choice_prediction) {
218  if (global_prediction) {
220  updateLocalHistTaken(local_history_idx);
221  return true;
222  } else {
224  updateLocalHistNotTaken(local_history_idx);
225  return false;
226  }
227  } else {
228  if (local_prediction) {
230  updateLocalHistTaken(local_history_idx);
231  return true;
232  } else {
234  updateLocalHistNotTaken(local_history_idx);
235  return false;
236  }
237  }
238 }
239 
240 void
241 TournamentBP::uncondBranch(ThreadID tid, Addr pc, void * &bp_history)
242 {
243  // Create BPHistory and pass it back to be recorded.
244  BPHistory *history = new BPHistory;
245  history->globalHistory = globalHistory[tid];
246  history->localPredTaken = true;
247  history->globalPredTaken = true;
248  history->globalUsed = true;
251  bp_history = static_cast<void *>(history);
252 
254 }
255 
256 void
257 TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken,
258  void *bp_history, bool squashed,
259  const StaticInstPtr & inst, Addr corrTarget)
260 {
261  assert(bp_history);
262 
263  BPHistory *history = static_cast<BPHistory *>(bp_history);
264 
265  unsigned local_history_idx = calcLocHistIdx(branch_addr);
266 
267  assert(local_history_idx < localHistoryTableSize);
268 
269  // Unconditional branches do not use local history.
270  bool old_local_pred_valid = history->localHistory !=
272 
273  // If this is a misprediction, restore the speculatively
274  // updated state (global history register and local history)
275  // and update again.
276  if (squashed) {
277  // Global history restore and update
278  globalHistory[tid] = (history->globalHistory << 1) | taken;
280 
281  // Local history restore and update.
282  if (old_local_pred_valid) {
283  localHistoryTable[local_history_idx] =
284  (history->localHistory << 1) | taken;
285  }
286 
287  return;
288  }
289 
290  unsigned old_local_pred_index = history->localHistory &
292 
293  assert(old_local_pred_index < localPredictorSize);
294 
295  // Update the choice predictor to tell it which one was correct if
296  // there was a prediction.
297  if (history->localPredTaken != history->globalPredTaken &&
298  old_local_pred_valid)
299  {
300  // If the local prediction matches the actual outcome,
301  // decrement the counter. Otherwise increment the
302  // counter.
303  unsigned choice_predictor_idx =
304  history->globalHistory & choiceHistoryMask;
305  if (history->localPredTaken == taken) {
306  choiceCtrs[choice_predictor_idx]--;
307  } else if (history->globalPredTaken == taken) {
308  choiceCtrs[choice_predictor_idx]++;
309  }
310  }
311 
312  // Update the counters with the proper
313  // resolution of the branch. Histories are updated
314  // speculatively, restored upon squash() calls, and
315  // recomputed upon update(squash = true) calls,
316  // so they do not need to be updated.
317  unsigned global_predictor_idx =
318  history->globalHistory & globalHistoryMask;
319  if (taken) {
320  globalCtrs[global_predictor_idx]++;
321  if (old_local_pred_valid) {
322  localCtrs[old_local_pred_index]++;
323  }
324  } else {
325  globalCtrs[global_predictor_idx]--;
326  if (old_local_pred_valid) {
327  localCtrs[old_local_pred_index]--;
328  }
329  }
330 
331  // We're done with this history, now delete it.
332  delete history;
333 }
334 
335 void
336 TournamentBP::squash(ThreadID tid, void *bp_history)
337 {
338  BPHistory *history = static_cast<BPHistory *>(bp_history);
339 
340  // Restore global history to state prior to this branch.
341  globalHistory[tid] = history->globalHistory;
342 
343  // Restore local history
344  if (history->localHistoryIdx != invalidPredictorIndex) {
345  localHistoryTable[history->localHistoryIdx] = history->localHistory;
346  }
347 
348  // Delete this BPHistory now that we're done with it.
349  delete history;
350 }
351 
352 #ifdef DEBUG
353 int
354 TournamentBP::BPHistory::newCount = 0;
355 #endif
356 
357 } // namespace branch_prediction
358 } // namespace gem5
gem5::branch_prediction::TournamentBP::squash
void squash(ThreadID tid, void *bp_history)
Restores the global branch history on a squash.
Definition: tournament.cc:336
gem5::branch_prediction::TournamentBP::BPHistory
The branch history information that is created upon predicting a branch.
Definition: tournament.hh:160
fatal
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:190
gem5::branch_prediction::TournamentBP::BPHistory::globalUsed
bool globalUsed
Definition: tournament.hh:175
tournament.hh
gem5::branch_prediction::TournamentBP::invalidPredictorIndex
static const int invalidPredictorIndex
Flag for invalid predictor index.
Definition: tournament.hh:179
gem5::branch_prediction::TournamentBP::globalThreshold
unsigned globalThreshold
Definition: tournament.hh:244
gem5::branch_prediction::TournamentBP::updateLocalHistTaken
void updateLocalHistTaken(unsigned local_history_idx)
Updates local histories as taken.
Definition: tournament.cc:153
gem5::branch_prediction::TournamentBP::choiceThreshold
unsigned choiceThreshold
Definition: tournament.hh:245
gem5::branch_prediction::TournamentBP::localPredictorMask
unsigned localPredictorMask
Mask to truncate values stored in the local history table.
Definition: tournament.hh:184
gem5::branch_prediction::TournamentBP::uncondBranch
void uncondBranch(ThreadID tid, Addr pc, void *&bp_history)
Records that there was an unconditional branch, and modifies the bp history to point to an object tha...
Definition: tournament.cc:241
gem5::branch_prediction::TournamentBP::localPredictorSize
unsigned localPredictorSize
Number of counters in the local predictor.
Definition: tournament.hh:181
gem5::branch_prediction::TournamentBP::choiceCtrs
std::vector< SatCounter8 > choiceCtrs
Array of counters that make up the choice predictor.
Definition: tournament.hh:238
gem5::branch_prediction::TournamentBP::btbUpdate
void btbUpdate(ThreadID tid, Addr branch_addr, void *&bp_history)
Updates the branch predictor to Not Taken if a BTB entry is invalid or not found.
Definition: tournament.cc:169
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:67
gem5::branch_prediction::TournamentBP::calcLocHistIdx
unsigned calcLocHistIdx(Addr &branch_addr)
Returns the local history index, given a branch address.
Definition: tournament.cc:129
gem5::isPowerOf2
static constexpr bool isPowerOf2(const T &n)
Definition: intmath.hh:98
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::TournamentBP::choiceHistoryMask
unsigned choiceHistoryMask
Mask to apply to globalHistory to access choice history table.
Definition: tournament.hh:225
gem5::GenericSatCounter< uint8_t >
gem5::branch_prediction::TournamentBP::updateGlobalHistNotTaken
void updateGlobalHistNotTaken(ThreadID tid)
Updates global history as not taken.
Definition: tournament.cc:145
bitfield.hh
gem5::branch_prediction::TournamentBP::update
void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, bool squashed, const StaticInstPtr &inst, Addr corrTarget)
Updates the branch predictor with the actual result of a branch.
Definition: tournament.cc:257
gem5::branch_prediction::TournamentBP::globalCtrs
std::vector< SatCounter8 > globalCtrs
Array of counters that make up the global predictor.
Definition: tournament.hh:208
gem5::branch_prediction::TournamentBP::localThreshold
unsigned localThreshold
Thresholds for the counter value; above the threshold is taken, equal to or below the threshold is no...
Definition: tournament.hh:243
gem5::branch_prediction::TournamentBP::BPHistory::globalHistory
unsigned globalHistory
Definition: tournament.hh:170
gem5::branch_prediction::TournamentBP::TournamentBP
TournamentBP(const TournamentBPParams &params)
Default branch predictor constructor.
Definition: tournament.cc:52
gem5::branch_prediction::TournamentBP::historyRegisterMask
unsigned historyRegisterMask
Mask to control how much history is stored.
Definition: tournament.hh:229
gem5::branch_prediction::TournamentBP::BPHistory::localPredTaken
bool localPredTaken
Definition: tournament.hh:173
gem5::branch_prediction::TournamentBP::updateGlobalHistTaken
void updateGlobalHistTaken(ThreadID tid)
Updates global history as taken.
Definition: tournament.cc:137
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::TournamentBP::localCtrs
std::vector< SatCounter8 > localCtrs
Local counters.
Definition: tournament.hh:190
gem5::branch_prediction::TournamentBP::globalHistoryMask
unsigned globalHistoryMask
Mask to apply to globalHistory to access global history table.
Definition: tournament.hh:221
gem5::branch_prediction::TournamentBP::localHistoryBits
unsigned localHistoryBits
Number of bits for each entry of the local history table.
Definition: tournament.hh:199
gem5::branch_prediction::TournamentBP::updateLocalHistNotTaken
void updateLocalHistNotTaken(unsigned local_history_idx)
Updates local histories as not taken.
Definition: tournament.cc:161
gem5::branch_prediction::TournamentBP::choiceCtrBits
unsigned choiceCtrBits
Number of bits in the choice predictor's counters.
Definition: tournament.hh:235
gem5::branch_prediction::BPredUnit::instShiftAmt
const unsigned instShiftAmt
Number of bits to shift instructions by for predictor addresses.
Definition: bpred_unit.hh:338
gem5::branch_prediction::TournamentBP::lookup
bool lookup(ThreadID tid, Addr branch_addr, void *&bp_history)
Looks up the given address in the branch predictor and returns a true/false value as to whether it is...
Definition: tournament.cc:180
gem5::ceilLog2
static constexpr int ceilLog2(const T &n)
Definition: intmath.hh:84
inform
#define inform(...)
Definition: logging.hh:247
gem5::branch_prediction::TournamentBP::choicePredictorSize
unsigned choicePredictorSize
Number of entries in the choice predictor.
Definition: tournament.hh:232
gem5::branch_prediction::TournamentBP::globalCtrBits
unsigned globalCtrBits
Number of bits of the global predictor's counters.
Definition: tournament.hh:205
gem5::branch_prediction::TournamentBP::localHistoryTableSize
unsigned localHistoryTableSize
Number of entries in the local history table.
Definition: tournament.hh:196
gem5::branch_prediction::TournamentBP::BPHistory::localHistoryIdx
unsigned localHistoryIdx
Definition: tournament.hh:171
gem5::MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:243
gem5::branch_prediction::TournamentBP::globalHistoryBits
unsigned globalHistoryBits
Number of bits for the global history.
Definition: tournament.hh:217
gem5::branch_prediction::BPredUnit
Basically a wrapper class to hold both the branch predictor and the BTB.
Definition: bpred_unit.hh:68
gem5::branch_prediction::TournamentBP::localHistoryTable
std::vector< unsigned > localHistoryTable
Array of local history table entries.
Definition: tournament.hh:193
gem5::branch_prediction::TournamentBP::globalPredictorSize
unsigned globalPredictorSize
Number of entries in the global predictor.
Definition: tournament.hh:202
intmath.hh
gem5::branch_prediction::TournamentBP::globalHistory
std::vector< unsigned > globalHistory
Global history register.
Definition: tournament.hh:213
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: tlb.cc:60
gem5::branch_prediction::TournamentBP::BPHistory::globalPredTaken
bool globalPredTaken
Definition: tournament.hh:174
gem5::branch_prediction::TournamentBP::BPHistory::localHistory
unsigned localHistory
Definition: tournament.hh:172
gem5::branch_prediction::TournamentBP::localCtrBits
unsigned localCtrBits
Number of bits of the local predictor's counters.
Definition: tournament.hh:187
gem5::ThreadID
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:242

Generated on Tue Dec 21 2021 11:34:27 for gem5 by doxygen 1.8.17