bpred_unit.hh revision 11721:b0853929e223
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 97 // @todo: Rename this function. 98 virtual void uncondBranch(ThreadID tid, Addr pc, void * &bp_history) = 0; 99 100 /** 101 * Tells the branch predictor to commit any updates until the given 102 * sequence number. 103 * @param done_sn The sequence number to commit any older updates up until. 104 * @param tid The thread id. 105 */ 106 void update(const InstSeqNum &done_sn, ThreadID tid); 107 108 /** 109 * Squashes all outstanding updates until a given sequence number. 110 * @param squashed_sn The sequence number to squash any younger updates up 111 * until. 112 * @param tid The thread id. 113 */ 114 void squash(const InstSeqNum &squashed_sn, ThreadID tid); 115 116 /** 117 * Squashes all outstanding updates until a given sequence number, and 118 * corrects that sn's update with the proper address and taken/not taken. 119 * @param squashed_sn The sequence number to squash any younger updates up 120 * until. 121 * @param corr_target The correct branch target. 122 * @param actually_taken The correct branch direction. 123 * @param tid The thread id. 124 */ 125 void squash(const InstSeqNum &squashed_sn, 126 const TheISA::PCState &corr_target, 127 bool actually_taken, ThreadID tid); 128 129 /** 130 * @param bp_history Pointer to the history object. The predictor 131 * will need to update any state and delete the object. 132 */ 133 virtual void squash(ThreadID tid, void *bp_history) = 0; 134 135 /** 136 * Looks up a given PC in the BP to see if it is taken or not taken. 137 * @param inst_PC The PC to look up. 138 * @param bp_history Pointer that will be set to an object that 139 * has the branch predictor state associated with the lookup. 140 * @return Whether the branch is taken or not taken. 141 */ 142 virtual bool lookup(ThreadID tid, Addr instPC, void * &bp_history) = 0; 143 144 /** 145 * If a branch is not taken, because the BTB address is invalid or missing, 146 * this function sets the appropriate counter in the global and local 147 * predictors to not taken. 148 * @param inst_PC The PC to look up the local predictor. 149 * @param bp_history Pointer that will be set to an object that 150 * has the branch predictor state associated with the lookup. 151 */ 152 virtual void btbUpdate(ThreadID tid, Addr instPC, void * &bp_history) = 0; 153 154 /** 155 * Looks up a given PC in the BTB to see if a matching entry exists. 156 * @param inst_PC The PC to look up. 157 * @return Whether the BTB contains the given PC. 158 */ 159 bool BTBValid(Addr instPC) 160 { return BTB.valid(instPC, 0); } 161 162 /** 163 * Looks up a given PC in the BTB to get the predicted target. 164 * @param inst_PC The PC to look up. 165 * @return The address of the target of the branch. 166 */ 167 TheISA::PCState BTBLookup(Addr instPC) 168 { return BTB.lookup(instPC, 0); } 169 170 /** 171 * Updates the BP with taken/not taken information. 172 * @param inst_PC The branch's PC that will be updated. 173 * @param taken Whether the branch was taken or not taken. 174 * @param bp_history Pointer to the branch predictor state that is 175 * associated with the branch lookup that is being updated. 176 * @param squashed Set to true when this function is called during a 177 * squash operation. 178 * @todo Make this update flexible enough to handle a global predictor. 179 */ 180 virtual void update(ThreadID tid, Addr instPC, bool taken, 181 void *bp_history, bool squashed) = 0; 182 /** 183 * Deletes the associated history with a branch, performs no predictor 184 * updates. Used for branches that mispredict and update tables but 185 * are still speculative and later retire. 186 * @param bp_history History to delete associated with this predictor 187 */ 188 virtual void retireSquashed(ThreadID tid, void *bp_history) = 0; 189 190 /** 191 * Updates the BTB with the target of a branch. 192 * @param inst_PC The branch's PC that will be updated. 193 * @param target_PC The branch's target that will be added to the BTB. 194 */ 195 void BTBUpdate(Addr instPC, const TheISA::PCState &target) 196 { BTB.update(instPC, target, 0); } 197 198 199 virtual unsigned getGHR(ThreadID tid, void* bp_history) const { return 0; } 200 201 void dump(); 202 203 private: 204 struct PredictorHistory { 205 /** 206 * Makes a predictor history struct that contains any 207 * information needed to update the predictor, BTB, and RAS. 208 */ 209 PredictorHistory(const InstSeqNum &seq_num, Addr instPC, 210 bool pred_taken, void *bp_history, 211 ThreadID _tid) 212 : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0), 213 RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), 214 wasCall(0), wasReturn(0), wasSquashed(0), wasIndirect(0) 215 {} 216 217 bool operator==(const PredictorHistory &entry) const { 218 return this->seqNum == entry.seqNum; 219 } 220 221 /** The sequence number for the predictor history entry. */ 222 InstSeqNum seqNum; 223 224 /** The PC associated with the sequence number. */ 225 Addr pc; 226 227 /** Pointer to the history object passed back from the branch 228 * predictor. It is used to update or restore state of the 229 * branch predictor. 230 */ 231 void *bpHistory; 232 233 /** The RAS target (only valid if a return). */ 234 TheISA::PCState RASTarget; 235 236 /** The RAS index of the instruction (only valid if a call). */ 237 unsigned RASIndex; 238 239 /** The thread id. */ 240 ThreadID tid; 241 242 /** Whether or not it was predicted taken. */ 243 bool predTaken; 244 245 /** Whether or not the RAS was used. */ 246 bool usedRAS; 247 248 /* Whether or not the RAS was pushed */ 249 bool pushedRAS; 250 251 /** Whether or not the instruction was a call. */ 252 bool wasCall; 253 254 /** Whether or not the instruction was a return. */ 255 bool wasReturn; 256 257 /** Whether this instruction has already mispredicted/updated bp */ 258 bool wasSquashed; 259 260 /** Wether this instruction was an indirect branch */ 261 bool wasIndirect; 262 }; 263 264 typedef std::deque<PredictorHistory> History; 265 266 /** Number of the threads for which the branch history is maintained. */ 267 const unsigned numThreads; 268 269 270 /** 271 * The per-thread predictor history. This is used to update the predictor 272 * as instructions are committed, or restore it to the proper state after 273 * a squash. 274 */ 275 std::vector<History> predHist; 276 277 /** The BTB. */ 278 DefaultBTB BTB; 279 280 /** The per-thread return address stack. */ 281 std::vector<ReturnAddrStack> RAS; 282 283 /** Option to disable indirect predictor. */ 284 const bool useIndirect; 285 286 /** The indirect target predictor. */ 287 IndirectPredictor iPred; 288 289 /** Stat for number of BP lookups. */ 290 Stats::Scalar lookups; 291 /** Stat for number of conditional branches predicted. */ 292 Stats::Scalar condPredicted; 293 /** Stat for number of conditional branches predicted incorrectly. */ 294 Stats::Scalar condIncorrect; 295 /** Stat for number of BTB lookups. */ 296 Stats::Scalar BTBLookups; 297 /** Stat for number of BTB hits. */ 298 Stats::Scalar BTBHits; 299 /** Stat for number of times the BTB is correct. */ 300 Stats::Scalar BTBCorrect; 301 /** Stat for percent times an entry in BTB found. */ 302 Stats::Formula BTBHitPct; 303 /** Stat for number of times the RAS is used to get a target. */ 304 Stats::Scalar usedRAS; 305 /** Stat for number of times the RAS is incorrect. */ 306 Stats::Scalar RASIncorrect; 307 308 /** Stat for the number of indirect target lookups.*/ 309 Stats::Scalar indirectLookups; 310 /** Stat for the number of indirect target hits.*/ 311 Stats::Scalar indirectHits; 312 /** Stat for the number of indirect target misses.*/ 313 Stats::Scalar indirectMisses; 314 /** Stat for the number of indirect target mispredictions.*/ 315 Stats::Scalar indirectMispredicted; 316 317 protected: 318 /** Number of bits to shift instructions by for predictor addresses. */ 319 const unsigned instShiftAmt; 320 321 /** 322 * @{ 323 * @name PMU Probe points. 324 */ 325 326 /** 327 * Helper method to instantiate probe points belonging to this 328 * object. 329 * 330 * @param name Name of the probe point. 331 * @return A unique_ptr to the new probe point. 332 */ 333 ProbePoints::PMUUPtr pmuProbePoint(const char *name); 334 335 336 /** 337 * Branches seen by the branch predictor 338 * 339 * @note This counter includes speculative branches. 340 */ 341 ProbePoints::PMUUPtr ppBranches; 342 343 /** Miss-predicted branches */ 344 ProbePoints::PMUUPtr ppMisses; 345 346 /** @} */ 347}; 348 349#endif // __CPU_PRED_BPRED_UNIT_HH__ 350