changeset a02932e2e73d in /z/repo/gem5
details: http://repo.gem5.org/gem5?cmd=changeset;node=a02932e2e73d
description:
BP: Fix several Branch Predictor issues.
1. Updates the Branch Predictor correctly to the state
just after a mispredicted branch, if a squash occurs.
2. If a BTB does not find an entry, the branch is predicted not taken.
The global history is modified to correctly reflect this prediction.
3. Local history is now updated at the fetch stage instead of
execute stage.
4. In the Update stage of the branch predictor the local predictors are
now correctly updated according to the state of local history during
fetch stage.
This patch also improves performance by as much as 17% on some
benchmarks
diffstat:
src/cpu/inorder/resources/bpred_unit.cc | 9 +-
src/cpu/inorder/resources/bpred_unit.hh | 3 +-
src/cpu/o3/bpred_unit.hh | 14 ++++-
src/cpu/o3/bpred_unit_impl.hh | 63 +++++++++++++++++++----
src/cpu/o3/commit_impl.hh | 7 ++-
src/cpu/o3/decode_impl.hh | 4 +
src/cpu/pred/2bit_local.cc | 8 +++
src/cpu/pred/2bit_local.hh | 21 ++++++++
src/cpu/pred/tournament.cc | 86 ++++++++++++++++++++------------
src/cpu/pred/tournament.hh | 28 +++++++++-
10 files changed, 188 insertions(+), 55 deletions(-)
diffs (truncated from 511 to 300 lines):
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/inorder/resources/bpred_unit.cc
--- a/src/cpu/inorder/resources/bpred_unit.cc Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/inorder/resources/bpred_unit.cc Mon Feb 13 12:26:24 2012 -0600
@@ -284,7 +284,8 @@
// Update the branch predictor with the correct results.
BPUpdate(predHist[tid].back().pc.instAddr(),
predHist[tid].back().predTaken,
- predHist[tid].back().bpHistory);
+ predHist[tid].back().bpHistory,
+ false);
predHist[tid].pop_back();
}
@@ -367,7 +368,7 @@
}
BPUpdate((*hist_it).pc.instAddr(), actually_taken,
- pred_hist.front().bpHistory);
+ pred_hist.front().bpHistory, true);
// only update BTB on branch taken right???
if (actually_taken)
@@ -425,12 +426,12 @@
void
-BPredUnit::BPUpdate(Addr inst_PC, bool taken, void *bp_history)
+BPredUnit::BPUpdate(Addr inst_PC, bool taken, void *bp_history, bool squashed)
{
if (predictor == Local) {
localBP->update(inst_PC, taken, bp_history);
} else if (predictor == Tournament) {
- tournamentBP->update(inst_PC, taken, bp_history);
+ tournamentBP->update(inst_PC, taken, bp_history, squashed);
} else {
panic("Predictor type is unexpected value!");
}
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/inorder/resources/bpred_unit.hh
--- a/src/cpu/inorder/resources/bpred_unit.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/inorder/resources/bpred_unit.hh Mon Feb 13 12:26:24 2012 -0600
@@ -160,9 +160,10 @@
* @param taken Whether the branch was taken or not taken.
* @param bp_history Pointer to the branch predictor state that is
* associated with the branch lookup that is being updated.
+ * @param squashed if the branch in question was squashed or not
* @todo Make this update flexible enough to handle a global predictor.
*/
- void BPUpdate(Addr instPC, bool taken, void *bp_history);
+ void BPUpdate(Addr instPC, bool taken, void *bp_history, bool squashed);
/**
* Updates the BTB with the target of a branch.
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/o3/bpred_unit.hh
--- a/src/cpu/o3/bpred_unit.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/o3/bpred_unit.hh Mon Feb 13 12:26:24 2012 -0600
@@ -137,6 +137,16 @@
*/
bool BPLookup(Addr instPC, void * &bp_history);
+ /**
+ * If a branch is not taken, because the BTB address is invalid or missing,
+ * this function sets the appropriate counter in the global and local
+ * predictors to not taken.
+ * @param inst_PC The PC to look up the local predictor.
+ * @param bp_history Pointer that will be set to an object that
+ * has the branch predictor state associated with the lookup.
+ */
+ void BPBTBUpdate(Addr instPC, void * &bp_history);
+
/**
* Looks up a given PC in the BTB to see if a matching entry exists.
* @param inst_PC The PC to look up.
@@ -159,9 +169,11 @@
* @param taken Whether the branch was taken or not taken.
* @param bp_history Pointer to the branch predictor state that is
* associated with the branch lookup that is being updated.
+ * @param squashed Set to true when this function is called during a
+ * squash operation.
* @todo Make this update flexible enough to handle a global predictor.
*/
- void BPUpdate(Addr instPC, bool taken, void *bp_history);
+ void BPUpdate(Addr instPC, bool taken, void *bp_history, bool squashed);
/**
* Updates the BTB with the target of a branch.
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/o3/bpred_unit_impl.hh
--- a/src/cpu/o3/bpred_unit_impl.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/o3/bpred_unit_impl.hh Mon Feb 13 12:26:24 2012 -0600
@@ -1,4 +1,16 @@
/*
+ * Copyright (c) 2011 ARM Limited
+ * 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.
*
@@ -166,12 +178,11 @@
BPUncond(bp_history);
} else {
++condPredicted;
-
pred_taken = BPLookup(pc.instAddr(), bp_history);
- DPRINTF(Fetch, "BranchPred: [tid:%i]: Branch predictor predicted %i "
- "for PC %s\n",
- tid, pred_taken, inst->pcState());
+ DPRINTF(Fetch, "BranchPred:[tid:%i]: [sn:%i] Branch predictor"
+ " predicted %i for PC %s\n",
+ tid, inst->seqNum, pred_taken, inst->pcState());
}
DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating prediction history "
@@ -231,6 +242,15 @@
DPRINTF(Fetch, "BranchPred: [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()) {
+ BPBTBUpdate(pc.instAddr(), bp_history);
+ DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
+ " called for %s\n",
+ tid, inst->seqNum, inst->pcState());
+ }
TheISA::advancePC(target, inst->staticInst);
}
@@ -261,7 +281,7 @@
// Update the branch predictor with the correct results.
BPUpdate(predHist[tid].back().pc,
predHist[tid].back().predTaken,
- predHist[tid].back().bpHistory);
+ predHist[tid].back().bpHistory, false);
predHist[tid].pop_back();
}
@@ -356,12 +376,15 @@
}
BPUpdate((*hist_it).pc, actually_taken,
- pred_hist.front().bpHistory);
-
- BTB.update((*hist_it).pc, corrTarget, tid);
-
- DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] "
- "PC %s.\n", tid, (*hist_it).seqNum, (*hist_it).pc);
+ pred_hist.front().bpHistory, true);
+ if (actually_taken){
+ DPRINTF(Fetch,"BranchPred: [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);
+ }
+ DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]"
+ " PC %s Actually Taken: %i\n", tid, (*hist_it).seqNum,
+ (*hist_it).pc, actually_taken);
pred_hist.erase(hist_it);
@@ -407,12 +430,26 @@
template <class Impl>
void
-BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history)
+BPredUnit<Impl>::BPBTBUpdate(Addr instPC, void * &bp_history)
+{
+ if (predictor == Local) {
+ return localBP->BTBUpdate(instPC, bp_history);
+ } else if (predictor == Tournament) {
+ return tournamentBP->BTBUpdate(instPC, bp_history);
+ } else {
+ panic("Predictor type is unexpected value!");
+ }
+}
+
+template <class Impl>
+void
+BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history,
+ bool squashed)
{
if (predictor == Local) {
localBP->update(instPC, taken, bp_history);
} else if (predictor == Tournament) {
- tournamentBP->update(instPC, taken, bp_history);
+ tournamentBP->update(instPC, taken, bp_history, squashed);
} else {
panic("Predictor type is unexpected value!");
}
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/o3/commit_impl.hh
--- a/src/cpu/o3/commit_impl.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/o3/commit_impl.hh Mon Feb 13 12:26:24 2012 -0600
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2010 ARM Limited
+ * Copyright (c) 2010-2011 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -868,6 +868,11 @@
fromIEW->branchTaken[tid];
toIEW->commitInfo[tid].squashInst =
rob->findInst(tid, squashed_inst);
+ if (toIEW->commitInfo[tid].mispredictInst) {
+ if (toIEW->commitInfo[tid].mispredictInst->isUncondCtrl()) {
+ toIEW->commitInfo[tid].branchTaken = true;
+ }
+ }
toIEW->commitInfo[tid].pc = fromIEW->pc[tid];
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/o3/decode_impl.hh
--- a/src/cpu/o3/decode_impl.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/o3/decode_impl.hh Mon Feb 13 12:26:24 2012 -0600
@@ -278,11 +278,15 @@
// Send back mispredict information.
toFetch->decodeInfo[tid].branchMispredict = true;
toFetch->decodeInfo[tid].predIncorrect = true;
+ toFetch->decodeInfo[tid].mispredictInst = inst;
toFetch->decodeInfo[tid].squash = true;
toFetch->decodeInfo[tid].doneSeqNum = inst->seqNum;
toFetch->decodeInfo[tid].nextPC = inst->branchTarget();
toFetch->decodeInfo[tid].branchTaken = inst->pcState().branching();
toFetch->decodeInfo[tid].squashInst = inst;
+ if (toFetch->decodeInfo[tid].mispredictInst->isUncondCtrl()) {
+ toFetch->decodeInfo[tid].branchTaken = true;
+ }
InstSeqNum squash_seq_num = inst->seqNum;
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/pred/2bit_local.cc
--- a/src/cpu/pred/2bit_local.cc Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/pred/2bit_local.cc Mon Feb 13 12:26:24 2012 -0600
@@ -79,6 +79,14 @@
}
}
+void
+LocalBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
+{
+// Place holder for a function that is called to update predictor history when
+// a BTB entry is invalid or not found.
+}
+
+
bool
LocalBP::lookup(Addr &branch_addr, void * &bp_history)
{
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/pred/2bit_local.hh
--- a/src/cpu/pred/2bit_local.hh Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/pred/2bit_local.hh Mon Feb 13 12:26:24 2012 -0600
@@ -1,4 +1,16 @@
/*
+ * Copyright (c) 2011 ARM Limited
+ * 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-2006 The Regents of The University of Michigan
* All rights reserved.
*
@@ -65,6 +77,15 @@
bool lookup(Addr &branch_addr, void * &bp_history);
/**
+ * Updates the branch predictor to Not Taken if a BTB entry is
+ * invalid or not found.
+ * @param branch_addr The address of the branch to look up.
+ * @param bp_history Pointer to any bp history state.
+ * @return Whether or not the branch is taken.
+ */
+ void BTBUpdate(Addr &branch_addr, void * &bp_history);
+
+ /**
* Updates the branch predictor with the actual result of a branch.
* @param branch_addr The address of the branch to update.
* @param taken Whether or not the branch was taken.
diff -r 7cbe0e2f6b86 -r a02932e2e73d src/cpu/pred/tournament.cc
--- a/src/cpu/pred/tournament.cc Mon Feb 13 06:46:43 2012 -0500
+++ b/src/cpu/pred/tournament.cc Mon Feb 13 12:26:24 2012 -0600
@@ -1,4 +1,16 @@
/*
+ * Copyright (c) 2011 ARM Limited
+ * All rights reserved
+ *
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
