bpred_unit.hh revision 11426:fb9d14204674
1/* 2 * Copyright (c) 2011-2012, 2014 ARM Limited 3 * Copyright (c) 2010 The University of Edinburgh 4 * All rights reserved 5 * 6 * The license below extends only to copyright in the software and shall 7 * not be construed as granting a license to any other intellectual 8 * property including but not limited to intellectual property relating 9 * to a hardware implementation of the functionality of the software 10 * licensed hereunder. You may use the software subject to the license 11 * terms below provided that you ensure that this notice is replicated 12 * unmodified and in its entirety in all distributions of the software, 13 * modified or unmodified, in source code or in binary form. 14 * 15 * Copyright (c) 2004-2005 The Regents of The University of Michigan 16 * All rights reserved. 17 * 18 * Redistribution and use in source and binary forms, with or without 19 * modification, are permitted provided that the following conditions are 20 * met: redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer; 22 * redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution; 25 * neither the name of the copyright holders nor the names of its 26 * contributors may be used to endorse or promote products derived from 27 * this software without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 40 * 41 * Authors: Kevin Lim 42 * Korey Sewell 43 * Timothy M. Jones 44 * Nilay Vaish 45 */ 46 47#ifndef __CPU_PRED_BPRED_UNIT_HH__ 48#define __CPU_PRED_BPRED_UNIT_HH__ 49 50#include <deque> 51 52#include "base/statistics.hh" 53#include "base/types.hh" 54#include "cpu/pred/btb.hh" 55#include "cpu/pred/indirect.hh" 56#include "cpu/pred/ras.hh" 57#include "cpu/inst_seq.hh" 58#include "cpu/static_inst.hh" 59#include "params/BranchPredictor.hh" 60#include "sim/probe/pmu.hh" 61#include "sim/sim_object.hh" 62 63/** 64 * Basically a wrapper class to hold both the branch predictor 65 * and the BTB. 66 */ 67class BPredUnit : public SimObject 68{ 69 public: 70 typedef BranchPredictorParams Params; 71 /** 72 * @param params The params object, that has the size of the BP and BTB. 73 */ 74 BPredUnit(const Params *p); 75 76 /** 77 * Registers statistics. 78 */ 79 void regStats() override; 80 81 void regProbePoints() override; 82 83 /** Perform sanity checks after a drain. */ 84 void drainSanityCheck() const; 85 86 /** 87 * Predicts whether or not the instruction is a taken branch, and the 88 * target of the branch if it is taken. 89 * @param inst The branch instruction. 90 * @param PC The predicted PC is passed back through this parameter. 91 * @param tid The thread id. 92 * @return Returns if the branch is taken or not. 93 */ 94 bool predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 95 TheISA::PCState &pc, ThreadID tid); 96 bool predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum, 97 int asid, TheISA::PCState &instPC, 98 TheISA::PCState &predPC, ThreadID tid); 99 100 // @todo: Rename this function. 101 virtual void uncondBranch(Addr pc, void * &bp_history) = 0; 102 103 /** 104 * Tells the branch predictor to commit any updates until the given 105 * sequence number. 106 * @param done_sn The sequence number to commit any older updates up until. 107 * @param tid The thread id. 108 */ 109 void update(const InstSeqNum &done_sn, ThreadID tid); 110 111 /** 112 * Squashes all outstanding updates until a given sequence number. 113 * @param squashed_sn The sequence number to squash any younger updates up 114 * until. 115 * @param tid The thread id. 116 */ 117 void squash(const InstSeqNum &squashed_sn, ThreadID tid); 118 119 /** 120 * Squashes all outstanding updates until a given sequence number, and 121 * corrects that sn's update with the proper address and taken/not taken. 122 * @param squashed_sn The sequence number to squash any younger updates up 123 * until. 124 * @param corr_target The correct branch target. 125 * @param actually_taken The correct branch direction. 126 * @param tid The thread id. 127 */ 128 void squash(const InstSeqNum &squashed_sn, 129 const TheISA::PCState &corr_target, 130 bool actually_taken, ThreadID tid); 131 132 /** 133 * @param bp_history Pointer to the history object. The predictor 134 * will need to update any state and delete the object. 135 */ 136 virtual void squash(void *bp_history) = 0; 137 138 /** 139 * Looks up a given PC in the BP to see if it is taken or not taken. 140 * @param inst_PC The PC to look up. 141 * @param bp_history Pointer that will be set to an object that 142 * has the branch predictor state associated with the lookup. 143 * @return Whether the branch is taken or not taken. 144 */ 145 virtual bool lookup(Addr instPC, void * &bp_history) = 0; 146 147 /** 148 * If a branch is not taken, because the BTB address is invalid or missing, 149 * this function sets the appropriate counter in the global and local 150 * predictors to not taken. 151 * @param inst_PC The PC to look up the local predictor. 152 * @param bp_history Pointer that will be set to an object that 153 * has the branch predictor state associated with the lookup. 154 */ 155 virtual void btbUpdate(Addr instPC, void * &bp_history) = 0; 156 157 /** 158 * Looks up a given PC in the BTB to see if a matching entry exists. 159 * @param inst_PC The PC to look up. 160 * @return Whether the BTB contains the given PC. 161 */ 162 bool BTBValid(Addr instPC) 163 { return BTB.valid(instPC, 0); } 164 165 /** 166 * Looks up a given PC in the BTB to get the predicted target. 167 * @param inst_PC The PC to look up. 168 * @return The address of the target of the branch. 169 */ 170 TheISA::PCState BTBLookup(Addr instPC) 171 { return BTB.lookup(instPC, 0); } 172 173 /** 174 * Updates the BP with taken/not taken information. 175 * @param inst_PC The branch's PC that will be updated. 176 * @param taken Whether the branch was taken or not taken. 177 * @param bp_history Pointer to the branch predictor state that is 178 * associated with the branch lookup that is being updated. 179 * @param squashed Set to true when this function is called during a 180 * squash operation. 181 * @todo Make this update flexible enough to handle a global predictor. 182 */ 183 virtual void update(Addr instPC, bool taken, void *bp_history, 184 bool squashed) = 0; 185 /** 186 * Deletes the associated history with a branch, performs no predictor 187 * updates. Used for branches that mispredict and update tables but 188 * are still speculative and later retire. 189 * @param bp_history History to delete associated with this predictor 190 */ 191 virtual void retireSquashed(void *bp_history) = 0; 192 193 /** 194 * Updates the BTB with the target of a branch. 195 * @param inst_PC The branch's PC that will be updated. 196 * @param target_PC The branch's target that will be added to the BTB. 197 */ 198 void BTBUpdate(Addr instPC, const TheISA::PCState &target) 199 { BTB.update(instPC, target, 0); } 200 201 202 virtual unsigned getGHR(void* bp_history) const { return 0; } 203 204 void dump(); 205 206 private: 207 struct PredictorHistory { 208 /** 209 * Makes a predictor history struct that contains any 210 * information needed to update the predictor, BTB, and RAS. 211 */ 212 PredictorHistory(const InstSeqNum &seq_num, Addr instPC, 213 bool pred_taken, void *bp_history, 214 ThreadID _tid) 215 : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0), 216 RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), 217 wasCall(0), wasReturn(0), wasSquashed(0), wasIndirect(0) 218 {} 219 220 bool operator==(const PredictorHistory &entry) const { 221 return this->seqNum == entry.seqNum; 222 } 223 224 /** The sequence number for the predictor history entry. */ 225 InstSeqNum seqNum; 226 227 /** The PC associated with the sequence number. */ 228 Addr pc; 229 230 /** Pointer to the history object passed back from the branch 231 * predictor. It is used to update or restore state of the 232 * branch predictor. 233 */ 234 void *bpHistory; 235 236 /** The RAS target (only valid if a return). */ 237 TheISA::PCState RASTarget; 238 239 /** The RAS index of the instruction (only valid if a call). */ 240 unsigned RASIndex; 241 242 /** The thread id. */ 243 ThreadID tid; 244 245 /** Whether or not it was predicted taken. */ 246 bool predTaken; 247 248 /** Whether or not the RAS was used. */ 249 bool usedRAS; 250 251 /* Whether or not the RAS was pushed */ 252 bool pushedRAS; 253 254 /** Whether or not the instruction was a call. */ 255 bool wasCall; 256 257 /** Whether or not the instruction was a return. */ 258 bool wasReturn; 259 260 /** Whether this instruction has already mispredicted/updated bp */ 261 bool wasSquashed; 262 263 /** Wether this instruction was an indirect branch */ 264 bool wasIndirect; 265 }; 266 267 typedef std::deque<PredictorHistory> History; 268 269 /** Number of the threads for which the branch history is maintained. */ 270 const unsigned numThreads; 271 272 273 /** 274 * The per-thread predictor history. This is used to update the predictor 275 * as instructions are committed, or restore it to the proper state after 276 * a squash. 277 */ 278 std::vector<History> predHist; 279 280 /** The BTB. */ 281 DefaultBTB BTB; 282 283 /** The per-thread return address stack. */ 284 std::vector<ReturnAddrStack> RAS; 285 286 /** Option to disable indirect predictor. */ 287 const bool useIndirect; 288 289 /** The indirect target predictor. */ 290 IndirectPredictor iPred; 291 292 /** Stat for number of BP lookups. */ 293 Stats::Scalar lookups; 294 /** Stat for number of conditional branches predicted. */ 295 Stats::Scalar condPredicted; 296 /** Stat for number of conditional branches predicted incorrectly. */ 297 Stats::Scalar condIncorrect; 298 /** Stat for number of BTB lookups. */ 299 Stats::Scalar BTBLookups; 300 /** Stat for number of BTB hits. */ 301 Stats::Scalar BTBHits; 302 /** Stat for number of times the BTB is correct. */ 303 Stats::Scalar BTBCorrect; 304 /** Stat for percent times an entry in BTB found. */ 305 Stats::Formula BTBHitPct; 306 /** Stat for number of times the RAS is used to get a target. */ 307 Stats::Scalar usedRAS; 308 /** Stat for number of times the RAS is incorrect. */ 309 Stats::Scalar RASIncorrect; 310 311 /** Stat for the number of indirect target lookups.*/ 312 Stats::Scalar indirectLookups; 313 /** Stat for the number of indirect target hits.*/ 314 Stats::Scalar indirectHits; 315 /** Stat for the number of indirect target misses.*/ 316 Stats::Scalar indirectMisses; 317 /** Stat for the number of indirect target mispredictions.*/ 318 Stats::Scalar indirectMispredicted; 319 320 protected: 321 /** Number of bits to shift instructions by for predictor addresses. */ 322 const unsigned instShiftAmt; 323 324 /** 325 * @{ 326 * @name PMU Probe points. 327 */ 328 329 /** 330 * Helper method to instantiate probe points belonging to this 331 * object. 332 * 333 * @param name Name of the probe point. 334 * @return A unique_ptr to the new probe point. 335 */ 336 ProbePoints::PMUUPtr pmuProbePoint(const char *name); 337 338 339 /** 340 * Branches seen by the branch predictor 341 * 342 * @note This counter includes speculative branches. 343 */ 344 ProbePoints::PMUUPtr ppBranches; 345 346 /** Miss-predicted branches */ 347 ProbePoints::PMUUPtr ppMisses; 348 349 /** @} */ 350}; 351 352#endif // __CPU_PRED_BPRED_UNIT_HH__ 353