diff options
Diffstat (limited to 'src/cpu/pred')
| -rw-r--r-- | src/cpu/pred/2bit_local.cc | 47 | ||||
| -rw-r--r-- | src/cpu/pred/2bit_local.hh | 26 | ||||
| -rw-r--r-- | src/cpu/pred/BranchPredictor.py | 54 | ||||
| -rw-r--r-- | src/cpu/pred/SConscript | 4 | ||||
| -rw-r--r-- | src/cpu/pred/bpred_unit.cc | 49 | ||||
| -rw-r--r-- | src/cpu/pred/bpred_unit.hh | 286 | ||||
| -rw-r--r-- | src/cpu/pred/bpred_unit_impl.hh | 536 | ||||
| -rw-r--r-- | src/cpu/pred/btb.hh | 6 | ||||
| -rw-r--r-- | src/cpu/pred/ras.hh | 6 | ||||
| -rw-r--r-- | src/cpu/pred/sat_counter.hh | 117 | ||||
| -rw-r--r-- | src/cpu/pred/tournament.cc | 37 | ||||
| -rw-r--r-- | src/cpu/pred/tournament.hh | 31 |
12 files changed, 1118 insertions, 81 deletions
diff --git a/src/cpu/pred/2bit_local.cc b/src/cpu/pred/2bit_local.cc index 4d18c419b..0fd0a10d3 100644 --- a/src/cpu/pred/2bit_local.cc +++ b/src/cpu/pred/2bit_local.cc @@ -34,12 +34,11 @@ #include "cpu/pred/2bit_local.hh" #include "debug/Fetch.hh" -LocalBP::LocalBP(unsigned _localPredictorSize, - unsigned _localCtrBits, - unsigned _instShiftAmt) - : localPredictorSize(_localPredictorSize), - localCtrBits(_localCtrBits), - instShiftAmt(_instShiftAmt) +LocalBP::LocalBP(const Params *params) + : BPredUnit(params), + localPredictorSize(params->localPredictorSize), + localCtrBits(params->localCtrBits), + instShiftAmt(params->instShiftAmt) { if (!isPowerOf2(localPredictorSize)) { fatal("Invalid local predictor size!\n"); @@ -54,20 +53,20 @@ LocalBP::LocalBP(unsigned _localPredictorSize, // Setup the index mask. indexMask = localPredictorSets - 1; - DPRINTF(Fetch, "Branch predictor: index mask: %#x\n", indexMask); + DPRINTF(Fetch, "index mask: %#x\n", indexMask); // Setup the array of counters for the local predictor. localCtrs.resize(localPredictorSets); for (unsigned i = 0; i < localPredictorSets; ++i) - localCtrs[i].setBits(_localCtrBits); + localCtrs[i].setBits(localCtrBits); - DPRINTF(Fetch, "Branch predictor: local predictor size: %i\n", + DPRINTF(Fetch, "local predictor size: %i\n", localPredictorSize); - DPRINTF(Fetch, "Branch predictor: local counter bits: %i\n", localCtrBits); + DPRINTF(Fetch, "local counter bits: %i\n", localCtrBits); - DPRINTF(Fetch, "Branch predictor: instruction shift amount: %i\n", + DPRINTF(Fetch, "instruction shift amount: %i\n", instShiftAmt); } @@ -80,7 +79,7 @@ LocalBP::reset() } void -LocalBP::BTBUpdate(Addr &branch_addr, void * &bp_history) +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. @@ -88,18 +87,18 @@ LocalBP::BTBUpdate(Addr &branch_addr, void * &bp_history) bool -LocalBP::lookup(Addr &branch_addr, void * &bp_history) +LocalBP::lookup(Addr branch_addr, void * &bp_history) { bool taken; uint8_t counter_val; unsigned local_predictor_idx = getLocalIndex(branch_addr); - DPRINTF(Fetch, "Branch predictor: Looking up index %#x\n", + DPRINTF(Fetch, "Looking up index %#x\n", local_predictor_idx); counter_val = localCtrs[local_predictor_idx].read(); - DPRINTF(Fetch, "Branch predictor: prediction is %i.\n", + DPRINTF(Fetch, "prediction is %i.\n", (int)counter_val); taken = getPrediction(counter_val); @@ -107,10 +106,10 @@ LocalBP::lookup(Addr &branch_addr, void * &bp_history) #if 0 // Speculative update. if (taken) { - DPRINTF(Fetch, "Branch predictor: Branch updated as taken.\n"); + DPRINTF(Fetch, "Branch updated as taken.\n"); localCtrs[local_predictor_idx].increment(); } else { - DPRINTF(Fetch, "Branch predictor: Branch updated as not taken.\n"); + DPRINTF(Fetch, "Branch updated as not taken.\n"); localCtrs[local_predictor_idx].decrement(); } #endif @@ -119,7 +118,7 @@ LocalBP::lookup(Addr &branch_addr, void * &bp_history) } void -LocalBP::update(Addr &branch_addr, bool taken, void *bp_history) +LocalBP::update(Addr branch_addr, bool taken, void *bp_history, bool squashed) { assert(bp_history == NULL); unsigned local_predictor_idx; @@ -127,14 +126,13 @@ LocalBP::update(Addr &branch_addr, bool taken, void *bp_history) // Update the local predictor. local_predictor_idx = getLocalIndex(branch_addr); - DPRINTF(Fetch, "Branch predictor: Looking up index %#x\n", - local_predictor_idx); + DPRINTF(Fetch, "Looking up index %#x\n", local_predictor_idx); if (taken) { - DPRINTF(Fetch, "Branch predictor: Branch updated as taken.\n"); + DPRINTF(Fetch, "Branch updated as taken.\n"); localCtrs[local_predictor_idx].increment(); } else { - DPRINTF(Fetch, "Branch predictor: Branch updated as not taken.\n"); + DPRINTF(Fetch, "Branch updated as not taken.\n"); localCtrs[local_predictor_idx].decrement(); } } @@ -153,3 +151,8 @@ LocalBP::getLocalIndex(Addr &branch_addr) { return (branch_addr >> instShiftAmt) & indexMask; } + +void +LocalBP::uncondBranch(void *&bp_history) +{ +} diff --git a/src/cpu/pred/2bit_local.hh b/src/cpu/pred/2bit_local.hh index 01a0b64db..23683cc67 100644 --- a/src/cpu/pred/2bit_local.hh +++ b/src/cpu/pred/2bit_local.hh @@ -38,15 +38,17 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Authors: Kevin Lim + * Timothy M. Jones */ -#ifndef __CPU_O3_2BIT_LOCAL_PRED_HH__ -#define __CPU_O3_2BIT_LOCAL_PRED_HH__ +#ifndef __CPU_PRED_2BIT_LOCAL_PRED_HH__ +#define __CPU_PRED_2BIT_LOCAL_PRED_HH__ #include <vector> #include "base/types.hh" -#include "cpu/o3/sat_counter.hh" +#include "cpu/pred/bpred_unit.hh" +#include "cpu/pred/sat_counter.hh" /** * Implements a local predictor that uses the PC to index into a table of @@ -55,17 +57,15 @@ * predictor state that needs to be recorded or updated; the update can be * determined solely by the branch being taken or not taken. */ -class LocalBP +class LocalBP : public BPredUnit { public: /** * Default branch predictor constructor. - * @param localPredictorSize Size of the local predictor. - * @param localCtrBits Number of bits per counter. - * @param instShiftAmt Offset amount for instructions to ignore alignment. */ - LocalBP(unsigned localPredictorSize, unsigned localCtrBits, - unsigned instShiftAmt); + LocalBP(const Params *params); + + virtual void uncondBranch(void * &bp_history); /** * Looks up the given address in the branch predictor and returns @@ -74,7 +74,7 @@ class LocalBP * @param bp_history Pointer to any bp history state. * @return Whether or not the branch is taken. */ - bool lookup(Addr &branch_addr, void * &bp_history); + bool lookup(Addr branch_addr, void * &bp_history); /** * Updates the branch predictor to Not Taken if a BTB entry is @@ -83,14 +83,14 @@ class LocalBP * @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); + 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. */ - void update(Addr &branch_addr, bool taken, void *bp_history); + void update(Addr branch_addr, bool taken, void *bp_history, bool squashed); void squash(void *bp_history) { assert(bp_history == NULL); } @@ -128,4 +128,4 @@ class LocalBP unsigned indexMask; }; -#endif // __CPU_O3_2BIT_LOCAL_PRED_HH__ +#endif // __CPU_PRED_2BIT_LOCAL_PRED_HH__ diff --git a/src/cpu/pred/BranchPredictor.py b/src/cpu/pred/BranchPredictor.py new file mode 100644 index 000000000..21001b360 --- /dev/null +++ b/src/cpu/pred/BranchPredictor.py @@ -0,0 +1,54 @@ +# Copyright (c) 2012 Mark D. Hill and David A. Wood +# 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: Nilay Vaish + +from m5.SimObject import SimObject +from m5.params import * + +class BranchPredictor(SimObject): + type = 'BranchPredictor' + cxx_class = 'BPredUnit' + cxx_header = "cpu/pred/bpred_unit.hh" + + numThreads = Param.Unsigned(1, "Number of threads") + predType = Param.String("tournament", + "Branch predictor type ('local', 'tournament')") + localPredictorSize = Param.Unsigned(2048, "Size of local predictor") + localCtrBits = Param.Unsigned(2, "Bits per counter") + localHistoryTableSize = Param.Unsigned(2048, "Size of local history table") + localHistoryBits = Param.Unsigned(11, "Bits for the local history") + globalPredictorSize = Param.Unsigned(8192, "Size of global predictor") + globalCtrBits = Param.Unsigned(2, "Bits per counter") + globalHistoryBits = Param.Unsigned(13, "Bits of history") + choicePredictorSize = Param.Unsigned(8192, "Size of choice predictor") + choiceCtrBits = Param.Unsigned(2, "Bits of choice counters") + + 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") diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript index 742c132c7..d30a7a04d 100644 --- a/src/cpu/pred/SConscript +++ b/src/cpu/pred/SConscript @@ -31,8 +31,12 @@ Import('*') if 'InOrderCPU' in env['CPU_MODELS'] or 'O3CPU' in env['CPU_MODELS']: + SimObject('BranchPredictor.py') + + Source('bpred_unit.cc') Source('2bit_local.cc') Source('btb.cc') Source('ras.cc') Source('tournament.cc') DebugFlag('FreeList') + DebugFlag('Branch') diff --git a/src/cpu/pred/bpred_unit.cc b/src/cpu/pred/bpred_unit.cc new file mode 100644 index 000000000..52a77119c --- /dev/null +++ b/src/cpu/pred/bpred_unit.cc @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2004-2006 The Regents of The University of Michigan + * Copyright (c) 2010 The University of Edinburgh + * Copyright (c) 2012 Mark D. Hill and David A. Wood + * 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: Kevin Lim + * Timothy M. Jones + */ + +#include "cpu/pred/2bit_local.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 { + fatal("Invalid BP selected!"); + } +} diff --git a/src/cpu/pred/bpred_unit.hh b/src/cpu/pred/bpred_unit.hh new file mode 100644 index 000000000..95f9a3573 --- /dev/null +++ b/src/cpu/pred/bpred_unit.hh @@ -0,0 +1,286 @@ +/* + * Copyright (c) 2011-2012 ARM Limited + * Copyright (c) 2010 The University of Edinburgh + * 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 + * 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: Kevin Lim + * Korey Sewell + * Timothy M. Jones + * Nilay Vaish + */ + +#ifndef __CPU_PRED_BPRED_UNIT_HH__ +#define __CPU_PRED_BPRED_UNIT_HH__ + +#include <list> + +#include "base/statistics.hh" +#include "base/types.hh" +#include "cpu/pred/btb.hh" +#include "cpu/pred/ras.hh" +#include "cpu/inst_seq.hh" +#include "cpu/static_inst.hh" +#include "params/BranchPredictor.hh" +#include "sim/sim_object.hh" + +/** + * Basically a wrapper class to hold both the branch predictor + * and the BTB. + */ +class BPredUnit : public SimObject +{ + public: + typedef BranchPredictorParams Params; + /** + * @param params The params object, that has the size of the BP and BTB. + */ + BPredUnit(const Params *p); + + /** + * Registers statistics. + */ + void regStats(); + + /** Perform sanity checks after a drain. */ + void drainSanityCheck() const; + + /** + * Predicts whether or not the instruction is a taken branch, and the + * target of the branch if it is taken. + * @param inst The branch instruction. + * @param PC The predicted PC is passed back through this parameter. + * @param tid The thread id. + * @return Returns if the branch is taken or not. + */ + bool predict(StaticInstPtr &inst, const InstSeqNum &seqNum, + TheISA::PCState &pc, ThreadID tid); + bool predictInOrder(StaticInstPtr &inst, const InstSeqNum &seqNum, + int asid, TheISA::PCState &instPC, TheISA::PCState &predPC, + ThreadID tid); + + // @todo: Rename this function. + virtual void uncondBranch(void * &bp_history) = 0; + + /** + * Tells the branch predictor to commit any updates until the given + * sequence number. + * @param done_sn The sequence number to commit any older updates up until. + * @param tid The thread id. + */ + void update(const InstSeqNum &done_sn, ThreadID tid); + + /** + * Squashes all outstanding updates until a given sequence number. + * @param squashed_sn The sequence number to squash any younger updates up + * until. + * @param tid The thread id. + */ + void squash(const InstSeqNum &squashed_sn, ThreadID tid); + + /** + * Squashes all outstanding updates until a given sequence number, and + * corrects that sn's update with the proper address and taken/not taken. + * @param squashed_sn The sequence number to squash any younger updates up + * until. + * @param corr_target The correct branch target. + * @param actually_taken The correct branch direction. + * @param tid The thread id. + */ + void squash(const InstSeqNum &squashed_sn, + const TheISA::PCState &corr_target, + bool actually_taken, ThreadID tid); + + /** + * @param bp_history Pointer to the history object. The predictor + * will need to update any state and delete the object. + */ + virtual void squash(void *bp_history) = 0; + + /** + * Looks up a given PC in the BP to see if it is taken or not taken. + * @param inst_PC The PC to look up. + * @param bp_history Pointer that will be set to an object that + * has the branch predictor state associated with the lookup. + * @return Whether the branch is taken or not taken. + */ + virtual bool lookup(Addr instPC, void * &bp_history) = 0; + + /** + * 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. + */ + virtual void btbUpdate(Addr instPC, void * &bp_history) = 0; + + /** + * Looks up a given PC in the BTB to see if a matching entry exists. + * @param inst_PC The PC to look up. + * @return Whether the BTB contains the given PC. + */ + bool BTBValid(Addr instPC) + { return BTB.valid(instPC, 0); } + + /** + * Looks up a given PC in the BTB to get the predicted target. + * @param inst_PC The PC to look up. + * @return The address of the target of the branch. + */ + TheISA::PCState BTBLookup(Addr instPC) + { return BTB.lookup(instPC, 0); } + + /** + * Updates the BP with taken/not taken information. + * @param inst_PC The branch's PC that will be updated. + * @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. + */ + virtual void update(Addr instPC, bool taken, void *bp_history, + bool squashed) = 0; + + /** + * Updates the BTB with the target of a branch. + * @param inst_PC The branch's PC that will be updated. + * @param target_PC The branch's target that will be added to the BTB. + */ + void BTBUpdate(Addr instPC, const TheISA::PCState &target) + { BTB.update(instPC, target, 0); } + + void dump(); + + private: + struct PredictorHistory { + /** + * Makes a predictor history struct that contains any + * information needed to update the predictor, BTB, and RAS. + */ + PredictorHistory(const InstSeqNum &seq_num, Addr instPC, + bool pred_taken, void *bp_history, + ThreadID _tid) + : 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) + {} + + bool operator==(const PredictorHistory &entry) const { + return this->seqNum == entry.seqNum; + } + + /** The sequence number for the predictor history entry. */ + InstSeqNum seqNum; + + /** The PC associated with the sequence number. */ + Addr pc; + + /** Pointer to the history object passed back from the branch + * predictor. It is used to update or restore state of the + * branch predictor. + */ + void *bpHistory; + + /** The RAS target (only valid if a return). */ + TheISA::PCState RASTarget; + + /** The RAS index of the instruction (only valid if a call). */ + unsigned RASIndex; + + /** The thread id. */ + ThreadID tid; + + /** Whether or not it was predicted taken. */ + bool predTaken; + + /** Whether or not the RAS was used. */ + bool usedRAS; + + /* Wether or not the RAS was pushed */ + bool pushedRAS; + + /** Whether or not the instruction was a call. */ + bool wasCall; + + /** Whether or not the instruction was a return. */ + bool wasReturn; + }; + + typedef std::list<PredictorHistory> History; + typedef History::iterator HistoryIt; + + /** Number of the threads for which the branch history is maintained. */ + uint32_t numThreads; + + /** + * The per-thread predictor history. This is used to update the predictor + * as instructions are committed, or restore it to the proper state after + * a squash. + */ + History *predHist; + + /** The BTB. */ + DefaultBTB BTB; + + /** The per-thread return address stack. */ + ReturnAddrStack *RAS; + + /** Stat for number of BP lookups. */ + Stats::Scalar lookups; + /** Stat for number of conditional branches predicted. */ + Stats::Scalar condPredicted; + /** Stat for number of conditional branches predicted incorrectly. */ + Stats::Scalar condIncorrect; + /** Stat for number of BTB lookups. */ + Stats::Scalar BTBLookups; + /** Stat for number of BTB hits. */ + Stats::Scalar BTBHits; + /** Stat for number of times the BTB is correct. */ + Stats::Scalar BTBCorrect; + /** Stat for percent times an entry in BTB found. */ + Stats::Formula BTBHitPct; + /** Stat for number of times the RAS is used to get a target. */ + Stats::Scalar usedRAS; + /** Stat for number of times the RAS is incorrect. */ + Stats::Scalar RASIncorrect; +}; + +#endif // __CPU_PRED_BPRED_UNIT_HH__ diff --git a/src/cpu/pred/bpred_unit_impl.hh b/src/cpu/pred/bpred_unit_impl.hh new file mode 100644 index 000000000..c3d1b7e9b --- /dev/null +++ b/src/cpu/pred/bpred_unit_impl.hh @@ -0,0 +1,536 @@ +/* + * Copyright (c) 2011-2012 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 + * 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: Kevin Lim + */ + +#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 "cpu/pred/bpred_unit.hh" +#include "debug/Branch.hh" + +BPredUnit::BPredUnit(const Params *params) + : SimObject(params), + BTB(params->BTBEntries, + params->BTBTagSize, + params->instShiftAmt) +{ + numThreads = params->numThreads; + + predHist = new History[numThreads]; + + RAS = new ReturnAddrStack[numThreads]; + for (int i=0; i < numThreads; i++) + RAS[i].init(params->RASSize); +} + +void +BPredUnit::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.") + ; +} + +void +BPredUnit::drainSanityCheck() const +{ + // We shouldn't have any outstanding requests when we resume from + // a drained system. + for (int i = 0; i < numThreads; ++i) + assert(predHist[i].empty()); +} + +bool +BPredUnit::predict(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; + + 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(bp_history); + } else { + ++condPredicted; + pred_taken = lookup(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 (BTB.valid(pc.instAddr(), tid)) { + ++BTBHits; + + // If it's not a return, use the BTB to get the 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(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 { + 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; +} + +bool +BPredUnit::predictInOrder(StaticInstPtr &inst, const InstSeqNum &seqNum, + int asid, TheISA::PCState &instPC, + TheISA::PCState &predPC, 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. + + using TheISA::MachInst; + + bool pred_taken = false; + TheISA::PCState target; + + ++lookups; + DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch " + "prediction\n", tid, seqNum, + inst->disassemble(instPC.instAddr()), instPC); + + 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(bp_history); + + if (inst->isReturn() && RAS[tid].empty()) { + DPRINTF(Branch, "[tid:%i] RAS is empty, predicting " + "false.\n", tid); + pred_taken = false; + } + } else { + ++condPredicted; + + pred_taken = lookup(predPC.instAddr(), bp_history); + } + + PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken, + bp_history, tid); + + // Now lookup in the BTB or RAS. + if (pred_taken) { + if (inst->isReturn()) { + ++usedRAS; + + // If it's a function return call, then look up the address + // in the RAS. + TheISA::PCState rasTop = RAS[tid].top(); + target = TheISA::buildRetPC(instPC, 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; + + assert(predict_record.RASIndex < 16); + + RAS[tid].pop(); + + DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " + "RAS predicted target: %s, RAS index: %i.\n", + tid, instPC, target, + predict_record.RASIndex); + } else { + ++BTBLookups; + + if (inst->isCall()) { + + RAS[tid].push(instPC); + 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, instPC, predPC, + RAS[tid].topIdx()); + } + + if (inst->isCall() && + inst->isUncondCtrl() && + inst->isDirectCtrl()) { + target = inst->branchTarget(instPC); + } else if (BTB.valid(predPC.instAddr(), asid)) { + ++BTBHits; + + // If it's not a return, use the BTB to get the target addr. + target = BTB.lookup(predPC.instAddr(), asid); + + DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s " + "predicted target is %s.\n", + tid, asid, instPC, target); + } else { + DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " + "valid entry, predicting false.\n",tid); + pred_taken = false; + } + } + } + + if (pred_taken) { + // Set the PC and the instruction's predicted target. + predPC = target; + } + DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n", + tid, seqNum, predPC); + + predHist[tid].push_front(predict_record); + + DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist " + "...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); + + while (!predHist[tid].empty() && + predHist[tid].back().seqNum <= done_sn) { + // Update the branch predictor with the correct results. + update(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]; + + 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(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; + + 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()) { + + HistoryIt 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; + } + + update((*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(); + } + + 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); + + } 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(); + } + } + DPRINTF(Branch, "[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); + + DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", tid, + predHist[tid].size()); + } else { + DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " + "update.\n", tid, squashed_sn); + } +} + +void +BPredUnit::dump() +{ + HistoryIt pred_hist_it; + + for (int i = 0; i < numThreads; ++i) { + if (!predHist[i].empty()) { + pred_hist_it = predHist[i].begin(); + + cprintf("predHist[%i].size(): %i\n", i, predHist[i].size()); + + while (pred_hist_it != predHist[i].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"); + } + } +} diff --git a/src/cpu/pred/btb.hh b/src/cpu/pred/btb.hh index 814b23872..3a773e40d 100644 --- a/src/cpu/pred/btb.hh +++ b/src/cpu/pred/btb.hh @@ -28,8 +28,8 @@ * Authors: Kevin Lim */ -#ifndef __CPU_O3_BTB_HH__ -#define __CPU_O3_BTB_HH__ +#ifndef __CPU_PRED_BTB_HH__ +#define __CPU_PRED_BTB_HH__ #include "arch/types.hh" #include "base/misc.hh" @@ -127,4 +127,4 @@ class DefaultBTB unsigned tagShiftAmt; }; -#endif // __CPU_O3_BTB_HH__ +#endif // __CPU_PRED_BTB_HH__ diff --git a/src/cpu/pred/ras.hh b/src/cpu/pred/ras.hh index ab92b34c2..924543eac 100644 --- a/src/cpu/pred/ras.hh +++ b/src/cpu/pred/ras.hh @@ -28,8 +28,8 @@ * Authors: Kevin Lim */ -#ifndef __CPU_O3_RAS_HH__ -#define __CPU_O3_RAS_HH__ +#ifndef __CPU_PRED_RAS_HH__ +#define __CPU_PRED_RAS_HH__ #include <vector> @@ -99,4 +99,4 @@ class ReturnAddrStack unsigned tos; }; -#endif // __CPU_O3_RAS_HH__ +#endif // __CPU_PRED_RAS_HH__ diff --git a/src/cpu/pred/sat_counter.hh b/src/cpu/pred/sat_counter.hh new file mode 100644 index 000000000..1294a4e08 --- /dev/null +++ b/src/cpu/pred/sat_counter.hh @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2005-2006 The Regents of The University of Michigan + * 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: Kevin Lim + */ + +#ifndef __CPU_PRED_SAT_COUNTER_HH__ +#define __CPU_PRED_SAT_COUNTER_HH__ + +#include "base/misc.hh" +#include "base/types.hh" + +/** + * Private counter class for the internal saturating counters. + * Implements an n bit saturating counter and provides methods to + * increment, decrement, and read it. + * @todo Consider making this something that more closely mimics a + * built in class so you can use ++ or --. + */ +class SatCounter +{ + public: + /** + * Constructor for the counter. + */ + SatCounter() + : initialVal(0), counter(0) + { } + + /** + * Constructor for the counter. + * @param bits How many bits the counter will have. + */ + SatCounter(unsigned bits) + : initialVal(0), maxVal((1 << bits) - 1), counter(0) + { } + + /** + * Constructor for the counter. + * @param bits How many bits the counter will have. + * @param initial_val Starting value for each counter. + */ + SatCounter(unsigned bits, uint8_t initial_val) + : initialVal(initial_val), maxVal((1 << bits) - 1), + counter(initial_val) + { + // Check to make sure initial value doesn't exceed the max + // counter value. + if (initial_val > maxVal) { + fatal("BP: Initial counter value exceeds max size."); + } + } + + /** + * Sets the number of bits. + */ + void setBits(unsigned bits) { maxVal = (1 << bits) - 1; } + + void reset() { counter = initialVal; } + + /** + * Increments the counter's current value. + */ + void increment() + { + if (counter < maxVal) { + ++counter; + } + } + + /** + * Decrements the counter's current value. + */ + void decrement() + { + if (counter > 0) { + --counter; + } + } + + /** + * Read the counter's value. + */ + const uint8_t read() const + { return counter; } + + private: + uint8_t initialVal; + uint8_t maxVal; + uint8_t counter; +}; + +#endif // __CPU_PRED_SAT_COUNTER_HH__ diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc index f36d30ae5..52a05960f 100644 --- a/src/cpu/pred/tournament.cc +++ b/src/cpu/pred/tournament.cc @@ -44,24 +44,17 @@ #include "base/intmath.hh" #include "cpu/pred/tournament.hh" -TournamentBP::TournamentBP(unsigned _localCtrBits, - unsigned _localHistoryTableSize, - unsigned _localHistoryBits, - unsigned _globalPredictorSize, - unsigned _globalHistoryBits, - unsigned _globalCtrBits, - unsigned _choicePredictorSize, - unsigned _choiceCtrBits, - unsigned _instShiftAmt) - : localCtrBits(_localCtrBits), - localHistoryTableSize(_localHistoryTableSize), - localHistoryBits(_localHistoryBits), - globalPredictorSize(_globalPredictorSize), - globalCtrBits(_globalCtrBits), - globalHistoryBits(_globalHistoryBits), - choicePredictorSize(_choicePredictorSize), - choiceCtrBits(_choiceCtrBits), - instShiftAmt(_instShiftAmt) +TournamentBP::TournamentBP(const Params *params) + : BPredUnit(params), + localCtrBits(params->localCtrBits), + localHistoryTableSize(params->localHistoryTableSize), + localHistoryBits(params->localHistoryBits), + globalPredictorSize(params->globalPredictorSize), + globalCtrBits(params->globalCtrBits), + globalHistoryBits(params->globalHistoryBits), + choicePredictorSize(params->choicePredictorSize), + choiceCtrBits(params->choiceCtrBits), + instShiftAmt(params->instShiftAmt) { localPredictorSize = ULL(1) << localHistoryBits; @@ -178,7 +171,7 @@ TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) void -TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history) +TournamentBP::btbUpdate(Addr branch_addr, void * &bp_history) { unsigned local_history_idx = calcLocHistIdx(branch_addr); //Update Global History to Not Taken (clear LSB) @@ -189,7 +182,7 @@ TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history) } bool -TournamentBP::lookup(Addr &branch_addr, void * &bp_history) +TournamentBP::lookup(Addr branch_addr, void * &bp_history) { bool local_prediction; unsigned local_history_idx; @@ -249,7 +242,7 @@ TournamentBP::lookup(Addr &branch_addr, void * &bp_history) } void -TournamentBP::uncondBr(void * &bp_history) +TournamentBP::uncondBranch(void * &bp_history) { // Create BPHistory and pass it back to be recorded. BPHistory *history = new BPHistory; @@ -264,7 +257,7 @@ TournamentBP::uncondBr(void * &bp_history) } 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; diff --git a/src/cpu/pred/tournament.hh b/src/cpu/pred/tournament.hh index 35cfd8455..39fff5bfb 100644 --- a/src/cpu/pred/tournament.hh +++ b/src/cpu/pred/tournament.hh @@ -38,15 +38,18 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Authors: Kevin Lim + * Timothy M. Jones + * Nilay Vaish */ -#ifndef __CPU_O3_TOURNAMENT_PRED_HH__ -#define __CPU_O3_TOURNAMENT_PRED_HH__ +#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ +#define __CPU_PRED_TOURNAMENT_PRED_HH__ #include <vector> #include "base/types.hh" -#include "cpu/o3/sat_counter.hh" +#include "cpu/pred/bpred_unit.hh" +#include "cpu/pred/sat_counter.hh" /** * Implements a tournament branch predictor, hopefully identical to the one @@ -57,21 +60,13 @@ * is speculatively updated, the rest are updated upon branches committing * or misspeculating. */ -class TournamentBP +class TournamentBP : public BPredUnit { public: /** * Default branch predictor constructor. */ - TournamentBP(unsigned localCtrBits, - unsigned localHistoryTableSize, - unsigned localHistoryBits, - unsigned globalPredictorSize, - unsigned globalHistoryBits, - unsigned globalCtrBits, - unsigned choicePredictorSize, - unsigned choiceCtrBits, - unsigned instShiftAmt); + TournamentBP(const Params *params); /** * Looks up the given address in the branch predictor and returns @@ -81,7 +76,7 @@ class TournamentBP * @param bp_history Pointer that will be set to the BPHistory object. * @return Whether or not the branch is taken. */ - bool lookup(Addr &branch_addr, void * &bp_history); + bool lookup(Addr branch_addr, void * &bp_history); /** * Records that there was an unconditional branch, and modifies @@ -89,7 +84,7 @@ class TournamentBP * global history stored in it. * @param bp_history Pointer that will be set to the BPHistory object. */ - void uncondBr(void * &bp_history); + void uncondBranch(void * &bp_history); /** * Updates the branch predictor to Not Taken if a BTB entry is * invalid or not found. @@ -97,7 +92,7 @@ class TournamentBP * @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); + 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. @@ -107,7 +102,7 @@ class TournamentBP * @param squashed is set when this function is called during a squash * operation. */ - void update(Addr &branch_addr, bool taken, void *bp_history, bool squashed); + void update(Addr branch_addr, bool taken, void *bp_history, bool squashed); /** * Restores the global branch history on a squash. @@ -250,4 +245,4 @@ class TournamentBP unsigned choiceThreshold; }; -#endif // __CPU_O3_TOURNAMENT_PRED_HH__ +#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ |