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 params->indirectGHRBits),
75 instShiftAmt(params->instShiftAmt)
76{
77 for (auto& r : RAS)
78 r.init(params->RASSize);
79}
80
81void
82BPredUnit::regStats()
83{
84 SimObject::regStats();
85
86 lookups
87 .name(name() + ".lookups")
88 .desc("Number of BP lookups")
89 ;
90
91 condPredicted
92 .name(name() + ".condPredicted")
93 .desc("Number of conditional branches predicted")
94 ;
95
96 condIncorrect
97 .name(name() + ".condIncorrect")
98 .desc("Number of conditional branches incorrect")
99 ;
100
101 BTBLookups
102 .name(name() + ".BTBLookups")
103 .desc("Number of BTB lookups")
104 ;
105
106 BTBHits
107 .name(name() + ".BTBHits")
108 .desc("Number of BTB hits")
109 ;
110
111 BTBCorrect
112 .name(name() + ".BTBCorrect")
113 .desc("Number of correct BTB predictions (this stat may not "
114 "work properly.")
115 ;
116
117 BTBHitPct
118 .name(name() + ".BTBHitPct")
119 .desc("BTB Hit Percentage")
120 .precision(6);
121 BTBHitPct = (BTBHits / BTBLookups) * 100;
122
123 usedRAS
124 .name(name() + ".usedRAS")
125 .desc("Number of times the RAS was used to get a target.")
126 ;
127
128 RASIncorrect
129 .name(name() + ".RASInCorrect")
130 .desc("Number of incorrect RAS predictions.")
131 ;
132
133 indirectLookups
134 .name(name() + ".indirectLookups")
135 .desc("Number of indirect predictor lookups.")
136 ;
137
138 indirectHits
139 .name(name() + ".indirectHits")
140 .desc("Number of indirect target hits.")
141 ;
142
143 indirectMisses
144 .name(name() + ".indirectMisses")
145 .desc("Number of indirect misses.")
146 ;
147
148 indirectMispredicted
149 .name(name() + "indirectMispredicted")
150 .desc("Number of mispredicted indirect branches.")
151 ;
152
153}
154
155ProbePoints::PMUUPtr
156BPredUnit::pmuProbePoint(const char *name)
157{
158 ProbePoints::PMUUPtr ptr;
159 ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
160
161 return ptr;
162}
163
164void
165BPredUnit::regProbePoints()
166{
167 ppBranches = pmuProbePoint("Branches");
168 ppMisses = pmuProbePoint("Misses");
169}
170
171void
172BPredUnit::drainSanityCheck() const
173{
174 // We shouldn't have any outstanding requests when we resume from
175 // a drained system.
176 for (const auto& ph M5_VAR_USED : predHist)
177 assert(ph.empty());
178}
179
180bool
181BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
182 TheISA::PCState &pc, ThreadID tid)
183{
184 // See if branch predictor predicts taken.
185 // If so, get its target addr either from the BTB or the RAS.
186 // Save off record of branch stuff so the RAS can be fixed
187 // up once it's done.
188
189 bool pred_taken = false;
190 TheISA::PCState target = pc;
191
192 ++lookups;
193 ppBranches->notify(1);
194
195 void *bp_history = NULL;
196 void *indirect_history = NULL;
197
198 if (inst->isUncondCtrl()) {
| 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 params->indirectGHRBits),
75 instShiftAmt(params->instShiftAmt)
76{
77 for (auto& r : RAS)
78 r.init(params->RASSize);
79}
80
81void
82BPredUnit::regStats()
83{
84 SimObject::regStats();
85
86 lookups
87 .name(name() + ".lookups")
88 .desc("Number of BP lookups")
89 ;
90
91 condPredicted
92 .name(name() + ".condPredicted")
93 .desc("Number of conditional branches predicted")
94 ;
95
96 condIncorrect
97 .name(name() + ".condIncorrect")
98 .desc("Number of conditional branches incorrect")
99 ;
100
101 BTBLookups
102 .name(name() + ".BTBLookups")
103 .desc("Number of BTB lookups")
104 ;
105
106 BTBHits
107 .name(name() + ".BTBHits")
108 .desc("Number of BTB hits")
109 ;
110
111 BTBCorrect
112 .name(name() + ".BTBCorrect")
113 .desc("Number of correct BTB predictions (this stat may not "
114 "work properly.")
115 ;
116
117 BTBHitPct
118 .name(name() + ".BTBHitPct")
119 .desc("BTB Hit Percentage")
120 .precision(6);
121 BTBHitPct = (BTBHits / BTBLookups) * 100;
122
123 usedRAS
124 .name(name() + ".usedRAS")
125 .desc("Number of times the RAS was used to get a target.")
126 ;
127
128 RASIncorrect
129 .name(name() + ".RASInCorrect")
130 .desc("Number of incorrect RAS predictions.")
131 ;
132
133 indirectLookups
134 .name(name() + ".indirectLookups")
135 .desc("Number of indirect predictor lookups.")
136 ;
137
138 indirectHits
139 .name(name() + ".indirectHits")
140 .desc("Number of indirect target hits.")
141 ;
142
143 indirectMisses
144 .name(name() + ".indirectMisses")
145 .desc("Number of indirect misses.")
146 ;
147
148 indirectMispredicted
149 .name(name() + "indirectMispredicted")
150 .desc("Number of mispredicted indirect branches.")
151 ;
152
153}
154
155ProbePoints::PMUUPtr
156BPredUnit::pmuProbePoint(const char *name)
157{
158 ProbePoints::PMUUPtr ptr;
159 ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
160
161 return ptr;
162}
163
164void
165BPredUnit::regProbePoints()
166{
167 ppBranches = pmuProbePoint("Branches");
168 ppMisses = pmuProbePoint("Misses");
169}
170
171void
172BPredUnit::drainSanityCheck() const
173{
174 // We shouldn't have any outstanding requests when we resume from
175 // a drained system.
176 for (const auto& ph M5_VAR_USED : predHist)
177 assert(ph.empty());
178}
179
180bool
181BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
182 TheISA::PCState &pc, ThreadID tid)
183{
184 // See if branch predictor predicts taken.
185 // If so, get its target addr either from the BTB or the RAS.
186 // Save off record of branch stuff so the RAS can be fixed
187 // up once it's done.
188
189 bool pred_taken = false;
190 TheISA::PCState target = pc;
191
192 ++lookups;
193 ppBranches->notify(1);
194
195 void *bp_history = NULL;
196 void *indirect_history = NULL;
197
198 if (inst->isUncondCtrl()) {
|
199 DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
| 199 DPRINTF(Branch, "[tid:%i] [sn:%llu] "
200 "Unconditional control\n",
201 tid,seqNum);
|
200 pred_taken = true;
201 // Tell the BP there was an unconditional branch.
202 uncondBranch(tid, pc.instAddr(), bp_history);
203 } else {
204 ++condPredicted;
205 pred_taken = lookup(tid, pc.instAddr(), bp_history);
206
| 202 pred_taken = true;
203 // Tell the BP there was an unconditional branch.
204 uncondBranch(tid, pc.instAddr(), bp_history);
205 } else {
206 ++condPredicted;
207 pred_taken = lookup(tid, pc.instAddr(), bp_history);
208
|
207 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
208 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc);
| 209 DPRINTF(Branch, "[tid:%i] [sn:%llu] "
210 "Branch predictor predicted %i for PC %s\n",
211 tid, seqNum, pred_taken, pc);
|
209 }
210
211 const bool orig_pred_taken = pred_taken;
212 if (useIndirect) {
213 iPred.genIndirectInfo(tid, indirect_history);
214 }
215
| 212 }
213
214 const bool orig_pred_taken = pred_taken;
215 if (useIndirect) {
216 iPred.genIndirectInfo(tid, indirect_history);
217 }
218
|
216 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
| 219 DPRINTF(Branch, "[tid:%i] [sn:%llu] "
220 "Creating prediction history "
|
217 "for PC %s\n", tid, seqNum, pc);
218
219 PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken,
220 bp_history, indirect_history, tid, inst);
221
222 // Now lookup in the BTB or RAS.
223 if (pred_taken) {
224 if (inst->isReturn()) {
225 ++usedRAS;
226 predict_record.wasReturn = true;
227 // If it's a function return call, then look up the address
228 // in the RAS.
229 TheISA::PCState rasTop = RAS[tid].top();
230 target = TheISA::buildRetPC(pc, rasTop);
231
232 // Record the top entry of the RAS, and its index.
233 predict_record.usedRAS = true;
234 predict_record.RASIndex = RAS[tid].topIdx();
235 predict_record.RASTarget = rasTop;
236
237 RAS[tid].pop();
238
| 221 "for PC %s\n", tid, seqNum, pc);
222
223 PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken,
224 bp_history, indirect_history, tid, inst);
225
226 // Now lookup in the BTB or RAS.
227 if (pred_taken) {
228 if (inst->isReturn()) {
229 ++usedRAS;
230 predict_record.wasReturn = true;
231 // If it's a function return call, then look up the address
232 // in the RAS.
233 TheISA::PCState rasTop = RAS[tid].top();
234 target = TheISA::buildRetPC(pc, rasTop);
235
236 // Record the top entry of the RAS, and its index.
237 predict_record.usedRAS = true;
238 predict_record.RASIndex = RAS[tid].topIdx();
239 predict_record.RASTarget = rasTop;
240
241 RAS[tid].pop();
242
|
239 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
240 "RAS predicted target: %s, RAS index: %i.\n",
241 tid, pc, target, predict_record.RASIndex);
| 243 DPRINTF(Branch, "[tid:%i] [sn:%llu] Instruction %s is a return, "
244 "RAS predicted target: %s, RAS index: %i\n",
245 tid, seqNum, pc, target, predict_record.RASIndex);
|
242 } else {
243 ++BTBLookups;
244
245 if (inst->isCall()) {
246 RAS[tid].push(pc);
247 predict_record.pushedRAS = true;
248
249 // Record that it was a call so that the top RAS entry can
250 // be popped off if the speculation is incorrect.
251 predict_record.wasCall = true;
252
| 246 } else {
247 ++BTBLookups;
248
249 if (inst->isCall()) {
250 RAS[tid].push(pc);
251 predict_record.pushedRAS = true;
252
253 // Record that it was a call so that the top RAS entry can
254 // be popped off if the speculation is incorrect.
255 predict_record.wasCall = true;
256
|
253 DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
254 "call, adding %s to the RAS index: %i.\n",
255 tid, pc, pc, RAS[tid].topIdx());
| 257 DPRINTF(Branch,
258 "[tid:%i] [sn:%llu] Instruction %s was a call, adding "
259 "%s to the RAS index: %i\n",
260 tid, seqNum, pc, pc, RAS[tid].topIdx());
|
256 }
257
258 if (inst->isDirectCtrl() || !useIndirect) {
259 // Check BTB on direct branches
260 if (BTB.valid(pc.instAddr(), tid)) {
261 ++BTBHits;
| 261 }
262
263 if (inst->isDirectCtrl() || !useIndirect) {
264 // Check BTB on direct branches
265 if (BTB.valid(pc.instAddr(), tid)) {
266 ++BTBHits;
|
262
| |
263 // If it's not a return, use the BTB to get target addr.
264 target = BTB.lookup(pc.instAddr(), tid);
| 267 // If it's not a return, use the BTB to get target addr.
268 target = BTB.lookup(pc.instAddr(), tid);
|
265
266 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
267 " target is %s.\n", tid, pc, target);
268
| 269 DPRINTF(Branch,
270 "[tid:%i] [sn:%llu] Instruction %s predicted "
271 "target is %s\n",
272 tid, seqNum, pc, target);
|
269 } else {
| 273 } else {
|
270 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
271 "valid entry.\n",tid);
| 274 DPRINTF(Branch, "[tid:%i] [sn:%llu] BTB doesn't have a "
275 "valid entry\n",tid,seqNum);
|
272 pred_taken = false;
273 // The Direction of the branch predictor is altered
274 // because the BTB did not have an entry
275 // The predictor needs to be updated accordingly
276 if (!inst->isCall() && !inst->isReturn()) {
277 btbUpdate(tid, pc.instAddr(), bp_history);
| 276 pred_taken = false;
277 // The Direction of the branch predictor is altered
278 // because the BTB did not have an entry
279 // The predictor needs to be updated accordingly
280 if (!inst->isCall() && !inst->isReturn()) {
281 btbUpdate(tid, pc.instAddr(), bp_history);
|
278 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
279 " called for %s\n", tid, seqNum, pc);
| 282 DPRINTF(Branch,
283 "[tid:%i] [sn:%llu] btbUpdate "
284 "called for %s\n",
285 tid, seqNum, pc);
|
280 } else if (inst->isCall() && !inst->isUncondCtrl()) {
281 RAS[tid].pop();
282 predict_record.pushedRAS = false;
283 }
284 TheISA::advancePC(target, inst);
285 }
286 } else {
287 predict_record.wasIndirect = true;
288 ++indirectLookups;
289 //Consult indirect predictor on indirect control
290 if (iPred.lookup(pc.instAddr(), target, tid)) {
291 // Indirect predictor hit
292 ++indirectHits;
| 286 } else if (inst->isCall() && !inst->isUncondCtrl()) {
287 RAS[tid].pop();
288 predict_record.pushedRAS = false;
289 }
290 TheISA::advancePC(target, inst);
291 }
292 } else {
293 predict_record.wasIndirect = true;
294 ++indirectLookups;
295 //Consult indirect predictor on indirect control
296 if (iPred.lookup(pc.instAddr(), target, tid)) {
297 // Indirect predictor hit
298 ++indirectHits;
|
293 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
294 "indirect target is %s.\n", tid, pc, target);
| 299 DPRINTF(Branch,
300 "[tid:%i] [sn:%llu] "
301 "Instruction %s predicted "
302 "indirect target is %s\n",
303 tid, seqNum, pc, target);
|
295 } else {
296 ++indirectMisses;
297 pred_taken = false;
| 304 } else {
305 ++indirectMisses;
306 pred_taken = false;
|
298 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
299 "target.\n", tid, pc);
| 307 DPRINTF(Branch,
308 "[tid:%i] [sn:%llu] "
309 "Instruction %s no indirect "
310 "target\n",
311 tid, seqNum, pc);
|
300 if (!inst->isCall() && !inst->isReturn()) {
301
302 } else if (inst->isCall() && !inst->isUncondCtrl()) {
303 RAS[tid].pop();
304 predict_record.pushedRAS = false;
305 }
306 TheISA::advancePC(target, inst);
307 }
308 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
309 tid);
310 }
311 }
312 } else {
313 if (inst->isReturn()) {
314 predict_record.wasReturn = true;
315 }
316 TheISA::advancePC(target, inst);
317 }
318 predict_record.target = target.instAddr();
319
320 pc = target;
321
322 if (useIndirect) {
323 // Update the indirect predictor with the direction prediction
324 // Note that this happens after indirect lookup, so it does not use
325 // the new information
326 // Note also that we use orig_pred_taken instead of pred_taken in
327 // as this is the actual outcome of the direction prediction
328 iPred.updateDirectionInfo(tid, orig_pred_taken);
329 }
330
331 predHist[tid].push_front(predict_record);
332
| 312 if (!inst->isCall() && !inst->isReturn()) {
313
314 } else if (inst->isCall() && !inst->isUncondCtrl()) {
315 RAS[tid].pop();
316 predict_record.pushedRAS = false;
317 }
318 TheISA::advancePC(target, inst);
319 }
320 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
321 tid);
322 }
323 }
324 } else {
325 if (inst->isReturn()) {
326 predict_record.wasReturn = true;
327 }
328 TheISA::advancePC(target, inst);
329 }
330 predict_record.target = target.instAddr();
331
332 pc = target;
333
334 if (useIndirect) {
335 // Update the indirect predictor with the direction prediction
336 // Note that this happens after indirect lookup, so it does not use
337 // the new information
338 // Note also that we use orig_pred_taken instead of pred_taken in
339 // as this is the actual outcome of the direction prediction
340 iPred.updateDirectionInfo(tid, orig_pred_taken);
341 }
342
343 predHist[tid].push_front(predict_record);
344
|
333 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
334 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
| 345 DPRINTF(Branch,
346 "[tid:%i] [sn:%llu] History entry added. "
347 "predHist.size(): %i\n",
348 tid, seqNum, predHist[tid].size());
|
335
336 return pred_taken;
337}
338
339void
340BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
341{
| 349
350 return pred_taken;
351}
352
353void
354BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
355{
|
342 DPRINTF(Branch, "[tid:%i]: Committing branches until "
343 "[sn:%lli].\n", tid, done_sn);
| 356 DPRINTF(Branch, "[tid:%i] Committing branches until "
357 "sn:%llu]\n", tid, done_sn);
|
344
345 while (!predHist[tid].empty() &&
346 predHist[tid].back().seqNum <= done_sn) {
347 // Update the branch predictor with the correct results.
348 update(tid, predHist[tid].back().pc,
349 predHist[tid].back().predTaken,
350 predHist[tid].back().bpHistory, false,
351 predHist[tid].back().inst,
352 predHist[tid].back().target);
353
354 if (useIndirect) {
355 iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory);
356 }
357
358 predHist[tid].pop_back();
359 }
360}
361
362void
363BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
364{
365 History &pred_hist = predHist[tid];
366
367 if (useIndirect) {
368 iPred.squash(squashed_sn, tid);
369 }
370
371 while (!pred_hist.empty() &&
372 pred_hist.front().seqNum > squashed_sn) {
373 if (pred_hist.front().usedRAS) {
| 358
359 while (!predHist[tid].empty() &&
360 predHist[tid].back().seqNum <= done_sn) {
361 // Update the branch predictor with the correct results.
362 update(tid, predHist[tid].back().pc,
363 predHist[tid].back().predTaken,
364 predHist[tid].back().bpHistory, false,
365 predHist[tid].back().inst,
366 predHist[tid].back().target);
367
368 if (useIndirect) {
369 iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory);
370 }
371
372 predHist[tid].pop_back();
373 }
374}
375
376void
377BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
378{
379 History &pred_hist = predHist[tid];
380
381 if (useIndirect) {
382 iPred.squash(squashed_sn, tid);
383 }
384
385 while (!pred_hist.empty() &&
386 pred_hist.front().seqNum > squashed_sn) {
387 if (pred_hist.front().usedRAS) {
|
374 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
375 " target: %s.\n", tid,
| 388 DPRINTF(Branch, "[tid:%i] [squash sn:%llu]"
389 " Restoring top of RAS to: %i,"
390 " target: %s\n", tid, squashed_sn,
|
376 pred_hist.front().RASIndex, pred_hist.front().RASTarget);
377
378 RAS[tid].restore(pred_hist.front().RASIndex,
379 pred_hist.front().RASTarget);
380 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
381 // Was a call but predicated false. Pop RAS here
| 391 pred_hist.front().RASIndex, pred_hist.front().RASTarget);
392
393 RAS[tid].restore(pred_hist.front().RASIndex,
394 pred_hist.front().RASTarget);
395 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
396 // Was a call but predicated false. Pop RAS here
|
382 DPRINTF(Branch, "[tid: %i] Squashing"
383 " Call [sn:%i] PC: %s Popping RAS\n", tid,
| 397 DPRINTF(Branch, "[tid:%i] [squash sn:%llu] Squashing"
398 " Call [sn:%llu] PC: %s Popping RAS\n", tid, squashed_sn,
|
384 pred_hist.front().seqNum, pred_hist.front().pc);
385 RAS[tid].pop();
386 }
387
388 // This call should delete the bpHistory.
389 squash(tid, pred_hist.front().bpHistory);
390 if (useIndirect) {
391 iPred.deleteIndirectInfo(tid, pred_hist.front().indirectHistory);
392 }
393
| 399 pred_hist.front().seqNum, pred_hist.front().pc);
400 RAS[tid].pop();
401 }
402
403 // This call should delete the bpHistory.
404 squash(tid, pred_hist.front().bpHistory);
405 if (useIndirect) {
406 iPred.deleteIndirectInfo(tid, pred_hist.front().indirectHistory);
407 }
408
|
394 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
395 "PC %s.\n", tid, pred_hist.front().seqNum,
| 409 DPRINTF(Branch, "[tid:%i] [squash sn:%llu] "
410 "Removing history for [sn:%llu] "
411 "PC %#x\n", tid, squashed_sn, pred_hist.front().seqNum,
|
396 pred_hist.front().pc);
397
398 pred_hist.pop_front();
399
| 412 pred_hist.front().pc);
413
414 pred_hist.pop_front();
415
|
400 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
401 tid, predHist[tid].size());
| 416 DPRINTF(Branch, "[tid:%i] [squash sn:%llu] predHist.size(): %i\n",
417 tid, squashed_sn, predHist[tid].size());
|
402 }
403}
404
405void
406BPredUnit::squash(const InstSeqNum &squashed_sn,
407 const TheISA::PCState &corrTarget,
408 bool actually_taken, ThreadID tid)
409{
410 // Now that we know that a branch was mispredicted, we need to undo
411 // all the branches that have been seen up until this branch and
412 // fix up everything.
413 // NOTE: This should be call conceivably in 2 scenarios:
414 // (1) After an branch is executed, it updates its status in the ROB
415 // The commit stage then checks the ROB update and sends a signal to
416 // the fetch stage to squash history after the mispredict
417 // (2) In the decode stage, you can find out early if a unconditional
418 // PC-relative, branch was predicted incorrectly. If so, a signal
419 // to the fetch stage is sent to squash history after the mispredict
420
421 History &pred_hist = predHist[tid];
422
423 ++condIncorrect;
424 ppMisses->notify(1);
425
| 418 }
419}
420
421void
422BPredUnit::squash(const InstSeqNum &squashed_sn,
423 const TheISA::PCState &corrTarget,
424 bool actually_taken, ThreadID tid)
425{
426 // Now that we know that a branch was mispredicted, we need to undo
427 // all the branches that have been seen up until this branch and
428 // fix up everything.
429 // NOTE: This should be call conceivably in 2 scenarios:
430 // (1) After an branch is executed, it updates its status in the ROB
431 // The commit stage then checks the ROB update and sends a signal to
432 // the fetch stage to squash history after the mispredict
433 // (2) In the decode stage, you can find out early if a unconditional
434 // PC-relative, branch was predicted incorrectly. If so, a signal
435 // to the fetch stage is sent to squash history after the mispredict
436
437 History &pred_hist = predHist[tid];
438
439 ++condIncorrect;
440 ppMisses->notify(1);
441
|
426 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
427 "setting target to %s.\n", tid, squashed_sn, corrTarget);
| 442 DPRINTF(Branch, "[tid:%i] Squashing from sequence number %i, "
443 "setting target to %s\n", tid, squashed_sn, corrTarget);
|
428
429 // Squash All Branches AFTER this mispredicted branch
430 squash(squashed_sn, tid);
431
432 // If there's a squash due to a syscall, there may not be an entry
433 // corresponding to the squash. In that case, don't bother trying to
434 // fix up the entry.
435 if (!pred_hist.empty()) {
436
437 auto hist_it = pred_hist.begin();
438 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
439 // squashed_sn);
440
441 //assert(hist_it != pred_hist.end());
442 if (pred_hist.front().seqNum != squashed_sn) {
443 DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
444 pred_hist.front().seqNum, squashed_sn);
445
446 assert(pred_hist.front().seqNum == squashed_sn);
447 }
448
449
450 if ((*hist_it).usedRAS) {
451 ++RASIncorrect;
| 444
445 // Squash All Branches AFTER this mispredicted branch
446 squash(squashed_sn, tid);
447
448 // If there's a squash due to a syscall, there may not be an entry
449 // corresponding to the squash. In that case, don't bother trying to
450 // fix up the entry.
451 if (!pred_hist.empty()) {
452
453 auto hist_it = pred_hist.begin();
454 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
455 // squashed_sn);
456
457 //assert(hist_it != pred_hist.end());
458 if (pred_hist.front().seqNum != squashed_sn) {
459 DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
460 pred_hist.front().seqNum, squashed_sn);
461
462 assert(pred_hist.front().seqNum == squashed_sn);
463 }
464
465
466 if ((*hist_it).usedRAS) {
467 ++RASIncorrect;
|
452 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
453 tid, hist_it->seqNum);
| 468 DPRINTF(Branch,
469 "[tid:%i] [squash sn:%llu] Incorrect RAS [sn:%llu]\n",
470 tid, squashed_sn, hist_it->seqNum);
|
454 }
455
456 // There are separate functions for in-order and out-of-order
457 // branch prediction, but not for update. Therefore, this
458 // call should take into account that the mispredicted branch may
459 // be on the wrong path (i.e., OoO execution), and that the counter
460 // counter table(s) should not be updated. Thus, this call should
461 // restore the state of the underlying predictor, for instance the
462 // local/global histories. The counter tables will be updated when
463 // the branch actually commits.
464
465 // Remember the correct direction for the update at commit.
466 pred_hist.front().predTaken = actually_taken;
467 pred_hist.front().target = corrTarget.instAddr();
468
469 update(tid, (*hist_it).pc, actually_taken,
470 pred_hist.front().bpHistory, true, pred_hist.front().inst,
471 corrTarget.instAddr());
472
473 if (useIndirect) {
474 iPred.changeDirectionPrediction(tid,
475 pred_hist.front().indirectHistory, actually_taken);
476 }
477
478 if (actually_taken) {
479 if (hist_it->wasReturn && !hist_it->usedRAS) {
| 471 }
472
473 // There are separate functions for in-order and out-of-order
474 // branch prediction, but not for update. Therefore, this
475 // call should take into account that the mispredicted branch may
476 // be on the wrong path (i.e., OoO execution), and that the counter
477 // counter table(s) should not be updated. Thus, this call should
478 // restore the state of the underlying predictor, for instance the
479 // local/global histories. The counter tables will be updated when
480 // the branch actually commits.
481
482 // Remember the correct direction for the update at commit.
483 pred_hist.front().predTaken = actually_taken;
484 pred_hist.front().target = corrTarget.instAddr();
485
486 update(tid, (*hist_it).pc, actually_taken,
487 pred_hist.front().bpHistory, true, pred_hist.front().inst,
488 corrTarget.instAddr());
489
490 if (useIndirect) {
491 iPred.changeDirectionPrediction(tid,
492 pred_hist.front().indirectHistory, actually_taken);
493 }
494
495 if (actually_taken) {
496 if (hist_it->wasReturn && !hist_it->usedRAS) {
|
480 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
481 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
482 hist_it->pc);
| 497 DPRINTF(Branch, "[tid:%i] [squash sn:%llu] "
498 "Incorrectly predicted "
499 "return [sn:%llu] PC: %#x\n", tid, squashed_sn,
500 hist_it->seqNum,
501 hist_it->pc);
|
483 RAS[tid].pop();
484 hist_it->usedRAS = true;
485 }
486 if (hist_it->wasIndirect) {
487 ++indirectMispredicted;
488 iPred.recordTarget(
489 hist_it->seqNum, pred_hist.front().indirectHistory,
490 corrTarget, tid);
491 } else {
| 502 RAS[tid].pop();
503 hist_it->usedRAS = true;
504 }
505 if (hist_it->wasIndirect) {
506 ++indirectMispredicted;
507 iPred.recordTarget(
508 hist_it->seqNum, pred_hist.front().indirectHistory,
509 corrTarget, tid);
510 } else {
|
492 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
493 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
| 511 DPRINTF(Branch,"[tid:%i] [squash sn:%llu] "
512 "BTB Update called for [sn:%llu] "
513 "PC %#x\n", tid, squashed_sn,
514 hist_it->seqNum, hist_it->pc);
|
494
495 BTB.update((*hist_it).pc, corrTarget, tid);
496 }
497 } else {
498 //Actually not Taken
499 if (hist_it->usedRAS) {
| 515
516 BTB.update((*hist_it).pc, corrTarget, tid);
517 }
518 } else {
519 //Actually not Taken
520 if (hist_it->usedRAS) {
|
500 DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
501 " return [sn:%i] PC: %s Restoring RAS\n", tid,
| 521 DPRINTF(Branch,
522 "[tid:%i] [squash sn:%llu] Incorrectly predicted "
523 "return [sn:%llu] PC: %#x Restoring RAS\n", tid,
524 squashed_sn,
|
502 hist_it->seqNum, hist_it->pc);
| 525 hist_it->seqNum, hist_it->pc);
|
503 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
504 " to: %i, target: %s.\n", tid,
| 526 DPRINTF(Branch,
527 "[tid:%i] [squash sn:%llu] Restoring top of RAS "
528 "to: %i, target: %s\n", tid, squashed_sn,
|
505 hist_it->RASIndex, hist_it->RASTarget);
506 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
507 hist_it->usedRAS = false;
508 } else if (hist_it->wasCall && hist_it->pushedRAS) {
509 //Was a Call but predicated false. Pop RAS here
| 529 hist_it->RASIndex, hist_it->RASTarget);
530 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
531 hist_it->usedRAS = false;
532 } else if (hist_it->wasCall && hist_it->pushedRAS) {
533 //Was a Call but predicated false. Pop RAS here
|
510 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
511 " Call [sn:%i] PC: %s Popping RAS\n", tid,
512 hist_it->seqNum, hist_it->pc);
| 534 DPRINTF(Branch,
535 "[tid:%i] [squash sn:%llu] "
536 "Incorrectly predicted "
537 "Call [sn:%llu] PC: %s Popping RAS\n",
538 tid, squashed_sn,
539 hist_it->seqNum, hist_it->pc);
|
513 RAS[tid].pop();
514 hist_it->pushedRAS = false;
515 }
516 }
517 } else {
| 540 RAS[tid].pop();
541 hist_it->pushedRAS = false;
542 }
543 }
544 } else {
|
518 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
519 "update.\n", tid, squashed_sn);
| 545 DPRINTF(Branch, "[tid:%i] [sn:%llu] pred_hist empty, can't "
546 "update\n", tid, squashed_sn);
|
520 }
521}
522
523void
524BPredUnit::dump()
525{
526 int i = 0;
527 for (const auto& ph : predHist) {
528 if (!ph.empty()) {
529 auto pred_hist_it = ph.begin();
530
531 cprintf("predHist[%i].size(): %i\n", i++, ph.size());
532
533 while (pred_hist_it != ph.end()) {
| 547 }
548}
549
550void
551BPredUnit::dump()
552{
553 int i = 0;
554 for (const auto& ph : predHist) {
555 if (!ph.empty()) {
556 auto pred_hist_it = ph.begin();
557
558 cprintf("predHist[%i].size(): %i\n", i++, ph.size());
559
560 while (pred_hist_it != ph.end()) {
|
534 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
| 561 cprintf("sn:%llu], PC:%#x, tid:%i, predTaken:%i, "
|
535 "bpHistory:%#x\n",
536 pred_hist_it->seqNum, pred_hist_it->pc,
537 pred_hist_it->tid, pred_hist_it->predTaken,
538 pred_hist_it->bpHistory);
539 pred_hist_it++;
540 }
541
542 cprintf("\n");
543 }
544 }
545}
546
| 562 "bpHistory:%#x\n",
563 pred_hist_it->seqNum, pred_hist_it->pc,
564 pred_hist_it->tid, pred_hist_it->predTaken,
565 pred_hist_it->bpHistory);
566 pred_hist_it++;
567 }
568
569 cprintf("\n");
570 }
571 }
572}
573
|