bpred_unit.hh revision 13654:dc3878f03a0c
12623SN/A/* 22623SN/A * Copyright (c) 2011-2012, 2014 ARM Limited 32623SN/A * Copyright (c) 2010 The University of Edinburgh 42623SN/A * All rights reserved 52623SN/A * 62623SN/A * The license below extends only to copyright in the software and shall 72623SN/A * not be construed as granting a license to any other intellectual 82623SN/A * property including but not limited to intellectual property relating 92623SN/A * to a hardware implementation of the functionality of the software 102623SN/A * licensed hereunder. You may use the software subject to the license 112623SN/A * terms below provided that you ensure that this notice is replicated 122623SN/A * unmodified and in its entirety in all distributions of the software, 132623SN/A * modified or unmodified, in source code or in binary form. 142623SN/A * 152623SN/A * Copyright (c) 2004-2005 The Regents of The University of Michigan 162623SN/A * All rights reserved. 172623SN/A * 182623SN/A * Redistribution and use in source and binary forms, with or without 192623SN/A * modification, are permitted provided that the following conditions are 202623SN/A * met: redistributions of source code must retain the above copyright 212623SN/A * notice, this list of conditions and the following disclaimer; 222623SN/A * redistributions in binary form must reproduce the above copyright 232623SN/A * notice, this list of conditions and the following disclaimer in the 242623SN/A * documentation and/or other materials provided with the distribution; 252623SN/A * neither the name of the copyright holders nor the names of its 262623SN/A * contributors may be used to endorse or promote products derived from 272665Ssaidi@eecs.umich.edu * this software without specific prior written permission. 282665Ssaidi@eecs.umich.edu * 292623SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 302623SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 313170Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 323806Ssaidi@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 332623SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 344040Ssaidi@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 356658Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 362623SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 372623SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 383348Sbinkertn@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 393348Sbinkertn@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 404762Snate@binkert.org * 417678Sgblack@eecs.umich.edu * Authors: Kevin Lim 422901Ssaidi@eecs.umich.edu * Korey Sewell 432623SN/A * Timothy M. Jones 442623SN/A * Nilay Vaish 452623SN/A */ 462623SN/A 472623SN/A#ifndef __CPU_PRED_BPRED_UNIT_HH__ 485606Snate@binkert.org#define __CPU_PRED_BPRED_UNIT_HH__ 492623SN/A 502623SN/A#include <deque> 512623SN/A 522623SN/A#include "base/statistics.hh" 532623SN/A#include "base/types.hh" 542623SN/A#include "cpu/pred/btb.hh" 552623SN/A#include "cpu/pred/indirect.hh" 562623SN/A#include "cpu/pred/ras.hh" 572623SN/A#include "cpu/inst_seq.hh" 582623SN/A#include "cpu/static_inst.hh" 592623SN/A#include "params/BranchPredictor.hh" 605336Shines@cs.fsu.edu#include "sim/probe/pmu.hh" 612623SN/A#include "sim/sim_object.hh" 624873Sstever@eecs.umich.edu 632623SN/A/** 642623SN/A * Basically a wrapper class to hold both the branch predictor 652856Srdreslin@umich.edu * and the BTB. 666227Snate@binkert.org */ 672856Srdreslin@umich.educlass BPredUnit : public SimObject 682856Srdreslin@umich.edu{ 692856Srdreslin@umich.edu public: 702856Srdreslin@umich.edu typedef BranchPredictorParams Params; 712856Srdreslin@umich.edu /** 724968Sacolyte@umich.edu * @param params The params object, that has the size of the BP and BTB. 734968Sacolyte@umich.edu */ 744968Sacolyte@umich.edu BPredUnit(const Params *p); 754968Sacolyte@umich.edu 762856Srdreslin@umich.edu /** 772856Srdreslin@umich.edu * Registers statistics. 782856Srdreslin@umich.edu */ 792623SN/A void regStats() override; 802623SN/A 812623SN/A void regProbePoints() override; 822623SN/A 832623SN/A /** Perform sanity checks after a drain. */ 842623SN/A void drainSanityCheck() const; 856221Snate@binkert.org 866221Snate@binkert.org /** 872680Sktlim@umich.edu * Predicts whether or not the instruction is a taken branch, and the 882623SN/A * target of the branch if it is taken. 892623SN/A * @param inst The branch instruction. 905714Shsul@eecs.umich.edu * @param PC The predicted PC is passed back through this parameter. 912623SN/A * @param tid The thread id. 922623SN/A * @return Returns if the branch is taken or not. 934968Sacolyte@umich.edu */ 944968Sacolyte@umich.edu bool predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 954968Sacolyte@umich.edu TheISA::PCState &pc, ThreadID tid); 964968Sacolyte@umich.edu 974968Sacolyte@umich.edu // @todo: Rename this function. 984968Sacolyte@umich.edu virtual void uncondBranch(ThreadID tid, Addr pc, void * &bp_history) = 0; 995714Shsul@eecs.umich.edu 1005712Shsul@eecs.umich.edu /** 1015712Shsul@eecs.umich.edu * Tells the branch predictor to commit any updates until the given 1025712Shsul@eecs.umich.edu * sequence number. 1032623SN/A * @param done_sn The sequence number to commit any older updates up until. 1042623SN/A * @param tid The thread id. 1052623SN/A */ 1063349Sbinkertn@umich.edu void update(const InstSeqNum &done_sn, ThreadID tid); 1072623SN/A 1083184Srdreslin@umich.edu /** 1092623SN/A * Squashes all outstanding updates until a given sequence number. 1102623SN/A * @param squashed_sn The sequence number to squash any younger updates up 1112623SN/A * until. 1122623SN/A * @param tid The thread id. 1133349Sbinkertn@umich.edu */ 1142623SN/A void squash(const InstSeqNum &squashed_sn, ThreadID tid); 1153310Srdreslin@umich.edu 1163649Srdreslin@umich.edu /** 1172623SN/A * Squashes all outstanding updates until a given sequence number, and 1182623SN/A * corrects that sn's update with the proper address and taken/not taken. 1192623SN/A * @param squashed_sn The sequence number to squash any younger updates up 1203349Sbinkertn@umich.edu * until. 1212623SN/A * @param corr_target The correct branch target. 1223184Srdreslin@umich.edu * @param actually_taken The correct branch direction. 1233184Srdreslin@umich.edu * @param tid The thread id. 1242623SN/A */ 1252623SN/A void squash(const InstSeqNum &squashed_sn, 1262623SN/A const TheISA::PCState &corr_target, 1272623SN/A bool actually_taken, ThreadID tid); 1282623SN/A 1293647Srdreslin@umich.edu /** 1303647Srdreslin@umich.edu * @param bp_history Pointer to the history object. The predictor 1313647Srdreslin@umich.edu * will need to update any state and delete the object. 1323647Srdreslin@umich.edu */ 1333647Srdreslin@umich.edu virtual void squash(ThreadID tid, void *bp_history) = 0; 1342626SN/A 1353647Srdreslin@umich.edu /** 1362626SN/A * Looks up a given PC in the BP to see if it is taken or not taken. 1372623SN/A * @param inst_PC The PC to look up. 1382623SN/A * @param bp_history Pointer that will be set to an object that 1392623SN/A * has the branch predictor state associated with the lookup. 1402657Ssaidi@eecs.umich.edu * @return Whether the branch is taken or not taken. 1412623SN/A */ 1422623SN/A virtual bool lookup(ThreadID tid, Addr instPC, void * &bp_history) = 0; 1432623SN/A 1442623SN/A /** 1452623SN/A * If a branch is not taken, because the BTB address is invalid or missing, 1464192Sktlim@umich.edu * this function sets the appropriate counter in the global and local 1474192Sktlim@umich.edu * predictors to not taken. 1484192Sktlim@umich.edu * @param inst_PC The PC to look up the local predictor. 1494192Sktlim@umich.edu * @param bp_history Pointer that will be set to an object that 1504192Sktlim@umich.edu * has the branch predictor state associated with the lookup. 1514192Sktlim@umich.edu */ 1524192Sktlim@umich.edu virtual void btbUpdate(ThreadID tid, Addr instPC, void * &bp_history) = 0; 1534192Sktlim@umich.edu 1545497Ssaidi@eecs.umich.edu /** 1554192Sktlim@umich.edu * Looks up a given PC in the BTB to see if a matching entry exists. 1564192Sktlim@umich.edu * @param inst_PC The PC to look up. 1572623SN/A * @return Whether the BTB contains the given PC. 1585529Snate@binkert.org */ 1596078Sgblack@eecs.umich.edu bool BTBValid(Addr instPC) 1605487Snate@binkert.org { return BTB.valid(instPC, 0); } 1615487Snate@binkert.org 1624968Sacolyte@umich.edu /** 1634968Sacolyte@umich.edu * Looks up a given PC in the BTB to get the predicted target. 1642623SN/A * @param inst_PC The PC to look up. 1652623SN/A * @return The address of the target of the branch. 1662623SN/A */ 1673647Srdreslin@umich.edu TheISA::PCState BTBLookup(Addr instPC) 1683647Srdreslin@umich.edu { return BTB.lookup(instPC, 0); } 1693647Srdreslin@umich.edu 1702623SN/A /** 1712623SN/A * Updates the BP with taken/not taken information. 1722623SN/A * @param inst_PC The branch's PC that will be updated. 1732623SN/A * @param taken Whether the branch was taken or not taken. 1742623SN/A * @param bp_history Pointer to the branch predictor state that is 1756775SBrad.Beckmann@amd.com * associated with the branch lookup that is being updated. 1766775SBrad.Beckmann@amd.com * @param squashed Set to true when this function is called during a 1776775SBrad.Beckmann@amd.com * squash operation. 1782623SN/A * @param inst Static instruction information 1792623SN/A * @param corrTarget The resolved target of the branch (only needed 1802623SN/A * for squashed branches) 1812623SN/A * @todo Make this update flexible enough to handle a global predictor. 1822623SN/A */ 1832915Sktlim@umich.edu virtual void update(ThreadID tid, Addr instPC, bool taken, 1842915Sktlim@umich.edu void *bp_history, bool squashed, 1856078Sgblack@eecs.umich.edu const StaticInstPtr & inst = StaticInst::nullStaticInstPtr, 1863145Shsul@eecs.umich.edu Addr corrTarget = MaxAddr) = 0; 1872623SN/A /** 1882623SN/A * Updates the BTB with the target of a branch. 1892623SN/A * @param inst_PC The branch's PC that will be updated. 1902623SN/A * @param target_PC The branch's target that will be added to the BTB. 1912623SN/A */ 1922623SN/A void BTBUpdate(Addr instPC, const TheISA::PCState &target) 1932623SN/A { BTB.update(instPC, target, 0); } 1942915Sktlim@umich.edu 1952915Sktlim@umich.edu 1966078Sgblack@eecs.umich.edu void dump(); 1973145Shsul@eecs.umich.edu 1982915Sktlim@umich.edu private: 1992915Sktlim@umich.edu struct PredictorHistory { 2002915Sktlim@umich.edu /** 2012915Sktlim@umich.edu * Makes a predictor history struct that contains any 2022915Sktlim@umich.edu * information needed to update the predictor, BTB, and RAS. 2032915Sktlim@umich.edu */ 2045220Ssaidi@eecs.umich.edu PredictorHistory(const InstSeqNum &seq_num, Addr instPC, 2055220Ssaidi@eecs.umich.edu bool pred_taken, void *bp_history, 2065220Ssaidi@eecs.umich.edu void *indirect_history, ThreadID _tid, 2074940Snate@binkert.org const StaticInstPtr & inst) 2085220Ssaidi@eecs.umich.edu : seqNum(seq_num), pc(instPC), bpHistory(bp_history), 2093324Shsul@eecs.umich.edu indirectHistory(indirect_history), RASTarget(0), RASIndex(0), 2105220Ssaidi@eecs.umich.edu tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), 2115220Ssaidi@eecs.umich.edu wasCall(0), wasReturn(0), wasIndirect(0), target(MaxAddr), 2125606Snate@binkert.org inst(inst) 2135606Snate@binkert.org {} 2142915Sktlim@umich.edu 2152623SN/A bool operator==(const PredictorHistory &entry) const { 2162623SN/A return this->seqNum == entry.seqNum; 2172623SN/A } 2182798Sktlim@umich.edu 2192623SN/A /** The sequence number for the predictor history entry. */ 2205496Ssaidi@eecs.umich.edu InstSeqNum seqNum; 2212798Sktlim@umich.edu 2222623SN/A /** The PC associated with the sequence number. */ 2232798Sktlim@umich.edu Addr pc; 2242623SN/A 2252623SN/A /** Pointer to the history object passed back from the branch 2262623SN/A * predictor. It is used to update or restore state of the 2272623SN/A * branch predictor. 2282623SN/A */ 2292623SN/A void *bpHistory; 2304192Sktlim@umich.edu 2312623SN/A void *indirectHistory; 2322623SN/A 2332623SN/A /** The RAS target (only valid if a return). */ 2342680Sktlim@umich.edu TheISA::PCState RASTarget; 2352623SN/A 2366221Snate@binkert.org /** The RAS index of the instruction (only valid if a call). */ 2376221Snate@binkert.org unsigned RASIndex; 2382680Sktlim@umich.edu 2392680Sktlim@umich.edu /** The thread id. */ 2402623SN/A ThreadID tid; 2415606Snate@binkert.org 2422623SN/A /** Whether or not it was predicted taken. */ 2432623SN/A bool predTaken; 2442623SN/A 2453512Sktlim@umich.edu /** Whether or not the RAS was used. */ 2463512Sktlim@umich.edu bool usedRAS; 2473512Sktlim@umich.edu 2485169Ssaidi@eecs.umich.edu /* Whether or not the RAS was pushed */ 2495712Shsul@eecs.umich.edu bool pushedRAS; 2505712Shsul@eecs.umich.edu 2515712Shsul@eecs.umich.edu /** Whether or not the instruction was a call. */ 2522623SN/A bool wasCall; 2532623SN/A 2542623SN/A /** Whether or not the instruction was a return. */ 2552623SN/A bool wasReturn; 2562623SN/A 2572623SN/A /** Wether this instruction was an indirect branch */ 2584940Snate@binkert.org bool wasIndirect; 2594940Snate@binkert.org 2602623SN/A /** Target of the branch. First it is predicted, and fixed later 2612683Sktlim@umich.edu * if necessary 2622623SN/A */ 2632623SN/A Addr target; 2642623SN/A 2652623SN/A /** The branch instrction */ 2662623SN/A const StaticInstPtr inst; 2675101Ssaidi@eecs.umich.edu }; 2683686Sktlim@umich.edu 2693430Sgblack@eecs.umich.edu typedef std::deque<PredictorHistory> History; 2705606Snate@binkert.org 2712623SN/A /** Number of the threads for which the branch history is maintained. */ 2722623SN/A const unsigned numThreads; 2732623SN/A 2742623SN/A 2752623SN/A /** 2762623SN/A * The per-thread predictor history. This is used to update the predictor 2772623SN/A * as instructions are committed, or restore it to the proper state after 2784940Snate@binkert.org * a squash. 2794940Snate@binkert.org */ 2802623SN/A std::vector<History> predHist; 2812683Sktlim@umich.edu 2822623SN/A /** The BTB. */ 2836043Sgblack@eecs.umich.edu DefaultBTB BTB; 2846043Sgblack@eecs.umich.edu 2856043Sgblack@eecs.umich.edu /** The per-thread return address stack. */ 2862623SN/A std::vector<ReturnAddrStack> RAS; 2872626SN/A 2882626SN/A /** Option to disable indirect predictor. */ 2892626SN/A const bool useIndirect; 2902626SN/A 2915606Snate@binkert.org /** The indirect target predictor. */ 2922623SN/A IndirectPredictor iPred; 2932623SN/A 2942623SN/A /** Stat for number of BP lookups. */ 2952623SN/A Stats::Scalar lookups; 2962623SN/A /** Stat for number of conditional branches predicted. */ 2972623SN/A Stats::Scalar condPredicted; 2982623SN/A /** Stat for number of conditional branches predicted incorrectly. */ 2997520Sgblack@eecs.umich.edu Stats::Scalar condIncorrect; 3007520Sgblack@eecs.umich.edu /** Stat for number of BTB lookups. */ 3012623SN/A Stats::Scalar BTBLookups; 3023169Sstever@eecs.umich.edu /** Stat for number of BTB hits. */ 3034870Sstever@eecs.umich.edu Stats::Scalar BTBHits; 3042623SN/A /** Stat for number of times the BTB is correct. */ 3052623SN/A Stats::Scalar BTBCorrect; 3062623SN/A /** Stat for percent times an entry in BTB found. */ 3072623SN/A Stats::Formula BTBHitPct; 3082623SN/A /** Stat for number of times the RAS is used to get a target. */ 3094999Sgblack@eecs.umich.edu Stats::Scalar usedRAS; 3106227Snate@binkert.org /** Stat for number of times the RAS is incorrect. */ 3114999Sgblack@eecs.umich.edu Stats::Scalar RASIncorrect; 3127520Sgblack@eecs.umich.edu 3132623SN/A /** Stat for the number of indirect target lookups.*/ 3144999Sgblack@eecs.umich.edu Stats::Scalar indirectLookups; 3154999Sgblack@eecs.umich.edu /** Stat for the number of indirect target hits.*/ 3167520Sgblack@eecs.umich.edu Stats::Scalar indirectHits; 3174999Sgblack@eecs.umich.edu /** Stat for the number of indirect target misses.*/ 3187520Sgblack@eecs.umich.edu Stats::Scalar indirectMisses; 3197520Sgblack@eecs.umich.edu /** Stat for the number of indirect target mispredictions.*/ 3204999Sgblack@eecs.umich.edu Stats::Scalar indirectMispredicted; 3214999Sgblack@eecs.umich.edu 3224999Sgblack@eecs.umich.edu protected: 3237520Sgblack@eecs.umich.edu /** Number of bits to shift instructions by for predictor addresses. */ 3247720Sgblack@eecs.umich.edu const unsigned instShiftAmt; 3254999Sgblack@eecs.umich.edu 3264999Sgblack@eecs.umich.edu /** 3276023Snate@binkert.org * @{ 3284999Sgblack@eecs.umich.edu * @name PMU Probe points. 3294999Sgblack@eecs.umich.edu */ 3306623Sgblack@eecs.umich.edu 3314999Sgblack@eecs.umich.edu /** 3326102Sgblack@eecs.umich.edu * Helper method to instantiate probe points belonging to this 3334999Sgblack@eecs.umich.edu * object. 3347520Sgblack@eecs.umich.edu * 3354999Sgblack@eecs.umich.edu * @param name Name of the probe point. 3364999Sgblack@eecs.umich.edu * @return A unique_ptr to the new probe point. 3374999Sgblack@eecs.umich.edu */ 3384999Sgblack@eecs.umich.edu ProbePoints::PMUUPtr pmuProbePoint(const char *name); 3394999Sgblack@eecs.umich.edu 3404999Sgblack@eecs.umich.edu 3414999Sgblack@eecs.umich.edu /** 3424999Sgblack@eecs.umich.edu * Branches seen by the branch predictor 3434999Sgblack@eecs.umich.edu * 3444999Sgblack@eecs.umich.edu * @note This counter includes speculative branches. 3455012Sgblack@eecs.umich.edu */ 3464999Sgblack@eecs.umich.edu ProbePoints::PMUUPtr ppBranches; 3474999Sgblack@eecs.umich.edu 3486102Sgblack@eecs.umich.edu /** Miss-predicted branches */ 3494999Sgblack@eecs.umich.edu ProbePoints::PMUUPtr ppMisses; 3504999Sgblack@eecs.umich.edu 3514968Sacolyte@umich.edu /** @} */ 3524986Ssaidi@eecs.umich.edu}; 3534999Sgblack@eecs.umich.edu 3546739Sgblack@eecs.umich.edu#endif // __CPU_PRED_BPRED_UNIT_HH__ 3556739Sgblack@eecs.umich.edu