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
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.
16 * Copyright (c) 2004-2005 The Regents of The University of Michigan
17 * All rights reserved.
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.
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.
45 #include "cpu/pred/bpred_unit.hh"
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"
56 BPredUnit::BPredUnit(const Params
*params
)
58 numThreads(params
->numThreads
),
60 BTB(params
->BTBEntries
,
62 params
->instShiftAmt
),
64 instShiftAmt(params
->instShiftAmt
)
67 r
.init(params
->RASSize
);
74 .name(name() + ".lookups")
75 .desc("Number of BP lookups")
79 .name(name() + ".condPredicted")
80 .desc("Number of conditional branches predicted")
84 .name(name() + ".condIncorrect")
85 .desc("Number of conditional branches incorrect")
89 .name(name() + ".BTBLookups")
90 .desc("Number of BTB lookups")
94 .name(name() + ".BTBHits")
95 .desc("Number of BTB hits")
99 .name(name() + ".BTBCorrect")
100 .desc("Number of correct BTB predictions (this stat may not "
105 .name(name() + ".BTBHitPct")
106 .desc("BTB Hit Percentage")
108 BTBHitPct
= (BTBHits
/ BTBLookups
) * 100;
111 .name(name() + ".usedRAS")
112 .desc("Number of times the RAS was used to get a target.")
116 .name(name() + ".RASInCorrect")
117 .desc("Number of incorrect RAS predictions.")
122 BPredUnit::pmuProbePoint(const char *name
)
124 ProbePoints::PMUUPtr ptr
;
125 ptr
.reset(new ProbePoints::PMU(getProbeManager(), name
));
131 BPredUnit::regProbePoints()
133 ppBranches
= pmuProbePoint("Branches");
134 ppMisses
= pmuProbePoint("Misses");
138 BPredUnit::drainSanityCheck() const
140 // We shouldn't have any outstanding requests when we resume from
142 for (const auto& ph M5_VAR_USED
: predHist
)
147 BPredUnit::predict(const StaticInstPtr
&inst
, const InstSeqNum
&seqNum
,
148 TheISA::PCState
&pc
, ThreadID tid
)
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.
155 bool pred_taken
= false;
156 TheISA::PCState target
= pc
;
159 ppBranches
->notify(1);
161 void *bp_history
= NULL
;
163 if (inst
->isUncondCtrl()) {
164 DPRINTF(Branch
, "[tid:%i]: Unconditional control.\n", tid
);
166 // Tell the BP there was an unconditional branch.
167 uncondBranch(pc
.instAddr(), bp_history
);
170 pred_taken
= lookup(pc
.instAddr(), bp_history
);
172 DPRINTF(Branch
, "[tid:%i]: [sn:%i] Branch predictor"
173 " predicted %i for PC %s\n", tid
, seqNum
, pred_taken
, pc
);
176 DPRINTF(Branch
, "[tid:%i]: [sn:%i] Creating prediction history "
177 "for PC %s\n", tid
, seqNum
, pc
);
179 PredictorHistory
predict_record(seqNum
, pc
.instAddr(),
180 pred_taken
, bp_history
, tid
);
182 // Now lookup in the BTB or RAS.
184 if (inst
->isReturn()) {
186 predict_record
.wasReturn
= true;
187 // If it's a function return call, then look up the address
189 TheISA::PCState rasTop
= RAS
[tid
].top();
190 target
= TheISA::buildRetPC(pc
, rasTop
);
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
;
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
);
205 if (inst
->isCall()) {
207 predict_record
.pushedRAS
= true;
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;
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());
218 if (BTB
.valid(pc
.instAddr(), tid
)) {
221 // If it's not a return, use the BTB to get the target addr.
222 target
= BTB
.lookup(pc
.instAddr(), tid
);
224 DPRINTF(Branch
, "[tid:%i]: Instruction %s predicted"
225 " target is %s.\n", tid
, pc
, target
);
228 DPRINTF(Branch
, "[tid:%i]: BTB doesn't have a "
229 "valid entry.\n",tid
);
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()) {
240 predict_record
.pushedRAS
= false;
242 TheISA::advancePC(target
, inst
);
246 if (inst
->isReturn()) {
247 predict_record
.wasReturn
= true;
249 TheISA::advancePC(target
, inst
);
254 predHist
[tid
].push_front(predict_record
);
256 DPRINTF(Branch
, "[tid:%i]: [sn:%i]: History entry added."
257 "predHist.size(): %i\n", tid
, seqNum
, predHist
[tid
].size());
263 BPredUnit::predictInOrder(const StaticInstPtr
&inst
, const InstSeqNum
&seqNum
,
264 int asid
, TheISA::PCState
&instPC
,
265 TheISA::PCState
&predPC
, ThreadID tid
)
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.
272 using TheISA::MachInst
;
274 bool pred_taken
= false;
275 TheISA::PCState target
;
278 ppBranches
->notify(1);
280 DPRINTF(Branch
, "[tid:%i] [sn:%i] %s ... PC %s doing branch "
281 "prediction\n", tid
, seqNum
,
282 inst
->disassemble(instPC
.instAddr()), instPC
);
284 void *bp_history
= NULL
;
286 if (inst
->isUncondCtrl()) {
287 DPRINTF(Branch
, "[tid:%i] Unconditional control.\n", tid
);
289 // Tell the BP there was an unconditional branch.
290 uncondBranch(instPC
.instAddr(), bp_history
);
292 if (inst
->isReturn() && RAS
[tid
].empty()) {
293 DPRINTF(Branch
, "[tid:%i] RAS is empty, predicting "
300 pred_taken
= lookup(predPC
.instAddr(), bp_history
);
303 PredictorHistory
predict_record(seqNum
, predPC
.instAddr(), pred_taken
,
306 // Now lookup in the BTB or RAS.
308 if (inst
->isReturn()) {
311 // If it's a function return call, then look up the address
313 TheISA::PCState rasTop
= RAS
[tid
].top();
314 target
= TheISA::buildRetPC(instPC
, rasTop
);
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
;
321 assert(predict_record
.RASIndex
< 16);
325 DPRINTF(Branch
, "[tid:%i]: Instruction %s is a return, "
326 "RAS predicted target: %s, RAS index: %i.\n",
328 predict_record
.RASIndex
);
332 if (inst
->isCall()) {
334 RAS
[tid
].push(instPC
);
335 predict_record
.pushedRAS
= true;
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;
341 DPRINTF(Branch
, "[tid:%i]: Instruction %s was a call"
342 ", adding %s to the RAS index: %i.\n",
347 if (inst
->isCall() &&
348 inst
->isUncondCtrl() &&
349 inst
->isDirectCtrl()) {
350 target
= inst
->branchTarget(instPC
);
351 } else if (BTB
.valid(predPC
.instAddr(), asid
)) {
354 // If it's not a return, use the BTB to get the target addr.
355 target
= BTB
.lookup(predPC
.instAddr(), asid
);
357 DPRINTF(Branch
, "[tid:%i]: [asid:%i] Instruction %s "
358 "predicted target is %s.\n",
359 tid
, asid
, instPC
, target
);
361 DPRINTF(Branch
, "[tid:%i]: BTB doesn't have a "
362 "valid entry, predicting false.\n",tid
);
369 // Set the PC and the instruction's predicted target.
372 DPRINTF(Branch
, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n",
373 tid
, seqNum
, predPC
);
375 predHist
[tid
].push_front(predict_record
);
377 DPRINTF(Branch
, "[tid:%i] [sn:%i] pushed onto front of predHist "
378 "...predHist.size(): %i\n",
379 tid
, seqNum
, predHist
[tid
].size());
385 BPredUnit::update(const InstSeqNum
&done_sn
, ThreadID tid
)
387 DPRINTF(Branch
, "[tid:%i]: Committing branches until "
388 "[sn:%lli].\n", tid
, done_sn
);
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);
397 retireSquashed(predHist
[tid
].back().bpHistory
);
400 predHist
[tid
].pop_back();
405 BPredUnit::squash(const InstSeqNum
&squashed_sn
, ThreadID tid
)
407 History
&pred_hist
= predHist
[tid
];
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
);
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
);
426 // This call should delete the bpHistory.
427 squash(pred_hist
.front().bpHistory
);
429 DPRINTF(Branch
, "[tid:%i]: Removing history for [sn:%i] "
430 "PC %s.\n", tid
, pred_hist
.front().seqNum
,
431 pred_hist
.front().pc
);
433 pred_hist
.pop_front();
435 DPRINTF(Branch
, "[tid:%i]: predHist.size(): %i\n",
436 tid
, predHist
[tid
].size());
441 BPredUnit::squash(const InstSeqNum
&squashed_sn
,
442 const TheISA::PCState
&corrTarget
,
443 bool actually_taken
, ThreadID tid
)
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
456 History
&pred_hist
= predHist
[tid
];
461 DPRINTF(Branch
, "[tid:%i]: Squashing from sequence number %i, "
462 "setting target to %s.\n", tid
, squashed_sn
, corrTarget
);
464 // Squash All Branches AFTER this mispredicted branch
465 squash(squashed_sn
, tid
);
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
470 if (!pred_hist
.empty()) {
472 auto hist_it
= pred_hist
.begin();
473 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
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
);
481 assert(pred_hist
.front().seqNum
== squashed_sn
);
485 if ((*hist_it
).usedRAS
) {
489 update((*hist_it
).pc
, actually_taken
,
490 pred_hist
.front().bpHistory
, true);
491 hist_it
->wasSquashed
= true;
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
,
499 hist_it
->usedRAS
= true;
502 DPRINTF(Branch
,"[tid: %i] BTB Update called for [sn:%i]"
503 " PC: %s\n", tid
,hist_it
->seqNum
, hist_it
->pc
);
505 BTB
.update((*hist_it
).pc
, corrTarget
, tid
);
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
);
524 hist_it
->pushedRAS
= false;
528 DPRINTF(Branch
, "[tid:%i]: [sn:%i] pred_hist empty, can't "
529 "update.\n", tid
, squashed_sn
);
537 for (const auto& ph
: predHist
) {
539 auto pred_hist_it
= ph
.begin();
541 cprintf("predHist[%i].size(): %i\n", i
++, ph
.size());
543 while (pred_hist_it
!= ph
.end()) {
544 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
546 pred_hist_it
->seqNum
, pred_hist_it
->pc
,
547 pred_hist_it
->tid
, pred_hist_it
->predTaken
,
548 pred_hist_it
->bpHistory
);