1/*
2 * Copyright (c) 2011-2012, 2014 ARM Limited
3 * Copyright (c) 2010 The University of Edinburgh
4 * Copyright (c) 2012 Mark D. Hill and David A. Wood
5 * All rights reserved
6 *
7 * The license below extends only to copyright in the software and shall
8 * not be construed as granting a license to any other intellectual
9 * property including but not limited to intellectual property relating
10 * to a hardware implementation of the functionality of the software
11 * licensed hereunder. You may use the software subject to the license
12 * terms below provided that you ensure that this notice is replicated
13 * unmodified and in its entirety in all distributions of the software,
14 * modified or unmodified, in source code or in binary form.
15 *
16 * Copyright (c) 2004-2005 The Regents of The University of Michigan
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met: redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer;
23 * redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution;
26 * neither the name of the copyright holders nor the names of its
27 * contributors may be used to endorse or promote products derived from
28 * this software without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Authors: Kevin Lim
43 */
44
45#include "cpu/pred/bpred_unit.hh"
46
47#include <algorithm>
48
49#include "arch/isa_traits.hh"
50#include "arch/types.hh"
51#include "arch/utility.hh"
52#include "base/trace.hh"
53#include "config/the_isa.hh"
54#include "debug/Branch.hh"
55
56BPredUnit::BPredUnit(const Params *params)
57 : SimObject(params),
58 numThreads(params->numThreads),
59 predHist(numThreads),
60 BTB(params->BTBEntries,
61 params->BTBTagSize,
62 params->instShiftAmt,
63 params->numThreads),
64 RAS(numThreads),
65 useIndirect(params->useIndirect),
66 iPred(params->indirectHashGHR,
67 params->indirectHashTargets,
68 params->indirectSets,
69 params->indirectWays,
70 params->indirectTagSize,
71 params->indirectPathLength,
72 params->instShiftAmt,
73 params->numThreads),
74 instShiftAmt(params->instShiftAmt)
75{
76 for (auto& r : RAS)
77 r.init(params->RASSize);
78}
79
80void
81BPredUnit::regStats()
82{
83 SimObject::regStats();
84
85 lookups
86 .name(name() + ".lookups")
87 .desc("Number of BP lookups")
88 ;
89
90 condPredicted
91 .name(name() + ".condPredicted")
92 .desc("Number of conditional branches predicted")
93 ;
94
95 condIncorrect
96 .name(name() + ".condIncorrect")
97 .desc("Number of conditional branches incorrect")
98 ;
99
100 BTBLookups
101 .name(name() + ".BTBLookups")
102 .desc("Number of BTB lookups")
103 ;
104
105 BTBHits
106 .name(name() + ".BTBHits")
107 .desc("Number of BTB hits")
108 ;
109
110 BTBCorrect
111 .name(name() + ".BTBCorrect")
112 .desc("Number of correct BTB predictions (this stat may not "
113 "work properly.")
114 ;
115
116 BTBHitPct
117 .name(name() + ".BTBHitPct")
118 .desc("BTB Hit Percentage")
119 .precision(6);
120 BTBHitPct = (BTBHits / BTBLookups) * 100;
121
122 usedRAS
123 .name(name() + ".usedRAS")
124 .desc("Number of times the RAS was used to get a target.")
125 ;
126
127 RASIncorrect
128 .name(name() + ".RASInCorrect")
129 .desc("Number of incorrect RAS predictions.")
130 ;
131
132 indirectLookups
133 .name(name() + ".indirectLookups")
134 .desc("Number of indirect predictor lookups.")
135 ;
136
137 indirectHits
138 .name(name() + ".indirectHits")
139 .desc("Number of indirect target hits.")
140 ;
141
142 indirectMisses
143 .name(name() + ".indirectMisses")
144 .desc("Number of indirect misses.")
145 ;
146
147 indirectMispredicted
148 .name(name() + "indirectMispredicted")
149 .desc("Number of mispredicted indirect branches.")
150 ;
151
152}
153
154ProbePoints::PMUUPtr
155BPredUnit::pmuProbePoint(const char *name)
156{
157 ProbePoints::PMUUPtr ptr;
158 ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
159
160 return ptr;
161}
162
163void
164BPredUnit::regProbePoints()
165{
166 ppBranches = pmuProbePoint("Branches");
167 ppMisses = pmuProbePoint("Misses");
168}
169
170void
171BPredUnit::drainSanityCheck() const
172{
173 // We shouldn't have any outstanding requests when we resume from
174 // a drained system.
175 for (const auto& ph M5_VAR_USED : predHist)
176 assert(ph.empty());
177}
178
179bool
180BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
181 TheISA::PCState &pc, ThreadID tid)
182{
183 // See if branch predictor predicts taken.
184 // If so, get its target addr either from the BTB or the RAS.
185 // Save off record of branch stuff so the RAS can be fixed
186 // up once it's done.
187
188 bool pred_taken = false;
189 TheISA::PCState target = pc;
190
191 ++lookups;
192 ppBranches->notify(1);
193
194 void *bp_history = NULL;
195
196 if (inst->isUncondCtrl()) {
197 DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
198 pred_taken = true;
199 // Tell the BP there was an unconditional branch.
200 uncondBranch(tid, pc.instAddr(), bp_history);
201 } else {
202 ++condPredicted;
203 pred_taken = lookup(tid, pc.instAddr(), bp_history);
204
205 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
206 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc);
207 }
208
209 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
210 "for PC %s\n", tid, seqNum, pc);
211
212 PredictorHistory predict_record(seqNum, pc.instAddr(),
| 1/*
2 * Copyright (c) 2011-2012, 2014 ARM Limited
3 * Copyright (c) 2010 The University of Edinburgh
4 * Copyright (c) 2012 Mark D. Hill and David A. Wood
5 * All rights reserved
6 *
7 * The license below extends only to copyright in the software and shall
8 * not be construed as granting a license to any other intellectual
9 * property including but not limited to intellectual property relating
10 * to a hardware implementation of the functionality of the software
11 * licensed hereunder. You may use the software subject to the license
12 * terms below provided that you ensure that this notice is replicated
13 * unmodified and in its entirety in all distributions of the software,
14 * modified or unmodified, in source code or in binary form.
15 *
16 * Copyright (c) 2004-2005 The Regents of The University of Michigan
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met: redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer;
23 * redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution;
26 * neither the name of the copyright holders nor the names of its
27 * contributors may be used to endorse or promote products derived from
28 * this software without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Authors: Kevin Lim
43 */
44
45#include "cpu/pred/bpred_unit.hh"
46
47#include <algorithm>
48
49#include "arch/isa_traits.hh"
50#include "arch/types.hh"
51#include "arch/utility.hh"
52#include "base/trace.hh"
53#include "config/the_isa.hh"
54#include "debug/Branch.hh"
55
56BPredUnit::BPredUnit(const Params *params)
57 : SimObject(params),
58 numThreads(params->numThreads),
59 predHist(numThreads),
60 BTB(params->BTBEntries,
61 params->BTBTagSize,
62 params->instShiftAmt,
63 params->numThreads),
64 RAS(numThreads),
65 useIndirect(params->useIndirect),
66 iPred(params->indirectHashGHR,
67 params->indirectHashTargets,
68 params->indirectSets,
69 params->indirectWays,
70 params->indirectTagSize,
71 params->indirectPathLength,
72 params->instShiftAmt,
73 params->numThreads),
74 instShiftAmt(params->instShiftAmt)
75{
76 for (auto& r : RAS)
77 r.init(params->RASSize);
78}
79
80void
81BPredUnit::regStats()
82{
83 SimObject::regStats();
84
85 lookups
86 .name(name() + ".lookups")
87 .desc("Number of BP lookups")
88 ;
89
90 condPredicted
91 .name(name() + ".condPredicted")
92 .desc("Number of conditional branches predicted")
93 ;
94
95 condIncorrect
96 .name(name() + ".condIncorrect")
97 .desc("Number of conditional branches incorrect")
98 ;
99
100 BTBLookups
101 .name(name() + ".BTBLookups")
102 .desc("Number of BTB lookups")
103 ;
104
105 BTBHits
106 .name(name() + ".BTBHits")
107 .desc("Number of BTB hits")
108 ;
109
110 BTBCorrect
111 .name(name() + ".BTBCorrect")
112 .desc("Number of correct BTB predictions (this stat may not "
113 "work properly.")
114 ;
115
116 BTBHitPct
117 .name(name() + ".BTBHitPct")
118 .desc("BTB Hit Percentage")
119 .precision(6);
120 BTBHitPct = (BTBHits / BTBLookups) * 100;
121
122 usedRAS
123 .name(name() + ".usedRAS")
124 .desc("Number of times the RAS was used to get a target.")
125 ;
126
127 RASIncorrect
128 .name(name() + ".RASInCorrect")
129 .desc("Number of incorrect RAS predictions.")
130 ;
131
132 indirectLookups
133 .name(name() + ".indirectLookups")
134 .desc("Number of indirect predictor lookups.")
135 ;
136
137 indirectHits
138 .name(name() + ".indirectHits")
139 .desc("Number of indirect target hits.")
140 ;
141
142 indirectMisses
143 .name(name() + ".indirectMisses")
144 .desc("Number of indirect misses.")
145 ;
146
147 indirectMispredicted
148 .name(name() + "indirectMispredicted")
149 .desc("Number of mispredicted indirect branches.")
150 ;
151
152}
153
154ProbePoints::PMUUPtr
155BPredUnit::pmuProbePoint(const char *name)
156{
157 ProbePoints::PMUUPtr ptr;
158 ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
159
160 return ptr;
161}
162
163void
164BPredUnit::regProbePoints()
165{
166 ppBranches = pmuProbePoint("Branches");
167 ppMisses = pmuProbePoint("Misses");
168}
169
170void
171BPredUnit::drainSanityCheck() const
172{
173 // We shouldn't have any outstanding requests when we resume from
174 // a drained system.
175 for (const auto& ph M5_VAR_USED : predHist)
176 assert(ph.empty());
177}
178
179bool
180BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
181 TheISA::PCState &pc, ThreadID tid)
182{
183 // See if branch predictor predicts taken.
184 // If so, get its target addr either from the BTB or the RAS.
185 // Save off record of branch stuff so the RAS can be fixed
186 // up once it's done.
187
188 bool pred_taken = false;
189 TheISA::PCState target = pc;
190
191 ++lookups;
192 ppBranches->notify(1);
193
194 void *bp_history = NULL;
195
196 if (inst->isUncondCtrl()) {
197 DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
198 pred_taken = true;
199 // Tell the BP there was an unconditional branch.
200 uncondBranch(tid, pc.instAddr(), bp_history);
201 } else {
202 ++condPredicted;
203 pred_taken = lookup(tid, pc.instAddr(), bp_history);
204
205 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
206 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc);
207 }
208
209 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
210 "for PC %s\n", tid, seqNum, pc);
211
212 PredictorHistory predict_record(seqNum, pc.instAddr(),
|
213 pred_taken, bp_history, tid);
| 213 pred_taken, bp_history, tid, inst);
|
214
215 // Now lookup in the BTB or RAS.
216 if (pred_taken) {
217 if (inst->isReturn()) {
218 ++usedRAS;
219 predict_record.wasReturn = true;
220 // If it's a function return call, then look up the address
221 // in the RAS.
222 TheISA::PCState rasTop = RAS[tid].top();
223 target = TheISA::buildRetPC(pc, rasTop);
224
225 // Record the top entry of the RAS, and its index.
226 predict_record.usedRAS = true;
227 predict_record.RASIndex = RAS[tid].topIdx();
228 predict_record.RASTarget = rasTop;
229
230 RAS[tid].pop();
231
232 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
233 "RAS predicted target: %s, RAS index: %i.\n",
234 tid, pc, target, predict_record.RASIndex);
235 } else {
236 ++BTBLookups;
237
238 if (inst->isCall()) {
239 RAS[tid].push(pc);
240 predict_record.pushedRAS = true;
241
242 // Record that it was a call so that the top RAS entry can
243 // be popped off if the speculation is incorrect.
244 predict_record.wasCall = true;
245
246 DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
247 "call, adding %s to the RAS index: %i.\n",
248 tid, pc, pc, RAS[tid].topIdx());
249 }
250
251 if (inst->isDirectCtrl() || !useIndirect) {
252 // Check BTB on direct branches
253 if (BTB.valid(pc.instAddr(), tid)) {
254 ++BTBHits;
255
256 // If it's not a return, use the BTB to get target addr.
257 target = BTB.lookup(pc.instAddr(), tid);
258
259 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
260 " target is %s.\n", tid, pc, target);
261
262 } else {
263 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
264 "valid entry.\n",tid);
265 pred_taken = false;
266 // The Direction of the branch predictor is altered
267 // because the BTB did not have an entry
268 // The predictor needs to be updated accordingly
269 if (!inst->isCall() && !inst->isReturn()) {
270 btbUpdate(tid, pc.instAddr(), bp_history);
271 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
272 " called for %s\n", tid, seqNum, pc);
273 } else if (inst->isCall() && !inst->isUncondCtrl()) {
274 RAS[tid].pop();
275 predict_record.pushedRAS = false;
276 }
277 TheISA::advancePC(target, inst);
278 }
279 } else {
280 predict_record.wasIndirect = true;
281 ++indirectLookups;
282 //Consult indirect predictor on indirect control
283 if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history),
284 target, tid)) {
285 // Indirect predictor hit
286 ++indirectHits;
287 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
288 "indirect target is %s.\n", tid, pc, target);
289 } else {
290 ++indirectMisses;
291 pred_taken = false;
292 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
293 "target.\n", tid, pc);
294 if (!inst->isCall() && !inst->isReturn()) {
295
296 } else if (inst->isCall() && !inst->isUncondCtrl()) {
297 RAS[tid].pop();
298 predict_record.pushedRAS = false;
299 }
300 TheISA::advancePC(target, inst);
301 }
302 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
303 tid);
304 }
305 }
306 } else {
307 if (inst->isReturn()) {
308 predict_record.wasReturn = true;
309 }
310 TheISA::advancePC(target, inst);
311 }
| 214
215 // Now lookup in the BTB or RAS.
216 if (pred_taken) {
217 if (inst->isReturn()) {
218 ++usedRAS;
219 predict_record.wasReturn = true;
220 // If it's a function return call, then look up the address
221 // in the RAS.
222 TheISA::PCState rasTop = RAS[tid].top();
223 target = TheISA::buildRetPC(pc, rasTop);
224
225 // Record the top entry of the RAS, and its index.
226 predict_record.usedRAS = true;
227 predict_record.RASIndex = RAS[tid].topIdx();
228 predict_record.RASTarget = rasTop;
229
230 RAS[tid].pop();
231
232 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
233 "RAS predicted target: %s, RAS index: %i.\n",
234 tid, pc, target, predict_record.RASIndex);
235 } else {
236 ++BTBLookups;
237
238 if (inst->isCall()) {
239 RAS[tid].push(pc);
240 predict_record.pushedRAS = true;
241
242 // Record that it was a call so that the top RAS entry can
243 // be popped off if the speculation is incorrect.
244 predict_record.wasCall = true;
245
246 DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
247 "call, adding %s to the RAS index: %i.\n",
248 tid, pc, pc, RAS[tid].topIdx());
249 }
250
251 if (inst->isDirectCtrl() || !useIndirect) {
252 // Check BTB on direct branches
253 if (BTB.valid(pc.instAddr(), tid)) {
254 ++BTBHits;
255
256 // If it's not a return, use the BTB to get target addr.
257 target = BTB.lookup(pc.instAddr(), tid);
258
259 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
260 " target is %s.\n", tid, pc, target);
261
262 } else {
263 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
264 "valid entry.\n",tid);
265 pred_taken = false;
266 // The Direction of the branch predictor is altered
267 // because the BTB did not have an entry
268 // The predictor needs to be updated accordingly
269 if (!inst->isCall() && !inst->isReturn()) {
270 btbUpdate(tid, pc.instAddr(), bp_history);
271 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
272 " called for %s\n", tid, seqNum, pc);
273 } else if (inst->isCall() && !inst->isUncondCtrl()) {
274 RAS[tid].pop();
275 predict_record.pushedRAS = false;
276 }
277 TheISA::advancePC(target, inst);
278 }
279 } else {
280 predict_record.wasIndirect = true;
281 ++indirectLookups;
282 //Consult indirect predictor on indirect control
283 if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history),
284 target, tid)) {
285 // Indirect predictor hit
286 ++indirectHits;
287 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
288 "indirect target is %s.\n", tid, pc, target);
289 } else {
290 ++indirectMisses;
291 pred_taken = false;
292 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
293 "target.\n", tid, pc);
294 if (!inst->isCall() && !inst->isReturn()) {
295
296 } else if (inst->isCall() && !inst->isUncondCtrl()) {
297 RAS[tid].pop();
298 predict_record.pushedRAS = false;
299 }
300 TheISA::advancePC(target, inst);
301 }
302 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
303 tid);
304 }
305 }
306 } else {
307 if (inst->isReturn()) {
308 predict_record.wasReturn = true;
309 }
310 TheISA::advancePC(target, inst);
311 }
|
| 312 predict_record.target = target.instAddr();
|
312
313 pc = target;
314
315 predHist[tid].push_front(predict_record);
316
317 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
318 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
319
320 return pred_taken;
321}
322
323void
324BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
325{
326 DPRINTF(Branch, "[tid:%i]: Committing branches until "
327 "[sn:%lli].\n", tid, done_sn);
328
329 iPred.commit(done_sn, tid);
330 while (!predHist[tid].empty() &&
331 predHist[tid].back().seqNum <= done_sn) {
332 // Update the branch predictor with the correct results.
333 update(tid, predHist[tid].back().pc,
334 predHist[tid].back().predTaken,
| 313
314 pc = target;
315
316 predHist[tid].push_front(predict_record);
317
318 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
319 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
320
321 return pred_taken;
322}
323
324void
325BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
326{
327 DPRINTF(Branch, "[tid:%i]: Committing branches until "
328 "[sn:%lli].\n", tid, done_sn);
329
330 iPred.commit(done_sn, tid);
331 while (!predHist[tid].empty() &&
332 predHist[tid].back().seqNum <= done_sn) {
333 // Update the branch predictor with the correct results.
334 update(tid, predHist[tid].back().pc,
335 predHist[tid].back().predTaken,
|
335 predHist[tid].back().bpHistory, false);
| 336 predHist[tid].back().bpHistory, false,
337 predHist[tid].back().inst,
338 predHist[tid].back().target);
|
336
337 predHist[tid].pop_back();
338 }
339}
340
341void
342BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
343{
344 History &pred_hist = predHist[tid];
345
346 iPred.squash(squashed_sn, tid);
347 while (!pred_hist.empty() &&
348 pred_hist.front().seqNum > squashed_sn) {
349 if (pred_hist.front().usedRAS) {
350 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
351 " target: %s.\n", tid,
352 pred_hist.front().RASIndex, pred_hist.front().RASTarget);
353
354 RAS[tid].restore(pred_hist.front().RASIndex,
355 pred_hist.front().RASTarget);
356 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
357 // Was a call but predicated false. Pop RAS here
358 DPRINTF(Branch, "[tid: %i] Squashing"
359 " Call [sn:%i] PC: %s Popping RAS\n", tid,
360 pred_hist.front().seqNum, pred_hist.front().pc);
361 RAS[tid].pop();
362 }
363
364 // This call should delete the bpHistory.
365 squash(tid, pred_hist.front().bpHistory);
366
367 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
368 "PC %s.\n", tid, pred_hist.front().seqNum,
369 pred_hist.front().pc);
370
371 pred_hist.pop_front();
372
373 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
374 tid, predHist[tid].size());
375 }
376}
377
378void
379BPredUnit::squash(const InstSeqNum &squashed_sn,
380 const TheISA::PCState &corrTarget,
381 bool actually_taken, ThreadID tid)
382{
383 // Now that we know that a branch was mispredicted, we need to undo
384 // all the branches that have been seen up until this branch and
385 // fix up everything.
386 // NOTE: This should be call conceivably in 2 scenarios:
387 // (1) After an branch is executed, it updates its status in the ROB
388 // The commit stage then checks the ROB update and sends a signal to
389 // the fetch stage to squash history after the mispredict
390 // (2) In the decode stage, you can find out early if a unconditional
391 // PC-relative, branch was predicted incorrectly. If so, a signal
392 // to the fetch stage is sent to squash history after the mispredict
393
394 History &pred_hist = predHist[tid];
395
396 ++condIncorrect;
397 ppMisses->notify(1);
398
399 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
400 "setting target to %s.\n", tid, squashed_sn, corrTarget);
401
402 // Squash All Branches AFTER this mispredicted branch
403 squash(squashed_sn, tid);
404
405 // If there's a squash due to a syscall, there may not be an entry
406 // corresponding to the squash. In that case, don't bother trying to
407 // fix up the entry.
408 if (!pred_hist.empty()) {
409
410 auto hist_it = pred_hist.begin();
411 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
412 // squashed_sn);
413
414 //assert(hist_it != pred_hist.end());
415 if (pred_hist.front().seqNum != squashed_sn) {
416 DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
417 pred_hist.front().seqNum, squashed_sn);
418
419 assert(pred_hist.front().seqNum == squashed_sn);
420 }
421
422
423 if ((*hist_it).usedRAS) {
424 ++RASIncorrect;
425 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
426 tid, hist_it->seqNum);
427 }
428
429 // Get the underlying Global History Register
430 unsigned ghr = getGHR(tid, hist_it->bpHistory);
431
432 // There are separate functions for in-order and out-of-order
433 // branch prediction, but not for update. Therefore, this
434 // call should take into account that the mispredicted branch may
435 // be on the wrong path (i.e., OoO execution), and that the counter
436 // counter table(s) should not be updated. Thus, this call should
437 // restore the state of the underlying predictor, for instance the
438 // local/global histories. The counter tables will be updated when
439 // the branch actually commits.
440
441 // Remember the correct direction for the update at commit.
442 pred_hist.front().predTaken = actually_taken;
| 339
340 predHist[tid].pop_back();
341 }
342}
343
344void
345BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
346{
347 History &pred_hist = predHist[tid];
348
349 iPred.squash(squashed_sn, tid);
350 while (!pred_hist.empty() &&
351 pred_hist.front().seqNum > squashed_sn) {
352 if (pred_hist.front().usedRAS) {
353 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
354 " target: %s.\n", tid,
355 pred_hist.front().RASIndex, pred_hist.front().RASTarget);
356
357 RAS[tid].restore(pred_hist.front().RASIndex,
358 pred_hist.front().RASTarget);
359 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
360 // Was a call but predicated false. Pop RAS here
361 DPRINTF(Branch, "[tid: %i] Squashing"
362 " Call [sn:%i] PC: %s Popping RAS\n", tid,
363 pred_hist.front().seqNum, pred_hist.front().pc);
364 RAS[tid].pop();
365 }
366
367 // This call should delete the bpHistory.
368 squash(tid, pred_hist.front().bpHistory);
369
370 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
371 "PC %s.\n", tid, pred_hist.front().seqNum,
372 pred_hist.front().pc);
373
374 pred_hist.pop_front();
375
376 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
377 tid, predHist[tid].size());
378 }
379}
380
381void
382BPredUnit::squash(const InstSeqNum &squashed_sn,
383 const TheISA::PCState &corrTarget,
384 bool actually_taken, ThreadID tid)
385{
386 // Now that we know that a branch was mispredicted, we need to undo
387 // all the branches that have been seen up until this branch and
388 // fix up everything.
389 // NOTE: This should be call conceivably in 2 scenarios:
390 // (1) After an branch is executed, it updates its status in the ROB
391 // The commit stage then checks the ROB update and sends a signal to
392 // the fetch stage to squash history after the mispredict
393 // (2) In the decode stage, you can find out early if a unconditional
394 // PC-relative, branch was predicted incorrectly. If so, a signal
395 // to the fetch stage is sent to squash history after the mispredict
396
397 History &pred_hist = predHist[tid];
398
399 ++condIncorrect;
400 ppMisses->notify(1);
401
402 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
403 "setting target to %s.\n", tid, squashed_sn, corrTarget);
404
405 // Squash All Branches AFTER this mispredicted branch
406 squash(squashed_sn, tid);
407
408 // If there's a squash due to a syscall, there may not be an entry
409 // corresponding to the squash. In that case, don't bother trying to
410 // fix up the entry.
411 if (!pred_hist.empty()) {
412
413 auto hist_it = pred_hist.begin();
414 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
415 // squashed_sn);
416
417 //assert(hist_it != pred_hist.end());
418 if (pred_hist.front().seqNum != squashed_sn) {
419 DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
420 pred_hist.front().seqNum, squashed_sn);
421
422 assert(pred_hist.front().seqNum == squashed_sn);
423 }
424
425
426 if ((*hist_it).usedRAS) {
427 ++RASIncorrect;
428 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
429 tid, hist_it->seqNum);
430 }
431
432 // Get the underlying Global History Register
433 unsigned ghr = getGHR(tid, hist_it->bpHistory);
434
435 // There are separate functions for in-order and out-of-order
436 // branch prediction, but not for update. Therefore, this
437 // call should take into account that the mispredicted branch may
438 // be on the wrong path (i.e., OoO execution), and that the counter
439 // counter table(s) should not be updated. Thus, this call should
440 // restore the state of the underlying predictor, for instance the
441 // local/global histories. The counter tables will be updated when
442 // the branch actually commits.
443
444 // Remember the correct direction for the update at commit.
445 pred_hist.front().predTaken = actually_taken;
|
| 446 pred_hist.front().target = corrTarget.instAddr();
|
443
444 update(tid, (*hist_it).pc, actually_taken,
| 447
448 update(tid, (*hist_it).pc, actually_taken,
|
445 pred_hist.front().bpHistory, true);
| 449 pred_hist.front().bpHistory, true, pred_hist.front().inst,
450 corrTarget.instAddr());
|
446
447 if (actually_taken) {
448 if (hist_it->wasReturn && !hist_it->usedRAS) {
449 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
450 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
451 hist_it->pc);
452 RAS[tid].pop();
453 hist_it->usedRAS = true;
454 }
455 if (hist_it->wasIndirect) {
456 ++indirectMispredicted;
457 iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid);
458 } else {
459 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
460 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
461
462 BTB.update((*hist_it).pc, corrTarget, tid);
463 }
464 } else {
465 //Actually not Taken
466 if (hist_it->usedRAS) {
467 DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
468 " return [sn:%i] PC: %s Restoring RAS\n", tid,
469 hist_it->seqNum, hist_it->pc);
470 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
471 " to: %i, target: %s.\n", tid,
472 hist_it->RASIndex, hist_it->RASTarget);
473 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
474 hist_it->usedRAS = false;
475 } else if (hist_it->wasCall && hist_it->pushedRAS) {
476 //Was a Call but predicated false. Pop RAS here
477 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
478 " Call [sn:%i] PC: %s Popping RAS\n", tid,
479 hist_it->seqNum, hist_it->pc);
480 RAS[tid].pop();
481 hist_it->pushedRAS = false;
482 }
483 }
484 } else {
485 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
486 "update.\n", tid, squashed_sn);
487 }
488}
489
490void
491BPredUnit::dump()
492{
493 int i = 0;
494 for (const auto& ph : predHist) {
495 if (!ph.empty()) {
496 auto pred_hist_it = ph.begin();
497
498 cprintf("predHist[%i].size(): %i\n", i++, ph.size());
499
500 while (pred_hist_it != ph.end()) {
501 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
502 "bpHistory:%#x\n",
503 pred_hist_it->seqNum, pred_hist_it->pc,
504 pred_hist_it->tid, pred_hist_it->predTaken,
505 pred_hist_it->bpHistory);
506 pred_hist_it++;
507 }
508
509 cprintf("\n");
510 }
511 }
512}
513
| 451
452 if (actually_taken) {
453 if (hist_it->wasReturn && !hist_it->usedRAS) {
454 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
455 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
456 hist_it->pc);
457 RAS[tid].pop();
458 hist_it->usedRAS = true;
459 }
460 if (hist_it->wasIndirect) {
461 ++indirectMispredicted;
462 iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid);
463 } else {
464 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
465 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
466
467 BTB.update((*hist_it).pc, corrTarget, tid);
468 }
469 } else {
470 //Actually not Taken
471 if (hist_it->usedRAS) {
472 DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
473 " return [sn:%i] PC: %s Restoring RAS\n", tid,
474 hist_it->seqNum, hist_it->pc);
475 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
476 " to: %i, target: %s.\n", tid,
477 hist_it->RASIndex, hist_it->RASTarget);
478 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
479 hist_it->usedRAS = false;
480 } else if (hist_it->wasCall && hist_it->pushedRAS) {
481 //Was a Call but predicated false. Pop RAS here
482 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
483 " Call [sn:%i] PC: %s Popping RAS\n", tid,
484 hist_it->seqNum, hist_it->pc);
485 RAS[tid].pop();
486 hist_it->pushedRAS = false;
487 }
488 }
489 } else {
490 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
491 "update.\n", tid, squashed_sn);
492 }
493}
494
495void
496BPredUnit::dump()
497{
498 int i = 0;
499 for (const auto& ph : predHist) {
500 if (!ph.empty()) {
501 auto pred_hist_it = ph.begin();
502
503 cprintf("predHist[%i].size(): %i\n", i++, ph.size());
504
505 while (pred_hist_it != ph.end()) {
506 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
507 "bpHistory:%#x\n",
508 pred_hist_it->seqNum, pred_hist_it->pc,
509 pred_hist_it->tid, pred_hist_it->predTaken,
510 pred_hist_it->bpHistory);
511 pred_hist_it++;
512 }
513
514 cprintf("\n");
515 }
516 }
517}
518
|