| /* |
| * Copyright (c) 2011-2012, 2014 ARM Limited |
| * Copyright (c) 2010 The University of Edinburgh |
| * Copyright (c) 2012 Mark D. Hill and David A. Wood |
| * All rights reserved |
| * |
| * The license below extends only to copyright in the software and shall |
| * not be construed as granting a license to any other intellectual |
| * property including but not limited to intellectual property relating |
| * to a hardware implementation of the functionality of the software |
| * licensed hereunder. You may use the software subject to the license |
| * terms below provided that you ensure that this notice is replicated |
| * unmodified and in its entirety in all distributions of the software, |
| * modified or unmodified, in source code or in binary form. |
| * |
| * Copyright (c) 2004-2005 The Regents of The University of Michigan |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer; |
| * redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution; |
| * neither the name of the copyright holders nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * Authors: Kevin Lim |
| */ |
| |
| #include "cpu/pred/bpred_unit.hh" |
| |
| #include <algorithm> |
| |
| #include "arch/isa_traits.hh" |
| #include "arch/types.hh" |
| #include "arch/utility.hh" |
| #include "base/trace.hh" |
| #include "config/the_isa.hh" |
| #include "debug/Branch.hh" |
| |
| BPredUnit::BPredUnit(const Params *params) |
| : SimObject(params), |
| numThreads(params->numThreads), |
| predHist(numThreads), |
| BTB(params->BTBEntries, |
| params->BTBTagSize, |
| params->instShiftAmt, |
| params->numThreads), |
| RAS(numThreads), |
| useIndirect(params->useIndirect), |
| iPred(params->indirectHashGHR, |
| params->indirectHashTargets, |
| params->indirectSets, |
| params->indirectWays, |
| params->indirectTagSize, |
| params->indirectPathLength, |
| params->instShiftAmt, |
| params->numThreads), |
| instShiftAmt(params->instShiftAmt) |
| { |
| for (auto& r : RAS) |
| r.init(params->RASSize); |
| } |
| |
| void |
| BPredUnit::regStats() |
| { |
| SimObject::regStats(); |
| |
| lookups |
| .name(name() + ".lookups") |
| .desc("Number of BP lookups") |
| ; |
| |
| condPredicted |
| .name(name() + ".condPredicted") |
| .desc("Number of conditional branches predicted") |
| ; |
| |
| condIncorrect |
| .name(name() + ".condIncorrect") |
| .desc("Number of conditional branches incorrect") |
| ; |
| |
| BTBLookups |
| .name(name() + ".BTBLookups") |
| .desc("Number of BTB lookups") |
| ; |
| |
| BTBHits |
| .name(name() + ".BTBHits") |
| .desc("Number of BTB hits") |
| ; |
| |
| BTBCorrect |
| .name(name() + ".BTBCorrect") |
| .desc("Number of correct BTB predictions (this stat may not " |
| "work properly.") |
| ; |
| |
| BTBHitPct |
| .name(name() + ".BTBHitPct") |
| .desc("BTB Hit Percentage") |
| .precision(6); |
| BTBHitPct = (BTBHits / BTBLookups) * 100; |
| |
| usedRAS |
| .name(name() + ".usedRAS") |
| .desc("Number of times the RAS was used to get a target.") |
| ; |
| |
| RASIncorrect |
| .name(name() + ".RASInCorrect") |
| .desc("Number of incorrect RAS predictions.") |
| ; |
| |
| indirectLookups |
| .name(name() + ".indirectLookups") |
| .desc("Number of indirect predictor lookups.") |
| ; |
| |
| indirectHits |
| .name(name() + ".indirectHits") |
| .desc("Number of indirect target hits.") |
| ; |
| |
| indirectMisses |
| .name(name() + ".indirectMisses") |
| .desc("Number of indirect misses.") |
| ; |
| |
| indirectMispredicted |
| .name(name() + "indirectMispredicted") |
| .desc("Number of mispredicted indirect branches.") |
| ; |
| |
| } |
| |
| ProbePoints::PMUUPtr |
| BPredUnit::pmuProbePoint(const char *name) |
| { |
| ProbePoints::PMUUPtr ptr; |
| ptr.reset(new ProbePoints::PMU(getProbeManager(), name)); |
| |
| return ptr; |
| } |
| |
| void |
| BPredUnit::regProbePoints() |
| { |
| ppBranches = pmuProbePoint("Branches"); |
| ppMisses = pmuProbePoint("Misses"); |
| } |
| |
| void |
| BPredUnit::drainSanityCheck() const |
| { |
| // We shouldn't have any outstanding requests when we resume from |
| // a drained system. |
| for (const auto& ph M5_VAR_USED : predHist) |
| assert(ph.empty()); |
| } |
| |
| bool |
| BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, |
| TheISA::PCState &pc, ThreadID tid) |
| { |
| // See if branch predictor predicts taken. |
| // If so, get its target addr either from the BTB or the RAS. |
| // Save off record of branch stuff so the RAS can be fixed |
| // up once it's done. |
| |
| bool pred_taken = false; |
| TheISA::PCState target = pc; |
| |
| ++lookups; |
| ppBranches->notify(1); |
| |
| void *bp_history = NULL; |
| void *indirect_history = NULL; |
| |
| if (inst->isUncondCtrl()) { |
| DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid); |
| pred_taken = true; |
| // Tell the BP there was an unconditional branch. |
| uncondBranch(tid, pc.instAddr(), bp_history); |
| } else { |
| ++condPredicted; |
| pred_taken = lookup(tid, pc.instAddr(), bp_history); |
| |
| DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor" |
| " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); |
| } |
| |
| if (useIndirect) { |
| iPred.updateDirectionInfo(tid, pred_taken, indirect_history); |
| } |
| |
| DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history " |
| "for PC %s\n", tid, seqNum, pc); |
| |
| PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken, |
| bp_history, indirect_history, tid, inst); |
| |
| // Now lookup in the BTB or RAS. |
| if (pred_taken) { |
| if (inst->isReturn()) { |
| ++usedRAS; |
| predict_record.wasReturn = true; |
| // If it's a function return call, then look up the address |
| // in the RAS. |
| TheISA::PCState rasTop = RAS[tid].top(); |
| target = TheISA::buildRetPC(pc, rasTop); |
| |
| // Record the top entry of the RAS, and its index. |
| predict_record.usedRAS = true; |
| predict_record.RASIndex = RAS[tid].topIdx(); |
| predict_record.RASTarget = rasTop; |
| |
| RAS[tid].pop(); |
| |
| DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " |
| "RAS predicted target: %s, RAS index: %i.\n", |
| tid, pc, target, predict_record.RASIndex); |
| } else { |
| ++BTBLookups; |
| |
| if (inst->isCall()) { |
| RAS[tid].push(pc); |
| predict_record.pushedRAS = true; |
| |
| // Record that it was a call so that the top RAS entry can |
| // be popped off if the speculation is incorrect. |
| predict_record.wasCall = true; |
| |
| DPRINTF(Branch, "[tid:%i]: Instruction %s was a " |
| "call, adding %s to the RAS index: %i.\n", |
| tid, pc, pc, RAS[tid].topIdx()); |
| } |
| |
| if (inst->isDirectCtrl() || !useIndirect) { |
| // Check BTB on direct branches |
| if (BTB.valid(pc.instAddr(), tid)) { |
| ++BTBHits; |
| |
| // If it's not a return, use the BTB to get target addr. |
| target = BTB.lookup(pc.instAddr(), tid); |
| |
| DPRINTF(Branch, "[tid:%i]: Instruction %s predicted" |
| " target is %s.\n", tid, pc, target); |
| |
| } else { |
| DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " |
| "valid entry.\n",tid); |
| pred_taken = false; |
| // The Direction of the branch predictor is altered |
| // because the BTB did not have an entry |
| // The predictor needs to be updated accordingly |
| if (!inst->isCall() && !inst->isReturn()) { |
| btbUpdate(tid, pc.instAddr(), bp_history); |
| DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate" |
| " called for %s\n", tid, seqNum, pc); |
| } else if (inst->isCall() && !inst->isUncondCtrl()) { |
| RAS[tid].pop(); |
| predict_record.pushedRAS = false; |
| } |
| TheISA::advancePC(target, inst); |
| } |
| } else { |
| predict_record.wasIndirect = true; |
| ++indirectLookups; |
| //Consult indirect predictor on indirect control |
| if (iPred.lookup(pc.instAddr(), target, tid)) { |
| // Indirect predictor hit |
| ++indirectHits; |
| DPRINTF(Branch, "[tid:%i]: Instruction %s predicted " |
| "indirect target is %s.\n", tid, pc, target); |
| } else { |
| ++indirectMisses; |
| pred_taken = false; |
| DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect " |
| "target.\n", tid, pc); |
| if (!inst->isCall() && !inst->isReturn()) { |
| |
| } else if (inst->isCall() && !inst->isUncondCtrl()) { |
| RAS[tid].pop(); |
| predict_record.pushedRAS = false; |
| } |
| TheISA::advancePC(target, inst); |
| } |
| iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum, |
| tid); |
| } |
| } |
| } else { |
| if (inst->isReturn()) { |
| predict_record.wasReturn = true; |
| } |
| TheISA::advancePC(target, inst); |
| } |
| predict_record.target = target.instAddr(); |
| |
| pc = target; |
| |
| predHist[tid].push_front(predict_record); |
| |
| DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." |
| "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); |
| |
| return pred_taken; |
| } |
| |
| void |
| BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) |
| { |
| DPRINTF(Branch, "[tid:%i]: Committing branches until " |
| "[sn:%lli].\n", tid, done_sn); |
| |
| while (!predHist[tid].empty() && |
| predHist[tid].back().seqNum <= done_sn) { |
| // Update the branch predictor with the correct results. |
| update(tid, predHist[tid].back().pc, |
| predHist[tid].back().predTaken, |
| predHist[tid].back().bpHistory, false, |
| predHist[tid].back().inst, |
| predHist[tid].back().target); |
| |
| iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory); |
| |
| predHist[tid].pop_back(); |
| } |
| } |
| |
| void |
| BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) |
| { |
| History &pred_hist = predHist[tid]; |
| |
| iPred.squash(squashed_sn, tid); |
| while (!pred_hist.empty() && |
| pred_hist.front().seqNum > squashed_sn) { |
| if (pred_hist.front().usedRAS) { |
| DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," |
| " target: %s.\n", tid, |
| pred_hist.front().RASIndex, pred_hist.front().RASTarget); |
| |
| RAS[tid].restore(pred_hist.front().RASIndex, |
| pred_hist.front().RASTarget); |
| } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { |
| // Was a call but predicated false. Pop RAS here |
| DPRINTF(Branch, "[tid: %i] Squashing" |
| " Call [sn:%i] PC: %s Popping RAS\n", tid, |
| pred_hist.front().seqNum, pred_hist.front().pc); |
| RAS[tid].pop(); |
| } |
| |
| // This call should delete the bpHistory. |
| squash(tid, pred_hist.front().bpHistory); |
| if (useIndirect) { |
| iPred.deleteDirectionInfo(tid, pred_hist.front().indirectHistory); |
| } |
| |
| DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " |
| "PC %s.\n", tid, pred_hist.front().seqNum, |
| pred_hist.front().pc); |
| |
| pred_hist.pop_front(); |
| |
| DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", |
| tid, predHist[tid].size()); |
| } |
| } |
| |
| void |
| BPredUnit::squash(const InstSeqNum &squashed_sn, |
| const TheISA::PCState &corrTarget, |
| bool actually_taken, ThreadID tid) |
| { |
| // Now that we know that a branch was mispredicted, we need to undo |
| // all the branches that have been seen up until this branch and |
| // fix up everything. |
| // NOTE: This should be call conceivably in 2 scenarios: |
| // (1) After an branch is executed, it updates its status in the ROB |
| // The commit stage then checks the ROB update and sends a signal to |
| // the fetch stage to squash history after the mispredict |
| // (2) In the decode stage, you can find out early if a unconditional |
| // PC-relative, branch was predicted incorrectly. If so, a signal |
| // to the fetch stage is sent to squash history after the mispredict |
| |
| History &pred_hist = predHist[tid]; |
| |
| ++condIncorrect; |
| ppMisses->notify(1); |
| |
| DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " |
| "setting target to %s.\n", tid, squashed_sn, corrTarget); |
| |
| // Squash All Branches AFTER this mispredicted branch |
| squash(squashed_sn, tid); |
| |
| // If there's a squash due to a syscall, there may not be an entry |
| // corresponding to the squash. In that case, don't bother trying to |
| // fix up the entry. |
| if (!pred_hist.empty()) { |
| |
| auto hist_it = pred_hist.begin(); |
| //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), |
| // squashed_sn); |
| |
| //assert(hist_it != pred_hist.end()); |
| if (pred_hist.front().seqNum != squashed_sn) { |
| DPRINTF(Branch, "Front sn %i != Squash sn %i\n", |
| pred_hist.front().seqNum, squashed_sn); |
| |
| assert(pred_hist.front().seqNum == squashed_sn); |
| } |
| |
| |
| if ((*hist_it).usedRAS) { |
| ++RASIncorrect; |
| DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n", |
| tid, hist_it->seqNum); |
| } |
| |
| // There are separate functions for in-order and out-of-order |
| // branch prediction, but not for update. Therefore, this |
| // call should take into account that the mispredicted branch may |
| // be on the wrong path (i.e., OoO execution), and that the counter |
| // counter table(s) should not be updated. Thus, this call should |
| // restore the state of the underlying predictor, for instance the |
| // local/global histories. The counter tables will be updated when |
| // the branch actually commits. |
| |
| // Remember the correct direction for the update at commit. |
| pred_hist.front().predTaken = actually_taken; |
| pred_hist.front().target = corrTarget.instAddr(); |
| |
| update(tid, (*hist_it).pc, actually_taken, |
| pred_hist.front().bpHistory, true, pred_hist.front().inst, |
| corrTarget.instAddr()); |
| |
| if (useIndirect) { |
| iPred.changeDirectionPrediction(tid, |
| pred_hist.front().indirectHistory, actually_taken); |
| } |
| |
| if (actually_taken) { |
| if (hist_it->wasReturn && !hist_it->usedRAS) { |
| DPRINTF(Branch, "[tid: %i] Incorrectly predicted" |
| " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, |
| hist_it->pc); |
| RAS[tid].pop(); |
| hist_it->usedRAS = true; |
| } |
| if (hist_it->wasIndirect) { |
| ++indirectMispredicted; |
| iPred.recordTarget(hist_it->seqNum, corrTarget, tid); |
| } else { |
| DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" |
| " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); |
| |
| BTB.update((*hist_it).pc, corrTarget, tid); |
| } |
| } else { |
| //Actually not Taken |
| if (hist_it->usedRAS) { |
| DPRINTF(Branch,"[tid: %i] Incorrectly predicted" |
| " return [sn:%i] PC: %s Restoring RAS\n", tid, |
| hist_it->seqNum, hist_it->pc); |
| DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" |
| " to: %i, target: %s.\n", tid, |
| hist_it->RASIndex, hist_it->RASTarget); |
| RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); |
| hist_it->usedRAS = false; |
| } else if (hist_it->wasCall && hist_it->pushedRAS) { |
| //Was a Call but predicated false. Pop RAS here |
| DPRINTF(Branch, "[tid: %i] Incorrectly predicted" |
| " Call [sn:%i] PC: %s Popping RAS\n", tid, |
| hist_it->seqNum, hist_it->pc); |
| RAS[tid].pop(); |
| hist_it->pushedRAS = false; |
| } |
| } |
| } else { |
| DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " |
| "update.\n", tid, squashed_sn); |
| } |
| } |
| |
| void |
| BPredUnit::dump() |
| { |
| int i = 0; |
| for (const auto& ph : predHist) { |
| if (!ph.empty()) { |
| auto pred_hist_it = ph.begin(); |
| |
| cprintf("predHist[%i].size(): %i\n", i++, ph.size()); |
| |
| while (pred_hist_it != ph.end()) { |
| cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " |
| "bpHistory:%#x\n", |
| pred_hist_it->seqNum, pred_hist_it->pc, |
| pred_hist_it->tid, pred_hist_it->predTaken, |
| pred_hist_it->bpHistory); |
| pred_hist_it++; |
| } |
| |
| cprintf("\n"); |
| } |
| } |
| } |
| |
