indirect.cc (13810:f50e3b82df73) indirect.cc (13957:25e9c77a8a99)
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;

--- 15 unchanged lines hidden (view full) ---

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 * Authors: Mitch Hayenga
29 */
30
31#include "cpu/pred/indirect.hh"
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;

--- 15 unchanged lines hidden (view full) ---

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 * Authors: Mitch Hayenga
29 */
30
31#include "cpu/pred/indirect.hh"
32
33#include "base/intmath.hh"
34#include "debug/Indirect.hh"
35
36IndirectPredictor::IndirectPredictor(bool hash_ghr, bool hash_targets,
37 unsigned num_sets, unsigned num_ways,
38 unsigned tag_bits, unsigned path_len, unsigned inst_shift,
39 unsigned num_threads, unsigned ghr_size)
40 : hashGHR(hash_ghr), hashTargets(hash_targets),
41 numSets(num_sets), numWays(num_ways), tagBits(tag_bits),
42 pathLength(path_len), instShift(inst_shift),
43 ghrNumBits(ghr_size), ghrMask((1 << ghr_size)-1)
44{
45 if (!isPowerOf2(numSets)) {
46 panic("Indirect predictor requires power of 2 number of sets");
47 }
48
49 threadInfo.resize(num_threads);
50
51 targetCache.resize(numSets);
52 for (unsigned i = 0; i < numSets; i++) {
53 targetCache[i].resize(numWays);
54 }
55
56 fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big");
57}
58
59void
60IndirectPredictor::genIndirectInfo(ThreadID tid, void* & indirect_history)
61{
62 // record the GHR as it was before this prediction
63 // It will be used to recover the history in case this prediction is
64 // wrong or belongs to bad path
65 indirect_history = new unsigned(threadInfo[tid].ghr);
66}
67
68void
69IndirectPredictor::updateDirectionInfo(
70 ThreadID tid, bool actually_taken)
71{
72 threadInfo[tid].ghr <<= 1;
73 threadInfo[tid].ghr |= actually_taken;
74 threadInfo[tid].ghr &= ghrMask;
75}
76
77void
78IndirectPredictor::changeDirectionPrediction(ThreadID tid,
79 void * indirect_history, bool actually_taken)
80{
81 unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
82 threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken;
83 threadInfo[tid].ghr &= ghrMask;
84}
85
86bool
87IndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target,
88 ThreadID tid)
89{
90 Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid);
91 Addr tag = getTag(br_addr);
92
93 assert(set_index < numSets);
94
95 DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index);
96 const auto &iset = targetCache[set_index];
97 for (auto way = iset.begin(); way != iset.end(); ++way) {
98 if (way->tag == tag) {
99 DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target);
100 target = way->target;
101 return true;
102 }
103 }
104 DPRINTF(Indirect, "Miss %x\n", br_addr);
105 return false;
106}
107
108void
109IndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr,
110 InstSeqNum seq_num, ThreadID tid)
111{
112 DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num);
113 HistoryEntry entry(br_addr, tgt_addr, seq_num);
114 threadInfo[tid].pathHist.push_back(entry);
115}
116
117void
118IndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid,
119 void * indirect_history)
120{
121 DPRINTF(Indirect, "Committing seq:%d\n", seq_num);
122 ThreadInfo &t_info = threadInfo[tid];
123
124 // we do not need to recover the GHR, so delete the information
125 unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
126 delete previousGhr;
127
128 if (t_info.pathHist.empty()) return;
129
130 if (t_info.headHistEntry < t_info.pathHist.size() &&
131 t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) {
132 if (t_info.headHistEntry >= pathLength) {
133 t_info.pathHist.pop_front();
134 } else {
135 ++t_info.headHistEntry;
136 }
137 }
138}
139
140void
141IndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid)
142{
143 DPRINTF(Indirect, "Squashing seq:%d\n", seq_num);
144 ThreadInfo &t_info = threadInfo[tid];
145 auto squash_itr = t_info.pathHist.begin();
146 while (squash_itr != t_info.pathHist.end()) {
147 if (squash_itr->seqNum > seq_num) {
148 break;
149 }
150 ++squash_itr;
151 }
152 if (squash_itr != t_info.pathHist.end()) {
153 DPRINTF(Indirect, "Squashing series starting with sn:%d\n",
154 squash_itr->seqNum);
155 }
156 t_info.pathHist.erase(squash_itr, t_info.pathHist.end());
157}
158
159void
160IndirectPredictor::deleteIndirectInfo(ThreadID tid, void * indirect_history)
161{
162 unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
163 threadInfo[tid].ghr = *previousGhr;
164
165 delete previousGhr;
166}
167
168void
169IndirectPredictor::recordTarget(
170 InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target,
171 ThreadID tid)
172{
173 ThreadInfo &t_info = threadInfo[tid];
174
175 unsigned * ghr = static_cast<unsigned *>(indirect_history);
176
177 // Should have just squashed so this branch should be the oldest
178 auto hist_entry = *(t_info.pathHist.rbegin());
179 // Temporarily pop it off the history so we can calculate the set
180 t_info.pathHist.pop_back();
181 Addr set_index = getSetIndex(hist_entry.pcAddr, *ghr, tid);
182 Addr tag = getTag(hist_entry.pcAddr);
183 hist_entry.targetAddr = target.instAddr();
184 t_info.pathHist.push_back(hist_entry);
185
186 assert(set_index < numSets);
187
188 auto &iset = targetCache[set_index];
189 for (auto way = iset.begin(); way != iset.end(); ++way) {
190 if (way->tag == tag) {
191 DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:"
192 "%s)\n", seq_num, hist_entry.pcAddr, set_index, target);
193 way->target = target;
194 return;
195 }
196 }
197
198 DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n",
199 seq_num, hist_entry.pcAddr, set_index, target);
200 // Did not find entry, random replacement
201 auto &way = iset[rand() % numWays];
202 way.tag = tag;
203 way.target = target;
204}
205
206
207inline Addr
208IndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid)
209{
210 ThreadInfo &t_info = threadInfo[tid];
211
212 Addr hash = br_addr >> instShift;
213 if (hashGHR) {
214 hash ^= ghr;
215 }
216 if (hashTargets) {
217 unsigned hash_shift = floorLog2(numSets) / pathLength;
218 for (int i = t_info.pathHist.size()-1, p = 0;
219 i >= 0 && p < pathLength; i--, p++) {
220 hash ^= (t_info.pathHist[i].targetAddr >>
221 (instShift + p*hash_shift));
222 }
223 }
224 return hash & (numSets-1);
225}
226
227inline Addr
228IndirectPredictor::getTag(Addr br_addr)
229{
230 return (br_addr >> instShift) & ((0x1<<tagBits)-1);
231}