2 * Copyright (c) 2011 ARM Limited
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
14 * Copyright (c) 2004-2005 The Regents of The University of Michigan
15 * All rights reserved.
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45 #include "arch/isa_traits.hh"
46 #include "arch/types.hh"
47 #include "arch/utility.hh"
48 #include "base/trace.hh"
49 #include "config/the_isa.hh"
50 #include "cpu/o3/bpred_unit.hh"
51 #include "debug/Fetch.hh"
52 #include "params/DerivO3CPU.hh"
55 BPredUnit<Impl>::BPredUnit(DerivO3CPUParams *params)
56 : _name(params->name + ".BPredUnit"),
57 BTB(params->BTBEntries,
61 // Setup the selected predictor.
62 if (params->predType == "local") {
63 localBP = new LocalBP(params->localPredictorSize,
65 params->instShiftAmt);
67 } else if (params->predType == "tournament") {
68 tournamentBP = new TournamentBP(params->localPredictorSize,
70 params->localHistoryTableSize,
71 params->localHistoryBits,
72 params->globalPredictorSize,
73 params->globalHistoryBits,
74 params->globalCtrBits,
75 params->choicePredictorSize,
76 params->choiceCtrBits,
77 params->instShiftAmt);
78 predictor = Tournament;
80 fatal("Invalid BP selected!");
83 for (int i=0; i < Impl::MaxThreads; i++)
84 RAS[i].init(params->RASSize);
89 BPredUnit<Impl>::regStats()
92 .name(name() + ".lookups")
93 .desc("Number of BP lookups")
97 .name(name() + ".condPredicted")
98 .desc("Number of conditional branches predicted")
102 .name(name() + ".condIncorrect")
103 .desc("Number of conditional branches incorrect")
107 .name(name() + ".BTBLookups")
108 .desc("Number of BTB lookups")
112 .name(name() + ".BTBHits")
113 .desc("Number of BTB hits")
117 .name(name() + ".BTBCorrect")
118 .desc("Number of correct BTB predictions (this stat may not "
123 .name(name() + ".usedRAS")
124 .desc("Number of times the RAS was used to get a target.")
128 .name(name() + ".RASInCorrect")
129 .desc("Number of incorrect RAS predictions.")
133 template <class Impl>
135 BPredUnit<Impl>::switchOut()
137 // Clear any state upon switch out.
138 for (int i = 0; i < Impl::MaxThreads; ++i) {
143 template <class Impl>
145 BPredUnit<Impl>::takeOverFrom()
147 // Can reset all predictor state, but it's not necessarily better
148 // than leaving it be.
150 for (int i = 0; i < Impl::MaxThreads; ++i)
158 template <class Impl>
160 BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
162 // See if branch predictor predicts taken.
163 // If so, get its target addr either from the BTB or the RAS.
164 // Save off record of branch stuff so the RAS can be fixed
165 // up once it's done.
167 bool pred_taken = false;
168 TheISA::PCState target = pc;
172 void *bp_history = NULL;
174 if (inst->isUncondCtrl()) {
175 DPRINTF(Fetch, "BranchPred: [tid:%i]: Unconditional control.\n", tid);
177 // Tell the BP there was an unconditional branch.
178 BPUncond(bp_history);
181 pred_taken = BPLookup(pc.instAddr(), bp_history);
183 DPRINTF(Fetch, "BranchPred:[tid:%i]: [sn:%i] Branch predictor"
184 " predicted %i for PC %s\n",
185 tid, inst->seqNum, pred_taken, inst->pcState());
188 DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating prediction history "
190 tid, inst->seqNum, inst->pcState());
192 PredictorHistory predict_record(inst->seqNum, pc.instAddr(),
193 pred_taken, bp_history, tid);
195 // Now lookup in the BTB or RAS.
197 if (inst->isReturn()) {
199 predict_record.wasReturn = true;
200 // If it's a function return call, then look up the address
202 TheISA::PCState rasTop = RAS[tid].top();
203 target = TheISA::buildRetPC(pc, rasTop);
205 // Record the top entry of the RAS, and its index.
206 predict_record.usedRAS = true;
207 predict_record.RASIndex = RAS[tid].topIdx();
208 predict_record.RASTarget = rasTop;
212 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s is a return, "
213 "RAS predicted target: %s, RAS index: %i.\n",
214 tid, inst->pcState(), target, predict_record.RASIndex);
218 if (inst->isCall()) {
220 predict_record.pushedRAS = true;
221 // Record that it was a call so that the top RAS entry can
222 // be popped off if the speculation is incorrect.
223 predict_record.wasCall = true;
225 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s was a "
226 "call, adding %s to the RAS index: %i.\n",
227 tid, inst->pcState(), pc, RAS[tid].topIdx());
230 if (BTB.valid(pc.instAddr(), tid)) {
232 predict_record.validBTB = true;
234 // If it's not a return, use the BTB to get the target addr.
235 target = BTB.lookup(pc.instAddr(), tid);
237 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s predicted"
238 " target is %s.\n", tid, inst->pcState(), target);
241 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
242 "valid entry.\n",tid);
244 // The Direction of the branch predictor is altered because the
245 // BTB did not have an entry
246 // The predictor needs to be updated accordingly
247 if (!inst->isCall() && !inst->isReturn()) {
248 BPBTBUpdate(pc.instAddr(), bp_history);
249 DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
251 tid, inst->seqNum, inst->pcState());
252 } else if (inst->isCall() && !inst->isUncondCtrl()) {
254 predict_record.pushedRAS = false;
256 TheISA::advancePC(target, inst->staticInst);
261 if (inst->isReturn()) {
262 predict_record.wasReturn = true;
264 TheISA::advancePC(target, inst->staticInst);
269 predHist[tid].push_front(predict_record);
271 DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i]: History entry added."
272 "predHist.size(): %i\n", tid, inst->seqNum, predHist[tid].size());
277 template <class Impl>
279 BPredUnit<Impl>::update(const InstSeqNum &done_sn, ThreadID tid)
281 DPRINTF(Fetch, "BranchPred: [tid:%i]: Committing branches until "
282 "[sn:%lli].\n", tid, done_sn);
284 while (!predHist[tid].empty() &&
285 predHist[tid].back().seqNum <= done_sn) {
286 // Update the branch predictor with the correct results.
287 BPUpdate(predHist[tid].back().pc,
288 predHist[tid].back().predTaken,
289 predHist[tid].back().bpHistory, false);
291 predHist[tid].pop_back();
295 template <class Impl>
297 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, ThreadID tid)
299 History &pred_hist = predHist[tid];
301 while (!pred_hist.empty() &&
302 pred_hist.front().seqNum > squashed_sn) {
303 if (pred_hist.front().usedRAS) {
304 DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i,"
305 " target: %s.\n", tid,
306 pred_hist.front().RASIndex, pred_hist.front().RASTarget);
308 RAS[tid].restore(pred_hist.front().RASIndex,
309 pred_hist.front().RASTarget);
310 } else if(pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
311 // Was a call but predicated false. Pop RAS here
312 DPRINTF(Fetch, "BranchPred: [tid: %i] Squashing"
313 " Call [sn:%i] PC: %s Popping RAS\n", tid,
314 pred_hist.front().seqNum, pred_hist.front().pc);
318 // This call should delete the bpHistory.
319 BPSquash(pred_hist.front().bpHistory);
321 DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] "
322 "PC %s.\n", tid, pred_hist.front().seqNum,
323 pred_hist.front().pc);
325 pred_hist.pop_front();
327 DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n",
328 tid, predHist[tid].size());
333 template <class Impl>
335 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
336 const TheISA::PCState &corrTarget,
340 // Now that we know that a branch was mispredicted, we need to undo
341 // all the branches that have been seen up until this branch and
342 // fix up everything.
343 // NOTE: This should be call conceivably in 2 scenarios:
344 // (1) After an branch is executed, it updates its status in the ROB
345 // The commit stage then checks the ROB update and sends a signal to
346 // the fetch stage to squash history after the mispredict
347 // (2) In the decode stage, you can find out early if a unconditional
348 // PC-relative, branch was predicted incorrectly. If so, a signal
349 // to the fetch stage is sent to squash history after the mispredict
351 History &pred_hist = predHist[tid];
355 DPRINTF(Fetch, "BranchPred: [tid:%i]: Squashing from sequence number %i, "
356 "setting target to %s.\n",
357 tid, squashed_sn, corrTarget);
359 // Squash All Branches AFTER this mispredicted branch
360 squash(squashed_sn, tid);
362 // If there's a squash due to a syscall, there may not be an entry
363 // corresponding to the squash. In that case, don't bother trying to
365 if (!pred_hist.empty()) {
367 HistoryIt hist_it = pred_hist.begin();
368 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
371 //assert(hist_it != pred_hist.end());
372 if (pred_hist.front().seqNum != squashed_sn) {
373 DPRINTF(Fetch, "Front sn %i != Squash sn %i\n",
374 pred_hist.front().seqNum, squashed_sn);
376 assert(pred_hist.front().seqNum == squashed_sn);
380 if ((*hist_it).usedRAS) {
384 BPUpdate((*hist_it).pc, actually_taken,
385 pred_hist.front().bpHistory, true);
386 if (actually_taken) {
387 if (hist_it->wasReturn && !hist_it->usedRAS) {
388 DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
389 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
393 DPRINTF(Fetch,"BranchPred: [tid: %i] BTB Update called for [sn:%i]"
394 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
397 BTB.update((*hist_it).pc, corrTarget, tid);
401 if (hist_it->usedRAS) {
402 DPRINTF(Fetch,"BranchPred: [tid: %i] Incorrectly predicted"
403 " return [sn:%i] PC: %s Restoring RAS\n", tid,
404 hist_it->seqNum, hist_it->pc);
405 DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS"
406 " to: %i, target: %s.\n", tid,
407 hist_it->RASIndex, hist_it->RASTarget);
408 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
410 } else if (hist_it->wasCall && hist_it->pushedRAS) {
411 //Was a Call but predicated false. Pop RAS here
412 DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
413 " Call [sn:%i] PC: %s Popping RAS\n", tid,
414 hist_it->seqNum, hist_it->pc);
418 DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]"
419 " PC %s Actually Taken: %i\n", tid, hist_it->seqNum,
420 hist_it->pc, actually_taken);
422 pred_hist.erase(hist_it);
424 DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid,
425 predHist[tid].size());
429 template <class Impl>
431 BPredUnit<Impl>::BPUncond(void * &bp_history)
433 // Only the tournament predictor cares about unconditional branches.
434 if (predictor == Tournament) {
435 tournamentBP->uncondBr(bp_history);
439 template <class Impl>
441 BPredUnit<Impl>::BPSquash(void *bp_history)
443 if (predictor == Local) {
444 localBP->squash(bp_history);
445 } else if (predictor == Tournament) {
446 tournamentBP->squash(bp_history);
448 panic("Predictor type is unexpected value!");
452 template <class Impl>
454 BPredUnit<Impl>::BPLookup(Addr instPC, void * &bp_history)
456 if (predictor == Local) {
457 return localBP->lookup(instPC, bp_history);
458 } else if (predictor == Tournament) {
459 return tournamentBP->lookup(instPC, bp_history);
461 panic("Predictor type is unexpected value!");
465 template <class Impl>
467 BPredUnit<Impl>::BPBTBUpdate(Addr instPC, void * &bp_history)
469 if (predictor == Local) {
470 return localBP->BTBUpdate(instPC, bp_history);
471 } else if (predictor == Tournament) {
472 return tournamentBP->BTBUpdate(instPC, bp_history);
474 panic("Predictor type is unexpected value!");
478 template <class Impl>
480 BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history,
483 if (predictor == Local) {
484 localBP->update(instPC, taken, bp_history);
485 } else if (predictor == Tournament) {
486 tournamentBP->update(instPC, taken, bp_history, squashed);
488 panic("Predictor type is unexpected value!");
492 template <class Impl>
494 BPredUnit<Impl>::dump()
496 HistoryIt pred_hist_it;
498 for (int i = 0; i < Impl::MaxThreads; ++i) {
499 if (!predHist[i].empty()) {
500 pred_hist_it = predHist[i].begin();
502 cprintf("predHist[%i].size(): %i\n", i, predHist[i].size());
504 while (pred_hist_it != predHist[i].end()) {
505 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
507 pred_hist_it->seqNum, pred_hist_it->pc,
508 pred_hist_it->tid, pred_hist_it->predTaken,
509 pred_hist_it->bpHistory);