gem5  v21.1.0.2
loop_predictor.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2014 The University of Wisconsin
3  *
4  * Copyright (c) 2006 INRIA (Institut National de Recherche en
5  * Informatique et en Automatique / French National Research Institute
6  * for Computer Science and Applied Mathematics)
7  *
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions are
12  * met: redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer;
14  * redistributions in binary form must reproduce the above copyright
15  * notice, this list of conditions and the following disclaimer in the
16  * documentation and/or other materials provided with the distribution;
17  * neither the name of the copyright holders nor the names of its
18  * contributors may be used to endorse or promote products derived from
19  * this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
35 
36 #include "base/random.hh"
37 #include "base/trace.hh"
38 #include "debug/LTage.hh"
39 #include "params/LoopPredictor.hh"
40 
41 namespace gem5
42 {
43 
44 namespace branch_prediction
45 {
46 
47 LoopPredictor::LoopPredictor(const LoopPredictorParams &p)
48  : SimObject(p), logSizeLoopPred(p.logSizeLoopPred),
49  loopTableAgeBits(p.loopTableAgeBits),
50  loopTableConfidenceBits(p.loopTableConfidenceBits),
51  loopTableTagBits(p.loopTableTagBits),
52  loopTableIterBits(p.loopTableIterBits),
53  logLoopTableAssoc(p.logLoopTableAssoc),
54  confidenceThreshold((1 << loopTableConfidenceBits) - 1),
55  loopTagMask((1 << loopTableTagBits) - 1),
56  loopNumIterMask((1 << loopTableIterBits) - 1),
57  loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1),
58  loopUseCounter(-1),
59  withLoopBits(p.withLoopBits),
60  useDirectionBit(p.useDirectionBit),
61  useSpeculation(p.useSpeculation),
62  useHashing(p.useHashing),
63  restrictAllocation(p.restrictAllocation),
64  initialLoopIter(p.initialLoopIter),
65  initialLoopAge(p.initialLoopAge),
66  optionalAgeReset(p.optionalAgeReset),
67  stats(this)
68 {
69  assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1));
70 }
71 
72 void
74 {
75  // we use uint16_t type for these vales, so they cannot be more than
76  // 16 bits
77  assert(loopTableTagBits <= 16);
78  assert(loopTableIterBits <= 16);
79 
81 
82  ltable = new LoopEntry[1ULL << logSizeLoopPred];
83 }
84 
87 {
88  return new BranchInfo();
89 }
90 
91 int
92 LoopPredictor::lindex(Addr pc_in, unsigned instShiftAmt) const
93 {
94  // The loop table is implemented as a linear table
95  // If associativity is N (N being 1 << logLoopTableAssoc),
96  // the first N entries are for set 0, the next N entries are for set 1,
97  // and so on.
98  // Thus, this function calculates the set and then it gets left shifted
99  // by logLoopTableAssoc in order to return the index of the first of the
100  // N entries of the set
101  Addr pc = pc_in >> instShiftAmt;
102  if (useHashing) {
103  pc ^= pc_in;
104  }
105  return ((pc & loopSetMask) << logLoopTableAssoc);
106 }
107 
108 int
109 LoopPredictor::finallindex(int index, int lowPcBits, int way) const
110 {
111  return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) :
112  (index))
113  + way;
114 }
115 
116 //loop prediction: only used if high confidence
117 bool
119  unsigned instShiftAmt) const
120 {
121  bi->loopHit = -1;
122  bi->loopPredValid = false;
123  bi->loopIndex = lindex(pc, instShiftAmt);
124 
125  if (useHashing) {
126  unsigned pcShift = logSizeLoopPred - logLoopTableAssoc;
127  bi->loopIndexB = (pc >> pcShift) & loopSetMask;
128  bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift + loopTableTagBits));
129  bi->loopTag &= loopTagMask;
130  } else {
131  unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc;
132  bi->loopTag = (pc >> pcShift) & loopTagMask;
133  // bi->loopIndexB is not used without hash
134  }
135 
136  for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
137  int idx = finallindex(bi->loopIndex, bi->loopIndexB, i);
138  if (ltable[idx].tag == bi->loopTag) {
139  bi->loopHit = i;
140  bi->loopPredValid = calcConf(idx);
141 
142  uint16_t iter = speculative ? ltable[idx].currentIterSpec
143  : ltable[idx].currentIter;
144 
145  if ((iter + 1) == ltable[idx].numIter) {
146  return useDirectionBit ? !(ltable[idx].dir) : false;
147  } else {
148  return useDirectionBit ? (ltable[idx].dir) : true;
149  }
150  }
151  }
152  return false;
153 }
154 
155 bool
157 {
159 }
160 
161 void
163 {
164  if (bi->loopHit>=0) {
165  int index = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
166  if (taken != ltable[index].dir) {
168  } else {
171  }
172  }
173 }
174 
175 bool
177 {
178  return false;
179 }
180 
181 void
182 LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred)
183 {
184  int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
185  if (bi->loopHit >= 0) {
186  //already a hit
187  if (bi->loopPredValid) {
188  if (taken != bi->loopPred) {
189  // free the entry
190  ltable[idx].numIter = 0;
191  ltable[idx].age = 0;
192  ltable[idx].confidence = 0;
193  ltable[idx].currentIter = 0;
194  return;
195  } else if (bi->loopPred != tage_pred || optionalAgeInc()) {
196  DPRINTF(LTage, "Loop Prediction success:%lx\n",pc);
197  unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
198  }
199  }
200 
201  ltable[idx].currentIter =
202  (ltable[idx].currentIter + 1) & loopNumIterMask;
203  if (ltable[idx].currentIter > ltable[idx].numIter) {
204  ltable[idx].confidence = 0;
205  if (ltable[idx].numIter != 0) {
206  // free the entry
207  ltable[idx].numIter = 0;
208  if (optionalAgeReset) {
209  ltable[idx].age = 0;
210  }
211  }
212  }
213 
214  if (taken != (useDirectionBit ? ltable[idx].dir : true)) {
215  if (ltable[idx].currentIter == ltable[idx].numIter) {
216  DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc);
217  unsignedCtrUpdate(ltable[idx].confidence, true,
219  //just do not predict when the loop count is 1 or 2
220  if (ltable[idx].numIter < 3) {
221  // free the entry
222  ltable[idx].dir = taken; // ignored if no useDirectionBit
223  ltable[idx].numIter = 0;
224  ltable[idx].age = 0;
225  ltable[idx].confidence = 0;
226  }
227  } else {
228  DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc);
229  if (ltable[idx].numIter == 0) {
230  // first complete nest;
231  ltable[idx].confidence = 0;
232  ltable[idx].numIter = ltable[idx].currentIter;
233  } else {
234  //not the same number of iterations as last time: free the
235  //entry
236  ltable[idx].numIter = 0;
237  if (optionalAgeReset) {
238  ltable[idx].age = 0;
239  }
240  ltable[idx].confidence = 0;
241  }
242  }
243  ltable[idx].currentIter = 0;
244  }
245 
246  } else if (useDirectionBit ? (bi->predTaken != taken) : taken) {
247  if ((random_mt.random<int>() & 3) == 0 || !restrictAllocation) {
248  //try to allocate an entry on taken branch
249  int nrand = random_mt.random<int>();
250  for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
251  int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1);
252  idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit);
253  if (ltable[idx].age == 0) {
254  DPRINTF(LTage,
255  "Allocating loop pred entry for branch %lx\n",
256  pc);
257  ltable[idx].dir = !taken; // ignored if no useDirectionBit
258  ltable[idx].tag = bi->loopTag;
259  ltable[idx].numIter = 0;
260  ltable[idx].age = initialLoopAge;
261  ltable[idx].confidence = 0;
263  break;
264 
265  } else {
266  ltable[idx].age--;
267  }
268  if (restrictAllocation) {
269  break;
270  }
271  }
272  }
273  }
274 }
275 
276 bool
277 LoopPredictor::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
278  BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt)
279 {
280  bool pred_taken = prev_pred_taken;
281  if (cond_branch) {
282  // loop prediction
283  bi->loopPred = getLoop(branch_pc, bi, useSpeculation, instShiftAmt);
284 
285  if ((loopUseCounter >= 0) && bi->loopPredValid) {
286  pred_taken = bi->loopPred;
287  bi->loopPredUsed = true;
288  }
289 
290  if (useSpeculation) {
291  specLoopUpdate(pred_taken, bi);
292  }
293  }
294 
295  return pred_taken;
296 }
297 
298 void
300 {
301  if (bi->loopHit >= 0) {
302  int idx = finallindex(bi->loopIndex,
303  bi->loopIndexB,
304  bi->loopHit);
305  ltable[idx].currentIterSpec = bi->currentIter;
306  }
307 }
308 
309 void
311 {
312  if (bi->loopHit >= 0) {
313  int idx = finallindex(bi->loopIndex,
314  bi->loopIndexB,
315  bi->loopHit);
316  ltable[idx].currentIterSpec = bi->currentIter;
317  }
318 }
319 
320 void
322 {
323  if (taken == bi->loopPred) {
324  stats.correct++;
325  } else {
326  stats.wrong++;
327  }
328 }
329 
330 void
331 LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
332  bool tage_pred, BranchInfo* bi,
333  unsigned instShiftAmt)
334 {
335  if (useSpeculation) {
336  // recalculate loop prediction without speculation
337  // It is ok to overwrite the loop prediction fields in bi
338  // as the stats have already been updated with the previous
339  // values
340  bi->loopPred = getLoop(branch_pc, bi, false, instShiftAmt);
341  }
342 
343  if (bi->loopPredValid) {
344  if (bi->predTaken != bi->loopPred) {
346  (bi->loopPred == taken),
347  withLoopBits);
348  }
349  }
350 
351  loopUpdate(branch_pc, taken, bi, tage_pred);
352 }
353 
355  statistics::Group *parent)
356  : statistics::Group(parent),
357  ADD_STAT(correct, statistics::units::Count::get(),
358  "Number of times the loop predictor is the provider and the "
359  "prediction is correct"),
360  ADD_STAT(wrong, statistics::units::Count::get(),
361  "Number of times the loop predictor is the provider and the "
362  "prediction is wrong")
363 {
364 }
365 
366 size_t
368 {
369  return (1ULL << logSizeLoopPred) *
370  ((useSpeculation ? 3 : 2) * loopTableIterBits +
373 }
374 
375 } // namespace branch_prediction
376 } // namespace gem5
gem5::branch_prediction::LoopPredictor::LoopEntry::currentIterSpec
uint16_t currentIterSpec
Definition: loop_predictor.hh:69
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::branch_prediction::LoopPredictor::lindex
int lindex(Addr pc_in, unsigned instShiftAmt) const
Computes the index used to access the loop predictor.
Definition: loop_predictor.cc:92
gem5::branch_prediction::LoopPredictor::squashLoop
void squashLoop(BranchInfo *bi)
Definition: loop_predictor.cc:310
random.hh
gem5::branch_prediction::LoopPredictor::LoopEntry::tag
uint16_t tag
Definition: loop_predictor.hh:71
gem5::branch_prediction::LoopPredictor::LoopEntry::confidence
uint8_t confidence
Definition: loop_predictor.hh:70
gem5::branch_prediction::LoopPredictor::logLoopTableAssoc
const unsigned logLoopTableAssoc
Definition: loop_predictor.hh:57
gem5::branch_prediction::LoopPredictor::init
void init() override
Initialize the loop predictor.
Definition: loop_predictor.cc:73
gem5::branch_prediction::LoopPredictor::initialLoopIter
const unsigned initialLoopIter
Definition: loop_predictor.hh:88
gem5::branch_prediction::LoopPredictor::squash
void squash(ThreadID tid, BranchInfo *bi)
Definition: loop_predictor.cc:299
gem5::branch_prediction::LoopPredictor::loopPredict
bool loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo *bi, bool prev_pred_taken, unsigned instShiftAmt)
Get the loop prediction.
Definition: loop_predictor.cc:277
gem5::branch_prediction::LoopPredictor::loopSetMask
const int loopSetMask
Definition: loop_predictor.hh:61
gem5::branch_prediction::LoopPredictor::getSizeInBits
size_t getSizeInBits() const
Definition: loop_predictor.cc:367
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::PowerISA::bi
Bitfield< 20, 16 > bi
Definition: types.hh:80
gem5::branch_prediction::LoopPredictor::withLoopBits
unsigned withLoopBits
Definition: loop_predictor.hh:82
gem5::branch_prediction::LoopPredictor::LoopEntry::age
uint8_t age
Definition: loop_predictor.hh:72
gem5::branch_prediction::LoopPredictor::specLoopUpdate
void specLoopUpdate(bool taken, BranchInfo *bi)
Speculatively updates the loop predictor iteration count (only for useSpeculation).
Definition: loop_predictor.cc:162
gem5::branch_prediction::LoopPredictor::logSizeLoopPred
const unsigned logSizeLoopPred
Definition: loop_predictor.hh:52
gem5::branch_prediction::LoopPredictor::optionalAgeReset
const bool optionalAgeReset
Definition: loop_predictor.hh:90
gem5::Random::random
std::enable_if_t< std::is_integral< T >::value, T > random()
Use the SFINAE idiom to choose an implementation based on whether the type is integral or floating po...
Definition: random.hh:90
gem5::branch_prediction::LoopPredictor::loopNumIterMask
const uint16_t loopNumIterMask
Definition: loop_predictor.hh:60
gem5::branch_prediction::LoopPredictor::signedCtrUpdate
static void signedCtrUpdate(int8_t &ctr, bool up, unsigned nbits)
Definition: loop_predictor.hh:117
gem5::branch_prediction::LoopPredictor::useDirectionBit
const bool useDirectionBit
Definition: loop_predictor.hh:84
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
ADD_STAT
#define ADD_STAT(n,...)
Convenience macro to add a stat to a statistics group.
Definition: group.hh:75
gem5::branch_prediction::LoopPredictor::ltable
LoopEntry * ltable
Definition: loop_predictor.hh:79
gem5::branch_prediction::LoopPredictor::optionalAgeInc
virtual bool optionalAgeInc() const
Definition: loop_predictor.cc:176
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::branch_prediction::LoopPredictor::loopTableTagBits
const unsigned loopTableTagBits
Definition: loop_predictor.hh:55
gem5::branch_prediction::LoopPredictor::unsignedCtrUpdate
static void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned nbits)
Updates an unsigned counter based on up/down parameter.
Definition: loop_predictor.hh:106
gem5::branch_prediction::LoopPredictor::loopTableConfidenceBits
const unsigned loopTableConfidenceBits
Definition: loop_predictor.hh:54
gem5::branch_prediction::LoopPredictor::loopTagMask
const uint16_t loopTagMask
Definition: loop_predictor.hh:59
gem5::branch_prediction::LoopPredictor::LoopEntry::currentIter
uint16_t currentIter
Definition: loop_predictor.hh:68
gem5::branch_prediction::LoopPredictor::condBranchUpdate
void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, bool tage_pred, BranchInfo *bi, unsigned instShiftAmt)
Update LTAGE for conditional branches.
Definition: loop_predictor.cc:331
gem5::SimObject
Abstract superclass for simulation objects.
Definition: sim_object.hh:146
gem5::branch_prediction::LoopPredictor::LoopPredictorStats::LoopPredictorStats
LoopPredictorStats(statistics::Group *parent)
Definition: loop_predictor.cc:354
gem5::branch_prediction::LoopPredictor::loopUpdate
void loopUpdate(Addr pc, bool Taken, BranchInfo *bi, bool tage_pred)
Updates the loop predictor.
Definition: loop_predictor.cc:182
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::LoopPredictor::useHashing
const bool useHashing
Definition: loop_predictor.hh:86
gem5::branch_prediction::LoopPredictor::initialLoopAge
const unsigned initialLoopAge
Definition: loop_predictor.hh:89
gem5::branch_prediction::LoopPredictor::finallindex
int finallindex(int lindex, int lowPcBits, int way) const
Computes the index used to access the ltable structures.
Definition: loop_predictor.cc:109
gem5::branch_prediction::LoopPredictor::updateStats
void updateStats(bool taken, BranchInfo *bi)
Update the stats.
Definition: loop_predictor.cc:321
loop_predictor.hh
gem5::branch_prediction::LoopPredictor::getLoop
bool getLoop(Addr pc, BranchInfo *bi, bool speculative, unsigned instShiftAmt) const
Get a branch prediction from the loop predictor.
Definition: loop_predictor.cc:118
gem5::branch_prediction::LoopPredictor::loopUseCounter
int8_t loopUseCounter
Definition: loop_predictor.hh:81
gem5::branch_prediction::LoopPredictor::useSpeculation
const bool useSpeculation
Definition: loop_predictor.hh:85
gem5::branch_prediction::LoopPredictor::LoopEntry::numIter
uint16_t numIter
Definition: loop_predictor.hh:67
gem5::branch_prediction::LoopPredictor::LoopEntry::dir
bool dir
Definition: loop_predictor.hh:73
gem5::MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:243
gem5::statistics::Group
Statistics container.
Definition: group.hh:93
gem5::branch_prediction::LoopPredictor::confidenceThreshold
const uint8_t confidenceThreshold
Definition: loop_predictor.hh:58
trace.hh
gem5::branch_prediction::LoopPredictor::calcConf
virtual bool calcConf(int index) const
Definition: loop_predictor.cc:156
gem5::branch_prediction::LoopPredictor::loopTableAgeBits
const unsigned loopTableAgeBits
Definition: loop_predictor.hh:53
gem5::branch_prediction::LoopPredictor::loopTableIterBits
const unsigned loopTableIterBits
Definition: loop_predictor.hh:56
gem5::branch_prediction::LoopPredictor::LoopEntry
Definition: loop_predictor.hh:65
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::branch_prediction::LoopPredictor::LoopPredictorStats::correct
statistics::Scalar correct
Definition: loop_predictor.hh:95
gem5::random_mt
Random random_mt
Definition: random.cc:99
gem5::branch_prediction::LoopPredictor::BranchInfo
Definition: loop_predictor.hh:129
gem5::branch_prediction::LoopPredictor::LoopPredictor
LoopPredictor(const LoopPredictorParams &p)
Definition: loop_predictor.cc:47
gem5::branch_prediction::LoopPredictor::restrictAllocation
const bool restrictAllocation
Definition: loop_predictor.hh:87
gem5::branch_prediction::LoopPredictor::makeBranchInfo
virtual BranchInfo * makeBranchInfo()
Definition: loop_predictor.cc:86
gem5::branch_prediction::LoopPredictor::LoopPredictorStats::wrong
statistics::Scalar wrong
Definition: loop_predictor.hh:96
gem5::ThreadID
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:242
gem5::branch_prediction::LoopPredictor::stats
gem5::branch_prediction::LoopPredictor::LoopPredictorStats stats

Generated on Tue Sep 21 2021 12:25:05 for gem5 by doxygen 1.8.17