bpred_unit.hh revision 6005
12381SN/A/* 213732Snikos.nikoleris@arm.com * Copyright (c) 2004-2005 The Regents of The University of Michigan 38949Sandreas.hansson@arm.com * All rights reserved. 48949Sandreas.hansson@arm.com * 58949Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 68949Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 78949Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 88949Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 98949Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 108949Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 118949Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 128949Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 138949Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 142592SN/A * this software without specific prior written permission. 1510975Sdavid.hashe@amd.com * 162381SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172381SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182381SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192381SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202381SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212381SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222381SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232381SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242381SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252381SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262381SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272381SN/A * 282381SN/A * Authors: Kevin Lim 292381SN/A */ 302381SN/A 312381SN/A#ifndef __CPU_O3_BPRED_UNIT_HH__ 322381SN/A#define __CPU_O3_BPRED_UNIT_HH__ 332381SN/A 342381SN/A#include "base/statistics.hh" 352381SN/A#include "cpu/inst_seq.hh" 362381SN/A 372381SN/A#include "cpu/o3/2bit_local_pred.hh" 382381SN/A#include "cpu/o3/btb.hh" 392381SN/A#include "cpu/o3/ras.hh" 402665Ssaidi@eecs.umich.edu#include "cpu/o3/tournament_pred.hh" 412665Ssaidi@eecs.umich.edu 422665Ssaidi@eecs.umich.edu#include "sim/host.hh" 432665Ssaidi@eecs.umich.edu 449031Sandreas.hansson@arm.com#include <list> 4512349Snikos.nikoleris@arm.com 462381SN/Aclass DerivO3CPUParams; 472381SN/A 482381SN/A/** 492381SN/A * Basically a wrapper class to hold both the branch predictor 502662Sstever@eecs.umich.edu * and the BTB. 512381SN/A */ 522381SN/Atemplate<class Impl> 532381SN/Aclass BPredUnit 542381SN/A{ 552381SN/A private: 568229Snate@binkert.org typedef typename Impl::DynInstPtr DynInstPtr; 573348Sbinkertn@umich.edu 583348Sbinkertn@umich.edu enum PredType { 593348Sbinkertn@umich.edu Local, 6013856Sodanrc@yahoo.com.br Tournament 615735Snate@binkert.org }; 624024Sbinkertn@umich.edu 635735Snate@binkert.org PredType predictor; 6412334Sgabeblack@google.com 655314Sstever@gmail.com const std::string _name; 666216Snate@binkert.org 6713347Sgabeblack@google.com public: 682392SN/A 694167Sbinkertn@umich.edu /** 702394SN/A * @param params The params object, that has the size of the BP and BTB. 718737Skoansin.tan@gmail.com */ 723349Sbinkertn@umich.edu BPredUnit(DerivO3CPUParams *params); 732394SN/A 742812Srdreslin@umich.edu const std::string &name() const { return _name; } 7512351Snikos.nikoleris@arm.com 762812Srdreslin@umich.edu /** 774022Sstever@eecs.umich.edu * Registers statistics. 784022Sstever@eecs.umich.edu */ 795735Snate@binkert.org void regStats(); 805735Snate@binkert.org 814022Sstever@eecs.umich.edu void switchOut(); 825735Snate@binkert.org 835735Snate@binkert.org void takeOverFrom(); 845735Snate@binkert.org 854022Sstever@eecs.umich.edu /** 864022Sstever@eecs.umich.edu * Predicts whether or not the instruction is a taken branch, and the 874022Sstever@eecs.umich.edu * target of the branch if it is taken. 884022Sstever@eecs.umich.edu * @param inst The branch instruction. 894473Sstever@eecs.umich.edu * @param PC The predicted PC is passed back through this parameter. 905319Sstever@gmail.com * @param tid The thread id. 914022Sstever@eecs.umich.edu * @return Returns if the branch is taken or not. 924022Sstever@eecs.umich.edu */ 9311199Sandreas.hansson@arm.com bool predict(DynInstPtr &inst, Addr &PC, unsigned tid); 9411199Sandreas.hansson@arm.com 9512344Snikos.nikoleris@arm.com // @todo: Rename this function. 9610883Sali.jafri@arm.com void BPUncond(void * &bp_history); 974022Sstever@eecs.umich.edu 9813367Syuetsu.kodama@riken.jp /** 994022Sstever@eecs.umich.edu * Tells the branch predictor to commit any updates until the given 1004022Sstever@eecs.umich.edu * sequence number. 1014022Sstever@eecs.umich.edu * @param done_sn The sequence number to commit any older updates up until. 10210886Sandreas.hansson@arm.com * @param tid The thread id. 1034022Sstever@eecs.umich.edu */ 1047465Ssteve.reinhardt@amd.com void update(const InstSeqNum &done_sn, unsigned tid); 1054628Sstever@eecs.umich.edu 1067465Ssteve.reinhardt@amd.com /** 1077465Ssteve.reinhardt@amd.com * Squashes all outstanding updates until a given sequence number. 1084022Sstever@eecs.umich.edu * @param squashed_sn The sequence number to squash any younger updates up 1094022Sstever@eecs.umich.edu * until. 11010885Sandreas.hansson@arm.com * @param tid The thread id. 11110885Sandreas.hansson@arm.com */ 1124626Sstever@eecs.umich.edu void squash(const InstSeqNum &squashed_sn, unsigned tid); 1134626Sstever@eecs.umich.edu 1147669Ssteve.reinhardt@amd.com /** 1154626Sstever@eecs.umich.edu * Squashes all outstanding updates until a given sequence number, and 1164040Ssaidi@eecs.umich.edu * corrects that sn's update with the proper address and taken/not taken. 1174040Ssaidi@eecs.umich.edu * @param squashed_sn The sequence number to squash any younger updates up 1185650Sgblack@eecs.umich.edu * until. 1195650Sgblack@eecs.umich.edu * @param corr_target The correct branch target. 12011256Santhony.gutierrez@amd.com * @param actually_taken The correct branch direction. 12111256Santhony.gutierrez@amd.com * @param tid The thread id. 12212347Snikos.nikoleris@arm.com */ 12312347Snikos.nikoleris@arm.com void squash(const InstSeqNum &squashed_sn, const Addr &corr_target, 12412347Snikos.nikoleris@arm.com bool actually_taken, unsigned tid); 12512347Snikos.nikoleris@arm.com 1264870Sstever@eecs.umich.edu /** 1274870Sstever@eecs.umich.edu * @param bp_history Pointer to the history object. The predictor 1284870Sstever@eecs.umich.edu * will need to update any state and delete the object. 1294870Sstever@eecs.umich.edu */ 1304870Sstever@eecs.umich.edu void BPSquash(void *bp_history); 1314870Sstever@eecs.umich.edu 1328436SBrad.Beckmann@amd.com /** 1338436SBrad.Beckmann@amd.com * Looks up a given PC in the BP to see if it is taken or not taken. 1345314Sstever@gmail.com * @param inst_PC The PC to look up. 1355314Sstever@gmail.com * @param bp_history Pointer that will be set to an object that 1368184Ssomayeh@cs.wisc.edu * has the branch predictor state associated with the lookup. 13710886Sandreas.hansson@arm.com * @return Whether the branch is taken or not taken. 13810886Sandreas.hansson@arm.com */ 1394022Sstever@eecs.umich.edu bool BPLookup(Addr &inst_PC, void * &bp_history); 1404022Sstever@eecs.umich.edu 1414022Sstever@eecs.umich.edu /** 1424022Sstever@eecs.umich.edu * Looks up a given PC in the BTB to see if a matching entry exists. 1435735Snate@binkert.org * @param inst_PC The PC to look up. 1445735Snate@binkert.org * @return Whether the BTB contains the given PC. 1455735Snate@binkert.org */ 1464022Sstever@eecs.umich.edu bool BTBValid(Addr &inst_PC) 1474022Sstever@eecs.umich.edu { return BTB.valid(inst_PC, 0); } 1484626Sstever@eecs.umich.edu 1494626Sstever@eecs.umich.edu /** 1507465Ssteve.reinhardt@amd.com * Looks up a given PC in the BTB to get the predicted target. 1514022Sstever@eecs.umich.edu * @param inst_PC The PC to look up. 15212347Snikos.nikoleris@arm.com * @return The address of the target of the branch. 15311284Sandreas.hansson@arm.com */ 1544626Sstever@eecs.umich.edu Addr BTBLookup(Addr &inst_PC) 1554626Sstever@eecs.umich.edu { return BTB.lookup(inst_PC, 0); } 1564626Sstever@eecs.umich.edu 15711199Sandreas.hansson@arm.com /** 1584022Sstever@eecs.umich.edu * Updates the BP with taken/not taken information. 1594022Sstever@eecs.umich.edu * @param inst_PC The branch's PC that will be updated. 1606076Sgblack@eecs.umich.edu * @param taken Whether the branch was taken or not taken. 1614626Sstever@eecs.umich.edu * @param bp_history Pointer to the branch predictor state that is 1624870Sstever@eecs.umich.edu * associated with the branch lookup that is being updated. 1635314Sstever@gmail.com * @todo Make this update flexible enough to handle a global predictor. 1648184Ssomayeh@cs.wisc.edu */ 16511600Sandreas.hansson@arm.com void BPUpdate(Addr &inst_PC, bool taken, void *bp_history); 1664022Sstever@eecs.umich.edu 1674022Sstever@eecs.umich.edu /** 1684022Sstever@eecs.umich.edu * Updates the BTB with the target of a branch. 1695735Snate@binkert.org * @param inst_PC The branch's PC that will be updated. 1705735Snate@binkert.org * @param target_PC The branch's target that will be added to the BTB. 1715735Snate@binkert.org */ 1725735Snate@binkert.org void BTBUpdate(Addr &inst_PC, Addr &target_PC) 1735735Snate@binkert.org { BTB.update(inst_PC, target_PC,0); } 1745735Snate@binkert.org 1755735Snate@binkert.org void dump(); 1764022Sstever@eecs.umich.edu 1775735Snate@binkert.org private: 1785735Snate@binkert.org struct PredictorHistory { 1794022Sstever@eecs.umich.edu /** 1805735Snate@binkert.org * Makes a predictor history struct that contains any 1814022Sstever@eecs.umich.edu * information needed to update the predictor, BTB, and RAS. 1824022Sstever@eecs.umich.edu */ 1834022Sstever@eecs.umich.edu PredictorHistory(const InstSeqNum &seq_num, const Addr &inst_PC, 1845735Snate@binkert.org const bool pred_taken, void *bp_history, 1854022Sstever@eecs.umich.edu const unsigned _tid) 1864022Sstever@eecs.umich.edu : seqNum(seq_num), PC(inst_PC), RASTarget(0), 1874022Sstever@eecs.umich.edu RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), 1884022Sstever@eecs.umich.edu wasCall(0), bpHistory(bp_history) 1894022Sstever@eecs.umich.edu { } 1904022Sstever@eecs.umich.edu 1915735Snate@binkert.org /** The sequence number for the predictor history entry. */ 1925735Snate@binkert.org InstSeqNum seqNum; 1935735Snate@binkert.org 1944022Sstever@eecs.umich.edu /** The PC associated with the sequence number. */ 1954022Sstever@eecs.umich.edu Addr PC; 1964022Sstever@eecs.umich.edu 1974022Sstever@eecs.umich.edu /** The RAS target (only valid if a return). */ 1984022Sstever@eecs.umich.edu Addr RASTarget; 19910583SCurtis.Dunham@arm.com 20010583SCurtis.Dunham@arm.com /** The RAS index of the instruction (only valid if a call). */ 20110583SCurtis.Dunham@arm.com unsigned RASIndex; 20210583SCurtis.Dunham@arm.com 20310583SCurtis.Dunham@arm.com /** The thread id. */ 20411284Sandreas.hansson@arm.com unsigned tid; 20510583SCurtis.Dunham@arm.com 20610583SCurtis.Dunham@arm.com /** Whether or not it was predicted taken. */ 20711199Sandreas.hansson@arm.com bool predTaken; 20812347Snikos.nikoleris@arm.com 20911600Sandreas.hansson@arm.com /** Whether or not the RAS was used. */ 21011199Sandreas.hansson@arm.com bool usedRAS; 21111199Sandreas.hansson@arm.com 21211199Sandreas.hansson@arm.com /** Whether or not the instruction was a call. */ 21311199Sandreas.hansson@arm.com bool wasCall; 21411199Sandreas.hansson@arm.com 21511199Sandreas.hansson@arm.com /** Pointer to the history object passed back from the branch 21610570Sandreas.hansson@arm.com * predictor. It is used to update or restore state of the 21710570Sandreas.hansson@arm.com * branch predictor. 21810570Sandreas.hansson@arm.com */ 21910570Sandreas.hansson@arm.com void *bpHistory; 22010570Sandreas.hansson@arm.com }; 22110570Sandreas.hansson@arm.com 2224022Sstever@eecs.umich.edu typedef std::list<PredictorHistory> History; 2236102Sgblack@eecs.umich.edu 22410343SCurtis.Dunham@arm.com /** 22510343SCurtis.Dunham@arm.com * The per-thread predictor history. This is used to update the predictor 22610343SCurtis.Dunham@arm.com * as instructions are committed, or restore it to the proper state after 22710343SCurtis.Dunham@arm.com * a squash. 2284870Sstever@eecs.umich.edu */ 2295314Sstever@gmail.com History predHist[Impl::MaxThreads]; 2308184Ssomayeh@cs.wisc.edu 2314022Sstever@eecs.umich.edu /** The local branch predictor. */ 23211294Sandreas.hansson@arm.com LocalBP *localBP; 2335735Snate@binkert.org 2345735Snate@binkert.org /** The tournament branch predictor. */ 2354022Sstever@eecs.umich.edu TournamentBP *tournamentBP; 2364022Sstever@eecs.umich.edu 2374022Sstever@eecs.umich.edu /** The BTB. */ 2385735Snate@binkert.org DefaultBTB BTB; 2395735Snate@binkert.org 2404022Sstever@eecs.umich.edu /** The per-thread return address stack. */ 2414022Sstever@eecs.umich.edu ReturnAddrStack RAS[Impl::MaxThreads]; 2425735Snate@binkert.org 2435735Snate@binkert.org /** Stat for number of BP lookups. */ 2445735Snate@binkert.org Stats::Scalar lookups; 2454022Sstever@eecs.umich.edu /** Stat for number of conditional branches predicted. */ 2465735Snate@binkert.org Stats::Scalar condPredicted; 2475735Snate@binkert.org /** Stat for number of conditional branches predicted incorrectly. */ 2484022Sstever@eecs.umich.edu Stats::Scalar condIncorrect; 2494022Sstever@eecs.umich.edu /** Stat for number of BTB lookups. */ 2502381SN/A Stats::Scalar BTBLookups; 2512662Sstever@eecs.umich.edu /** Stat for number of BTB hits. */ 2522662Sstever@eecs.umich.edu Stats::Scalar BTBHits; 2532662Sstever@eecs.umich.edu /** Stat for number of times the BTB is correct. */ 2542662Sstever@eecs.umich.edu Stats::Scalar BTBCorrect; 2552662Sstever@eecs.umich.edu /** Stat for number of times the RAS is used to get a target. */ 2562381SN/A Stats::Scalar usedRAS; 2579044SAli.Saidi@ARM.com /** Stat for number of times the RAS is incorrect. */ 2582381SN/A Stats::Scalar RASIncorrect; 2592813Srdreslin@umich.edu}; 2605735Snate@binkert.org 2615735Snate@binkert.org#endif // __CPU_O3_BPRED_UNIT_HH__ 2624022Sstever@eecs.umich.edu