summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/cpu/inorder/resources/bpred_unit.cc9
-rw-r--r--src/cpu/inorder/resources/bpred_unit.hh3
-rw-r--r--src/cpu/o3/bpred_unit.hh14
-rw-r--r--src/cpu/o3/bpred_unit_impl.hh63
-rw-r--r--src/cpu/o3/commit_impl.hh7
-rw-r--r--src/cpu/o3/decode_impl.hh4
-rw-r--r--src/cpu/pred/2bit_local.cc8
-rw-r--r--src/cpu/pred/2bit_local.hh21
-rw-r--r--src/cpu/pred/tournament.cc86
-rw-r--r--src/cpu/pred/tournament.hh28
10 files changed, 188 insertions, 55 deletions
diff --git a/src/cpu/inorder/resources/bpred_unit.cc b/src/cpu/inorder/resources/bpred_unit.cc
index 778366532..1a458e1d6 100644
--- a/src/cpu/inorder/resources/bpred_unit.cc
+++ b/src/cpu/inorder/resources/bpred_unit.cc
@@ -284,7 +284,8 @@ BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
// 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 @@ BPredUnit::squash(const InstSeqNum &squashed_sn,
}
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 @@ BPredUnit::BPLookup(Addr inst_PC, void * &bp_history)
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 --git a/src/cpu/inorder/resources/bpred_unit.hh b/src/cpu/inorder/resources/bpred_unit.hh
index 33ca4a0c6..b5d12d2db 100644
--- a/src/cpu/inorder/resources/bpred_unit.hh
+++ b/src/cpu/inorder/resources/bpred_unit.hh
@@ -160,9 +160,10 @@ class BPredUnit
* @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 --git a/src/cpu/o3/bpred_unit.hh b/src/cpu/o3/bpred_unit.hh
index 8dbba9085..d3ae93b38 100644
--- a/src/cpu/o3/bpred_unit.hh
+++ b/src/cpu/o3/bpred_unit.hh
@@ -137,6 +137,16 @@ class BPredUnit
*/
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 @@ class BPredUnit
* @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 --git a/src/cpu/o3/bpred_unit_impl.hh b/src/cpu/o3/bpred_unit_impl.hh
index e0292e232..8502f342c 100644
--- a/src/cpu/o3/bpred_unit_impl.hh
+++ b/src/cpu/o3/bpred_unit_impl.hh
@@ -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 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
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 @@ BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
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 @@ BPredUnit<Impl>::update(const InstSeqNum &done_sn, ThreadID tid)
// 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 @@ BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
}
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 @@ BPredUnit<Impl>::BPLookup(Addr instPC, void * &bp_history)
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 --git a/src/cpu/o3/commit_impl.hh b/src/cpu/o3/commit_impl.hh
index 7ca42ae5b..b4cc4b017 100644
--- a/src/cpu/o3/commit_impl.hh
+++ b/src/cpu/o3/commit_impl.hh
@@ -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 @@ DefaultCommit<Impl>::commit()
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 --git a/src/cpu/o3/decode_impl.hh b/src/cpu/o3/decode_impl.hh
index 60bca1041..22b89f4a8 100644
--- a/src/cpu/o3/decode_impl.hh
+++ b/src/cpu/o3/decode_impl.hh
@@ -278,11 +278,15 @@ DefaultDecode<Impl>::squash(DynInstPtr &inst, ThreadID tid)
// 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 --git a/src/cpu/pred/2bit_local.cc b/src/cpu/pred/2bit_local.cc
index dc8cf50b7..4d18c419b 100644
--- a/src/cpu/pred/2bit_local.cc
+++ b/src/cpu/pred/2bit_local.cc
@@ -79,6 +79,14 @@ LocalBP::reset()
}
}
+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 --git a/src/cpu/pred/2bit_local.hh b/src/cpu/pred/2bit_local.hh
index 8b7bb8463..01a0b64db 100644
--- a/src/cpu/pred/2bit_local.hh
+++ b/src/cpu/pred/2bit_local.hh
@@ -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 @@ class LocalBP
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 --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc
index 9608dc011..3adafb608 100644
--- a/src/cpu/pred/tournament.cc
+++ b/src/cpu/pred/tournament.cc
@@ -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.
*
@@ -146,6 +158,18 @@ TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx)
(localHistoryTable[local_history_idx] << 1);
}
+
+void
+TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
+{
+ unsigned local_history_idx = calcLocHistIdx(branch_addr);
+ //Update Global History to Not Taken
+ globalHistory = globalHistory & (globalHistoryMask - 1);
+ //Update Local History to Not Taken
+ localHistoryTable[local_history_idx] =
+ localHistoryTable[local_history_idx] & (localPredictorMask - 1);
+}
+
bool
TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
{
@@ -174,6 +198,7 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
history->localPredTaken = local_prediction;
history->globalPredTaken = global_prediction;
history->globalUsed = choice_prediction;
+ history->localHistory = local_predictor_idx;
bp_history = (void *)history;
assert(globalHistory < globalPredictorSize &&
@@ -184,30 +209,22 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history)
// all histories.
if (choice_prediction) {
if (global_prediction) {
-// updateHistoriesTaken(local_history_idx);
-// globalCtrs[globalHistory].increment();
-// localCtrs[local_history_idx].increment();
updateGlobalHistTaken();
+ updateLocalHistTaken(local_history_idx);
return true;
} else {
-// updateHistoriesNotTaken(local_history_idx);
-// globalCtrs[globalHistory].decrement();
-// localCtrs[local_history_idx].decrement();
updateGlobalHistNotTaken();
+ updateLocalHistNotTaken(local_history_idx);
return false;
}
} else {
if (local_prediction) {
-// updateHistoriesTaken(local_history_idx);
-// globalCtrs[globalHistory].increment();
-// localCtrs[local_history_idx].increment();
updateGlobalHistTaken();
+ updateLocalHistTaken(local_history_idx);
return true;
} else {
-// updateHistoriesNotTaken(local_history_idx);
-// globalCtrs[globalHistory].decrement();
-// localCtrs[local_history_idx].decrement();
updateGlobalHistNotTaken();
+ updateLocalHistNotTaken(local_history_idx);
return false;
}
}
@@ -222,16 +239,18 @@ TournamentBP::uncondBr(void * &bp_history)
history->localPredTaken = true;
history->globalPredTaken = true;
history->globalUsed = true;
+ history->localHistory = invalidPredictorIndex;
bp_history = static_cast<void *>(history);
updateGlobalHistTaken();
}
void
-TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
+TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history,
+ bool squashed)
{
unsigned local_history_idx;
- unsigned local_predictor_idx;
+ unsigned local_predictor_idx M5_VAR_USED;
unsigned local_predictor_hist;
// Get the local predictor's current prediction
@@ -259,33 +278,34 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history)
// resolution of the branch. Global history is updated
// speculatively and restored upon squash() calls, so it does not
// need to be updated.
+ unsigned old_local_pred_index = history->localHistory
+ & localPredictorMask;
if (taken) {
- localCtrs[local_predictor_idx].increment();
globalCtrs[history->globalHistory].increment();
-
- updateLocalHistTaken(local_history_idx);
+ if (old_local_pred_index != invalidPredictorIndex) {
+ localCtrs[old_local_pred_index].increment();
+ }
} else {
- localCtrs[local_predictor_idx].decrement();
globalCtrs[history->globalHistory].decrement();
-
- updateLocalHistNotTaken(local_history_idx);
+ if (old_local_pred_index != invalidPredictorIndex) {
+ localCtrs[old_local_pred_index].decrement();
+ }
}
- bool mispredict = false;
-
- //global predictor used and mispredicted
- if (history->globalUsed && history->globalPredTaken != taken)
- mispredict = true;
- //local predictor used and mispredicted
- else if (!history->globalUsed && history->localPredTaken != taken)
- mispredict = true;
-
- if (mispredict) {
+ if (squashed) {
if (taken) {
- globalHistory = globalHistory | 1;
+ globalHistory = (history->globalHistory << 1) | 1;
+ globalHistory = globalHistory & globalHistoryMask;
+ if (history->localHistory != invalidPredictorIndex)
+ localHistoryTable[local_history_idx] =
+ (history->localHistory << 1) | 1;
} else {
- unsigned mask = globalHistoryMask - 1;
- globalHistory = globalHistory & mask;
+ globalHistory = (history->globalHistory << 1);
+ globalHistory = globalHistory & globalHistoryMask;
+ if (history->localHistory != invalidPredictorIndex) {
+ localHistoryTable[local_history_idx] =
+ history->localHistory << 1;
+ }
}
}
diff --git a/src/cpu/pred/tournament.hh b/src/cpu/pred/tournament.hh
index 96bd43ed6..f9df2a61d 100644
--- a/src/cpu/pred/tournament.hh
+++ b/src/cpu/pred/tournament.hh
@@ -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.
*
@@ -79,15 +91,24 @@ class TournamentBP
* @param bp_history Pointer that will be set to the BPHistory object.
*/
void uncondBr(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.
* @param bp_history Pointer to the BPHistory object that was created
* when the branch was predicted.
+ * @param squashed is set when this function is called during a squash
+ * operation.
*/
- void update(Addr &branch_addr, bool taken, void *bp_history);
+ void update(Addr &branch_addr, bool taken, void *bp_history, bool squashed);
/**
* Restores the global branch history on a squash.
@@ -149,11 +170,14 @@ class TournamentBP
static int newCount;
#endif
unsigned globalHistory;
+ unsigned localHistory;
bool localPredTaken;
bool globalPredTaken;
bool globalUsed;
};
+ /** Flag for invalid predictor index */
+ static const int invalidPredictorIndex = -1;
/** Local counters. */
std::vector<SatCounter> localCtrs;