From bcf6983bc605b884fba52ec74634bddfd395cd5e Mon Sep 17 00:00:00 2001 From: Jairo Balart Date: Sun, 6 Jan 2019 20:35:11 +0100 Subject: [PATCH] cpu: Proposal for changing the indirect branch predictor interface Now the indirect branch predictor handles its own GHR instead of getting the one from the direction predictor. Also, now the commit method of the indirect predictor is called for every pending branch on an update, as the indirect predictors may want to update their interal structures/histories with the information of each branch. Change-Id: I7053fbea42a53960a3bc1ba32912cc99c160511e Reviewed-on: https://gem5-review.googlesource.com/c/15318 Reviewed-by: Andreas Sandberg Maintainer: Andreas Sandberg --- src/cpu/pred/bi_mode.cc | 6 ------ src/cpu/pred/bi_mode.hh | 1 - src/cpu/pred/bpred_unit.cc | 24 +++++++++++++-------- src/cpu/pred/bpred_unit.hh | 16 +++++++------- src/cpu/pred/indirect.cc | 43 +++++++++++++++++++++++++++++++++----- src/cpu/pred/indirect.hh | 17 +++++++++------ src/cpu/pred/tage.cc | 10 --------- src/cpu/pred/tage.hh | 1 - src/cpu/pred/tournament.cc | 6 ------ src/cpu/pred/tournament.hh | 2 -- 10 files changed, 73 insertions(+), 53 deletions(-) diff --git a/src/cpu/pred/bi_mode.cc b/src/cpu/pred/bi_mode.cc index 18286a702..e3a1e51ae 100644 --- a/src/cpu/pred/bi_mode.cc +++ b/src/cpu/pred/bi_mode.cc @@ -229,12 +229,6 @@ BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, delete history; } -unsigned -BiModeBP::getGHR(ThreadID tid, void *bp_history) const -{ - return static_cast(bp_history)->globalHistoryReg; -} - void BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken) { diff --git a/src/cpu/pred/bi_mode.hh b/src/cpu/pred/bi_mode.hh index 34766b599..e24c5ee5f 100644 --- a/src/cpu/pred/bi_mode.hh +++ b/src/cpu/pred/bi_mode.hh @@ -63,7 +63,6 @@ class BiModeBP : public BPredUnit void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history); void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, bool squashed, const StaticInstPtr & inst, Addr corrTarget); - unsigned getGHR(ThreadID tid, void *bp_history) const; private: void updateGlobalHistReg(ThreadID tid, bool taken); diff --git a/src/cpu/pred/bpred_unit.cc b/src/cpu/pred/bpred_unit.cc index 455773cce..a768cc19e 100644 --- a/src/cpu/pred/bpred_unit.cc +++ b/src/cpu/pred/bpred_unit.cc @@ -192,6 +192,7 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, ppBranches->notify(1); void *bp_history = NULL; + void *indirect_history = NULL; if (inst->isUncondCtrl()) { DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid); @@ -206,11 +207,15 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); } + if (useIndirect) { + iPred.updateDirectionInfo(tid, pred_taken, indirect_history); + } + 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, inst); + PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken, + bp_history, indirect_history, tid, inst); // Now lookup in the BTB or RAS. if (pred_taken) { @@ -280,8 +285,7 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, predict_record.wasIndirect = true; ++indirectLookups; //Consult indirect predictor on indirect control - if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history), - target, tid)) { + if (iPred.lookup(pc.instAddr(), target, tid)) { // Indirect predictor hit ++indirectHits; DPRINTF(Branch, "[tid:%i]: Instruction %s predicted " @@ -327,7 +331,6 @@ 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. @@ -337,6 +340,8 @@ BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) predHist[tid].back().inst, predHist[tid].back().target); + iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory); + predHist[tid].pop_back(); } } @@ -366,6 +371,7 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) // This call should delete the bpHistory. squash(tid, pred_hist.front().bpHistory); + iPred.deleteDirectionInfo(tid, pred_hist.front().indirectHistory); DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " "PC %s.\n", tid, pred_hist.front().seqNum, @@ -429,9 +435,6 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, 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 @@ -449,6 +452,9 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, pred_hist.front().bpHistory, true, pred_hist.front().inst, corrTarget.instAddr()); + iPred.changeDirectionPrediction(tid, pred_hist.front().indirectHistory, + actually_taken); + if (actually_taken) { if (hist_it->wasReturn && !hist_it->usedRAS) { DPRINTF(Branch, "[tid: %i] Incorrectly predicted" @@ -459,7 +465,7 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, } if (hist_it->wasIndirect) { ++indirectMispredicted; - iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid); + iPred.recordTarget(hist_it->seqNum, corrTarget, tid); } else { DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); diff --git a/src/cpu/pred/bpred_unit.hh b/src/cpu/pred/bpred_unit.hh index 9a75bbde0..0ad6867f3 100644 --- a/src/cpu/pred/bpred_unit.hh +++ b/src/cpu/pred/bpred_unit.hh @@ -193,8 +193,6 @@ class BPredUnit : public SimObject { BTB.update(instPC, target, 0); } - virtual unsigned getGHR(ThreadID tid, void* bp_history) const { return 0; } - void dump(); private: @@ -205,11 +203,13 @@ class BPredUnit : public SimObject */ PredictorHistory(const InstSeqNum &seq_num, Addr instPC, bool pred_taken, void *bp_history, - ThreadID _tid, const StaticInstPtr & inst) - : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0), - RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), - wasCall(0), wasReturn(0), wasIndirect(0), - target(MaxAddr), inst(inst) + void *indirect_history, ThreadID _tid, + const StaticInstPtr & inst) + : seqNum(seq_num), pc(instPC), bpHistory(bp_history), + indirectHistory(indirect_history), RASTarget(0), RASIndex(0), + tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), + wasCall(0), wasReturn(0), wasIndirect(0), target(MaxAddr), + inst(inst) {} bool operator==(const PredictorHistory &entry) const { @@ -228,6 +228,8 @@ class BPredUnit : public SimObject */ void *bpHistory; + void *indirectHistory; + /** The RAS target (only valid if a return). */ TheISA::PCState RASTarget; diff --git a/src/cpu/pred/indirect.cc b/src/cpu/pred/indirect.cc index a8934d55e..6690abbd6 100644 --- a/src/cpu/pred/indirect.cc +++ b/src/cpu/pred/indirect.cc @@ -53,11 +53,31 @@ IndirectPredictor::IndirectPredictor(bool hash_ghr, bool hash_targets, } } +void +IndirectPredictor::updateDirectionInfo(ThreadID tid, bool taken, + void* & indirect_history) +{ + // record the GHR as it was before this prediction + // It will be used to recover the history in case this prediction is + // wrong or belongs to bad path + indirect_history = new unsigned(threadInfo[tid].ghr); + + threadInfo[tid].ghr <<= taken; +} + +void +IndirectPredictor::changeDirectionPrediction(ThreadID tid, + void * indirect_history, bool actually_taken) +{ + unsigned * previousGhr = static_cast(indirect_history); + threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken; +} + bool -IndirectPredictor::lookup(Addr br_addr, unsigned ghr, TheISA::PCState& target, +IndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target, ThreadID tid) { - Addr set_index = getSetIndex(br_addr, ghr, tid); + Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid); Addr tag = getTag(br_addr); assert(set_index < numSets); @@ -85,11 +105,16 @@ IndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, } void -IndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid) +IndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid, + void * indirect_history) { DPRINTF(Indirect, "Committing seq:%d\n", seq_num); ThreadInfo &t_info = threadInfo[tid]; + // we do not need to recover the GHR, so delete the information + unsigned * previousGhr = static_cast(indirect_history); + delete previousGhr; + if (t_info.pathHist.empty()) return; if (t_info.headHistEntry < t_info.pathHist.size() && @@ -121,9 +146,17 @@ IndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); } +void +IndirectPredictor::deleteDirectionInfo(ThreadID tid, void * indirect_history) +{ + unsigned * previousGhr = static_cast(indirect_history); + threadInfo[tid].ghr = *previousGhr; + + delete previousGhr; +} void -IndirectPredictor::recordTarget(InstSeqNum seq_num, unsigned ghr, +IndirectPredictor::recordTarget(InstSeqNum seq_num, const TheISA::PCState& target, ThreadID tid) { ThreadInfo &t_info = threadInfo[tid]; @@ -132,7 +165,7 @@ IndirectPredictor::recordTarget(InstSeqNum seq_num, unsigned ghr, auto hist_entry = *(t_info.pathHist.rbegin()); // Temporarily pop it off the history so we can calculate the set t_info.pathHist.pop_back(); - Addr set_index = getSetIndex(hist_entry.pcAddr, ghr, tid); + Addr set_index = getSetIndex(hist_entry.pcAddr, t_info.ghr, tid); Addr tag = getTag(hist_entry.pcAddr); hist_entry.targetAddr = target.instAddr(); t_info.pathHist.push_back(hist_entry); diff --git a/src/cpu/pred/indirect.hh b/src/cpu/pred/indirect.hh index 89450530e..226a77848 100644 --- a/src/cpu/pred/indirect.hh +++ b/src/cpu/pred/indirect.hh @@ -44,14 +44,18 @@ class IndirectPredictor unsigned num_sets, unsigned num_ways, unsigned tag_bits, unsigned path_len, unsigned inst_shift, unsigned num_threads); - bool lookup(Addr br_addr, unsigned ghr, TheISA::PCState& br_target, - ThreadID tid); + bool lookup(Addr br_addr, TheISA::PCState& br_target, ThreadID tid); void recordIndirect(Addr br_addr, Addr tgt_addr, InstSeqNum seq_num, ThreadID tid); - void commit(InstSeqNum seq_num, ThreadID tid); + void commit(InstSeqNum seq_num, ThreadID tid, void * indirect_history); void squash(InstSeqNum seq_num, ThreadID tid); - void recordTarget(InstSeqNum seq_num, unsigned ghr, - const TheISA::PCState& target, ThreadID tid); + void recordTarget(InstSeqNum seq_num, const TheISA::PCState& target, + ThreadID tid); + void updateDirectionInfo(ThreadID tid, bool taken, + void* & indirect_history); + void changeDirectionPrediction(ThreadID tid, void * indirect_history, + bool actually_taken); + void deleteDirectionInfo(ThreadID tid, void * indirect_history); private: const bool hashGHR; @@ -85,10 +89,11 @@ class IndirectPredictor struct ThreadInfo { - ThreadInfo() : headHistEntry(0) { } + ThreadInfo() : headHistEntry(0), ghr(0) { } std::deque pathHist; unsigned headHistEntry; + unsigned ghr; }; std::vector threadInfo; diff --git a/src/cpu/pred/tage.cc b/src/cpu/pred/tage.cc index 50beb20ca..5702c04b3 100644 --- a/src/cpu/pred/tage.cc +++ b/src/cpu/pred/tage.cc @@ -51,16 +51,6 @@ TAGE::TAGE(const TAGEParams *params) : BPredUnit(params), tage(params->tage) { } -// Get GHR for hashing indirect predictor -// Build history backwards from pointer in -// bp_history. -unsigned -TAGE::getGHR(ThreadID tid, void *bp_history) const -{ - TageBranchInfo* bi = static_cast(bp_history); - return tage->getGHR(tid, bi->tageBranchInfo); -} - // PREDICTOR UPDATE void TAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, diff --git a/src/cpu/pred/tage.hh b/src/cpu/pred/tage.hh index b75051dd7..0c5cde295 100644 --- a/src/cpu/pred/tage.hh +++ b/src/cpu/pred/tage.hh @@ -89,7 +89,6 @@ class TAGE: public BPredUnit bool squashed, const StaticInstPtr & inst, Addr corrTarget) override; virtual void squash(ThreadID tid, void *bp_history) override; - unsigned getGHR(ThreadID tid, void *bp_history) const override; }; #endif // __CPU_PRED_TAGE diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc index 6ed208b1a..67beb09ef 100644 --- a/src/cpu/pred/tournament.cc +++ b/src/cpu/pred/tournament.cc @@ -366,12 +366,6 @@ TournamentBPParams::create() return new TournamentBP(this); } -unsigned -TournamentBP::getGHR(ThreadID tid, void *bp_history) const -{ - return static_cast(bp_history)->globalHistory; -} - #ifdef DEBUG int TournamentBP::BPHistory::newCount = 0; diff --git a/src/cpu/pred/tournament.hh b/src/cpu/pred/tournament.hh index e1e50816e..0eb69e12f 100644 --- a/src/cpu/pred/tournament.hh +++ b/src/cpu/pred/tournament.hh @@ -115,8 +115,6 @@ class TournamentBP : public BPredUnit */ void squash(ThreadID tid, void *bp_history); - unsigned getGHR(ThreadID tid, void *bp_history) const; - private: /** * Returns if the branch should be taken or not, given a counter -- 2.30.2