bpred_unit.cc revision 13957
11689SN/A/* 210785Sgope@wisc.edu * Copyright (c) 2011-2012, 2014 ARM Limited 39480Snilay@cs.wisc.edu * Copyright (c) 2010 The University of Edinburgh 49480Snilay@cs.wisc.edu * Copyright (c) 2012 Mark D. Hill and David A. Wood 510785Sgope@wisc.edu * All rights reserved 610785Sgope@wisc.edu * 710785Sgope@wisc.edu * The license below extends only to copyright in the software and shall 810785Sgope@wisc.edu * not be construed as granting a license to any other intellectual 910785Sgope@wisc.edu * property including but not limited to intellectual property relating 1010785Sgope@wisc.edu * to a hardware implementation of the functionality of the software 1110785Sgope@wisc.edu * licensed hereunder. You may use the software subject to the license 1210785Sgope@wisc.edu * terms below provided that you ensure that this notice is replicated 1310785Sgope@wisc.edu * unmodified and in its entirety in all distributions of the software, 1410785Sgope@wisc.edu * modified or unmodified, in source code or in binary form. 1510785Sgope@wisc.edu * 1610785Sgope@wisc.edu * Copyright (c) 2004-2005 The Regents of The University of Michigan 171689SN/A * All rights reserved. 181689SN/A * 191689SN/A * Redistribution and use in source and binary forms, with or without 201689SN/A * modification, are permitted provided that the following conditions are 211689SN/A * met: redistributions of source code must retain the above copyright 221689SN/A * notice, this list of conditions and the following disclaimer; 231689SN/A * redistributions in binary form must reproduce the above copyright 241689SN/A * notice, this list of conditions and the following disclaimer in the 251689SN/A * documentation and/or other materials provided with the distribution; 261689SN/A * neither the name of the copyright holders nor the names of its 271689SN/A * contributors may be used to endorse or promote products derived from 281689SN/A * this software without specific prior written permission. 291689SN/A * 301689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 311689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 321689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 331689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 341689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 351689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 361689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 371689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 381689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 391689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 401689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 412665SN/A * 422665SN/A * Authors: Kevin Lim 431689SN/A */ 441061SN/A 4510785Sgope@wisc.edu#include "cpu/pred/bpred_unit.hh" 461061SN/A 4710785Sgope@wisc.edu#include <algorithm> 4810785Sgope@wisc.edu 4910785Sgope@wisc.edu#include "arch/isa_traits.hh" 5010785Sgope@wisc.edu#include "arch/types.hh" 5110785Sgope@wisc.edu#include "arch/utility.hh" 5210785Sgope@wisc.edu#include "base/trace.hh" 5310785Sgope@wisc.edu#include "config/the_isa.hh" 5410785Sgope@wisc.edu#include "debug/Branch.hh" 5510785Sgope@wisc.edu 5610785Sgope@wisc.eduBPredUnit::BPredUnit(const Params *params) 5710785Sgope@wisc.edu : SimObject(params), 5810785Sgope@wisc.edu numThreads(params->numThreads), 5910785Sgope@wisc.edu predHist(numThreads), 6010785Sgope@wisc.edu BTB(params->BTBEntries, 6110785Sgope@wisc.edu params->BTBTagSize, 6211432Smitch.hayenga@arm.com params->instShiftAmt, 6311432Smitch.hayenga@arm.com params->numThreads), 6410785Sgope@wisc.edu RAS(numThreads), 6513957Sjairo.balart@metempsy.com iPred(params->indirectBranchPred), 6610785Sgope@wisc.edu instShiftAmt(params->instShiftAmt) 679480Snilay@cs.wisc.edu{ 6810785Sgope@wisc.edu for (auto& r : RAS) 6910785Sgope@wisc.edu r.init(params->RASSize); 7010785Sgope@wisc.edu} 7110785Sgope@wisc.edu 7210785Sgope@wisc.eduvoid 7310785Sgope@wisc.eduBPredUnit::regStats() 7410785Sgope@wisc.edu{ 7511523Sdavid.guillen@arm.com SimObject::regStats(); 7611523Sdavid.guillen@arm.com 7710785Sgope@wisc.edu lookups 7810785Sgope@wisc.edu .name(name() + ".lookups") 7910785Sgope@wisc.edu .desc("Number of BP lookups") 8010785Sgope@wisc.edu ; 8110785Sgope@wisc.edu 8210785Sgope@wisc.edu condPredicted 8310785Sgope@wisc.edu .name(name() + ".condPredicted") 8410785Sgope@wisc.edu .desc("Number of conditional branches predicted") 8510785Sgope@wisc.edu ; 8610785Sgope@wisc.edu 8710785Sgope@wisc.edu condIncorrect 8810785Sgope@wisc.edu .name(name() + ".condIncorrect") 8910785Sgope@wisc.edu .desc("Number of conditional branches incorrect") 9010785Sgope@wisc.edu ; 9110785Sgope@wisc.edu 9210785Sgope@wisc.edu BTBLookups 9310785Sgope@wisc.edu .name(name() + ".BTBLookups") 9410785Sgope@wisc.edu .desc("Number of BTB lookups") 9510785Sgope@wisc.edu ; 9610785Sgope@wisc.edu 9710785Sgope@wisc.edu BTBHits 9810785Sgope@wisc.edu .name(name() + ".BTBHits") 9910785Sgope@wisc.edu .desc("Number of BTB hits") 10010785Sgope@wisc.edu ; 10110785Sgope@wisc.edu 10210785Sgope@wisc.edu BTBCorrect 10310785Sgope@wisc.edu .name(name() + ".BTBCorrect") 10410785Sgope@wisc.edu .desc("Number of correct BTB predictions (this stat may not " 10510785Sgope@wisc.edu "work properly.") 10610785Sgope@wisc.edu ; 10710785Sgope@wisc.edu 10810785Sgope@wisc.edu BTBHitPct 10910785Sgope@wisc.edu .name(name() + ".BTBHitPct") 11010785Sgope@wisc.edu .desc("BTB Hit Percentage") 11110785Sgope@wisc.edu .precision(6); 11210785Sgope@wisc.edu BTBHitPct = (BTBHits / BTBLookups) * 100; 11310785Sgope@wisc.edu 11410785Sgope@wisc.edu usedRAS 11510785Sgope@wisc.edu .name(name() + ".usedRAS") 11610785Sgope@wisc.edu .desc("Number of times the RAS was used to get a target.") 11710785Sgope@wisc.edu ; 11810785Sgope@wisc.edu 11910785Sgope@wisc.edu RASIncorrect 12010785Sgope@wisc.edu .name(name() + ".RASInCorrect") 12110785Sgope@wisc.edu .desc("Number of incorrect RAS predictions.") 12210785Sgope@wisc.edu ; 12311433Smitch.hayenga@arm.com 12411433Smitch.hayenga@arm.com indirectLookups 12511433Smitch.hayenga@arm.com .name(name() + ".indirectLookups") 12611433Smitch.hayenga@arm.com .desc("Number of indirect predictor lookups.") 12711433Smitch.hayenga@arm.com ; 12811433Smitch.hayenga@arm.com 12911433Smitch.hayenga@arm.com indirectHits 13011433Smitch.hayenga@arm.com .name(name() + ".indirectHits") 13111433Smitch.hayenga@arm.com .desc("Number of indirect target hits.") 13211433Smitch.hayenga@arm.com ; 13311433Smitch.hayenga@arm.com 13411433Smitch.hayenga@arm.com indirectMisses 13511433Smitch.hayenga@arm.com .name(name() + ".indirectMisses") 13611433Smitch.hayenga@arm.com .desc("Number of indirect misses.") 13711433Smitch.hayenga@arm.com ; 13811433Smitch.hayenga@arm.com 13911433Smitch.hayenga@arm.com indirectMispredicted 14011433Smitch.hayenga@arm.com .name(name() + "indirectMispredicted") 14111433Smitch.hayenga@arm.com .desc("Number of mispredicted indirect branches.") 14211433Smitch.hayenga@arm.com ; 14311433Smitch.hayenga@arm.com 14410785Sgope@wisc.edu} 14510785Sgope@wisc.edu 14610785Sgope@wisc.eduProbePoints::PMUUPtr 14710785Sgope@wisc.eduBPredUnit::pmuProbePoint(const char *name) 14810785Sgope@wisc.edu{ 14910785Sgope@wisc.edu ProbePoints::PMUUPtr ptr; 15010785Sgope@wisc.edu ptr.reset(new ProbePoints::PMU(getProbeManager(), name)); 15110785Sgope@wisc.edu 15210785Sgope@wisc.edu return ptr; 15310785Sgope@wisc.edu} 15410785Sgope@wisc.edu 15510785Sgope@wisc.eduvoid 15610785Sgope@wisc.eduBPredUnit::regProbePoints() 15710785Sgope@wisc.edu{ 15810785Sgope@wisc.edu ppBranches = pmuProbePoint("Branches"); 15910785Sgope@wisc.edu ppMisses = pmuProbePoint("Misses"); 16010785Sgope@wisc.edu} 16110785Sgope@wisc.edu 16210785Sgope@wisc.eduvoid 16310785Sgope@wisc.eduBPredUnit::drainSanityCheck() const 16410785Sgope@wisc.edu{ 16510785Sgope@wisc.edu // We shouldn't have any outstanding requests when we resume from 16610785Sgope@wisc.edu // a drained system. 16710785Sgope@wisc.edu for (const auto& ph M5_VAR_USED : predHist) 16810785Sgope@wisc.edu assert(ph.empty()); 16910785Sgope@wisc.edu} 17010785Sgope@wisc.edu 17110785Sgope@wisc.edubool 17210785Sgope@wisc.eduBPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 17310785Sgope@wisc.edu TheISA::PCState &pc, ThreadID tid) 17410785Sgope@wisc.edu{ 17510785Sgope@wisc.edu // See if branch predictor predicts taken. 17610785Sgope@wisc.edu // If so, get its target addr either from the BTB or the RAS. 17710785Sgope@wisc.edu // Save off record of branch stuff so the RAS can be fixed 17810785Sgope@wisc.edu // up once it's done. 17910785Sgope@wisc.edu 18010785Sgope@wisc.edu bool pred_taken = false; 18110785Sgope@wisc.edu TheISA::PCState target = pc; 18210785Sgope@wisc.edu 18310785Sgope@wisc.edu ++lookups; 18410785Sgope@wisc.edu ppBranches->notify(1); 18510785Sgope@wisc.edu 18610785Sgope@wisc.edu void *bp_history = NULL; 18713654Sjairo.balart@metempsy.com void *indirect_history = NULL; 18810785Sgope@wisc.edu 18910785Sgope@wisc.edu if (inst->isUncondCtrl()) { 19013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] " 19113831SAndrea.Mondelli@ucf.edu "Unconditional control\n", 19213831SAndrea.Mondelli@ucf.edu tid,seqNum); 19310785Sgope@wisc.edu pred_taken = true; 19410785Sgope@wisc.edu // Tell the BP there was an unconditional branch. 19511434Smitch.hayenga@arm.com uncondBranch(tid, pc.instAddr(), bp_history); 1969480Snilay@cs.wisc.edu } else { 19710785Sgope@wisc.edu ++condPredicted; 19811434Smitch.hayenga@arm.com pred_taken = lookup(tid, pc.instAddr(), bp_history); 19910785Sgope@wisc.edu 20013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] " 20113831SAndrea.Mondelli@ucf.edu "Branch predictor predicted %i for PC %s\n", 20213831SAndrea.Mondelli@ucf.edu tid, seqNum, pred_taken, pc); 20310785Sgope@wisc.edu } 20410785Sgope@wisc.edu 20513810Spau.cabre@metempsy.com const bool orig_pred_taken = pred_taken; 20613957Sjairo.balart@metempsy.com if (iPred) { 20713957Sjairo.balart@metempsy.com iPred->genIndirectInfo(tid, indirect_history); 20813654Sjairo.balart@metempsy.com } 20913654Sjairo.balart@metempsy.com 21013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] " 21113831SAndrea.Mondelli@ucf.edu "Creating prediction history " 21210785Sgope@wisc.edu "for PC %s\n", tid, seqNum, pc); 21310785Sgope@wisc.edu 21413654Sjairo.balart@metempsy.com PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken, 21513654Sjairo.balart@metempsy.com bp_history, indirect_history, tid, inst); 21610785Sgope@wisc.edu 21710785Sgope@wisc.edu // Now lookup in the BTB or RAS. 21810785Sgope@wisc.edu if (pred_taken) { 21910785Sgope@wisc.edu if (inst->isReturn()) { 22010785Sgope@wisc.edu ++usedRAS; 22110785Sgope@wisc.edu predict_record.wasReturn = true; 22210785Sgope@wisc.edu // If it's a function return call, then look up the address 22310785Sgope@wisc.edu // in the RAS. 22410785Sgope@wisc.edu TheISA::PCState rasTop = RAS[tid].top(); 22510785Sgope@wisc.edu target = TheISA::buildRetPC(pc, rasTop); 22610785Sgope@wisc.edu 22710785Sgope@wisc.edu // Record the top entry of the RAS, and its index. 22810785Sgope@wisc.edu predict_record.usedRAS = true; 22910785Sgope@wisc.edu predict_record.RASIndex = RAS[tid].topIdx(); 23010785Sgope@wisc.edu predict_record.RASTarget = rasTop; 23110785Sgope@wisc.edu 23210785Sgope@wisc.edu RAS[tid].pop(); 23310785Sgope@wisc.edu 23413831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] Instruction %s is a return, " 23513831SAndrea.Mondelli@ucf.edu "RAS predicted target: %s, RAS index: %i\n", 23613831SAndrea.Mondelli@ucf.edu tid, seqNum, pc, target, predict_record.RASIndex); 23710785Sgope@wisc.edu } else { 23810785Sgope@wisc.edu ++BTBLookups; 23910785Sgope@wisc.edu 24010785Sgope@wisc.edu if (inst->isCall()) { 24110785Sgope@wisc.edu RAS[tid].push(pc); 24210785Sgope@wisc.edu predict_record.pushedRAS = true; 24310785Sgope@wisc.edu 24410785Sgope@wisc.edu // Record that it was a call so that the top RAS entry can 24510785Sgope@wisc.edu // be popped off if the speculation is incorrect. 24610785Sgope@wisc.edu predict_record.wasCall = true; 24710785Sgope@wisc.edu 24813831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 24913831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] Instruction %s was a call, adding " 25013831SAndrea.Mondelli@ucf.edu "%s to the RAS index: %i\n", 25113831SAndrea.Mondelli@ucf.edu tid, seqNum, pc, pc, RAS[tid].topIdx()); 25210785Sgope@wisc.edu } 25310785Sgope@wisc.edu 25413957Sjairo.balart@metempsy.com if (inst->isDirectCtrl() || !iPred) { 25511433Smitch.hayenga@arm.com // Check BTB on direct branches 25611433Smitch.hayenga@arm.com if (BTB.valid(pc.instAddr(), tid)) { 25711433Smitch.hayenga@arm.com ++BTBHits; 25811433Smitch.hayenga@arm.com // If it's not a return, use the BTB to get target addr. 25911433Smitch.hayenga@arm.com target = BTB.lookup(pc.instAddr(), tid); 26013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 26113831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] Instruction %s predicted " 26213831SAndrea.Mondelli@ucf.edu "target is %s\n", 26313831SAndrea.Mondelli@ucf.edu tid, seqNum, pc, target); 26411433Smitch.hayenga@arm.com } else { 26513831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] BTB doesn't have a " 26613831SAndrea.Mondelli@ucf.edu "valid entry\n",tid,seqNum); 26711433Smitch.hayenga@arm.com pred_taken = false; 26811433Smitch.hayenga@arm.com // The Direction of the branch predictor is altered 26911433Smitch.hayenga@arm.com // because the BTB did not have an entry 27011433Smitch.hayenga@arm.com // The predictor needs to be updated accordingly 27111433Smitch.hayenga@arm.com if (!inst->isCall() && !inst->isReturn()) { 27211434Smitch.hayenga@arm.com btbUpdate(tid, pc.instAddr(), bp_history); 27313831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 27413831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] btbUpdate " 27513831SAndrea.Mondelli@ucf.edu "called for %s\n", 27613831SAndrea.Mondelli@ucf.edu tid, seqNum, pc); 27711433Smitch.hayenga@arm.com } else if (inst->isCall() && !inst->isUncondCtrl()) { 27811433Smitch.hayenga@arm.com RAS[tid].pop(); 27911433Smitch.hayenga@arm.com predict_record.pushedRAS = false; 28011433Smitch.hayenga@arm.com } 28111433Smitch.hayenga@arm.com TheISA::advancePC(target, inst); 28211433Smitch.hayenga@arm.com } 28311429Sandreas.sandberg@arm.com } else { 28411433Smitch.hayenga@arm.com predict_record.wasIndirect = true; 28511433Smitch.hayenga@arm.com ++indirectLookups; 28611433Smitch.hayenga@arm.com //Consult indirect predictor on indirect control 28713957Sjairo.balart@metempsy.com if (iPred->lookup(pc.instAddr(), target, tid)) { 28811433Smitch.hayenga@arm.com // Indirect predictor hit 28911433Smitch.hayenga@arm.com ++indirectHits; 29013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 29113831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] " 29213831SAndrea.Mondelli@ucf.edu "Instruction %s predicted " 29313831SAndrea.Mondelli@ucf.edu "indirect target is %s\n", 29413831SAndrea.Mondelli@ucf.edu tid, seqNum, pc, target); 29511433Smitch.hayenga@arm.com } else { 29611433Smitch.hayenga@arm.com ++indirectMisses; 29711433Smitch.hayenga@arm.com pred_taken = false; 29813831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 29913831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] " 30013831SAndrea.Mondelli@ucf.edu "Instruction %s no indirect " 30113831SAndrea.Mondelli@ucf.edu "target\n", 30213831SAndrea.Mondelli@ucf.edu tid, seqNum, pc); 30311433Smitch.hayenga@arm.com if (!inst->isCall() && !inst->isReturn()) { 30411433Smitch.hayenga@arm.com 30511433Smitch.hayenga@arm.com } else if (inst->isCall() && !inst->isUncondCtrl()) { 30611433Smitch.hayenga@arm.com RAS[tid].pop(); 30711433Smitch.hayenga@arm.com predict_record.pushedRAS = false; 30811433Smitch.hayenga@arm.com } 30911433Smitch.hayenga@arm.com TheISA::advancePC(target, inst); 31011426Smitch.hayenga@arm.com } 31113957Sjairo.balart@metempsy.com iPred->recordIndirect(pc.instAddr(), target.instAddr(), seqNum, 31211433Smitch.hayenga@arm.com tid); 31310785Sgope@wisc.edu } 31410785Sgope@wisc.edu } 31510785Sgope@wisc.edu } else { 31610785Sgope@wisc.edu if (inst->isReturn()) { 31710785Sgope@wisc.edu predict_record.wasReturn = true; 31810785Sgope@wisc.edu } 31910785Sgope@wisc.edu TheISA::advancePC(target, inst); 32010785Sgope@wisc.edu } 32113626Sjairo.balart@metempsy.com predict_record.target = target.instAddr(); 32210785Sgope@wisc.edu 32310785Sgope@wisc.edu pc = target; 32410785Sgope@wisc.edu 32513957Sjairo.balart@metempsy.com if (iPred) { 32613810Spau.cabre@metempsy.com // Update the indirect predictor with the direction prediction 32713810Spau.cabre@metempsy.com // Note that this happens after indirect lookup, so it does not use 32813810Spau.cabre@metempsy.com // the new information 32913810Spau.cabre@metempsy.com // Note also that we use orig_pred_taken instead of pred_taken in 33013810Spau.cabre@metempsy.com // as this is the actual outcome of the direction prediction 33113957Sjairo.balart@metempsy.com iPred->updateDirectionInfo(tid, orig_pred_taken); 33213810Spau.cabre@metempsy.com } 33313810Spau.cabre@metempsy.com 33410785Sgope@wisc.edu predHist[tid].push_front(predict_record); 33510785Sgope@wisc.edu 33613831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 33713831SAndrea.Mondelli@ucf.edu "[tid:%i] [sn:%llu] History entry added. " 33813831SAndrea.Mondelli@ucf.edu "predHist.size(): %i\n", 33913831SAndrea.Mondelli@ucf.edu tid, seqNum, predHist[tid].size()); 34010785Sgope@wisc.edu 34110785Sgope@wisc.edu return pred_taken; 34210785Sgope@wisc.edu} 34310785Sgope@wisc.edu 34410785Sgope@wisc.eduvoid 34510785Sgope@wisc.eduBPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 34610785Sgope@wisc.edu{ 34713831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] Committing branches until " 34813831SAndrea.Mondelli@ucf.edu "sn:%llu]\n", tid, done_sn); 34910785Sgope@wisc.edu 35010785Sgope@wisc.edu while (!predHist[tid].empty() && 35110785Sgope@wisc.edu predHist[tid].back().seqNum <= done_sn) { 35210785Sgope@wisc.edu // Update the branch predictor with the correct results. 35311783Sarthur.perais@inria.fr update(tid, predHist[tid].back().pc, 35411783Sarthur.perais@inria.fr predHist[tid].back().predTaken, 35513626Sjairo.balart@metempsy.com predHist[tid].back().bpHistory, false, 35613626Sjairo.balart@metempsy.com predHist[tid].back().inst, 35713626Sjairo.balart@metempsy.com predHist[tid].back().target); 35810785Sgope@wisc.edu 35913957Sjairo.balart@metempsy.com if (iPred) { 36013957Sjairo.balart@metempsy.com iPred->commit(done_sn, tid, predHist[tid].back().indirectHistory); 36113810Spau.cabre@metempsy.com } 36213654Sjairo.balart@metempsy.com 36310785Sgope@wisc.edu predHist[tid].pop_back(); 3649480Snilay@cs.wisc.edu } 3659480Snilay@cs.wisc.edu} 36610785Sgope@wisc.edu 36710785Sgope@wisc.eduvoid 36810785Sgope@wisc.eduBPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 36910785Sgope@wisc.edu{ 37010785Sgope@wisc.edu History &pred_hist = predHist[tid]; 37110785Sgope@wisc.edu 37213957Sjairo.balart@metempsy.com if (iPred) { 37313957Sjairo.balart@metempsy.com iPred->squash(squashed_sn, tid); 37413810Spau.cabre@metempsy.com } 37513810Spau.cabre@metempsy.com 37610785Sgope@wisc.edu while (!pred_hist.empty() && 37710785Sgope@wisc.edu pred_hist.front().seqNum > squashed_sn) { 37810785Sgope@wisc.edu if (pred_hist.front().usedRAS) { 37913831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [squash sn:%llu]" 38013831SAndrea.Mondelli@ucf.edu " Restoring top of RAS to: %i," 38113831SAndrea.Mondelli@ucf.edu " target: %s\n", tid, squashed_sn, 38210785Sgope@wisc.edu pred_hist.front().RASIndex, pred_hist.front().RASTarget); 38310785Sgope@wisc.edu 38410785Sgope@wisc.edu RAS[tid].restore(pred_hist.front().RASIndex, 38510785Sgope@wisc.edu pred_hist.front().RASTarget); 38611321Ssteve.reinhardt@amd.com } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 38710785Sgope@wisc.edu // Was a call but predicated false. Pop RAS here 38813831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [squash sn:%llu] Squashing" 38913831SAndrea.Mondelli@ucf.edu " Call [sn:%llu] PC: %s Popping RAS\n", tid, squashed_sn, 39010785Sgope@wisc.edu pred_hist.front().seqNum, pred_hist.front().pc); 39110785Sgope@wisc.edu RAS[tid].pop(); 39210785Sgope@wisc.edu } 39310785Sgope@wisc.edu 39410785Sgope@wisc.edu // This call should delete the bpHistory. 39511434Smitch.hayenga@arm.com squash(tid, pred_hist.front().bpHistory); 39613957Sjairo.balart@metempsy.com if (iPred) { 39713957Sjairo.balart@metempsy.com iPred->deleteIndirectInfo(tid, pred_hist.front().indirectHistory); 39813733Ssrikant.bharadwaj@amd.com } 39910785Sgope@wisc.edu 40013831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [squash sn:%llu] " 40113831SAndrea.Mondelli@ucf.edu "Removing history for [sn:%llu] " 40213831SAndrea.Mondelli@ucf.edu "PC %#x\n", tid, squashed_sn, pred_hist.front().seqNum, 40310785Sgope@wisc.edu pred_hist.front().pc); 40410785Sgope@wisc.edu 40510785Sgope@wisc.edu pred_hist.pop_front(); 40610785Sgope@wisc.edu 40713831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [squash sn:%llu] predHist.size(): %i\n", 40813831SAndrea.Mondelli@ucf.edu tid, squashed_sn, predHist[tid].size()); 40910785Sgope@wisc.edu } 41010785Sgope@wisc.edu} 41110785Sgope@wisc.edu 41210785Sgope@wisc.eduvoid 41310785Sgope@wisc.eduBPredUnit::squash(const InstSeqNum &squashed_sn, 41410785Sgope@wisc.edu const TheISA::PCState &corrTarget, 41510785Sgope@wisc.edu bool actually_taken, ThreadID tid) 41610785Sgope@wisc.edu{ 41710785Sgope@wisc.edu // Now that we know that a branch was mispredicted, we need to undo 41810785Sgope@wisc.edu // all the branches that have been seen up until this branch and 41910785Sgope@wisc.edu // fix up everything. 42010785Sgope@wisc.edu // NOTE: This should be call conceivably in 2 scenarios: 42110785Sgope@wisc.edu // (1) After an branch is executed, it updates its status in the ROB 42210785Sgope@wisc.edu // The commit stage then checks the ROB update and sends a signal to 42310785Sgope@wisc.edu // the fetch stage to squash history after the mispredict 42410785Sgope@wisc.edu // (2) In the decode stage, you can find out early if a unconditional 42510785Sgope@wisc.edu // PC-relative, branch was predicted incorrectly. If so, a signal 42610785Sgope@wisc.edu // to the fetch stage is sent to squash history after the mispredict 42710785Sgope@wisc.edu 42810785Sgope@wisc.edu History &pred_hist = predHist[tid]; 42910785Sgope@wisc.edu 43010785Sgope@wisc.edu ++condIncorrect; 43110785Sgope@wisc.edu ppMisses->notify(1); 43210785Sgope@wisc.edu 43313831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] Squashing from sequence number %i, " 43413831SAndrea.Mondelli@ucf.edu "setting target to %s\n", tid, squashed_sn, corrTarget); 43510785Sgope@wisc.edu 43610785Sgope@wisc.edu // Squash All Branches AFTER this mispredicted branch 43710785Sgope@wisc.edu squash(squashed_sn, tid); 43810785Sgope@wisc.edu 43910785Sgope@wisc.edu // If there's a squash due to a syscall, there may not be an entry 44010785Sgope@wisc.edu // corresponding to the squash. In that case, don't bother trying to 44110785Sgope@wisc.edu // fix up the entry. 44210785Sgope@wisc.edu if (!pred_hist.empty()) { 44310785Sgope@wisc.edu 44410785Sgope@wisc.edu auto hist_it = pred_hist.begin(); 44510785Sgope@wisc.edu //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 44610785Sgope@wisc.edu // squashed_sn); 44710785Sgope@wisc.edu 44810785Sgope@wisc.edu //assert(hist_it != pred_hist.end()); 44910785Sgope@wisc.edu if (pred_hist.front().seqNum != squashed_sn) { 45010785Sgope@wisc.edu DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 45110785Sgope@wisc.edu pred_hist.front().seqNum, squashed_sn); 45210785Sgope@wisc.edu 45310785Sgope@wisc.edu assert(pred_hist.front().seqNum == squashed_sn); 45410785Sgope@wisc.edu } 45510785Sgope@wisc.edu 45610785Sgope@wisc.edu 45710785Sgope@wisc.edu if ((*hist_it).usedRAS) { 45810785Sgope@wisc.edu ++RASIncorrect; 45913831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 46013831SAndrea.Mondelli@ucf.edu "[tid:%i] [squash sn:%llu] Incorrect RAS [sn:%llu]\n", 46113831SAndrea.Mondelli@ucf.edu tid, squashed_sn, hist_it->seqNum); 46210785Sgope@wisc.edu } 46310785Sgope@wisc.edu 46411783Sarthur.perais@inria.fr // There are separate functions for in-order and out-of-order 46511783Sarthur.perais@inria.fr // branch prediction, but not for update. Therefore, this 46611783Sarthur.perais@inria.fr // call should take into account that the mispredicted branch may 46711783Sarthur.perais@inria.fr // be on the wrong path (i.e., OoO execution), and that the counter 46811783Sarthur.perais@inria.fr // counter table(s) should not be updated. Thus, this call should 46911783Sarthur.perais@inria.fr // restore the state of the underlying predictor, for instance the 47011783Sarthur.perais@inria.fr // local/global histories. The counter tables will be updated when 47111783Sarthur.perais@inria.fr // the branch actually commits. 47211783Sarthur.perais@inria.fr 47311783Sarthur.perais@inria.fr // Remember the correct direction for the update at commit. 47411783Sarthur.perais@inria.fr pred_hist.front().predTaken = actually_taken; 47513626Sjairo.balart@metempsy.com pred_hist.front().target = corrTarget.instAddr(); 47611783Sarthur.perais@inria.fr 47711434Smitch.hayenga@arm.com update(tid, (*hist_it).pc, actually_taken, 47813626Sjairo.balart@metempsy.com pred_hist.front().bpHistory, true, pred_hist.front().inst, 47913626Sjairo.balart@metempsy.com corrTarget.instAddr()); 48010785Sgope@wisc.edu 48113957Sjairo.balart@metempsy.com if (iPred) { 48213957Sjairo.balart@metempsy.com iPred->changeDirectionPrediction(tid, 48313733Ssrikant.bharadwaj@amd.com pred_hist.front().indirectHistory, actually_taken); 48413733Ssrikant.bharadwaj@amd.com } 48513654Sjairo.balart@metempsy.com 48610785Sgope@wisc.edu if (actually_taken) { 48710785Sgope@wisc.edu if (hist_it->wasReturn && !hist_it->usedRAS) { 48813831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [squash sn:%llu] " 48913831SAndrea.Mondelli@ucf.edu "Incorrectly predicted " 49013831SAndrea.Mondelli@ucf.edu "return [sn:%llu] PC: %#x\n", tid, squashed_sn, 49113831SAndrea.Mondelli@ucf.edu hist_it->seqNum, 49213831SAndrea.Mondelli@ucf.edu hist_it->pc); 49310785Sgope@wisc.edu RAS[tid].pop(); 49410785Sgope@wisc.edu hist_it->usedRAS = true; 49510785Sgope@wisc.edu } 49611433Smitch.hayenga@arm.com if (hist_it->wasIndirect) { 49711433Smitch.hayenga@arm.com ++indirectMispredicted; 49813957Sjairo.balart@metempsy.com if (iPred) { 49913957Sjairo.balart@metempsy.com iPred->recordTarget( 50013957Sjairo.balart@metempsy.com hist_it->seqNum, pred_hist.front().indirectHistory, 50113957Sjairo.balart@metempsy.com corrTarget, tid); 50213957Sjairo.balart@metempsy.com } 50311433Smitch.hayenga@arm.com } else { 50413831SAndrea.Mondelli@ucf.edu DPRINTF(Branch,"[tid:%i] [squash sn:%llu] " 50513831SAndrea.Mondelli@ucf.edu "BTB Update called for [sn:%llu] " 50613831SAndrea.Mondelli@ucf.edu "PC %#x\n", tid, squashed_sn, 50713831SAndrea.Mondelli@ucf.edu hist_it->seqNum, hist_it->pc); 50810785Sgope@wisc.edu 50911433Smitch.hayenga@arm.com BTB.update((*hist_it).pc, corrTarget, tid); 51011433Smitch.hayenga@arm.com } 51110785Sgope@wisc.edu } else { 51210785Sgope@wisc.edu //Actually not Taken 51310785Sgope@wisc.edu if (hist_it->usedRAS) { 51413831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 51513831SAndrea.Mondelli@ucf.edu "[tid:%i] [squash sn:%llu] Incorrectly predicted " 51613831SAndrea.Mondelli@ucf.edu "return [sn:%llu] PC: %#x Restoring RAS\n", tid, 51713831SAndrea.Mondelli@ucf.edu squashed_sn, 51810785Sgope@wisc.edu hist_it->seqNum, hist_it->pc); 51913831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 52013831SAndrea.Mondelli@ucf.edu "[tid:%i] [squash sn:%llu] Restoring top of RAS " 52113831SAndrea.Mondelli@ucf.edu "to: %i, target: %s\n", tid, squashed_sn, 52210785Sgope@wisc.edu hist_it->RASIndex, hist_it->RASTarget); 52310785Sgope@wisc.edu RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 52410785Sgope@wisc.edu hist_it->usedRAS = false; 52510785Sgope@wisc.edu } else if (hist_it->wasCall && hist_it->pushedRAS) { 52610785Sgope@wisc.edu //Was a Call but predicated false. Pop RAS here 52713831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, 52813831SAndrea.Mondelli@ucf.edu "[tid:%i] [squash sn:%llu] " 52913831SAndrea.Mondelli@ucf.edu "Incorrectly predicted " 53013831SAndrea.Mondelli@ucf.edu "Call [sn:%llu] PC: %s Popping RAS\n", 53113831SAndrea.Mondelli@ucf.edu tid, squashed_sn, 53213831SAndrea.Mondelli@ucf.edu hist_it->seqNum, hist_it->pc); 53310785Sgope@wisc.edu RAS[tid].pop(); 53410785Sgope@wisc.edu hist_it->pushedRAS = false; 53510785Sgope@wisc.edu } 53610785Sgope@wisc.edu } 53710785Sgope@wisc.edu } else { 53813831SAndrea.Mondelli@ucf.edu DPRINTF(Branch, "[tid:%i] [sn:%llu] pred_hist empty, can't " 53913831SAndrea.Mondelli@ucf.edu "update\n", tid, squashed_sn); 54010785Sgope@wisc.edu } 54110785Sgope@wisc.edu} 54210785Sgope@wisc.edu 54310785Sgope@wisc.eduvoid 54410785Sgope@wisc.eduBPredUnit::dump() 54510785Sgope@wisc.edu{ 54610785Sgope@wisc.edu int i = 0; 54710785Sgope@wisc.edu for (const auto& ph : predHist) { 54810785Sgope@wisc.edu if (!ph.empty()) { 54910785Sgope@wisc.edu auto pred_hist_it = ph.begin(); 55010785Sgope@wisc.edu 55110785Sgope@wisc.edu cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 55210785Sgope@wisc.edu 55310785Sgope@wisc.edu while (pred_hist_it != ph.end()) { 55413831SAndrea.Mondelli@ucf.edu cprintf("sn:%llu], PC:%#x, tid:%i, predTaken:%i, " 55510785Sgope@wisc.edu "bpHistory:%#x\n", 55610785Sgope@wisc.edu pred_hist_it->seqNum, pred_hist_it->pc, 55710785Sgope@wisc.edu pred_hist_it->tid, pred_hist_it->predTaken, 55810785Sgope@wisc.edu pred_hist_it->bpHistory); 55910785Sgope@wisc.edu pred_hist_it++; 56010785Sgope@wisc.edu } 56110785Sgope@wisc.edu 56210785Sgope@wisc.edu cprintf("\n"); 56310785Sgope@wisc.edu } 56410785Sgope@wisc.edu } 56510785Sgope@wisc.edu} 56610785Sgope@wisc.edu 567