gem5  v20.1.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 TournamentBP::TournamentBP(const TournamentBPParams *params)
47  : BPredUnit(params),
48  localPredictorSize(params->localPredictorSize),
49  localCtrBits(params->localCtrBits),
50  localCtrs(localPredictorSize, SatCounter(localCtrBits)),
51  localHistoryTableSize(params->localHistoryTableSize),
52  localHistoryBits(ceilLog2(params->localPredictorSize)),
53  globalPredictorSize(params->globalPredictorSize),
54  globalCtrBits(params->globalCtrBits),
55  globalCtrs(globalPredictorSize, SatCounter(globalCtrBits)),
56  globalHistory(params->numThreads, 0),
57  globalHistoryBits(
58  ceilLog2(params->globalPredictorSize) >
59  ceilLog2(params->choicePredictorSize) ?
60  ceilLog2(params->globalPredictorSize) :
61  ceilLog2(params->choicePredictorSize)),
62  choicePredictorSize(params->choicePredictorSize),
63  choiceCtrBits(params->choiceCtrBits),
64  choiceCtrs(choicePredictorSize, SatCounter(choiceCtrBits))
65 {
67  fatal("Invalid local predictor size!\n");
68  }
69 
71  fatal("Invalid global predictor size!\n");
72  }
73 
75 
77  fatal("Invalid local history table size!\n");
78  }
79 
80  //Setup the history table for the local table
82 
83  for (int i = 0; i < localHistoryTableSize; ++i)
84  localHistoryTable[i] = 0;
85 
86  // Set up the global history mask
87  // this is equivalent to mask(log2(globalPredictorSize)
89 
91  fatal("Invalid choice predictor size!\n");
92  }
93 
94  // Set up choiceHistoryMask
95  // this is equivalent to mask(log2(choicePredictorSize)
97 
98  //Set up historyRegisterMask
100 
101  //Check that predictors don't use more bits than they have available
103  fatal("Global predictor too large for global history bits!\n");
104  }
106  fatal("Choice predictor too large for global history bits!\n");
107  }
108 
111  inform("More global history bits than required by predictors\n");
112  }
113 
114  // Set thresholds for the three predictors' counters
115  // This is equivalent to (2^(Ctr))/2 - 1
116  localThreshold = (ULL(1) << (localCtrBits - 1)) - 1;
117  globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
118  choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
119 }
120 
121 inline
122 unsigned
124 {
125  // Get low order bits after removing instruction offset.
126  return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1);
127 }
128 
129 inline
130 void
132 {
133  globalHistory[tid] = (globalHistory[tid] << 1) | 1;
135 }
136 
137 inline
138 void
140 {
141  globalHistory[tid] = (globalHistory[tid] << 1);
143 }
144 
145 inline
146 void
147 TournamentBP::updateLocalHistTaken(unsigned local_history_idx)
148 {
149  localHistoryTable[local_history_idx] =
150  (localHistoryTable[local_history_idx] << 1) | 1;
151 }
152 
153 inline
154 void
155 TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
156 {
157  localHistoryTable[local_history_idx] =
158  (localHistoryTable[local_history_idx] << 1);
159 }
160 
161 
162 void
163 TournamentBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history)
164 {
165  unsigned local_history_idx = calcLocHistIdx(branch_addr);
166  //Update Global History to Not Taken (clear LSB)
167  globalHistory[tid] &= (historyRegisterMask & ~ULL(1));
168  //Update Local History to Not Taken
169  localHistoryTable[local_history_idx] =
170  localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
171 }
172 
173 bool
174 TournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history)
175 {
176  bool local_prediction;
177  unsigned local_history_idx;
178  unsigned local_predictor_idx;
179 
180  bool global_prediction;
181  bool choice_prediction;
182 
183  //Lookup in the local predictor to get its branch prediction
184  local_history_idx = calcLocHistIdx(branch_addr);
185  local_predictor_idx = localHistoryTable[local_history_idx]
187  local_prediction = localCtrs[local_predictor_idx] > localThreshold;
188 
189  //Lookup in the global predictor to get its branch prediction
190  global_prediction = globalThreshold <
192 
193  //Lookup in the choice predictor to see which one to use
194  choice_prediction = choiceThreshold <
196 
197  // Create BPHistory and pass it back to be recorded.
198  BPHistory *history = new BPHistory;
199  history->globalHistory = globalHistory[tid];
200  history->localPredTaken = local_prediction;
201  history->globalPredTaken = global_prediction;
202  history->globalUsed = choice_prediction;
203  history->localHistoryIdx = local_history_idx;
204  history->localHistory = local_predictor_idx;
205  bp_history = (void *)history;
206 
207  assert(local_history_idx < localHistoryTableSize);
208 
209  // Speculative update of the global history and the
210  // selected local history.
211  if (choice_prediction) {
212  if (global_prediction) {
214  updateLocalHistTaken(local_history_idx);
215  return true;
216  } else {
218  updateLocalHistNotTaken(local_history_idx);
219  return false;
220  }
221  } else {
222  if (local_prediction) {
224  updateLocalHistTaken(local_history_idx);
225  return true;
226  } else {
228  updateLocalHistNotTaken(local_history_idx);
229  return false;
230  }
231  }
232 }
233 
234 void
235 TournamentBP::uncondBranch(ThreadID tid, Addr pc, void * &bp_history)
236 {
237  // Create BPHistory and pass it back to be recorded.
238  BPHistory *history = new BPHistory;
239  history->globalHistory = globalHistory[tid];
240  history->localPredTaken = true;
241  history->globalPredTaken = true;
242  history->globalUsed = true;
245  bp_history = static_cast<void *>(history);
246 
248 }
249 
250 void
251 TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken,
252  void *bp_history, bool squashed,
253  const StaticInstPtr & inst, Addr corrTarget)
254 {
255  assert(bp_history);
256 
257  BPHistory *history = static_cast<BPHistory *>(bp_history);
258 
259  unsigned local_history_idx = calcLocHistIdx(branch_addr);
260 
261  assert(local_history_idx < localHistoryTableSize);
262 
263  // Unconditional branches do not use local history.
264  bool old_local_pred_valid = history->localHistory !=
266 
267  // If this is a misprediction, restore the speculatively
268  // updated state (global history register and local history)
269  // and update again.
270  if (squashed) {
271  // Global history restore and update
272  globalHistory[tid] = (history->globalHistory << 1) | taken;
274 
275  // Local history restore and update.
276  if (old_local_pred_valid) {
277  localHistoryTable[local_history_idx] =
278  (history->localHistory << 1) | taken;
279  }
280 
281  return;
282  }
283 
284  unsigned old_local_pred_index = history->localHistory &
286 
287  assert(old_local_pred_index < localPredictorSize);
288 
289  // Update the choice predictor to tell it which one was correct if
290  // there was a prediction.
291  if (history->localPredTaken != history->globalPredTaken &&
292  old_local_pred_valid)
293  {
294  // If the local prediction matches the actual outcome,
295  // decrement the counter. Otherwise increment the
296  // counter.
297  unsigned choice_predictor_idx =
298  history->globalHistory & choiceHistoryMask;
299  if (history->localPredTaken == taken) {
300  choiceCtrs[choice_predictor_idx]--;
301  } else if (history->globalPredTaken == taken) {
302  choiceCtrs[choice_predictor_idx]++;
303  }
304  }
305 
306  // Update the counters with the proper
307  // resolution of the branch. Histories are updated
308  // speculatively, restored upon squash() calls, and
309  // recomputed upon update(squash = true) calls,
310  // so they do not need to be updated.
311  unsigned global_predictor_idx =
312  history->globalHistory & globalHistoryMask;
313  if (taken) {
314  globalCtrs[global_predictor_idx]++;
315  if (old_local_pred_valid) {
316  localCtrs[old_local_pred_index]++;
317  }
318  } else {
319  globalCtrs[global_predictor_idx]--;
320  if (old_local_pred_valid) {
321  localCtrs[old_local_pred_index]--;
322  }
323  }
324 
325  // We're done with this history, now delete it.
326  delete history;
327 }
328 
329 void
330 TournamentBP::squash(ThreadID tid, void *bp_history)
331 {
332  BPHistory *history = static_cast<BPHistory *>(bp_history);
333 
334  // Restore global history to state prior to this branch.
335  globalHistory[tid] = history->globalHistory;
336 
337  // Restore local history
338  if (history->localHistoryIdx != invalidPredictorIndex) {
339  localHistoryTable[history->localHistoryIdx] = history->localHistory;
340  }
341 
342  // Delete this BPHistory now that we're done with it.
343  delete history;
344 }
345 
347 TournamentBPParams::create()
348 {
349  return new TournamentBP(this);
350 }
351 
352 #ifdef DEBUG
353 int
354 TournamentBP::BPHistory::newCount = 0;
355 #endif
fatal
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:183
TournamentBP::choicePredictorSize
unsigned choicePredictorSize
Number of entries in the choice predictor.
Definition: tournament.hh:225
TournamentBP::globalHistoryMask
unsigned globalHistoryMask
Mask to apply to globalHistory to access global history table.
Definition: tournament.hh:214
TournamentBP::invalidPredictorIndex
static const int invalidPredictorIndex
Flag for invalid predictor index.
Definition: tournament.hh:172
tournament.hh
TournamentBP::updateLocalHistTaken
void updateLocalHistTaken(unsigned local_history_idx)
Updates local histories as taken.
Definition: tournament.cc:147
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:236
TournamentBP::localPredictorMask
unsigned localPredictorMask
Mask to truncate values stored in the local history table.
Definition: tournament.hh:177
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
TournamentBP::choiceThreshold
unsigned choiceThreshold
Definition: tournament.hh:238
ThreadID
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:227
TournamentBP::localHistoryTable
std::vector< unsigned > localHistoryTable
Array of local history table entries.
Definition: tournament.hh:186
TournamentBP::localCtrBits
unsigned localCtrBits
Number of bits of the local predictor's counters.
Definition: tournament.hh:180
TournamentBP::BPHistory::localHistory
unsigned localHistory
Definition: tournament.hh:165
TournamentBP::BPHistory::localPredTaken
bool localPredTaken
Definition: tournament.hh:166
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:163
TournamentBP::TournamentBP
TournamentBP(const TournamentBPParams *params)
Default branch predictor constructor.
Definition: tournament.cc:46
TournamentBP::squash
void squash(ThreadID tid, void *bp_history)
Restores the global branch history on a squash.
Definition: tournament.cc:330
TournamentBP::BPHistory::globalUsed
bool globalUsed
Definition: tournament.hh:168
TournamentBP::updateGlobalHistTaken
void updateGlobalHistTaken(ThreadID tid)
Updates global history as taken.
Definition: tournament.cc:131
TournamentBP::localHistoryBits
unsigned localHistoryBits
Number of bits for each entry of the local history table.
Definition: tournament.hh:192
BPredUnit::instShiftAmt
const unsigned instShiftAmt
Number of bits to shift instructions by for predictor addresses.
Definition: bpred_unit.hh:312
TournamentBP::choiceCtrBits
unsigned choiceCtrBits
Number of bits in the choice predictor's counters.
Definition: tournament.hh:228
TournamentBP::BPHistory
The branch history information that is created upon predicting a branch.
Definition: tournament.hh:154
TournamentBP::globalHistory
std::vector< unsigned > globalHistory
Global history register.
Definition: tournament.hh:206
TournamentBP::globalThreshold
unsigned globalThreshold
Definition: tournament.hh:237
TournamentBP::BPHistory::globalHistory
unsigned globalHistory
Definition: tournament.hh:163
ceilLog2
int ceilLog2(const T &n)
Definition: intmath.hh:88
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:174
bitfield.hh
TournamentBP::localCtrs
std::vector< SatCounter > localCtrs
Local counters.
Definition: tournament.hh:183
TournamentBP::updateLocalHistNotTaken
void updateLocalHistNotTaken(unsigned local_history_idx)
Updates local histories as not taken.
Definition: tournament.cc:155
MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:240
TournamentBP::historyRegisterMask
unsigned historyRegisterMask
Mask to control how much history is stored.
Definition: tournament.hh:222
TournamentBP::calcLocHistIdx
unsigned calcLocHistIdx(Addr &branch_addr)
Returns the local history index, given a branch address.
Definition: tournament.cc:123
BPredUnit
Basically a wrapper class to hold both the branch predictor and the BTB.
Definition: bpred_unit.hh:62
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
TournamentBP::updateGlobalHistNotTaken
void updateGlobalHistNotTaken(ThreadID tid)
Updates global history as not taken.
Definition: tournament.cc:139
TournamentBP::localHistoryTableSize
unsigned localHistoryTableSize
Number of entries in the local history table.
Definition: tournament.hh:189
TournamentBP::BPHistory::localHistoryIdx
unsigned localHistoryIdx
Definition: tournament.hh:164
SatCounter
Implements an n bit saturating counter and provides methods to increment, decrement,...
Definition: sat_counter.hh:54
TournamentBP::BPHistory::globalPredTaken
bool globalPredTaken
Definition: tournament.hh:167
TournamentBP::localPredictorSize
unsigned localPredictorSize
Number of counters in the local predictor.
Definition: tournament.hh:174
inform
#define inform(...)
Definition: logging.hh:240
TournamentBP::globalPredictorSize
unsigned globalPredictorSize
Number of entries in the global predictor.
Definition: tournament.hh:195
TournamentBP::choiceCtrs
std::vector< SatCounter > choiceCtrs
Array of counters that make up the choice predictor.
Definition: tournament.hh:231
TournamentBP
Implements a tournament branch predictor, hopefully identical to the one used in the 21264.
Definition: tournament.hh:59
RefCountingPtr< StaticInst >
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:235
TournamentBP::globalCtrs
std::vector< SatCounter > globalCtrs
Array of counters that make up the global predictor.
Definition: tournament.hh:201
intmath.hh
TournamentBP::globalHistoryBits
unsigned globalHistoryBits
Number of bits for the global history.
Definition: tournament.hh:210
isPowerOf2
bool isPowerOf2(const T &n)
Definition: intmath.hh:102
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:251
ULL
#define ULL(N)
uint64_t constant
Definition: types.hh:50
TournamentBP::globalCtrBits
unsigned globalCtrBits
Number of bits of the global predictor's counters.
Definition: tournament.hh:198
ArmISA::mask
Bitfield< 28, 24 > mask
Definition: miscregs_types.hh:711
TournamentBP::choiceHistoryMask
unsigned choiceHistoryMask
Mask to apply to globalHistory to access choice history table.
Definition: tournament.hh:218

Generated on Wed Sep 30 2020 14:02:09 for gem5 by doxygen 1.8.17