bpred_unit.hh revision 9444
1/* 2 * Copyright (c) 2011-2012 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2004-2005 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Kevin Lim 41 */ 42 43#ifndef __CPU_O3_BPRED_UNIT_HH__ 44#define __CPU_O3_BPRED_UNIT_HH__ 45 46#include <list> 47 48#include "base/statistics.hh" 49#include "base/types.hh" 50#include "cpu/pred/2bit_local.hh" 51#include "cpu/pred/btb.hh" 52#include "cpu/pred/ras.hh" 53#include "cpu/pred/tournament.hh" 54#include "cpu/inst_seq.hh" 55 56struct DerivO3CPUParams; 57 58/** 59 * Basically a wrapper class to hold both the branch predictor 60 * and the BTB. 61 */ 62template<class Impl> 63class BPredUnit 64{ 65 private: 66 typedef typename Impl::DynInstPtr DynInstPtr; 67 68 enum PredType { 69 Local, 70 Tournament 71 }; 72 73 PredType predictor; 74 75 const std::string _name; 76 77 public: 78 79 /** 80 * @param params The params object, that has the size of the BP and BTB. 81 */ 82 BPredUnit(DerivO3CPUParams *params); 83 84 const std::string &name() const { return _name; } 85 86 /** 87 * Registers statistics. 88 */ 89 void regStats(); 90 91 /** Perform sanity checks after a drain. */ 92 void drainSanityCheck() const; 93 94 /** Take over execution from another CPU's thread. */ 95 void takeOverFrom(); 96 97 /** 98 * Predicts whether or not the instruction is a taken branch, and the 99 * target of the branch if it is taken. 100 * @param inst The branch instruction. 101 * @param PC The predicted PC is passed back through this parameter. 102 * @param tid The thread id. 103 * @return Returns if the branch is taken or not. 104 */ 105 bool predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid); 106 107 // @todo: Rename this function. 108 void BPUncond(void * &bp_history); 109 110 /** 111 * Tells the branch predictor to commit any updates until the given 112 * sequence number. 113 * @param done_sn The sequence number to commit any older updates up until. 114 * @param tid The thread id. 115 */ 116 void update(const InstSeqNum &done_sn, ThreadID tid); 117 118 /** 119 * Squashes all outstanding updates until a given sequence number. 120 * @param squashed_sn The sequence number to squash any younger updates up 121 * until. 122 * @param tid The thread id. 123 */ 124 void squash(const InstSeqNum &squashed_sn, ThreadID tid); 125 126 /** 127 * Squashes all outstanding updates until a given sequence number, and 128 * corrects that sn's update with the proper address and taken/not taken. 129 * @param squashed_sn The sequence number to squash any younger updates up 130 * until. 131 * @param corr_target The correct branch target. 132 * @param actually_taken The correct branch direction. 133 * @param tid The thread id. 134 */ 135 void squash(const InstSeqNum &squashed_sn, 136 const TheISA::PCState &corr_target, 137 bool actually_taken, ThreadID tid); 138 139 /** 140 * @param bp_history Pointer to the history object. The predictor 141 * will need to update any state and delete the object. 142 */ 143 void BPSquash(void *bp_history); 144 145 /** 146 * Looks up a given PC in the BP to see if it is taken or not taken. 147 * @param inst_PC The PC to look up. 148 * @param bp_history Pointer that will be set to an object that 149 * has the branch predictor state associated with the lookup. 150 * @return Whether the branch is taken or not taken. 151 */ 152 bool BPLookup(Addr instPC, void * &bp_history); 153 154 /** 155 * If a branch is not taken, because the BTB address is invalid or missing, 156 * this function sets the appropriate counter in the global and local 157 * predictors to not taken. 158 * @param inst_PC The PC to look up the local predictor. 159 * @param bp_history Pointer that will be set to an object that 160 * has the branch predictor state associated with the lookup. 161 */ 162 void BPBTBUpdate(Addr instPC, void * &bp_history); 163 164 /** 165 * Looks up a given PC in the BTB to see if a matching entry exists. 166 * @param inst_PC The PC to look up. 167 * @return Whether the BTB contains the given PC. 168 */ 169 bool BTBValid(Addr instPC) 170 { return BTB.valid(instPC, 0); } 171 172 /** 173 * Looks up a given PC in the BTB to get the predicted target. 174 * @param inst_PC The PC to look up. 175 * @return The address of the target of the branch. 176 */ 177 TheISA::PCState BTBLookup(Addr instPC) 178 { return BTB.lookup(instPC, 0); } 179 180 /** 181 * Updates the BP with taken/not taken information. 182 * @param inst_PC The branch's PC that will be updated. 183 * @param taken Whether the branch was taken or not taken. 184 * @param bp_history Pointer to the branch predictor state that is 185 * associated with the branch lookup that is being updated. 186 * @param squashed Set to true when this function is called during a 187 * squash operation. 188 * @todo Make this update flexible enough to handle a global predictor. 189 */ 190 void BPUpdate(Addr instPC, bool taken, void *bp_history, bool squashed); 191 192 /** 193 * Updates the BTB with the target of a branch. 194 * @param inst_PC The branch's PC that will be updated. 195 * @param target_PC The branch's target that will be added to the BTB. 196 */ 197 void BTBUpdate(Addr instPC, const TheISA::PCState &target) 198 { BTB.update(instPC, target, 0); } 199 200 void dump(); 201 202 private: 203 struct PredictorHistory { 204 /** 205 * Makes a predictor history struct that contains any 206 * information needed to update the predictor, BTB, and RAS. 207 */ 208 PredictorHistory(const InstSeqNum &seq_num, Addr instPC, 209 bool pred_taken, void *bp_history, 210 ThreadID _tid) 211 : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0), 212 RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), 213 wasCall(0), wasReturn(0), validBTB(0) 214 {} 215 216 bool operator==(const PredictorHistory &entry) const { 217 return this->seqNum == entry.seqNum; 218 } 219 220 /** The sequence number for the predictor history entry. */ 221 InstSeqNum seqNum; 222 223 /** The PC associated with the sequence number. */ 224 Addr pc; 225 226 /** Pointer to the history object passed back from the branch 227 * predictor. It is used to update or restore state of the 228 * branch predictor. 229 */ 230 void *bpHistory; 231 232 /** The RAS target (only valid if a return). */ 233 TheISA::PCState RASTarget; 234 235 /** The RAS index of the instruction (only valid if a call). */ 236 unsigned RASIndex; 237 238 /** The thread id. */ 239 ThreadID tid; 240 241 /** Whether or not it was predicted taken. */ 242 bool predTaken; 243 244 /** Whether or not the RAS was used. */ 245 bool usedRAS; 246 247 /* Wether or not the RAS was pushed */ 248 bool pushedRAS; 249 250 /** Whether or not the instruction was a call. */ 251 bool wasCall; 252 253 /** Whether or not the instruction was a return. */ 254 bool wasReturn; 255 /** Whether or not the instruction had a valid BTB entry. */ 256 bool validBTB; 257 }; 258 259 typedef std::list<PredictorHistory> History; 260 typedef typename History::iterator HistoryIt; 261 262 /** 263 * The per-thread predictor history. This is used to update the predictor 264 * as instructions are committed, or restore it to the proper state after 265 * a squash. 266 */ 267 History predHist[Impl::MaxThreads]; 268 269 /** The local branch predictor. */ 270 LocalBP *localBP; 271 272 /** The tournament branch predictor. */ 273 TournamentBP *tournamentBP; 274 275 /** The BTB. */ 276 DefaultBTB BTB; 277 278 /** The per-thread return address stack. */ 279 ReturnAddrStack RAS[Impl::MaxThreads]; 280 281 /** Stat for number of BP lookups. */ 282 Stats::Scalar lookups; 283 /** Stat for number of conditional branches predicted. */ 284 Stats::Scalar condPredicted; 285 /** Stat for number of conditional branches predicted incorrectly. */ 286 Stats::Scalar condIncorrect; 287 /** Stat for number of BTB lookups. */ 288 Stats::Scalar BTBLookups; 289 /** Stat for number of BTB hits. */ 290 Stats::Scalar BTBHits; 291 /** Stat for number of times the BTB is correct. */ 292 Stats::Scalar BTBCorrect; 293 /** Stat for number of times the RAS is used to get a target. */ 294 Stats::Scalar usedRAS; 295 /** Stat for number of times the RAS is incorrect. */ 296 Stats::Scalar RASIncorrect; 297}; 298 299#endif // __CPU_O3_BPRED_UNIT_HH__ 300