From 0473f8f65f8c70ddaf55e9f90b99631a9baacaa7 Mon Sep 17 00:00:00 2001 From: Jairo Balart Date: Sun, 6 Jan 2019 22:26:12 +0100 Subject: [PATCH] cpu: Make the indirect predictor into a SimObject Change-Id: Ice6549773def7d3e944fae450d4a079bc351e2ba Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/15319 Reviewed-by: Andreas Sandberg Maintainer: Andreas Sandberg Tested-by: kokoro --- src/cpu/pred/BranchPredictor.py | 32 +++-- src/cpu/pred/SConscript | 1 + src/cpu/pred/bpred_unit.cc | 49 +++---- src/cpu/pred/bpred_unit.hh | 5 +- src/cpu/pred/indirect.cc | 200 -------------------------- src/cpu/pred/indirect.hh | 87 ++++-------- src/cpu/pred/simple_indirect.cc | 243 ++++++++++++++++++++++++++++++++ src/cpu/pred/simple_indirect.hh | 104 ++++++++++++++ 8 files changed, 418 insertions(+), 303 deletions(-) create mode 100644 src/cpu/pred/simple_indirect.cc create mode 100644 src/cpu/pred/simple_indirect.hh diff --git a/src/cpu/pred/BranchPredictor.py b/src/cpu/pred/BranchPredictor.py index edcb58698..9c59574ff 100644 --- a/src/cpu/pred/BranchPredictor.py +++ b/src/cpu/pred/BranchPredictor.py @@ -31,19 +31,19 @@ from m5.SimObject import SimObject from m5.params import * from m5.proxy import * -class BranchPredictor(SimObject): - type = 'BranchPredictor' - cxx_class = 'BPredUnit' - cxx_header = "cpu/pred/bpred_unit.hh" +class IndirectPredictor(SimObject): + type = 'IndirectPredictor' + cxx_class = 'IndirectPredictor' + cxx_header = "cpu/pred/indirect.hh" abstract = True numThreads = Param.Unsigned(Parent.numThreads, "Number of threads") - BTBEntries = Param.Unsigned(4096, "Number of BTB entries") - BTBTagSize = Param.Unsigned(16, "Size of the BTB tags, in bits") - RASSize = Param.Unsigned(16, "RAS size") - instShiftAmt = Param.Unsigned(2, "Number of bits to shift instructions by") - useIndirect = Param.Bool(True, "Use indirect branch predictor") +class SimpleIndirectPredictor(IndirectPredictor): + type = 'SimpleIndirectPredictor' + cxx_class = 'SimpleIndirectPredictor' + cxx_header = "cpu/pred/simple_indirect.hh" + indirectHashGHR = Param.Bool(True, "Hash branch predictor GHR") indirectHashTargets = Param.Bool(True, "Hash path history targets") indirectSets = Param.Unsigned(256, "Cache sets for indirect predictor") @@ -52,8 +52,22 @@ class BranchPredictor(SimObject): indirectPathLength = Param.Unsigned(3, "Previous indirect targets to use for path history") indirectGHRBits = Param.Unsigned(13, "Indirect GHR number of bits") + instShiftAmt = Param.Unsigned(2, "Number of bits to shift instructions by") +class BranchPredictor(SimObject): + type = 'BranchPredictor' + cxx_class = 'BPredUnit' + cxx_header = "cpu/pred/bpred_unit.hh" + abstract = True + + numThreads = Param.Unsigned(Parent.numThreads, "Number of threads") + BTBEntries = Param.Unsigned(4096, "Number of BTB entries") + BTBTagSize = Param.Unsigned(16, "Size of the BTB tags, in bits") + RASSize = Param.Unsigned(16, "RAS size") + instShiftAmt = Param.Unsigned(2, "Number of bits to shift instructions by") + indirectBranchPred = Param.IndirectPredictor(SimpleIndirectPredictor(), + "Indirect branch predictor, set to NULL to disable indirect predictions") class LocalBP(BranchPredictor): type = 'LocalBP' diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript index e3a521983..736586197 100644 --- a/src/cpu/pred/SConscript +++ b/src/cpu/pred/SConscript @@ -39,6 +39,7 @@ DebugFlag('Indirect') Source('bpred_unit.cc') Source('2bit_local.cc') Source('btb.cc') +Source('simple_indirect.cc') Source('indirect.cc') Source('ras.cc') Source('tournament.cc') diff --git a/src/cpu/pred/bpred_unit.cc b/src/cpu/pred/bpred_unit.cc index 176b6a73f..2b549d3ab 100644 --- a/src/cpu/pred/bpred_unit.cc +++ b/src/cpu/pred/bpred_unit.cc @@ -62,16 +62,7 @@ BPredUnit::BPredUnit(const Params *params) 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, - params->indirectGHRBits), + iPred(params->indirectBranchPred), instShiftAmt(params->instShiftAmt) { for (auto& r : RAS) @@ -212,8 +203,8 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, } const bool orig_pred_taken = pred_taken; - if (useIndirect) { - iPred.genIndirectInfo(tid, indirect_history); + if (iPred) { + iPred->genIndirectInfo(tid, indirect_history); } DPRINTF(Branch, "[tid:%i] [sn:%llu] " @@ -260,7 +251,7 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, tid, seqNum, pc, pc, RAS[tid].topIdx()); } - if (inst->isDirectCtrl() || !useIndirect) { + if (inst->isDirectCtrl() || !iPred) { // Check BTB on direct branches if (BTB.valid(pc.instAddr(), tid)) { ++BTBHits; @@ -293,7 +284,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(), target, tid)) { + if (iPred->lookup(pc.instAddr(), target, tid)) { // Indirect predictor hit ++indirectHits; DPRINTF(Branch, @@ -317,7 +308,7 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, } TheISA::advancePC(target, inst); } - iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum, + iPred->recordIndirect(pc.instAddr(), target.instAddr(), seqNum, tid); } } @@ -331,13 +322,13 @@ BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, pc = target; - if (useIndirect) { + if (iPred) { // Update the indirect predictor with the direction prediction // Note that this happens after indirect lookup, so it does not use // the new information // Note also that we use orig_pred_taken instead of pred_taken in // as this is the actual outcome of the direction prediction - iPred.updateDirectionInfo(tid, orig_pred_taken); + iPred->updateDirectionInfo(tid, orig_pred_taken); } predHist[tid].push_front(predict_record); @@ -365,8 +356,8 @@ BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) predHist[tid].back().inst, predHist[tid].back().target); - if (useIndirect) { - iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory); + if (iPred) { + iPred->commit(done_sn, tid, predHist[tid].back().indirectHistory); } predHist[tid].pop_back(); @@ -378,8 +369,8 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) { History &pred_hist = predHist[tid]; - if (useIndirect) { - iPred.squash(squashed_sn, tid); + if (iPred) { + iPred->squash(squashed_sn, tid); } while (!pred_hist.empty() && @@ -402,8 +393,8 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) // This call should delete the bpHistory. squash(tid, pred_hist.front().bpHistory); - if (useIndirect) { - iPred.deleteIndirectInfo(tid, pred_hist.front().indirectHistory); + if (iPred) { + iPred->deleteIndirectInfo(tid, pred_hist.front().indirectHistory); } DPRINTF(Branch, "[tid:%i] [squash sn:%llu] " @@ -487,8 +478,8 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, pred_hist.front().bpHistory, true, pred_hist.front().inst, corrTarget.instAddr()); - if (useIndirect) { - iPred.changeDirectionPrediction(tid, + if (iPred) { + iPred->changeDirectionPrediction(tid, pred_hist.front().indirectHistory, actually_taken); } @@ -504,9 +495,11 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, } if (hist_it->wasIndirect) { ++indirectMispredicted; - iPred.recordTarget( - hist_it->seqNum, pred_hist.front().indirectHistory, - corrTarget, tid); + if (iPred) { + iPred->recordTarget( + hist_it->seqNum, pred_hist.front().indirectHistory, + corrTarget, tid); + } } else { DPRINTF(Branch,"[tid:%i] [squash sn:%llu] " "BTB Update called for [sn:%llu] " diff --git a/src/cpu/pred/bpred_unit.hh b/src/cpu/pred/bpred_unit.hh index 0ad6867f3..fb2d0b1ee 100644 --- a/src/cpu/pred/bpred_unit.hh +++ b/src/cpu/pred/bpred_unit.hh @@ -285,11 +285,8 @@ class BPredUnit : public SimObject /** The per-thread return address stack. */ std::vector RAS; - /** Option to disable indirect predictor. */ - const bool useIndirect; - /** The indirect target predictor. */ - IndirectPredictor iPred; + IndirectPredictor * iPred; /** Stat for number of BP lookups. */ Stats::Scalar lookups; diff --git a/src/cpu/pred/indirect.cc b/src/cpu/pred/indirect.cc index 2f88566b4..2f0aca1af 100644 --- a/src/cpu/pred/indirect.cc +++ b/src/cpu/pred/indirect.cc @@ -29,203 +29,3 @@ */ #include "cpu/pred/indirect.hh" - -#include "base/intmath.hh" -#include "debug/Indirect.hh" - -IndirectPredictor::IndirectPredictor(bool hash_ghr, bool hash_targets, - unsigned num_sets, unsigned num_ways, - unsigned tag_bits, unsigned path_len, unsigned inst_shift, - unsigned num_threads, unsigned ghr_size) - : hashGHR(hash_ghr), hashTargets(hash_targets), - numSets(num_sets), numWays(num_ways), tagBits(tag_bits), - pathLength(path_len), instShift(inst_shift), - ghrNumBits(ghr_size), ghrMask((1 << ghr_size)-1) -{ - if (!isPowerOf2(numSets)) { - panic("Indirect predictor requires power of 2 number of sets"); - } - - threadInfo.resize(num_threads); - - targetCache.resize(numSets); - for (unsigned i = 0; i < numSets; i++) { - targetCache[i].resize(numWays); - } - - fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big"); -} - -void -IndirectPredictor::genIndirectInfo(ThreadID tid, 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); -} - -void -IndirectPredictor::updateDirectionInfo( - ThreadID tid, bool actually_taken) -{ - threadInfo[tid].ghr <<= 1; - threadInfo[tid].ghr |= actually_taken; - threadInfo[tid].ghr &= ghrMask; -} - -void -IndirectPredictor::changeDirectionPrediction(ThreadID tid, - void * indirect_history, bool actually_taken) -{ - unsigned * previousGhr = static_cast(indirect_history); - threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken; - threadInfo[tid].ghr &= ghrMask; -} - -bool -IndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target, - ThreadID tid) -{ - Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid); - Addr tag = getTag(br_addr); - - assert(set_index < numSets); - - DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index); - const auto &iset = targetCache[set_index]; - for (auto way = iset.begin(); way != iset.end(); ++way) { - if (way->tag == tag) { - DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target); - target = way->target; - return true; - } - } - DPRINTF(Indirect, "Miss %x\n", br_addr); - return false; -} - -void -IndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, - InstSeqNum seq_num, ThreadID tid) -{ - DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num); - HistoryEntry entry(br_addr, tgt_addr, seq_num); - threadInfo[tid].pathHist.push_back(entry); -} - -void -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() && - t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) { - if (t_info.headHistEntry >= pathLength) { - t_info.pathHist.pop_front(); - } else { - ++t_info.headHistEntry; - } - } -} - -void -IndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) -{ - DPRINTF(Indirect, "Squashing seq:%d\n", seq_num); - ThreadInfo &t_info = threadInfo[tid]; - auto squash_itr = t_info.pathHist.begin(); - while (squash_itr != t_info.pathHist.end()) { - if (squash_itr->seqNum > seq_num) { - break; - } - ++squash_itr; - } - if (squash_itr != t_info.pathHist.end()) { - DPRINTF(Indirect, "Squashing series starting with sn:%d\n", - squash_itr->seqNum); - } - t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); -} - -void -IndirectPredictor::deleteIndirectInfo(ThreadID tid, void * indirect_history) -{ - unsigned * previousGhr = static_cast(indirect_history); - threadInfo[tid].ghr = *previousGhr; - - delete previousGhr; -} - -void -IndirectPredictor::recordTarget( - InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target, - ThreadID tid) -{ - ThreadInfo &t_info = threadInfo[tid]; - - unsigned * ghr = static_cast(indirect_history); - - // Should have just squashed so this branch should be the oldest - 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 tag = getTag(hist_entry.pcAddr); - hist_entry.targetAddr = target.instAddr(); - t_info.pathHist.push_back(hist_entry); - - assert(set_index < numSets); - - auto &iset = targetCache[set_index]; - for (auto way = iset.begin(); way != iset.end(); ++way) { - if (way->tag == tag) { - DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:" - "%s)\n", seq_num, hist_entry.pcAddr, set_index, target); - way->target = target; - return; - } - } - - DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n", - seq_num, hist_entry.pcAddr, set_index, target); - // Did not find entry, random replacement - auto &way = iset[rand() % numWays]; - way.tag = tag; - way.target = target; -} - - -inline Addr -IndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid) -{ - ThreadInfo &t_info = threadInfo[tid]; - - Addr hash = br_addr >> instShift; - if (hashGHR) { - hash ^= ghr; - } - if (hashTargets) { - unsigned hash_shift = floorLog2(numSets) / pathLength; - for (int i = t_info.pathHist.size()-1, p = 0; - i >= 0 && p < pathLength; i--, p++) { - hash ^= (t_info.pathHist[i].targetAddr >> - (instShift + p*hash_shift)); - } - } - return hash & (numSets-1); -} - -inline Addr -IndirectPredictor::getTag(Addr br_addr) -{ - return (br_addr >> instShift) & ((0x1< +#ifndef __CPU_PRED_INDIRECT_BASE_HH__ +#define __CPU_PRED_INDIRECT_BASE_HH__ #include "arch/isa_traits.hh" #include "config/the_isa.hh" #include "cpu/inst_seq.hh" +#include "params/IndirectPredictor.hh" +#include "sim/sim_object.hh" -class IndirectPredictor +class IndirectPredictor : public SimObject { public: - IndirectPredictor(bool hash_ghr, bool hash_targets, - unsigned num_sets, unsigned num_ways, - unsigned tag_bits, unsigned path_len, - unsigned inst_shift, unsigned num_threads, - unsigned ghr_size); - 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 * indirect_history); - void squash(InstSeqNum seq_num, ThreadID tid); - void recordTarget(InstSeqNum seq_num, void * indirect_history, - const TheISA::PCState& target, ThreadID tid); - void genIndirectInfo(ThreadID tid, void* & indirect_history); - void updateDirectionInfo(ThreadID tid, bool actually_taken); - void deleteIndirectInfo(ThreadID tid, void * indirect_history); - void changeDirectionPrediction(ThreadID tid, void * indirect_history, - bool actually_taken); - - private: - const bool hashGHR; - const bool hashTargets; - const unsigned numSets; - const unsigned numWays; - const unsigned tagBits; - const unsigned pathLength; - const unsigned instShift; - const unsigned ghrNumBits; - const unsigned ghrMask; - - struct IPredEntry - { - IPredEntry() : tag(0), target(0) { } - Addr tag; - TheISA::PCState target; - }; - std::vector > targetCache; + typedef IndirectPredictorParams Params; - Addr getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid); - Addr getTag(Addr br_addr); - - struct HistoryEntry + IndirectPredictor(const Params *params) + : SimObject(params) { - HistoryEntry(Addr br_addr, Addr tgt_addr, InstSeqNum seq_num) - : pcAddr(br_addr), targetAddr(tgt_addr), seqNum(seq_num) { } - Addr pcAddr; - Addr targetAddr; - InstSeqNum seqNum; - }; - - - struct ThreadInfo { - ThreadInfo() : headHistEntry(0), ghr(0) { } - - std::deque pathHist; - unsigned headHistEntry; - unsigned ghr; - }; + } - std::vector threadInfo; + virtual bool lookup(Addr br_addr, TheISA::PCState& br_target, + ThreadID tid) = 0; + virtual void recordIndirect(Addr br_addr, Addr tgt_addr, + InstSeqNum seq_num, ThreadID tid) = 0; + virtual void commit(InstSeqNum seq_num, ThreadID tid, + void * indirect_history) = 0; + virtual void squash(InstSeqNum seq_num, ThreadID tid) = 0; + virtual void recordTarget(InstSeqNum seq_num, void * indirect_history, + const TheISA::PCState& target, ThreadID tid) = 0; + virtual void genIndirectInfo(ThreadID tid, void* & indirect_history) = 0; + virtual void updateDirectionInfo(ThreadID tid, bool actually_taken) = 0; + virtual void deleteIndirectInfo(ThreadID tid, void * indirect_history) = 0; + virtual void changeDirectionPrediction(ThreadID tid, + void * indirect_history, + bool actually_taken) = 0; }; -#endif // __CPU_PRED_INDIRECT_HH__ +#endif // __CPU_PRED_INDIRECT_BASE_HH__ diff --git a/src/cpu/pred/simple_indirect.cc b/src/cpu/pred/simple_indirect.cc new file mode 100644 index 000000000..b820c0ac4 --- /dev/null +++ b/src/cpu/pred/simple_indirect.cc @@ -0,0 +1,243 @@ +/* + * Copyright (c) 2014 ARM Limited + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Mitch Hayenga + */ + +#include "cpu/pred/simple_indirect.hh" + +#include "base/intmath.hh" +#include "debug/Indirect.hh" + +SimpleIndirectPredictor::SimpleIndirectPredictor( + const SimpleIndirectPredictorParams * params) + : IndirectPredictor(params), + hashGHR(params->indirectHashGHR), + hashTargets(params->indirectHashTargets), + numSets(params->indirectSets), + numWays(params->indirectWays), + tagBits(params->indirectTagSize), + pathLength(params->indirectPathLength), + instShift(params->instShiftAmt), + ghrNumBits(params->indirectGHRBits), + ghrMask((1 << params->indirectGHRBits)-1) +{ + if (!isPowerOf2(numSets)) { + panic("Indirect predictor requires power of 2 number of sets"); + } + + threadInfo.resize(params->numThreads); + + targetCache.resize(numSets); + for (unsigned i = 0; i < numSets; i++) { + targetCache[i].resize(numWays); + } + + fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big"); +} + +void +SimpleIndirectPredictor::genIndirectInfo(ThreadID tid, + 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); +} + +void +SimpleIndirectPredictor::updateDirectionInfo( + ThreadID tid, bool actually_taken) +{ + threadInfo[tid].ghr <<= 1; + threadInfo[tid].ghr |= actually_taken; + threadInfo[tid].ghr &= ghrMask; +} + +void +SimpleIndirectPredictor::changeDirectionPrediction(ThreadID tid, + void * indirect_history, bool actually_taken) +{ + unsigned * previousGhr = static_cast(indirect_history); + threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken; + threadInfo[tid].ghr &= ghrMask; +} + +bool +SimpleIndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target, + ThreadID tid) +{ + Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid); + Addr tag = getTag(br_addr); + + assert(set_index < numSets); + + DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index); + const auto &iset = targetCache[set_index]; + for (auto way = iset.begin(); way != iset.end(); ++way) { + if (way->tag == tag) { + DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target); + target = way->target; + return true; + } + } + DPRINTF(Indirect, "Miss %x\n", br_addr); + return false; +} + +void +SimpleIndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, + InstSeqNum seq_num, ThreadID tid) +{ + DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num); + HistoryEntry entry(br_addr, tgt_addr, seq_num); + threadInfo[tid].pathHist.push_back(entry); +} + +void +SimpleIndirectPredictor::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() && + t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) { + if (t_info.headHistEntry >= pathLength) { + t_info.pathHist.pop_front(); + } else { + ++t_info.headHistEntry; + } + } +} + +void +SimpleIndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) +{ + DPRINTF(Indirect, "Squashing seq:%d\n", seq_num); + ThreadInfo &t_info = threadInfo[tid]; + auto squash_itr = t_info.pathHist.begin(); + while (squash_itr != t_info.pathHist.end()) { + if (squash_itr->seqNum > seq_num) { + break; + } + ++squash_itr; + } + if (squash_itr != t_info.pathHist.end()) { + DPRINTF(Indirect, "Squashing series starting with sn:%d\n", + squash_itr->seqNum); + } + t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); +} + +void +SimpleIndirectPredictor::deleteIndirectInfo(ThreadID tid, + void * indirect_history) +{ + unsigned * previousGhr = static_cast(indirect_history); + threadInfo[tid].ghr = *previousGhr; + + delete previousGhr; +} + +void +SimpleIndirectPredictor::recordTarget( + InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target, + ThreadID tid) +{ + ThreadInfo &t_info = threadInfo[tid]; + + unsigned * ghr = static_cast(indirect_history); + + // Should have just squashed so this branch should be the oldest + 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 tag = getTag(hist_entry.pcAddr); + hist_entry.targetAddr = target.instAddr(); + t_info.pathHist.push_back(hist_entry); + + assert(set_index < numSets); + + auto &iset = targetCache[set_index]; + for (auto way = iset.begin(); way != iset.end(); ++way) { + if (way->tag == tag) { + DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:" + "%s)\n", seq_num, hist_entry.pcAddr, set_index, target); + way->target = target; + return; + } + } + + DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n", + seq_num, hist_entry.pcAddr, set_index, target); + // Did not find entry, random replacement + auto &way = iset[rand() % numWays]; + way.tag = tag; + way.target = target; +} + + +inline Addr +SimpleIndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid) +{ + ThreadInfo &t_info = threadInfo[tid]; + + Addr hash = br_addr >> instShift; + if (hashGHR) { + hash ^= ghr; + } + if (hashTargets) { + unsigned hash_shift = floorLog2(numSets) / pathLength; + for (int i = t_info.pathHist.size()-1, p = 0; + i >= 0 && p < pathLength; i--, p++) { + hash ^= (t_info.pathHist[i].targetAddr >> + (instShift + p*hash_shift)); + } + } + return hash & (numSets-1); +} + +inline Addr +SimpleIndirectPredictor::getTag(Addr br_addr) +{ + return (br_addr >> instShift) & ((0x1< + +#include "arch/isa_traits.hh" +#include "config/the_isa.hh" +#include "cpu/inst_seq.hh" +#include "cpu/pred/indirect.hh" +#include "params/SimpleIndirectPredictor.hh" + +class SimpleIndirectPredictor : public IndirectPredictor +{ + public: + SimpleIndirectPredictor(const SimpleIndirectPredictorParams * params); + + 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 * indirect_history); + void squash(InstSeqNum seq_num, ThreadID tid); + void recordTarget(InstSeqNum seq_num, void * indirect_history, + const TheISA::PCState& target, ThreadID tid); + void genIndirectInfo(ThreadID tid, void* & indirect_history); + void updateDirectionInfo(ThreadID tid, bool actually_taken); + void deleteIndirectInfo(ThreadID tid, void * indirect_history); + void changeDirectionPrediction(ThreadID tid, void * indirect_history, + bool actually_taken); + + private: + const bool hashGHR; + const bool hashTargets; + const unsigned numSets; + const unsigned numWays; + const unsigned tagBits; + const unsigned pathLength; + const unsigned instShift; + const unsigned ghrNumBits; + const unsigned ghrMask; + + struct IPredEntry + { + IPredEntry() : tag(0), target(0) { } + Addr tag; + TheISA::PCState target; + }; + + std::vector > targetCache; + + Addr getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid); + Addr getTag(Addr br_addr); + + struct HistoryEntry + { + HistoryEntry(Addr br_addr, Addr tgt_addr, InstSeqNum seq_num) + : pcAddr(br_addr), targetAddr(tgt_addr), seqNum(seq_num) { } + Addr pcAddr; + Addr targetAddr; + InstSeqNum seqNum; + }; + + + struct ThreadInfo { + ThreadInfo() : headHistEntry(0), ghr(0) { } + + std::deque pathHist; + unsigned headHistEntry; + unsigned ghr; + }; + + std::vector threadInfo; +}; + +#endif // __CPU_PRED_INDIRECT_HH__ -- 2.30.2