gem5  v21.1.0.2
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  if (way->tag == tag) {
108  DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target);
109  target = way->target;
110  return true;
111  }
112  }
113  DPRINTF(Indirect, "Miss %x\n", br_addr);
114  return false;
115 }
116 
117 void
119  InstSeqNum seq_num, ThreadID tid)
120 {
121  DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num);
122  HistoryEntry entry(br_addr, tgt_addr, seq_num);
123  threadInfo[tid].pathHist.push_back(entry);
124 }
125 
126 void
128  void * indirect_history)
129 {
130  DPRINTF(Indirect, "Committing seq:%d\n", seq_num);
131  ThreadInfo &t_info = threadInfo[tid];
132 
133  // we do not need to recover the GHR, so delete the information
134  unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
135  delete previousGhr;
136 
137  if (t_info.pathHist.empty()) return;
138 
139  if (t_info.headHistEntry < t_info.pathHist.size() &&
140  t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) {
141  if (t_info.headHistEntry >= pathLength) {
142  t_info.pathHist.pop_front();
143  } else {
144  ++t_info.headHistEntry;
145  }
146  }
147 }
148 
149 void
151 {
152  DPRINTF(Indirect, "Squashing seq:%d\n", seq_num);
153  ThreadInfo &t_info = threadInfo[tid];
154  auto squash_itr = t_info.pathHist.begin();
155  while (squash_itr != t_info.pathHist.end()) {
156  if (squash_itr->seqNum > seq_num) {
157  break;
158  }
159  ++squash_itr;
160  }
161  if (squash_itr != t_info.pathHist.end()) {
162  DPRINTF(Indirect, "Squashing series starting with sn:%d\n",
163  squash_itr->seqNum);
164  }
165  t_info.pathHist.erase(squash_itr, t_info.pathHist.end());
166 }
167 
168 void
170  void * indirect_history)
171 {
172  unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
173  threadInfo[tid].ghr = *previousGhr;
174 
175  delete previousGhr;
176 }
177 
178 void
180  InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target,
181  ThreadID tid)
182 {
183  ThreadInfo &t_info = threadInfo[tid];
184 
185  unsigned * ghr = static_cast<unsigned *>(indirect_history);
186 
187  // Should have just squashed so this branch should be the oldest
188  auto hist_entry = *(t_info.pathHist.rbegin());
189  // Temporarily pop it off the history so we can calculate the set
190  t_info.pathHist.pop_back();
191  Addr set_index = getSetIndex(hist_entry.pcAddr, *ghr, tid);
192  Addr tag = getTag(hist_entry.pcAddr);
193  hist_entry.targetAddr = target.instAddr();
194  t_info.pathHist.push_back(hist_entry);
195 
196  assert(set_index < numSets);
197 
198  auto &iset = targetCache[set_index];
199  for (auto way = iset.begin(); way != iset.end(); ++way) {
200  if (way->tag == tag) {
201  DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:"
202  "%s)\n", seq_num, hist_entry.pcAddr, set_index, target);
203  way->target = target;
204  return;
205  }
206  }
207 
208  DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n",
209  seq_num, hist_entry.pcAddr, set_index, target);
210  // Did not find entry, random replacement
211  auto &way = iset[rand() % numWays];
212  way.tag = tag;
213  way.target = target;
214 }
215 
216 
217 inline Addr
219 {
220  ThreadInfo &t_info = threadInfo[tid];
221 
222  Addr hash = br_addr >> instShift;
223  if (hashGHR) {
224  hash ^= ghr;
225  }
226  if (hashTargets) {
227  unsigned hash_shift = floorLog2(numSets) / pathLength;
228  for (int i = t_info.pathHist.size()-1, p = 0;
229  i >= 0 && p < pathLength; i--, p++) {
230  hash ^= (t_info.pathHist[i].targetAddr >>
231  (instShift + p*hash_shift));
232  }
233  }
234  return hash & (numSets-1);
235 }
236 
237 inline Addr
239 {
240  return (br_addr >> instShift) & ((0x1<<tagBits)-1);
241 }
242 
243 } // namespace branch_prediction
244 } // namespace gem5
gem5::branch_prediction::SimpleIndirectPredictor::numSets
const unsigned numSets
Definition: simple_indirect.hh:66
gem5::branch_prediction::SimpleIndirectPredictor::getTag
Addr getTag(Addr br_addr)
Definition: simple_indirect.cc:238
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::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
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:86
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:169
gem5::MipsISA::PCState
GenericISA::DelaySlotPCState< 4 > PCState
Definition: pcstate.hh:40
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:96
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:102
simple_indirect.hh
gem5::branch_prediction::SimpleIndirectPredictor::targetCache
std::vector< std::vector< IPredEntry > > targetCache
Definition: simple_indirect.hh:81
gem5::branch_prediction::SimpleIndirectPredictor::getSetIndex
Addr getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid)
Definition: simple_indirect.cc:218
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:127
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:150
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo::pathHist
std::deque< HistoryEntry > pathHist
Definition: simple_indirect.hh:100
gem5::branch_prediction::SimpleIndirectPredictor::ThreadInfo::headHistEntry
unsigned headHistEntry
Definition: simple_indirect.hh:101
gem5::branch_prediction::IndirectPredictor
Definition: indirect.hh:44
gem5::branch_prediction::SimpleIndirectPredictor::tagBits
const unsigned tagBits
Definition: simple_indirect.hh:68
gem5::floorLog2
static constexpr std::enable_if_t< std::is_integral< T >::value, int > floorLog2(T x)
Definition: intmath.hh:59
gem5::InstSeqNum
uint64_t InstSeqNum
Definition: inst_seq.hh:40
gem5::branch_prediction::SimpleIndirectPredictor::recordTarget
void recordTarget(InstSeqNum seq_num, void *indirect_history, const TheISA::PCState &target, ThreadID tid)
Definition: simple_indirect.cc:179
gem5::branch_prediction::SimpleIndirectPredictor::threadInfo
std::vector< ThreadInfo > threadInfo
Definition: simple_indirect.hh:105
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:225
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::branch_prediction::SimpleIndirectPredictor::recordIndirect
void recordIndirect(Addr br_addr, Addr tgt_addr, InstSeqNum seq_num, ThreadID tid)
Definition: simple_indirect.cc:118
gem5::branch_prediction::SimpleIndirectPredictor::lookup
bool lookup(Addr br_addr, TheISA::PCState &br_target, ThreadID tid)
Definition: simple_indirect.cc:96
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:177
gem5::branch_prediction::SimpleIndirectPredictor::SimpleIndirectPredictor
SimpleIndirectPredictor(const SimpleIndirectPredictorParams &params)
Definition: simple_indirect.cc:40

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