bpred_unit.hh revision 10330
111986Sandreas.sandberg@arm.com/* 211986Sandreas.sandberg@arm.com * Copyright (c) 2011-2012, 2014 ARM Limited 311986Sandreas.sandberg@arm.com * Copyright (c) 2010 The University of Edinburgh 411986Sandreas.sandberg@arm.com * All rights reserved 511986Sandreas.sandberg@arm.com * 611986Sandreas.sandberg@arm.com * The license below extends only to copyright in the software and shall 711986Sandreas.sandberg@arm.com * not be construed as granting a license to any other intellectual 811986Sandreas.sandberg@arm.com * property including but not limited to intellectual property relating 911986Sandreas.sandberg@arm.com * to a hardware implementation of the functionality of the software 1011986Sandreas.sandberg@arm.com * licensed hereunder. You may use the software subject to the license 1111986Sandreas.sandberg@arm.com * terms below provided that you ensure that this notice is replicated 1211986Sandreas.sandberg@arm.com * unmodified and in its entirety in all distributions of the software, 1311986Sandreas.sandberg@arm.com * modified or unmodified, in source code or in binary form. 1411986Sandreas.sandberg@arm.com * 1511986Sandreas.sandberg@arm.com * Copyright (c) 2004-2005 The Regents of The University of Michigan 1611986Sandreas.sandberg@arm.com * All rights reserved. 1711986Sandreas.sandberg@arm.com * 1811986Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 1911986Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 2011986Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright 2111986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer; 2211986Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright 2311986Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 2411986Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution; 2511986Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 2611986Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 2711986Sandreas.sandberg@arm.com * this software without specific prior written permission. 2811986Sandreas.sandberg@arm.com * 2911986Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 3011986Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3111986Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3211986Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3311986Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3411986Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3511986Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3611986Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3711986Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3811986Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3911986Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 4011986Sandreas.sandberg@arm.com * 4111986Sandreas.sandberg@arm.com * Authors: Kevin Lim 4211986Sandreas.sandberg@arm.com * Korey Sewell 4311986Sandreas.sandberg@arm.com * Timothy M. Jones 4411986Sandreas.sandberg@arm.com * Nilay Vaish 4511986Sandreas.sandberg@arm.com */ 4611986Sandreas.sandberg@arm.com 4711986Sandreas.sandberg@arm.com#ifndef __CPU_PRED_BPRED_UNIT_HH__ 4811986Sandreas.sandberg@arm.com#define __CPU_PRED_BPRED_UNIT_HH__ 4911986Sandreas.sandberg@arm.com 5011986Sandreas.sandberg@arm.com#include <deque> 5111986Sandreas.sandberg@arm.com 5211986Sandreas.sandberg@arm.com#include "base/statistics.hh" 5311986Sandreas.sandberg@arm.com#include "base/types.hh" 5411986Sandreas.sandberg@arm.com#include "cpu/pred/btb.hh" 5511986Sandreas.sandberg@arm.com#include "cpu/pred/ras.hh" 5611986Sandreas.sandberg@arm.com#include "cpu/inst_seq.hh" 5711986Sandreas.sandberg@arm.com#include "cpu/static_inst.hh" 5811986Sandreas.sandberg@arm.com#include "params/BranchPredictor.hh" 5911986Sandreas.sandberg@arm.com#include "sim/sim_object.hh" 6011986Sandreas.sandberg@arm.com 6111986Sandreas.sandberg@arm.com/** 6211986Sandreas.sandberg@arm.com * Basically a wrapper class to hold both the branch predictor 6311986Sandreas.sandberg@arm.com * and the BTB. 6411986Sandreas.sandberg@arm.com */ 6511986Sandreas.sandberg@arm.comclass BPredUnit : public SimObject 6611986Sandreas.sandberg@arm.com{ 6711986Sandreas.sandberg@arm.com public: 6811986Sandreas.sandberg@arm.com typedef BranchPredictorParams Params; 6911986Sandreas.sandberg@arm.com /** 7011986Sandreas.sandberg@arm.com * @param params The params object, that has the size of the BP and BTB. 7111986Sandreas.sandberg@arm.com */ 7211986Sandreas.sandberg@arm.com BPredUnit(const Params *p); 7311986Sandreas.sandberg@arm.com 7411986Sandreas.sandberg@arm.com /** 7511986Sandreas.sandberg@arm.com * Registers statistics. 7611986Sandreas.sandberg@arm.com */ 7711986Sandreas.sandberg@arm.com void regStats(); 7811986Sandreas.sandberg@arm.com 7911986Sandreas.sandberg@arm.com /** Perform sanity checks after a drain. */ 8011986Sandreas.sandberg@arm.com void drainSanityCheck() const; 8111986Sandreas.sandberg@arm.com 8211986Sandreas.sandberg@arm.com /** 8311986Sandreas.sandberg@arm.com * Predicts whether or not the instruction is a taken branch, and the 8411986Sandreas.sandberg@arm.com * target of the branch if it is taken. 8511986Sandreas.sandberg@arm.com * @param inst The branch instruction. 8611986Sandreas.sandberg@arm.com * @param PC The predicted PC is passed back through this parameter. 8711986Sandreas.sandberg@arm.com * @param tid The thread id. 8811986Sandreas.sandberg@arm.com * @return Returns if the branch is taken or not. 8911986Sandreas.sandberg@arm.com */ 9011986Sandreas.sandberg@arm.com bool predict(StaticInstPtr &inst, const InstSeqNum &seqNum, 9111986Sandreas.sandberg@arm.com TheISA::PCState &pc, ThreadID tid); 9211986Sandreas.sandberg@arm.com bool predictInOrder(StaticInstPtr &inst, const InstSeqNum &seqNum, 9311986Sandreas.sandberg@arm.com int asid, TheISA::PCState &instPC, 9411986Sandreas.sandberg@arm.com TheISA::PCState &predPC, ThreadID tid); 9511986Sandreas.sandberg@arm.com 9611986Sandreas.sandberg@arm.com // @todo: Rename this function. 9711986Sandreas.sandberg@arm.com virtual void uncondBranch(void * &bp_history) = 0; 9811986Sandreas.sandberg@arm.com 9911986Sandreas.sandberg@arm.com /** 10011986Sandreas.sandberg@arm.com * Tells the branch predictor to commit any updates until the given 10111986Sandreas.sandberg@arm.com * sequence number. 10211986Sandreas.sandberg@arm.com * @param done_sn The sequence number to commit any older updates up until. 10311986Sandreas.sandberg@arm.com * @param tid The thread id. 10411986Sandreas.sandberg@arm.com */ 10511986Sandreas.sandberg@arm.com void update(const InstSeqNum &done_sn, ThreadID tid); 10611986Sandreas.sandberg@arm.com 10711986Sandreas.sandberg@arm.com /** 10811986Sandreas.sandberg@arm.com * Squashes all outstanding updates until a given sequence number. 10911986Sandreas.sandberg@arm.com * @param squashed_sn The sequence number to squash any younger updates up 11011986Sandreas.sandberg@arm.com * until. 11111986Sandreas.sandberg@arm.com * @param tid The thread id. 11211986Sandreas.sandberg@arm.com */ 11311986Sandreas.sandberg@arm.com void squash(const InstSeqNum &squashed_sn, ThreadID tid); 11411986Sandreas.sandberg@arm.com 11511986Sandreas.sandberg@arm.com /** 11611986Sandreas.sandberg@arm.com * Squashes all outstanding updates until a given sequence number, and 11711986Sandreas.sandberg@arm.com * corrects that sn's update with the proper address and taken/not taken. 11811986Sandreas.sandberg@arm.com * @param squashed_sn The sequence number to squash any younger updates up 11911986Sandreas.sandberg@arm.com * until. 12011986Sandreas.sandberg@arm.com * @param corr_target The correct branch target. 12111986Sandreas.sandberg@arm.com * @param actually_taken The correct branch direction. 12211986Sandreas.sandberg@arm.com * @param tid The thread id. 12311986Sandreas.sandberg@arm.com */ 12411986Sandreas.sandberg@arm.com void squash(const InstSeqNum &squashed_sn, 12511986Sandreas.sandberg@arm.com const TheISA::PCState &corr_target, 12611986Sandreas.sandberg@arm.com bool actually_taken, ThreadID tid); 12711986Sandreas.sandberg@arm.com 12811986Sandreas.sandberg@arm.com /** 12911986Sandreas.sandberg@arm.com * @param bp_history Pointer to the history object. The predictor 13011986Sandreas.sandberg@arm.com * will need to update any state and delete the object. 13111986Sandreas.sandberg@arm.com */ 13211986Sandreas.sandberg@arm.com virtual void squash(void *bp_history) = 0; 13311986Sandreas.sandberg@arm.com 13411986Sandreas.sandberg@arm.com /** 13511986Sandreas.sandberg@arm.com * Looks up a given PC in the BP to see if it is taken or not taken. 13611986Sandreas.sandberg@arm.com * @param inst_PC The PC to look up. 13711986Sandreas.sandberg@arm.com * @param bp_history Pointer that will be set to an object that 13811986Sandreas.sandberg@arm.com * has the branch predictor state associated with the lookup. 13911986Sandreas.sandberg@arm.com * @return Whether the branch is taken or not taken. 14011986Sandreas.sandberg@arm.com */ 14111986Sandreas.sandberg@arm.com virtual bool lookup(Addr instPC, void * &bp_history) = 0; 14211986Sandreas.sandberg@arm.com 14311986Sandreas.sandberg@arm.com /** 14411986Sandreas.sandberg@arm.com * If a branch is not taken, because the BTB address is invalid or missing, 14511986Sandreas.sandberg@arm.com * this function sets the appropriate counter in the global and local 14611986Sandreas.sandberg@arm.com * predictors to not taken. 14711986Sandreas.sandberg@arm.com * @param inst_PC The PC to look up the local predictor. 14811986Sandreas.sandberg@arm.com * @param bp_history Pointer that will be set to an object that 14911986Sandreas.sandberg@arm.com * has the branch predictor state associated with the lookup. 15011986Sandreas.sandberg@arm.com */ 15111986Sandreas.sandberg@arm.com virtual void btbUpdate(Addr instPC, void * &bp_history) = 0; 15211986Sandreas.sandberg@arm.com 15311986Sandreas.sandberg@arm.com /** 15411986Sandreas.sandberg@arm.com * Looks up a given PC in the BTB to see if a matching entry exists. 15511986Sandreas.sandberg@arm.com * @param inst_PC The PC to look up. 15611986Sandreas.sandberg@arm.com * @return Whether the BTB contains the given PC. 15711986Sandreas.sandberg@arm.com */ 15811986Sandreas.sandberg@arm.com bool BTBValid(Addr instPC) 15911986Sandreas.sandberg@arm.com { return BTB.valid(instPC, 0); } 160 161 /** 162 * Looks up a given PC in the BTB to get the predicted target. 163 * @param inst_PC The PC to look up. 164 * @return The address of the target of the branch. 165 */ 166 TheISA::PCState BTBLookup(Addr instPC) 167 { return BTB.lookup(instPC, 0); } 168 169 /** 170 * Updates the BP with taken/not taken information. 171 * @param inst_PC The branch's PC that will be updated. 172 * @param taken Whether the branch was taken or not taken. 173 * @param bp_history Pointer to the branch predictor state that is 174 * associated with the branch lookup that is being updated. 175 * @param squashed Set to true when this function is called during a 176 * squash operation. 177 * @todo Make this update flexible enough to handle a global predictor. 178 */ 179 virtual void update(Addr instPC, bool taken, void *bp_history, 180 bool squashed) = 0; 181 /** 182 * Deletes the associated history with a branch, performs no predictor 183 * updates. Used for branches that mispredict and update tables but 184 * are still speculative and later retire. 185 * @param bp_history History to delete associated with this predictor 186 */ 187 virtual void retireSquashed(void *bp_history) = 0; 188 189 /** 190 * Updates the BTB with the target of a branch. 191 * @param inst_PC The branch's PC that will be updated. 192 * @param target_PC The branch's target that will be added to the BTB. 193 */ 194 void BTBUpdate(Addr instPC, const TheISA::PCState &target) 195 { BTB.update(instPC, target, 0); } 196 197 void dump(); 198 199 private: 200 struct PredictorHistory { 201 /** 202 * Makes a predictor history struct that contains any 203 * information needed to update the predictor, BTB, and RAS. 204 */ 205 PredictorHistory(const InstSeqNum &seq_num, Addr instPC, 206 bool pred_taken, void *bp_history, 207 ThreadID _tid) 208 : seqNum(seq_num), pc(instPC), bpHistory(bp_history), RASTarget(0), 209 RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), pushedRAS(0), 210 wasCall(0), wasReturn(0), wasSquashed(0) 211 {} 212 213 bool operator==(const PredictorHistory &entry) const { 214 return this->seqNum == entry.seqNum; 215 } 216 217 /** The sequence number for the predictor history entry. */ 218 InstSeqNum seqNum; 219 220 /** The PC associated with the sequence number. */ 221 Addr pc; 222 223 /** Pointer to the history object passed back from the branch 224 * predictor. It is used to update or restore state of the 225 * branch predictor. 226 */ 227 void *bpHistory; 228 229 /** The RAS target (only valid if a return). */ 230 TheISA::PCState RASTarget; 231 232 /** The RAS index of the instruction (only valid if a call). */ 233 unsigned RASIndex; 234 235 /** The thread id. */ 236 ThreadID tid; 237 238 /** Whether or not it was predicted taken. */ 239 bool predTaken; 240 241 /** Whether or not the RAS was used. */ 242 bool usedRAS; 243 244 /* Whether or not the RAS was pushed */ 245 bool pushedRAS; 246 247 /** Whether or not the instruction was a call. */ 248 bool wasCall; 249 250 /** Whether or not the instruction was a return. */ 251 bool wasReturn; 252 253 /** Whether this instruction has already mispredicted/updated bp */ 254 bool wasSquashed; 255 }; 256 257 typedef std::deque<PredictorHistory> History; 258 259 /** Number of the threads for which the branch history is maintained. */ 260 uint32_t numThreads; 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 std::vector<History> predHist; 268 269 /** The BTB. */ 270 DefaultBTB BTB; 271 272 /** The per-thread return address stack. */ 273 std::vector<ReturnAddrStack> RAS; 274 275 /** Stat for number of BP lookups. */ 276 Stats::Scalar lookups; 277 /** Stat for number of conditional branches predicted. */ 278 Stats::Scalar condPredicted; 279 /** Stat for number of conditional branches predicted incorrectly. */ 280 Stats::Scalar condIncorrect; 281 /** Stat for number of BTB lookups. */ 282 Stats::Scalar BTBLookups; 283 /** Stat for number of BTB hits. */ 284 Stats::Scalar BTBHits; 285 /** Stat for number of times the BTB is correct. */ 286 Stats::Scalar BTBCorrect; 287 /** Stat for percent times an entry in BTB found. */ 288 Stats::Formula BTBHitPct; 289 /** Stat for number of times the RAS is used to get a target. */ 290 Stats::Scalar usedRAS; 291 /** Stat for number of times the RAS is incorrect. */ 292 Stats::Scalar RASIncorrect; 293}; 294 295#endif // __CPU_PRED_BPRED_UNIT_HH__ 296