/*
- * Copyright (c) 2004-2006 The Regents of The University of Michigan
+ * Copyright (c) 2011-2012, 2014 ARM Limited
* Copyright (c) 2010 The University of Edinburgh
* Copyright (c) 2012 Mark D. Hill and David A. Wood
+ * All rights reserved
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder. You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
+ * Copyright (c) 2004-2005 The Regents of The University of Michigan
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Authors: Kevin Lim
- * Timothy M. Jones
*/
-#include "cpu/pred/2bit_local.hh"
-#include "cpu/pred/bi_mode.hh"
-#include "cpu/pred/bpred_unit_impl.hh"
-#include "cpu/pred/tournament.hh"
-
-BPredUnit *
-BranchPredictorParams::create()
-{
- // Setup the selected predictor.
- if (predType == "local") {
- return new LocalBP(this);
- } else if (predType == "tournament") {
- return new TournamentBP(this);
- } else if (predType == "bi-mode") {
- return new BiModeBP(this);
+#include "cpu/pred/bpred_unit.hh"
+
+#include <algorithm>
+
+#include "arch/isa_traits.hh"
+#include "arch/types.hh"
+#include "arch/utility.hh"
+#include "base/trace.hh"
+#include "config/the_isa.hh"
+#include "debug/Branch.hh"
+
+BPredUnit::BPredUnit(const Params *params)
+ : SimObject(params),
+ numThreads(params->numThreads),
+ predHist(numThreads),
+ BTB(params->BTBEntries,
+ params->BTBTagSize,
+ params->instShiftAmt,
+ params->numThreads),
+ RAS(numThreads),
+ useIndirect(params->useIndirect),
+ iPred(params->indirectHashGHR,
+ params->indirectHashTargets,
+ params->indirectSets,
+ params->indirectWays,
+ params->indirectTagSize,
+ params->indirectPathLength,
+ params->instShiftAmt,
+ params->numThreads),
+ instShiftAmt(params->instShiftAmt)
+{
+ for (auto& r : RAS)
+ r.init(params->RASSize);
+}
+
+void
+BPredUnit::regStats()
+{
+ SimObject::regStats();
+
+ lookups
+ .name(name() + ".lookups")
+ .desc("Number of BP lookups")
+ ;
+
+ condPredicted
+ .name(name() + ".condPredicted")
+ .desc("Number of conditional branches predicted")
+ ;
+
+ condIncorrect
+ .name(name() + ".condIncorrect")
+ .desc("Number of conditional branches incorrect")
+ ;
+
+ BTBLookups
+ .name(name() + ".BTBLookups")
+ .desc("Number of BTB lookups")
+ ;
+
+ BTBHits
+ .name(name() + ".BTBHits")
+ .desc("Number of BTB hits")
+ ;
+
+ BTBCorrect
+ .name(name() + ".BTBCorrect")
+ .desc("Number of correct BTB predictions (this stat may not "
+ "work properly.")
+ ;
+
+ BTBHitPct
+ .name(name() + ".BTBHitPct")
+ .desc("BTB Hit Percentage")
+ .precision(6);
+ BTBHitPct = (BTBHits / BTBLookups) * 100;
+
+ usedRAS
+ .name(name() + ".usedRAS")
+ .desc("Number of times the RAS was used to get a target.")
+ ;
+
+ RASIncorrect
+ .name(name() + ".RASInCorrect")
+ .desc("Number of incorrect RAS predictions.")
+ ;
+
+ indirectLookups
+ .name(name() + ".indirectLookups")
+ .desc("Number of indirect predictor lookups.")
+ ;
+
+ indirectHits
+ .name(name() + ".indirectHits")
+ .desc("Number of indirect target hits.")
+ ;
+
+ indirectMisses
+ .name(name() + ".indirectMisses")
+ .desc("Number of indirect misses.")
+ ;
+
+ indirectMispredicted
+ .name(name() + "indirectMispredicted")
+ .desc("Number of mispredicted indirect branches.")
+ ;
+
+}
+
+ProbePoints::PMUUPtr
+BPredUnit::pmuProbePoint(const char *name)
+{
+ ProbePoints::PMUUPtr ptr;
+ ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
+
+ return ptr;
+}
+
+void
+BPredUnit::regProbePoints()
+{
+ ppBranches = pmuProbePoint("Branches");
+ ppMisses = pmuProbePoint("Misses");
+}
+
+void
+BPredUnit::drainSanityCheck() const
+{
+ // We shouldn't have any outstanding requests when we resume from
+ // a drained system.
+ for (const auto& ph M5_VAR_USED : predHist)
+ assert(ph.empty());
+}
+
+bool
+BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
+ TheISA::PCState &pc, ThreadID tid)
+{
+ // See if branch predictor predicts taken.
+ // If so, get its target addr either from the BTB or the RAS.
+ // Save off record of branch stuff so the RAS can be fixed
+ // up once it's done.
+
+ bool pred_taken = false;
+ TheISA::PCState target = pc;
+
+ ++lookups;
+ ppBranches->notify(1);
+
+ void *bp_history = NULL;
+
+ if (inst->isUncondCtrl()) {
+ DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
+ pred_taken = true;
+ // Tell the BP there was an unconditional branch.
+ uncondBranch(tid, pc.instAddr(), bp_history);
+ } else {
+ ++condPredicted;
+ pred_taken = lookup(tid, pc.instAddr(), bp_history);
+
+ DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
+ " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc);
+ }
+
+ DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
+ "for PC %s\n", tid, seqNum, pc);
+
+ PredictorHistory predict_record(seqNum, pc.instAddr(),
+ pred_taken, bp_history, tid);
+
+ // Now lookup in the BTB or RAS.
+ if (pred_taken) {
+ if (inst->isReturn()) {
+ ++usedRAS;
+ predict_record.wasReturn = true;
+ // If it's a function return call, then look up the address
+ // in the RAS.
+ TheISA::PCState rasTop = RAS[tid].top();
+ target = TheISA::buildRetPC(pc, rasTop);
+
+ // Record the top entry of the RAS, and its index.
+ predict_record.usedRAS = true;
+ predict_record.RASIndex = RAS[tid].topIdx();
+ predict_record.RASTarget = rasTop;
+
+ RAS[tid].pop();
+
+ DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
+ "RAS predicted target: %s, RAS index: %i.\n",
+ tid, pc, target, predict_record.RASIndex);
+ } else {
+ ++BTBLookups;
+
+ if (inst->isCall()) {
+ RAS[tid].push(pc);
+ predict_record.pushedRAS = true;
+
+ // Record that it was a call so that the top RAS entry can
+ // be popped off if the speculation is incorrect.
+ predict_record.wasCall = true;
+
+ DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
+ "call, adding %s to the RAS index: %i.\n",
+ tid, pc, pc, RAS[tid].topIdx());
+ }
+
+ if (inst->isDirectCtrl() || !useIndirect) {
+ // Check BTB on direct branches
+ if (BTB.valid(pc.instAddr(), tid)) {
+ ++BTBHits;
+
+ // If it's not a return, use the BTB to get target addr.
+ target = BTB.lookup(pc.instAddr(), tid);
+
+ DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
+ " target is %s.\n", tid, pc, target);
+
+ } else {
+ DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
+ "valid entry.\n",tid);
+ pred_taken = false;
+ // The Direction of the branch predictor is altered
+ // because the BTB did not have an entry
+ // The predictor needs to be updated accordingly
+ if (!inst->isCall() && !inst->isReturn()) {
+ btbUpdate(tid, pc.instAddr(), bp_history);
+ DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
+ " called for %s\n", tid, seqNum, pc);
+ } else if (inst->isCall() && !inst->isUncondCtrl()) {
+ RAS[tid].pop();
+ predict_record.pushedRAS = false;
+ }
+ TheISA::advancePC(target, inst);
+ }
+ } else {
+ predict_record.wasIndirect = true;
+ ++indirectLookups;
+ //Consult indirect predictor on indirect control
+ if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history),
+ target, tid)) {
+ // Indirect predictor hit
+ ++indirectHits;
+ DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
+ "indirect target is %s.\n", tid, pc, target);
+ } else {
+ ++indirectMisses;
+ pred_taken = false;
+ DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
+ "target.\n", tid, pc);
+ if (!inst->isCall() && !inst->isReturn()) {
+
+ } else if (inst->isCall() && !inst->isUncondCtrl()) {
+ RAS[tid].pop();
+ predict_record.pushedRAS = false;
+ }
+ TheISA::advancePC(target, inst);
+ }
+ iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
+ tid);
+ }
+ }
} else {
- fatal("Invalid BP selected!");
+ if (inst->isReturn()) {
+ predict_record.wasReturn = true;
+ }
+ TheISA::advancePC(target, inst);
+ }
+
+ pc = target;
+
+ predHist[tid].push_front(predict_record);
+
+ DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
+ "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
+
+ return pred_taken;
+}
+
+void
+BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
+{
+ DPRINTF(Branch, "[tid:%i]: Committing branches until "
+ "[sn:%lli].\n", tid, done_sn);
+
+ iPred.commit(done_sn, tid);
+ while (!predHist[tid].empty() &&
+ predHist[tid].back().seqNum <= done_sn) {
+ // Update the branch predictor with the correct results.
+ update(tid, predHist[tid].back().pc,
+ predHist[tid].back().predTaken,
+ predHist[tid].back().bpHistory, false);
+
+ predHist[tid].pop_back();
}
}
+
+void
+BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
+{
+ History &pred_hist = predHist[tid];
+
+ iPred.squash(squashed_sn, tid);
+ while (!pred_hist.empty() &&
+ pred_hist.front().seqNum > squashed_sn) {
+ if (pred_hist.front().usedRAS) {
+ DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
+ " target: %s.\n", tid,
+ pred_hist.front().RASIndex, pred_hist.front().RASTarget);
+
+ RAS[tid].restore(pred_hist.front().RASIndex,
+ pred_hist.front().RASTarget);
+ } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
+ // Was a call but predicated false. Pop RAS here
+ DPRINTF(Branch, "[tid: %i] Squashing"
+ " Call [sn:%i] PC: %s Popping RAS\n", tid,
+ pred_hist.front().seqNum, pred_hist.front().pc);
+ RAS[tid].pop();
+ }
+
+ // This call should delete the bpHistory.
+ squash(tid, pred_hist.front().bpHistory);
+
+ DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
+ "PC %s.\n", tid, pred_hist.front().seqNum,
+ pred_hist.front().pc);
+
+ pred_hist.pop_front();
+
+ DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
+ tid, predHist[tid].size());
+ }
+}
+
+void
+BPredUnit::squash(const InstSeqNum &squashed_sn,
+ const TheISA::PCState &corrTarget,
+ bool actually_taken, ThreadID tid)
+{
+ // Now that we know that a branch was mispredicted, we need to undo
+ // all the branches that have been seen up until this branch and
+ // fix up everything.
+ // NOTE: This should be call conceivably in 2 scenarios:
+ // (1) After an branch is executed, it updates its status in the ROB
+ // The commit stage then checks the ROB update and sends a signal to
+ // the fetch stage to squash history after the mispredict
+ // (2) In the decode stage, you can find out early if a unconditional
+ // PC-relative, branch was predicted incorrectly. If so, a signal
+ // to the fetch stage is sent to squash history after the mispredict
+
+ History &pred_hist = predHist[tid];
+
+ ++condIncorrect;
+ ppMisses->notify(1);
+
+ DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
+ "setting target to %s.\n", tid, squashed_sn, corrTarget);
+
+ // Squash All Branches AFTER this mispredicted branch
+ squash(squashed_sn, tid);
+
+ // If there's a squash due to a syscall, there may not be an entry
+ // corresponding to the squash. In that case, don't bother trying to
+ // fix up the entry.
+ if (!pred_hist.empty()) {
+
+ auto hist_it = pred_hist.begin();
+ //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
+ // squashed_sn);
+
+ //assert(hist_it != pred_hist.end());
+ if (pred_hist.front().seqNum != squashed_sn) {
+ DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
+ pred_hist.front().seqNum, squashed_sn);
+
+ assert(pred_hist.front().seqNum == squashed_sn);
+ }
+
+
+ if ((*hist_it).usedRAS) {
+ ++RASIncorrect;
+ DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
+ tid, hist_it->seqNum);
+ }
+
+ // Get the underlying Global History Register
+ unsigned ghr = getGHR(tid, hist_it->bpHistory);
+
+ // There are separate functions for in-order and out-of-order
+ // branch prediction, but not for update. Therefore, this
+ // call should take into account that the mispredicted branch may
+ // be on the wrong path (i.e., OoO execution), and that the counter
+ // counter table(s) should not be updated. Thus, this call should
+ // restore the state of the underlying predictor, for instance the
+ // local/global histories. The counter tables will be updated when
+ // the branch actually commits.
+
+ // Remember the correct direction for the update at commit.
+ pred_hist.front().predTaken = actually_taken;
+
+ update(tid, (*hist_it).pc, actually_taken,
+ pred_hist.front().bpHistory, true);
+
+ if (actually_taken) {
+ if (hist_it->wasReturn && !hist_it->usedRAS) {
+ DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
+ " return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
+ hist_it->pc);
+ RAS[tid].pop();
+ hist_it->usedRAS = true;
+ }
+ if (hist_it->wasIndirect) {
+ ++indirectMispredicted;
+ iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid);
+ } else {
+ DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
+ " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
+
+ BTB.update((*hist_it).pc, corrTarget, tid);
+ }
+ } else {
+ //Actually not Taken
+ if (hist_it->usedRAS) {
+ DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
+ " return [sn:%i] PC: %s Restoring RAS\n", tid,
+ hist_it->seqNum, hist_it->pc);
+ DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
+ " to: %i, target: %s.\n", tid,
+ hist_it->RASIndex, hist_it->RASTarget);
+ RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
+ hist_it->usedRAS = false;
+ } else if (hist_it->wasCall && hist_it->pushedRAS) {
+ //Was a Call but predicated false. Pop RAS here
+ DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
+ " Call [sn:%i] PC: %s Popping RAS\n", tid,
+ hist_it->seqNum, hist_it->pc);
+ RAS[tid].pop();
+ hist_it->pushedRAS = false;
+ }
+ }
+ } else {
+ DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
+ "update.\n", tid, squashed_sn);
+ }
+}
+
+void
+BPredUnit::dump()
+{
+ int i = 0;
+ for (const auto& ph : predHist) {
+ if (!ph.empty()) {
+ auto pred_hist_it = ph.begin();
+
+ cprintf("predHist[%i].size(): %i\n", i++, ph.size());
+
+ while (pred_hist_it != ph.end()) {
+ cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
+ "bpHistory:%#x\n",
+ pred_hist_it->seqNum, pred_hist_it->pc,
+ pred_hist_it->tid, pred_hist_it->predTaken,
+ pred_hist_it->bpHistory);
+ pred_hist_it++;
+ }
+
+ cprintf("\n");
+ }
+ }
+}
+
projects / gem5.git / blobdiff