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