bpred_unit.cc revision 11432
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), 6510785Sgope@wisc.edu instShiftAmt(params->instShiftAmt) 669480Snilay@cs.wisc.edu{ 6710785Sgope@wisc.edu for (auto& r : RAS) 6810785Sgope@wisc.edu r.init(params->RASSize); 6910785Sgope@wisc.edu} 7010785Sgope@wisc.edu 7110785Sgope@wisc.eduvoid 7210785Sgope@wisc.eduBPredUnit::regStats() 7310785Sgope@wisc.edu{ 7410785Sgope@wisc.edu lookups 7510785Sgope@wisc.edu .name(name() + ".lookups") 7610785Sgope@wisc.edu .desc("Number of BP lookups") 7710785Sgope@wisc.edu ; 7810785Sgope@wisc.edu 7910785Sgope@wisc.edu condPredicted 8010785Sgope@wisc.edu .name(name() + ".condPredicted") 8110785Sgope@wisc.edu .desc("Number of conditional branches predicted") 8210785Sgope@wisc.edu ; 8310785Sgope@wisc.edu 8410785Sgope@wisc.edu condIncorrect 8510785Sgope@wisc.edu .name(name() + ".condIncorrect") 8610785Sgope@wisc.edu .desc("Number of conditional branches incorrect") 8710785Sgope@wisc.edu ; 8810785Sgope@wisc.edu 8910785Sgope@wisc.edu BTBLookups 9010785Sgope@wisc.edu .name(name() + ".BTBLookups") 9110785Sgope@wisc.edu .desc("Number of BTB lookups") 9210785Sgope@wisc.edu ; 9310785Sgope@wisc.edu 9410785Sgope@wisc.edu BTBHits 9510785Sgope@wisc.edu .name(name() + ".BTBHits") 9610785Sgope@wisc.edu .desc("Number of BTB hits") 9710785Sgope@wisc.edu ; 9810785Sgope@wisc.edu 9910785Sgope@wisc.edu BTBCorrect 10010785Sgope@wisc.edu .name(name() + ".BTBCorrect") 10110785Sgope@wisc.edu .desc("Number of correct BTB predictions (this stat may not " 10210785Sgope@wisc.edu "work properly.") 10310785Sgope@wisc.edu ; 10410785Sgope@wisc.edu 10510785Sgope@wisc.edu BTBHitPct 10610785Sgope@wisc.edu .name(name() + ".BTBHitPct") 10710785Sgope@wisc.edu .desc("BTB Hit Percentage") 10810785Sgope@wisc.edu .precision(6); 10910785Sgope@wisc.edu BTBHitPct = (BTBHits / BTBLookups) * 100; 11010785Sgope@wisc.edu 11110785Sgope@wisc.edu usedRAS 11210785Sgope@wisc.edu .name(name() + ".usedRAS") 11310785Sgope@wisc.edu .desc("Number of times the RAS was used to get a target.") 11410785Sgope@wisc.edu ; 11510785Sgope@wisc.edu 11610785Sgope@wisc.edu RASIncorrect 11710785Sgope@wisc.edu .name(name() + ".RASInCorrect") 11810785Sgope@wisc.edu .desc("Number of incorrect RAS predictions.") 11910785Sgope@wisc.edu ; 12010785Sgope@wisc.edu} 12110785Sgope@wisc.edu 12210785Sgope@wisc.eduProbePoints::PMUUPtr 12310785Sgope@wisc.eduBPredUnit::pmuProbePoint(const char *name) 12410785Sgope@wisc.edu{ 12510785Sgope@wisc.edu ProbePoints::PMUUPtr ptr; 12610785Sgope@wisc.edu ptr.reset(new ProbePoints::PMU(getProbeManager(), name)); 12710785Sgope@wisc.edu 12810785Sgope@wisc.edu return ptr; 12910785Sgope@wisc.edu} 13010785Sgope@wisc.edu 13110785Sgope@wisc.eduvoid 13210785Sgope@wisc.eduBPredUnit::regProbePoints() 13310785Sgope@wisc.edu{ 13410785Sgope@wisc.edu ppBranches = pmuProbePoint("Branches"); 13510785Sgope@wisc.edu ppMisses = pmuProbePoint("Misses"); 13610785Sgope@wisc.edu} 13710785Sgope@wisc.edu 13810785Sgope@wisc.eduvoid 13910785Sgope@wisc.eduBPredUnit::drainSanityCheck() const 14010785Sgope@wisc.edu{ 14110785Sgope@wisc.edu // We shouldn't have any outstanding requests when we resume from 14210785Sgope@wisc.edu // a drained system. 14310785Sgope@wisc.edu for (const auto& ph M5_VAR_USED : predHist) 14410785Sgope@wisc.edu assert(ph.empty()); 14510785Sgope@wisc.edu} 14610785Sgope@wisc.edu 14710785Sgope@wisc.edubool 14810785Sgope@wisc.eduBPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 14910785Sgope@wisc.edu TheISA::PCState &pc, ThreadID tid) 15010785Sgope@wisc.edu{ 15110785Sgope@wisc.edu // See if branch predictor predicts taken. 15210785Sgope@wisc.edu // If so, get its target addr either from the BTB or the RAS. 15310785Sgope@wisc.edu // Save off record of branch stuff so the RAS can be fixed 15410785Sgope@wisc.edu // up once it's done. 15510785Sgope@wisc.edu 15610785Sgope@wisc.edu bool pred_taken = false; 15710785Sgope@wisc.edu TheISA::PCState target = pc; 15810785Sgope@wisc.edu 15910785Sgope@wisc.edu ++lookups; 16010785Sgope@wisc.edu ppBranches->notify(1); 16110785Sgope@wisc.edu 16210785Sgope@wisc.edu void *bp_history = NULL; 16310785Sgope@wisc.edu 16410785Sgope@wisc.edu if (inst->isUncondCtrl()) { 16510785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid); 16610785Sgope@wisc.edu pred_taken = true; 16710785Sgope@wisc.edu // Tell the BP there was an unconditional branch. 16811429Sandreas.sandberg@arm.com uncondBranch(pc.instAddr(), bp_history); 1699480Snilay@cs.wisc.edu } else { 17010785Sgope@wisc.edu ++condPredicted; 17111429Sandreas.sandberg@arm.com pred_taken = lookup(pc.instAddr(), bp_history); 17210785Sgope@wisc.edu 17310785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor" 17410785Sgope@wisc.edu " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); 17510785Sgope@wisc.edu } 17610785Sgope@wisc.edu 17710785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history " 17810785Sgope@wisc.edu "for PC %s\n", tid, seqNum, pc); 17910785Sgope@wisc.edu 18010785Sgope@wisc.edu PredictorHistory predict_record(seqNum, pc.instAddr(), 18110785Sgope@wisc.edu pred_taken, bp_history, tid); 18210785Sgope@wisc.edu 18310785Sgope@wisc.edu // Now lookup in the BTB or RAS. 18410785Sgope@wisc.edu if (pred_taken) { 18510785Sgope@wisc.edu if (inst->isReturn()) { 18610785Sgope@wisc.edu ++usedRAS; 18710785Sgope@wisc.edu predict_record.wasReturn = true; 18810785Sgope@wisc.edu // If it's a function return call, then look up the address 18910785Sgope@wisc.edu // in the RAS. 19010785Sgope@wisc.edu TheISA::PCState rasTop = RAS[tid].top(); 19110785Sgope@wisc.edu target = TheISA::buildRetPC(pc, rasTop); 19210785Sgope@wisc.edu 19310785Sgope@wisc.edu // Record the top entry of the RAS, and its index. 19410785Sgope@wisc.edu predict_record.usedRAS = true; 19510785Sgope@wisc.edu predict_record.RASIndex = RAS[tid].topIdx(); 19610785Sgope@wisc.edu predict_record.RASTarget = rasTop; 19710785Sgope@wisc.edu 19810785Sgope@wisc.edu RAS[tid].pop(); 19910785Sgope@wisc.edu 20010785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 20110785Sgope@wisc.edu "RAS predicted target: %s, RAS index: %i.\n", 20210785Sgope@wisc.edu tid, pc, target, predict_record.RASIndex); 20310785Sgope@wisc.edu } else { 20410785Sgope@wisc.edu ++BTBLookups; 20510785Sgope@wisc.edu 20610785Sgope@wisc.edu if (inst->isCall()) { 20710785Sgope@wisc.edu RAS[tid].push(pc); 20810785Sgope@wisc.edu predict_record.pushedRAS = true; 20910785Sgope@wisc.edu 21010785Sgope@wisc.edu // Record that it was a call so that the top RAS entry can 21110785Sgope@wisc.edu // be popped off if the speculation is incorrect. 21210785Sgope@wisc.edu predict_record.wasCall = true; 21310785Sgope@wisc.edu 21410785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Instruction %s was a " 21510785Sgope@wisc.edu "call, adding %s to the RAS index: %i.\n", 21610785Sgope@wisc.edu tid, pc, pc, RAS[tid].topIdx()); 21710785Sgope@wisc.edu } 21810785Sgope@wisc.edu 21911429Sandreas.sandberg@arm.com if (BTB.valid(pc.instAddr(), tid)) { 22011429Sandreas.sandberg@arm.com ++BTBHits; 22110785Sgope@wisc.edu 22211429Sandreas.sandberg@arm.com // If it's not a return, use the BTB to get the target addr. 22311429Sandreas.sandberg@arm.com target = BTB.lookup(pc.instAddr(), tid); 22410785Sgope@wisc.edu 22511429Sandreas.sandberg@arm.com DPRINTF(Branch, "[tid:%i]: Instruction %s predicted" 22611429Sandreas.sandberg@arm.com " target is %s.\n", tid, pc, target); 22710785Sgope@wisc.edu 22811429Sandreas.sandberg@arm.com } else { 22911429Sandreas.sandberg@arm.com DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 23011429Sandreas.sandberg@arm.com "valid entry.\n",tid); 23111429Sandreas.sandberg@arm.com pred_taken = false; 23211429Sandreas.sandberg@arm.com // The Direction of the branch predictor is altered because the 23311429Sandreas.sandberg@arm.com // BTB did not have an entry 23411429Sandreas.sandberg@arm.com // The predictor needs to be updated accordingly 23511429Sandreas.sandberg@arm.com if (!inst->isCall() && !inst->isReturn()) { 23611429Sandreas.sandberg@arm.com btbUpdate(pc.instAddr(), bp_history); 23711429Sandreas.sandberg@arm.com DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate" 23811429Sandreas.sandberg@arm.com " called for %s\n", tid, seqNum, pc); 23911429Sandreas.sandberg@arm.com } else if (inst->isCall() && !inst->isUncondCtrl()) { 24011429Sandreas.sandberg@arm.com RAS[tid].pop(); 24111429Sandreas.sandberg@arm.com predict_record.pushedRAS = false; 24211426Smitch.hayenga@arm.com } 24311429Sandreas.sandberg@arm.com TheISA::advancePC(target, inst); 24410785Sgope@wisc.edu } 24510785Sgope@wisc.edu } 24610785Sgope@wisc.edu } else { 24710785Sgope@wisc.edu if (inst->isReturn()) { 24810785Sgope@wisc.edu predict_record.wasReturn = true; 24910785Sgope@wisc.edu } 25010785Sgope@wisc.edu TheISA::advancePC(target, inst); 25110785Sgope@wisc.edu } 25210785Sgope@wisc.edu 25310785Sgope@wisc.edu pc = target; 25410785Sgope@wisc.edu 25510785Sgope@wisc.edu predHist[tid].push_front(predict_record); 25610785Sgope@wisc.edu 25710785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." 25810785Sgope@wisc.edu "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); 25910785Sgope@wisc.edu 26010785Sgope@wisc.edu return pred_taken; 26110785Sgope@wisc.edu} 26210785Sgope@wisc.edu 26310785Sgope@wisc.edubool 26410785Sgope@wisc.eduBPredUnit::predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum, 26510785Sgope@wisc.edu int asid, TheISA::PCState &instPC, 26610785Sgope@wisc.edu TheISA::PCState &predPC, ThreadID tid) 26710785Sgope@wisc.edu{ 26810785Sgope@wisc.edu // See if branch predictor predicts taken. 26910785Sgope@wisc.edu // If so, get its target addr either from the BTB or the RAS. 27010785Sgope@wisc.edu // Save off record of branch stuff so the RAS can be fixed 27110785Sgope@wisc.edu // up once it's done. 27210785Sgope@wisc.edu 27310785Sgope@wisc.edu using TheISA::MachInst; 27410785Sgope@wisc.edu 27510785Sgope@wisc.edu bool pred_taken = false; 27610785Sgope@wisc.edu TheISA::PCState target; 27710785Sgope@wisc.edu 27810785Sgope@wisc.edu ++lookups; 27910785Sgope@wisc.edu ppBranches->notify(1); 28010785Sgope@wisc.edu 28110785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch " 28210785Sgope@wisc.edu "prediction\n", tid, seqNum, 28310785Sgope@wisc.edu inst->disassemble(instPC.instAddr()), instPC); 28410785Sgope@wisc.edu 28510785Sgope@wisc.edu void *bp_history = NULL; 28610785Sgope@wisc.edu 28710785Sgope@wisc.edu if (inst->isUncondCtrl()) { 28810785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i] Unconditional control.\n", tid); 28910785Sgope@wisc.edu pred_taken = true; 29010785Sgope@wisc.edu // Tell the BP there was an unconditional branch. 29111429Sandreas.sandberg@arm.com uncondBranch(instPC.instAddr(), bp_history); 29210785Sgope@wisc.edu 29310785Sgope@wisc.edu if (inst->isReturn() && RAS[tid].empty()) { 29410785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i] RAS is empty, predicting " 29510785Sgope@wisc.edu "false.\n", tid); 29610785Sgope@wisc.edu pred_taken = false; 29710785Sgope@wisc.edu } 29810785Sgope@wisc.edu } else { 29910785Sgope@wisc.edu ++condPredicted; 30010785Sgope@wisc.edu 30111429Sandreas.sandberg@arm.com pred_taken = lookup(predPC.instAddr(), bp_history); 30210785Sgope@wisc.edu } 30310785Sgope@wisc.edu 30410785Sgope@wisc.edu PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken, 30510785Sgope@wisc.edu bp_history, tid); 30610785Sgope@wisc.edu 30710785Sgope@wisc.edu // Now lookup in the BTB or RAS. 30810785Sgope@wisc.edu if (pred_taken) { 30910785Sgope@wisc.edu if (inst->isReturn()) { 31010785Sgope@wisc.edu ++usedRAS; 31110785Sgope@wisc.edu 31210785Sgope@wisc.edu // If it's a function return call, then look up the address 31310785Sgope@wisc.edu // in the RAS. 31410785Sgope@wisc.edu TheISA::PCState rasTop = RAS[tid].top(); 31510785Sgope@wisc.edu target = TheISA::buildRetPC(instPC, rasTop); 31610785Sgope@wisc.edu 31710785Sgope@wisc.edu // Record the top entry of the RAS, and its index. 31810785Sgope@wisc.edu predict_record.usedRAS = true; 31910785Sgope@wisc.edu predict_record.RASIndex = RAS[tid].topIdx(); 32010785Sgope@wisc.edu predict_record.RASTarget = rasTop; 32110785Sgope@wisc.edu 32210785Sgope@wisc.edu assert(predict_record.RASIndex < 16); 32310785Sgope@wisc.edu 32410785Sgope@wisc.edu RAS[tid].pop(); 32510785Sgope@wisc.edu 32610785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 32710785Sgope@wisc.edu "RAS predicted target: %s, RAS index: %i.\n", 32810785Sgope@wisc.edu tid, instPC, target, 32910785Sgope@wisc.edu predict_record.RASIndex); 33010785Sgope@wisc.edu } else { 33110785Sgope@wisc.edu ++BTBLookups; 33210785Sgope@wisc.edu 33310785Sgope@wisc.edu if (inst->isCall()) { 33410785Sgope@wisc.edu 33510785Sgope@wisc.edu RAS[tid].push(instPC); 33610785Sgope@wisc.edu predict_record.pushedRAS = true; 33710785Sgope@wisc.edu 33810785Sgope@wisc.edu // Record that it was a call so that the top RAS entry can 33910785Sgope@wisc.edu // be popped off if the speculation is incorrect. 34010785Sgope@wisc.edu predict_record.wasCall = true; 34110785Sgope@wisc.edu 34210785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Instruction %s was a call" 34310785Sgope@wisc.edu ", adding %s to the RAS index: %i.\n", 34410785Sgope@wisc.edu tid, instPC, predPC, 34510785Sgope@wisc.edu RAS[tid].topIdx()); 34610785Sgope@wisc.edu } 34710785Sgope@wisc.edu 34810785Sgope@wisc.edu if (inst->isCall() && 34910785Sgope@wisc.edu inst->isUncondCtrl() && 35010785Sgope@wisc.edu inst->isDirectCtrl()) { 35110785Sgope@wisc.edu target = inst->branchTarget(instPC); 35210785Sgope@wisc.edu } else if (BTB.valid(predPC.instAddr(), asid)) { 35310785Sgope@wisc.edu ++BTBHits; 35410785Sgope@wisc.edu 35510785Sgope@wisc.edu // If it's not a return, use the BTB to get the target addr. 35610785Sgope@wisc.edu target = BTB.lookup(predPC.instAddr(), asid); 35710785Sgope@wisc.edu 35810785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s " 35910785Sgope@wisc.edu "predicted target is %s.\n", 36010785Sgope@wisc.edu tid, asid, instPC, target); 36110785Sgope@wisc.edu } else { 36210785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 36310785Sgope@wisc.edu "valid entry, predicting false.\n",tid); 36410785Sgope@wisc.edu pred_taken = false; 36510785Sgope@wisc.edu } 36610785Sgope@wisc.edu } 36710785Sgope@wisc.edu } 36810785Sgope@wisc.edu 36910785Sgope@wisc.edu if (pred_taken) { 37010785Sgope@wisc.edu // Set the PC and the instruction's predicted target. 37110785Sgope@wisc.edu predPC = target; 37210785Sgope@wisc.edu } 37310785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n", 37410785Sgope@wisc.edu tid, seqNum, predPC); 37510785Sgope@wisc.edu 37610785Sgope@wisc.edu predHist[tid].push_front(predict_record); 37710785Sgope@wisc.edu 37810785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist " 37910785Sgope@wisc.edu "...predHist.size(): %i\n", 38010785Sgope@wisc.edu tid, seqNum, predHist[tid].size()); 38110785Sgope@wisc.edu 38210785Sgope@wisc.edu return pred_taken; 38310785Sgope@wisc.edu} 38410785Sgope@wisc.edu 38510785Sgope@wisc.eduvoid 38610785Sgope@wisc.eduBPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 38710785Sgope@wisc.edu{ 38810785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Committing branches until " 38910785Sgope@wisc.edu "[sn:%lli].\n", tid, done_sn); 39010785Sgope@wisc.edu 39110785Sgope@wisc.edu while (!predHist[tid].empty() && 39210785Sgope@wisc.edu predHist[tid].back().seqNum <= done_sn) { 39310785Sgope@wisc.edu // Update the branch predictor with the correct results. 39410785Sgope@wisc.edu if (!predHist[tid].back().wasSquashed) { 39511429Sandreas.sandberg@arm.com update(predHist[tid].back().pc, predHist[tid].back().predTaken, 39611429Sandreas.sandberg@arm.com predHist[tid].back().bpHistory, false); 39710785Sgope@wisc.edu } else { 39811429Sandreas.sandberg@arm.com retireSquashed(predHist[tid].back().bpHistory); 39910785Sgope@wisc.edu } 40010785Sgope@wisc.edu 40110785Sgope@wisc.edu predHist[tid].pop_back(); 4029480Snilay@cs.wisc.edu } 4039480Snilay@cs.wisc.edu} 40410785Sgope@wisc.edu 40510785Sgope@wisc.eduvoid 40610785Sgope@wisc.eduBPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 40710785Sgope@wisc.edu{ 40810785Sgope@wisc.edu History &pred_hist = predHist[tid]; 40910785Sgope@wisc.edu 41010785Sgope@wisc.edu while (!pred_hist.empty() && 41110785Sgope@wisc.edu pred_hist.front().seqNum > squashed_sn) { 41210785Sgope@wisc.edu if (pred_hist.front().usedRAS) { 41310785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," 41410785Sgope@wisc.edu " target: %s.\n", tid, 41510785Sgope@wisc.edu pred_hist.front().RASIndex, pred_hist.front().RASTarget); 41610785Sgope@wisc.edu 41710785Sgope@wisc.edu RAS[tid].restore(pred_hist.front().RASIndex, 41810785Sgope@wisc.edu pred_hist.front().RASTarget); 41911321Ssteve.reinhardt@amd.com } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 42010785Sgope@wisc.edu // Was a call but predicated false. Pop RAS here 42110785Sgope@wisc.edu DPRINTF(Branch, "[tid: %i] Squashing" 42210785Sgope@wisc.edu " Call [sn:%i] PC: %s Popping RAS\n", tid, 42310785Sgope@wisc.edu pred_hist.front().seqNum, pred_hist.front().pc); 42410785Sgope@wisc.edu RAS[tid].pop(); 42510785Sgope@wisc.edu } 42610785Sgope@wisc.edu 42710785Sgope@wisc.edu // This call should delete the bpHistory. 42811429Sandreas.sandberg@arm.com squash(pred_hist.front().bpHistory); 42910785Sgope@wisc.edu 43010785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " 43110785Sgope@wisc.edu "PC %s.\n", tid, pred_hist.front().seqNum, 43210785Sgope@wisc.edu pred_hist.front().pc); 43310785Sgope@wisc.edu 43410785Sgope@wisc.edu pred_hist.pop_front(); 43510785Sgope@wisc.edu 43610785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", 43710785Sgope@wisc.edu tid, predHist[tid].size()); 43810785Sgope@wisc.edu } 43910785Sgope@wisc.edu} 44010785Sgope@wisc.edu 44110785Sgope@wisc.eduvoid 44210785Sgope@wisc.eduBPredUnit::squash(const InstSeqNum &squashed_sn, 44310785Sgope@wisc.edu const TheISA::PCState &corrTarget, 44410785Sgope@wisc.edu bool actually_taken, ThreadID tid) 44510785Sgope@wisc.edu{ 44610785Sgope@wisc.edu // Now that we know that a branch was mispredicted, we need to undo 44710785Sgope@wisc.edu // all the branches that have been seen up until this branch and 44810785Sgope@wisc.edu // fix up everything. 44910785Sgope@wisc.edu // NOTE: This should be call conceivably in 2 scenarios: 45010785Sgope@wisc.edu // (1) After an branch is executed, it updates its status in the ROB 45110785Sgope@wisc.edu // The commit stage then checks the ROB update and sends a signal to 45210785Sgope@wisc.edu // the fetch stage to squash history after the mispredict 45310785Sgope@wisc.edu // (2) In the decode stage, you can find out early if a unconditional 45410785Sgope@wisc.edu // PC-relative, branch was predicted incorrectly. If so, a signal 45510785Sgope@wisc.edu // to the fetch stage is sent to squash history after the mispredict 45610785Sgope@wisc.edu 45710785Sgope@wisc.edu History &pred_hist = predHist[tid]; 45810785Sgope@wisc.edu 45910785Sgope@wisc.edu ++condIncorrect; 46010785Sgope@wisc.edu ppMisses->notify(1); 46110785Sgope@wisc.edu 46210785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " 46310785Sgope@wisc.edu "setting target to %s.\n", tid, squashed_sn, corrTarget); 46410785Sgope@wisc.edu 46510785Sgope@wisc.edu // Squash All Branches AFTER this mispredicted branch 46610785Sgope@wisc.edu squash(squashed_sn, tid); 46710785Sgope@wisc.edu 46810785Sgope@wisc.edu // If there's a squash due to a syscall, there may not be an entry 46910785Sgope@wisc.edu // corresponding to the squash. In that case, don't bother trying to 47010785Sgope@wisc.edu // fix up the entry. 47110785Sgope@wisc.edu if (!pred_hist.empty()) { 47210785Sgope@wisc.edu 47310785Sgope@wisc.edu auto hist_it = pred_hist.begin(); 47410785Sgope@wisc.edu //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 47510785Sgope@wisc.edu // squashed_sn); 47610785Sgope@wisc.edu 47710785Sgope@wisc.edu //assert(hist_it != pred_hist.end()); 47810785Sgope@wisc.edu if (pred_hist.front().seqNum != squashed_sn) { 47910785Sgope@wisc.edu DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 48010785Sgope@wisc.edu pred_hist.front().seqNum, squashed_sn); 48110785Sgope@wisc.edu 48210785Sgope@wisc.edu assert(pred_hist.front().seqNum == squashed_sn); 48310785Sgope@wisc.edu } 48410785Sgope@wisc.edu 48510785Sgope@wisc.edu 48610785Sgope@wisc.edu if ((*hist_it).usedRAS) { 48710785Sgope@wisc.edu ++RASIncorrect; 48810785Sgope@wisc.edu } 48910785Sgope@wisc.edu 49011429Sandreas.sandberg@arm.com update((*hist_it).pc, actually_taken, 49110785Sgope@wisc.edu pred_hist.front().bpHistory, true); 49210785Sgope@wisc.edu hist_it->wasSquashed = true; 49310785Sgope@wisc.edu 49410785Sgope@wisc.edu if (actually_taken) { 49510785Sgope@wisc.edu if (hist_it->wasReturn && !hist_it->usedRAS) { 49610785Sgope@wisc.edu DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 49710785Sgope@wisc.edu " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, 49810785Sgope@wisc.edu hist_it->pc); 49910785Sgope@wisc.edu RAS[tid].pop(); 50010785Sgope@wisc.edu hist_it->usedRAS = true; 50110785Sgope@wisc.edu } 50210785Sgope@wisc.edu 50311429Sandreas.sandberg@arm.com DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" 50411429Sandreas.sandberg@arm.com " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); 50511429Sandreas.sandberg@arm.com 50611429Sandreas.sandberg@arm.com BTB.update((*hist_it).pc, corrTarget, tid); 50711429Sandreas.sandberg@arm.com 50810785Sgope@wisc.edu } else { 50910785Sgope@wisc.edu //Actually not Taken 51010785Sgope@wisc.edu if (hist_it->usedRAS) { 51110785Sgope@wisc.edu DPRINTF(Branch,"[tid: %i] Incorrectly predicted" 51210785Sgope@wisc.edu " return [sn:%i] PC: %s Restoring RAS\n", tid, 51310785Sgope@wisc.edu hist_it->seqNum, hist_it->pc); 51410785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" 51510785Sgope@wisc.edu " to: %i, target: %s.\n", tid, 51610785Sgope@wisc.edu hist_it->RASIndex, hist_it->RASTarget); 51710785Sgope@wisc.edu RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 51810785Sgope@wisc.edu hist_it->usedRAS = false; 51910785Sgope@wisc.edu } else if (hist_it->wasCall && hist_it->pushedRAS) { 52010785Sgope@wisc.edu //Was a Call but predicated false. Pop RAS here 52110785Sgope@wisc.edu DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 52210785Sgope@wisc.edu " Call [sn:%i] PC: %s Popping RAS\n", tid, 52310785Sgope@wisc.edu hist_it->seqNum, hist_it->pc); 52410785Sgope@wisc.edu RAS[tid].pop(); 52510785Sgope@wisc.edu hist_it->pushedRAS = false; 52610785Sgope@wisc.edu } 52710785Sgope@wisc.edu } 52810785Sgope@wisc.edu } else { 52910785Sgope@wisc.edu DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " 53010785Sgope@wisc.edu "update.\n", tid, squashed_sn); 53110785Sgope@wisc.edu } 53210785Sgope@wisc.edu} 53310785Sgope@wisc.edu 53410785Sgope@wisc.eduvoid 53510785Sgope@wisc.eduBPredUnit::dump() 53610785Sgope@wisc.edu{ 53710785Sgope@wisc.edu int i = 0; 53810785Sgope@wisc.edu for (const auto& ph : predHist) { 53910785Sgope@wisc.edu if (!ph.empty()) { 54010785Sgope@wisc.edu auto pred_hist_it = ph.begin(); 54110785Sgope@wisc.edu 54210785Sgope@wisc.edu cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 54310785Sgope@wisc.edu 54410785Sgope@wisc.edu while (pred_hist_it != ph.end()) { 54510785Sgope@wisc.edu cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " 54610785Sgope@wisc.edu "bpHistory:%#x\n", 54710785Sgope@wisc.edu pred_hist_it->seqNum, pred_hist_it->pc, 54810785Sgope@wisc.edu pred_hist_it->tid, pred_hist_it->predTaken, 54910785Sgope@wisc.edu pred_hist_it->bpHistory); 55010785Sgope@wisc.edu pred_hist_it++; 55110785Sgope@wisc.edu } 55210785Sgope@wisc.edu 55310785Sgope@wisc.edu cprintf("\n"); 55410785Sgope@wisc.edu } 55510785Sgope@wisc.edu } 55610785Sgope@wisc.edu} 55710785Sgope@wisc.edu 558