gem5  v21.2.0.0
simple_indirect.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2014 ARM Limited
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 
30 
31 #include "base/intmath.hh"
32 #include "debug/Indirect.hh"
33 
34 namespace gem5
35 {
36 
37 namespace branch_prediction
38 {
39 
41  const SimpleIndirectPredictorParams &params)
42  : IndirectPredictor(params),
43  hashGHR(params.indirectHashGHR),
44  hashTargets(params.indirectHashTargets),
45  numSets(params.indirectSets),
46  numWays(params.indirectWays),
47  tagBits(params.indirectTagSize),
48  pathLength(params.indirectPathLength),
49  instShift(params.instShiftAmt),
50  ghrNumBits(params.indirectGHRBits),
51  ghrMask((1 << params.indirectGHRBits)-1)
52 {
53  if (!isPowerOf2(numSets)) {
54  panic("Indirect predictor requires power of 2 number of sets");
55  }
56 
57  threadInfo.resize(params.numThreads);
58 
59  targetCache.resize(numSets);
60  for (unsigned i = 0; i < numSets; i++) {
61  targetCache[i].resize(numWays);
62  }
63 
64  fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big");
65 }
66 
67 void
69  void* & indirect_history)
70 {
71  // record the GHR as it was before this prediction
72  // It will be used to recover the history in case this prediction is
73  // wrong or belongs to bad path
74  indirect_history = new unsigned(threadInfo[tid].ghr);
75 }
76 
77 void
79  ThreadID tid, bool actually_taken)
80 {
81  threadInfo[tid].ghr <<= 1;
82  threadInfo[tid].ghr |= actually_taken;
83  threadInfo[tid].ghr &= ghrMask;
84 }
85 
86 void
88  void * indirect_history, bool actually_taken)
89 {
90  unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
91  threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken;
92  threadInfo[tid].ghr &= ghrMask;
93 }
94 
95 bool
97  ThreadID tid)
98 {
99  Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid);
100  Addr tag = getTag(br_addr);
101 
102  assert(set_index < numSets);
103 
104  DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index);
105  const auto &iset = targetCache[set_index];
106  for (auto way = iset.begin(); way != iset.end(); ++way) {
107  // tag may be 0 and match the default in way->tag, so we also have to
108  // check that way->target has been initialized.
109  if (way->tag == tag && way->target) {
110  DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, *way->target);
111  set(target, *way->target);
112  return true;
113  }
114  }
115  DPRINTF(Indirect, "Miss %x\n", br_addr);
116  return false;
117 }
118 
119 void
121  InstSeqNum seq_num, ThreadID tid)
122 {
123  DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num);
124  HistoryEntry entry(br_addr, tgt_addr, seq_num);
125  threadInfo[tid].pathHist.push_back(entry);
126 }
127 
128 void
130  void * indirect_history)
131 {
132  DPRINTF(Indirect, "Committing seq:%d\n", seq_num);
133  ThreadInfo &t_info = threadInfo[tid];
134 
135  // we do not need to recover the GHR, so delete the information
136  unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
137  delete previousGhr;
138 
139  if (t_info.pathHist.empty()) return;
140 
141  if (t_info.headHistEntry < t_info.pathHist.size() &&
142  t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) {
143  if (t_info.headHistEntry >= pathLength) {
144  t_info.pathHist.pop_front();
145  } else {
146  ++t_info.headHistEntry;
147  }
148  }
149 }
150 
151 void
153 {
154  DPRINTF(Indirect, "Squashing seq:%d\n", seq_num);
155  ThreadInfo &t_info = threadInfo[tid];
156  auto squash_itr = t_info.pathHist.begin();
157  while (squash_itr != t_info.pathHist.end()) {
158  if (squash_itr->seqNum > seq_num) {
159  break;
160  }
161  ++squash_itr;
162  }
163  if (squash_itr != t_info.pathHist.end()) {
164  DPRINTF(Indirect, "Squashing series starting with sn:%d\n",
165  squash_itr->seqNum);
166  }
167  t_info.pathHist.erase(squash_itr, t_info.pathHist.end());
168 }
169 
170 void
172  void * indirect_history)
173 {
174  unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
175  threadInfo[tid].ghr = *previousGhr;
176 
177  delete previousGhr;
178 }
179 
180 void
182  InstSeqNum seq_num, void * indirect_history, const PCStateBase& target,
183  ThreadID tid)
184 {
185  ThreadInfo &t_info = threadInfo[tid];
186 
187  unsigned * ghr = static_cast<unsigned *>(indirect_history);
188 
189  // Should have just squashed so this branch should be the oldest
190  auto hist_entry = *(t_info.pathHist.rbegin());
191  // Temporarily pop it off the history so we can calculate the set
192  t_info.pathHist.pop_back();
193  Addr set_index = getSetIndex(hist_entry.pcAddr, *ghr, tid);
194  Addr tag = getTag(hist_entry.pcAddr);
195  hist_entry.targetAddr = target.instAddr();
196  t_info.pathHist.push_back(hist_entry);
197 
198  assert(set_index < numSets);
199 
200  auto &iset = targetCache[set_index];
201  for (auto way = iset.begin(); way != iset.end(); ++way) {
202  if (way->tag == tag) {
203  DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:"
204  "%s)\n", seq_num, hist_entry.pcAddr, set_index, target);
205  set(way->target, target);
206  return;
207  }
208  }
209 
210  DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n",
211  seq_num, hist_entry.pcAddr, set_index, target);
212  // Did not find entry, random replacement
213  auto &way = iset[rand() % numWays];
214  way.tag = tag;
215  set(way.target, target);
216 }
217 
218 
219 inline Addr
221 {
222  ThreadInfo &t_info = threadInfo[tid];
223 
224  Addr hash = br_addr >> instShift;
225  if (hashGHR) {
226  hash ^= ghr;
227  }
228  if (hashTargets) {
229  unsigned hash_shift = floorLog2(numSets) / pathLength;
230  for (int i = t_info.pathHist.size()-1, p = 0;
231  i >= 0 && p < pathLength; i--, p++) {
232  hash ^= (t_info.pathHist[i].targetAddr >>
233  (instShift + p*hash_shift));
234  }
235  }
236  return hash & (numSets-1);
237 }
238 
239 inline Addr
241 {
242  return (br_addr >> instShift) & ((0x1<<tagBits)-1);
243 }
244 
245 } // namespace branch_prediction
246 } // namespace gem5
gem5::branch_prediction::SimpleIndirectPredictor::numSets
const unsigned numSets
Definition: simple_indirect.hh:66
gem5::PCStateBase::instAddr
Addr instAddr() const
Returns the memory address of the instruction this PC points to.
Definition: pcstate.hh:107
gem5::branch_prediction::SimpleIndirectPredictor::getTag
Addr getTag(Addr br_addr)
Definition: simple_indirect.cc:240
gem5::branch_prediction::SimpleIndirectPredictor::updateDirectionInfo
void updateDirectionInfo(ThreadID tid, bool actually_taken)
Definition: simple_indirect.cc:78
gem5::branch_prediction::SimpleIndirectPredictor::instShift
const unsigned instShift
Definition: simple_indirect.hh:70
gem5::branch_prediction::SimpleIndirectPredictor::hashTargets
const bool hashTargets
Definition: simple_indirect.hh:65
gem5::branch_prediction::SimpleIndirectPredictor::genIndirectInfo
void genIndirectInfo(ThreadID tid, void *&indirect_history)
Definition: simple_indirect.cc:68
gem5::branch_prediction::SimpleIndirectPredictor::hashGHR
const bool hashGHR
Definition: simple_indirect.hh:64
gem5::floorLog2
static constexpr std::enable_if_t< std::is_integral_v< T >, int > floorLog2(T x)
Definition: intmath.hh:59
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:67
gem5::isPowerOf2
static constexpr bool isPowerOf2(const T &n)
Definition: intmath.hh:98
gem5::branch_prediction::SimpleIndirectPredictor::ghrMask
const unsigned ghrMask
Definition: simple_indirect.hh:72
gem5::branch_prediction::SimpleIndirectPredictor::HistoryEntry
Definition: simple_indirect.hh:85
gem5::SimObject::params
const Params & params() const
Definition: sim_object.hh:176
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
gem5::branch_prediction::SimpleIndirectPredictor::deleteIndirectInfo
void deleteIndirectInfo(ThreadID tid, void *indirect_history)
Definition: simple_indirect.cc:171
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::branch_prediction::SimpleIndirectPredictor::changeDirectionPrediction
void changeDirectionPrediction(ThreadID tid, void *indirect_history, bool actually_taken)
Definition: simple_indirect.cc:87
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo
Definition: simple_indirect.hh:95
gem5::branch_prediction::SimpleIndirectPredictor::numWays
const unsigned numWays
Definition: simple_indirect.hh:67
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo::ghr
unsigned ghr
Definition: simple_indirect.hh:99
simple_indirect.hh
gem5::branch_prediction::SimpleIndirectPredictor::targetCache
std::vector< std::vector< IPredEntry > > targetCache
Definition: simple_indirect.hh:80
gem5::branch_prediction::SimpleIndirectPredictor::getSetIndex
Addr getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid)
Definition: simple_indirect.cc:220
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::SimpleIndirectPredictor::commit
void commit(InstSeqNum seq_num, ThreadID tid, void *indirect_history)
Definition: simple_indirect.cc:129
gem5::branch_prediction::SimpleIndirectPredictor::pathLength
const unsigned pathLength
Definition: simple_indirect.hh:69
gem5::branch_prediction::SimpleIndirectPredictor::squash
void squash(InstSeqNum seq_num, ThreadID tid)
Definition: simple_indirect.cc:152
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo::pathHist
std::deque< HistoryEntry > pathHist
Definition: simple_indirect.hh:97
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo::headHistEntry
unsigned headHistEntry
Definition: simple_indirect.hh:98
gem5::branch_prediction::IndirectPredictor
Definition: indirect.hh:44
gem5::branch_prediction::SimpleIndirectPredictor::tagBits
const unsigned tagBits
Definition: simple_indirect.hh:68
gem5::InstSeqNum
uint64_t InstSeqNum
Definition: inst_seq.hh:40
gem5::branch_prediction::SimpleIndirectPredictor::threadInfo
std::vector< ThreadInfo > threadInfo
Definition: simple_indirect.hh:102
gem5::PCStateBase
Definition: pcstate.hh:57
intmath.hh
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:226
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: tlb.cc:60
gem5::branch_prediction::SimpleIndirectPredictor::recordIndirect
void recordIndirect(Addr br_addr, Addr tgt_addr, InstSeqNum seq_num, ThreadID tid)
Definition: simple_indirect.cc:120
gem5::branch_prediction::SimpleIndirectPredictor::lookup
bool lookup(Addr br_addr, PCStateBase &br_target, ThreadID tid)
Definition: simple_indirect.cc:96
gem5::branch_prediction::SimpleIndirectPredictor::recordTarget
void recordTarget(InstSeqNum seq_num, void *indirect_history, const PCStateBase &target, ThreadID tid)
Definition: simple_indirect.cc:181
gem5::ThreadID
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:242
gem5::branch_prediction::SimpleIndirectPredictor::ghrNumBits
const unsigned ghrNumBits
Definition: simple_indirect.hh:71
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:178
gem5::branch_prediction::SimpleIndirectPredictor::SimpleIndirectPredictor
SimpleIndirectPredictor(const SimpleIndirectPredictorParams &params)
Definition: simple_indirect.cc:40

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