bpred_unit.hh revision 6216
12068SN/A/* 22068SN/A * Copyright (c) 2004-2005 The Regents of The University of Michigan 32188SN/A * All rights reserved. 42068SN/A * 52068SN/A * Redistribution and use in source and binary forms, with or without 62068SN/A * modification, are permitted provided that the following conditions are 72068SN/A * met: redistributions of source code must retain the above copyright 82068SN/A * notice, this list of conditions and the following disclaimer; 92068SN/A * redistributions in binary form must reproduce the above copyright 102068SN/A * notice, this list of conditions and the following disclaimer in the 112068SN/A * documentation and/or other materials provided with the distribution; 122068SN/A * neither the name of the copyright holders nor the names of its 132068SN/A * contributors may be used to endorse or promote products derived from 142068SN/A * this software without specific prior written permission. 152068SN/A * 162068SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172068SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182068SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192068SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202068SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212068SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222068SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232068SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242068SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252068SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262068SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272068SN/A * 282665Ssaidi@eecs.umich.edu * Authors: Kevin Lim 292665Ssaidi@eecs.umich.edu */ 302068SN/A 312649Ssaidi@eecs.umich.edu#ifndef __CPU_O3_BPRED_UNIT_HH__ 322649Ssaidi@eecs.umich.edu#define __CPU_O3_BPRED_UNIT_HH__ 332649Ssaidi@eecs.umich.edu 342649Ssaidi@eecs.umich.edu#include <list> 352649Ssaidi@eecs.umich.edu 362068SN/A#include "base/statistics.hh" 372068SN/A#include "base/types.hh" 382068SN/A#include "cpu/inst_seq.hh" 392068SN/A#include "cpu/o3/2bit_local_pred.hh" 402068SN/A#include "cpu/o3/btb.hh" 412068SN/A#include "cpu/o3/ras.hh" 422068SN/A#include "cpu/o3/tournament_pred.hh" 432068SN/A 442075SN/Aclass DerivO3CPUParams; 452075SN/A 462075SN/A/** 472075SN/A * Basically a wrapper class to hold both the branch predictor 482075SN/A * and the BTB. 492075SN/A */ 502735Sktlim@umich.edutemplate<class Impl> 512069SN/Aclass BPredUnit 522069SN/A{ 532075SN/A private: 542735Sktlim@umich.edu typedef typename Impl::DynInstPtr DynInstPtr; 552068SN/A 562068SN/A enum PredType { 572068SN/A Local, 582075SN/A Tournament 592075SN/A }; 602068SN/A 612068SN/A PredType predictor; 622075SN/A 632075SN/A const std::string _name; 642068SN/A 652068SN/A public: 662068SN/A 672075SN/A /** 682075SN/A * @param params The params object, that has the size of the BP and BTB. 692075SN/A */ 702075SN/A BPredUnit(DerivO3CPUParams *params); 712075SN/A 722075SN/A const std::string &name() const { return _name; } 732075SN/A 742735Sktlim@umich.edu /** 752069SN/A * Registers statistics. 762069SN/A */ 772075SN/A void regStats(); 782735Sktlim@umich.edu 792068SN/A void switchOut(); 802068SN/A 812068SN/A void takeOverFrom(); 822075SN/A 832068SN/A /** 842069SN/A * Predicts whether or not the instruction is a taken branch, and the 852068SN/A * target of the branch if it is taken. 862068SN/A * @param inst The branch instruction. 874027Sstever@eecs.umich.edu * @param PC The predicted PC is passed back through this parameter. 884027Sstever@eecs.umich.edu * @param tid The thread id. 894027Sstever@eecs.umich.edu * @return Returns if the branch is taken or not. 902336SN/A */ 912075SN/A bool predict(DynInstPtr &inst, Addr &PC, unsigned tid); 922068SN/A 932069SN/A // @todo: Rename this function. 942068SN/A void BPUncond(void * &bp_history); 952068SN/A 962068SN/A /** 972068SN/A * Tells the branch predictor to commit any updates until the given 982068SN/A * sequence number. 992068SN/A * @param done_sn The sequence number to commit any older updates up until. 1002068SN/A * @param tid The thread id. 1012068SN/A */ 1024027Sstever@eecs.umich.edu void update(const InstSeqNum &done_sn, unsigned tid); 1034027Sstever@eecs.umich.edu 1044027Sstever@eecs.umich.edu /** 1054027Sstever@eecs.umich.edu * Squashes all outstanding updates until a given sequence number. 1064027Sstever@eecs.umich.edu * @param squashed_sn The sequence number to squash any younger updates up 1074027Sstever@eecs.umich.edu * until. 1082336SN/A * @param tid The thread id. 1092068SN/A */ 1102068SN/A void squash(const InstSeqNum &squashed_sn, unsigned tid); 1112068SN/A 1122068SN/A /** 1132068SN/A * Squashes all outstanding updates until a given sequence number, and 1142068SN/A * corrects that sn's update with the proper address and taken/not taken. 1152068SN/A * @param squashed_sn The sequence number to squash any younger updates up 1162068SN/A * until. 1172068SN/A * @param corr_target The correct branch target. 1182068SN/A * @param actually_taken The correct branch direction. 1192068SN/A * @param tid The thread id. 1202068SN/A */ 1212147SN/A void squash(const InstSeqNum &squashed_sn, const Addr &corr_target, 1222068SN/A bool actually_taken, unsigned tid); 1232068SN/A 1242068SN/A /** 1252068SN/A * @param bp_history Pointer to the history object. The predictor 1262068SN/A * will need to update any state and delete the object. 1272068SN/A */ 1282068SN/A void BPSquash(void *bp_history); 1292068SN/A 1302068SN/A /** 1312068SN/A * Looks up a given PC in the BP to see if it is taken or not taken. 1322068SN/A * @param inst_PC The PC to look up. 1332147SN/A * @param bp_history Pointer that will be set to an object that 1342068SN/A * has the branch predictor state associated with the lookup. 1352068SN/A * @return Whether the branch is taken or not taken. 1362068SN/A */ 1372068SN/A bool BPLookup(Addr &inst_PC, void * &bp_history); 1382068SN/A 1392068SN/A /** 1402068SN/A * Looks up a given PC in the BTB to see if a matching entry exists. 1412068SN/A * @param inst_PC The PC to look up. 1422068SN/A * @return Whether the BTB contains the given PC. 1432068SN/A */ 1442068SN/A bool BTBValid(Addr &inst_PC) 1452068SN/A { return BTB.valid(inst_PC, 0); } 1462068SN/A 1472147SN/A /** 1482068SN/A * Looks up a given PC in the BTB to get the predicted target. 1492068SN/A * @param inst_PC The PC to look up. 1502068SN/A * @return The address of the target of the branch. 1512068SN/A */ 1522068SN/A Addr BTBLookup(Addr &inst_PC) 1532068SN/A { return BTB.lookup(inst_PC, 0); } 1542068SN/A 1552068SN/A /** 1562068SN/A * Updates the BP with taken/not taken information. 1572068SN/A * @param inst_PC The branch's PC that will be updated. 1582068SN/A * @param taken Whether the branch was taken or not taken. 1592068SN/A * @param bp_history Pointer to the branch predictor state that is 1602068SN/A * associated with the branch lookup that is being updated. 1612147SN/A * @todo Make this update flexible enough to handle a global predictor. 1622068SN/A */ 1632068SN/A void BPUpdate(Addr &inst_PC, bool taken, void *bp_history); 1642068SN/A 1652068SN/A /** 1662068SN/A * Updates the BTB with the target of a branch. 1672068SN/A * @param inst_PC The branch's PC that will be updated. 1682068SN/A * @param target_PC The branch's target that will be added to the BTB. 1692068SN/A */ 1702068SN/A void BTBUpdate(Addr &inst_PC, Addr &target_PC) 1712068SN/A { BTB.update(inst_PC, target_PC,0); } 1722068SN/A 1732068SN/A void dump(); 1742068SN/A 1752068SN/A private: 1762068SN/A struct PredictorHistory { 1772068SN/A /** 1782068SN/A * Makes a predictor history struct that contains any 1792068SN/A * information needed to update the predictor, BTB, and RAS. 1802068SN/A */ 1812068SN/A PredictorHistory(const InstSeqNum &seq_num, const Addr &inst_PC, 1822068SN/A const bool pred_taken, void *bp_history, 1832068SN/A const unsigned _tid) 1842068SN/A : seqNum(seq_num), PC(inst_PC), RASTarget(0), 1852068SN/A RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), 1862068SN/A wasCall(0), bpHistory(bp_history) 1872068SN/A { } 1882068SN/A 1892068SN/A bool operator==(const PredictorHistory &entry) const { 1902068SN/A return this->seqNum == entry.seqNum; 1912068SN/A } 1922068SN/A 1932068SN/A /** The sequence number for the predictor history entry. */ 1942068SN/A InstSeqNum seqNum; 1952068SN/A 1962068SN/A /** The PC associated with the sequence number. */ 1972068SN/A Addr PC; 1982068SN/A 1992068SN/A /** The RAS target (only valid if a return). */ 2002068SN/A Addr RASTarget; 2012068SN/A 2022068SN/A /** The RAS index of the instruction (only valid if a call). */ 2032068SN/A unsigned RASIndex; 2042068SN/A 2052068SN/A /** The thread id. */ 2062068SN/A unsigned tid; 2072068SN/A 2082068SN/A /** Whether or not it was predicted taken. */ 2092068SN/A bool predTaken; 2102068SN/A 2112068SN/A /** Whether or not the RAS was used. */ 2122068SN/A bool usedRAS; 2132068SN/A 2142068SN/A /** Whether or not the instruction was a call. */ 2152068SN/A bool wasCall; 2162068SN/A 2172068SN/A /** Pointer to the history object passed back from the branch 2182068SN/A * predictor. It is used to update or restore state of the 2192068SN/A * branch predictor. 2202068SN/A */ 2212068SN/A void *bpHistory; 2222068SN/A }; 2232068SN/A 2242068SN/A typedef std::list<PredictorHistory> History; 2252068SN/A typedef typename History::iterator HistoryIt; 2262068SN/A 2272068SN/A /** 2282068SN/A * The per-thread predictor history. This is used to update the predictor 2292068SN/A * as instructions are committed, or restore it to the proper state after 2302068SN/A * a squash. 2312068SN/A */ 2322068SN/A History predHist[Impl::MaxThreads]; 2332068SN/A 2342068SN/A /** The local branch predictor. */ 2352068SN/A LocalBP *localBP; 2362068SN/A 2372068SN/A /** The tournament branch predictor. */ 2382068SN/A TournamentBP *tournamentBP; 2392068SN/A 2402068SN/A /** The BTB. */ 2412068SN/A DefaultBTB BTB; 2422068SN/A 2432068SN/A /** The per-thread return address stack. */ 2442068SN/A ReturnAddrStack RAS[Impl::MaxThreads]; 2452068SN/A 2462068SN/A /** Stat for number of BP lookups. */ 2472068SN/A Stats::Scalar lookups; 2482068SN/A /** Stat for number of conditional branches predicted. */ 2492068SN/A Stats::Scalar condPredicted; 2502068SN/A /** Stat for number of conditional branches predicted incorrectly. */ 2512068SN/A Stats::Scalar condIncorrect; 2522068SN/A /** Stat for number of BTB lookups. */ 2532068SN/A Stats::Scalar BTBLookups; 2542068SN/A /** Stat for number of BTB hits. */ 2552068SN/A Stats::Scalar BTBHits; 2562068SN/A /** Stat for number of times the BTB is correct. */ 2572068SN/A Stats::Scalar BTBCorrect; 2582068SN/A /** Stat for number of times the RAS is used to get a target. */ 2592068SN/A Stats::Scalar usedRAS; 2602068SN/A /** Stat for number of times the RAS is incorrect. */ 2612068SN/A Stats::Scalar RASIncorrect; 2622068SN/A}; 2632068SN/A 2642068SN/A#endif // __CPU_O3_BPRED_UNIT_HH__ 2652068SN/A