From 9b05e96b9efdb9cdcc4e40ef9c96b1228df7a175 Mon Sep 17 00:00:00 2001 From: Mrinmoy Ghosh Date: Mon, 13 Feb 2012 12:26:25 -0600 Subject: [PATCH] BPred: Fix RAS to handle predicated call/return instructions. Change RAS to fix issues with predicated call/return instructions. Handled all cases in the life of a predicated call and return instruction. --- src/cpu/o3/bpred_unit.hh | 18 ++++++- src/cpu/o3/bpred_unit_impl.hh | 61 +++++++++++++++++----- src/cpu/o3/commit_impl.hh | 4 ++ src/cpu/pred/tournament.cc | 97 +++++++++++++++++++---------------- 4 files changed, 123 insertions(+), 57 deletions(-) diff --git a/src/cpu/o3/bpred_unit.hh b/src/cpu/o3/bpred_unit.hh index d3ae93b38..673472b69 100644 --- a/src/cpu/o3/bpred_unit.hh +++ b/src/cpu/o3/bpred_unit.hh @@ -1,4 +1,16 @@ /* + * Copyright (c) 2011 ARM Limited + * 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. * @@ -196,7 +208,7 @@ class BPredUnit ThreadID _tid) : seqNum(seq_num), pc(instPC), RASTarget(0), RASIndex(0), tid(_tid), predTaken(pred_taken), usedRAS(0), - wasCall(0), bpHistory(bp_history) + wasCall(0), wasReturn(0), validBTB(0), bpHistory(bp_history) {} bool operator==(const PredictorHistory &entry) const { @@ -227,6 +239,10 @@ class BPredUnit /** Whether or not the instruction was a call. */ bool wasCall; + /** Whether or not the instruction was a return. */ + bool wasReturn; + /** Whether or not the instruction had a valid BTB entry. */ + bool validBTB; /** Pointer to the history object passed back from the branch * predictor. It is used to update or restore state of the * branch predictor. diff --git a/src/cpu/o3/bpred_unit_impl.hh b/src/cpu/o3/bpred_unit_impl.hh index 8502f342c..1e75de90c 100644 --- a/src/cpu/o3/bpred_unit_impl.hh +++ b/src/cpu/o3/bpred_unit_impl.hh @@ -196,7 +196,7 @@ BPredUnit::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid) 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(); @@ -231,6 +231,7 @@ BPredUnit::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid) if (BTB.valid(pc.instAddr(), tid)) { ++BTBHits; + predict_record.validBTB = true; // If it's not a return, use the BTB to get the target addr. target = BTB.lookup(pc.instAddr(), tid); @@ -250,12 +251,17 @@ BPredUnit::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid) DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate" " called for %s\n", tid, inst->seqNum, inst->pcState()); + } else if (inst->isCall() && !inst->isUncondCtrl()) { + RAS[tid].pop(); } TheISA::advancePC(target, inst->staticInst); } } } else { + if (inst->isReturn()) { + predict_record.wasReturn = true; + } TheISA::advancePC(target, inst->staticInst); } @@ -302,12 +308,13 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) RAS[tid].restore(pred_hist.front().RASIndex, pred_hist.front().RASTarget); - } else if (pred_hist.front().wasCall) { - DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing speculative entry " - "added to the RAS.\n",tid); - - RAS[tid].pop(); - } + } else if(pred_hist.front().wasCall && pred_hist.front().validBTB) { + // Was a call but predicated false. Pop RAS here + DPRINTF(Fetch, "BranchPred: [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. BPSquash(pred_hist.front().bpHistory); @@ -377,18 +384,46 @@ BPredUnit::squash(const InstSeqNum &squashed_sn, BPUpdate((*hist_it).pc, actually_taken, pred_hist.front().bpHistory, true); - if (actually_taken){ - DPRINTF(Fetch,"BranchPred: [tid: %i] BTB Update called for [sn:%i]" - " PC: %s\n", tid,(*hist_it).seqNum, (*hist_it).pc); + if (actually_taken) { + if (hist_it->wasReturn && !hist_it->usedRAS) { + DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted" + " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, + hist_it->pc); + RAS[tid].pop(); + } + DPRINTF(Fetch,"BranchPred: [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(Fetch,"BranchPred: [tid: %i] Incorrectly predicted" + " return [sn:%i] PC: %s Restoring RAS\n", tid, + hist_it->seqNum, hist_it->pc); + DPRINTF(Fetch, "BranchPred: [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); + + } else if (hist_it->wasCall && hist_it->validBTB) { + //Was a Call but predicated false. Pop RAS here + DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted" + " Call [sn:%i] PC: %s Popping RAS\n", tid, + hist_it->seqNum, hist_it->pc); + RAS[tid].pop(); + } } DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]" - " PC %s Actually Taken: %i\n", tid, (*hist_it).seqNum, - (*hist_it).pc, actually_taken); + " PC %s Actually Taken: %i\n", tid, hist_it->seqNum, + hist_it->pc, actually_taken); pred_hist.erase(hist_it); - DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, predHist[tid].size()); + DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, + predHist[tid].size()); } } diff --git a/src/cpu/o3/commit_impl.hh b/src/cpu/o3/commit_impl.hh index b4cc4b017..bb82c37a8 100644 --- a/src/cpu/o3/commit_impl.hh +++ b/src/cpu/o3/commit_impl.hh @@ -1232,6 +1232,10 @@ DefaultCommit::commitHead(DynInstPtr &head_inst, unsigned inst_num) delete head_inst->traceData; head_inst->traceData = NULL; } + if (head_inst->isReturn()) { + DPRINTF(Commit,"Return Instruction Committed [sn:%lli] PC %s \n", + head_inst->seqNum, head_inst->pcState()); + } // Update the commit rename map for (int i = 0; i < head_inst->numDestRegs(); i++) { diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc index 3adafb608..b6320ca8a 100644 --- a/src/cpu/pred/tournament.cc +++ b/src/cpu/pred/tournament.cc @@ -258,59 +258,70 @@ TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history, local_predictor_hist = localHistoryTable[local_history_idx]; local_predictor_idx = local_predictor_hist & localPredictorMask; - // Update the choice predictor to tell it which one was correct if - // there was a prediction. if (bp_history) { BPHistory *history = static_cast(bp_history); - if (history->localPredTaken != history->globalPredTaken) { - // If the local prediction matches the actual outcome, - // decerement the counter. Otherwise increment the - // counter. - if (history->localPredTaken == taken) { - choiceCtrs[history->globalHistory].decrement(); - } else if (history->globalPredTaken == taken){ - choiceCtrs[history->globalHistory].increment(); - } - - } - - // Update the counters and local history with the proper - // resolution of the branch. Global history is updated - // speculatively and restored upon squash() calls, so it does not - // need to be updated. + // Update may also be called if the Branch target is incorrect even if + // the prediction is correct. In that case do not update the counters. + bool historyPred = false; unsigned old_local_pred_index = history->localHistory - & localPredictorMask; - if (taken) { - globalCtrs[history->globalHistory].increment(); - if (old_local_pred_index != invalidPredictorIndex) { - localCtrs[old_local_pred_index].increment(); - } + & localPredictorMask; + if (history->globalUsed) { + historyPred = history->globalPredTaken; } else { - globalCtrs[history->globalHistory].decrement(); - if (old_local_pred_index != invalidPredictorIndex) { - localCtrs[old_local_pred_index].decrement(); - } - } - - if (squashed) { - if (taken) { - globalHistory = (history->globalHistory << 1) | 1; - globalHistory = globalHistory & globalHistoryMask; - if (history->localHistory != invalidPredictorIndex) - localHistoryTable[local_history_idx] = + historyPred = history->localPredTaken; + } + if (historyPred != taken || !squashed) { + // Update the choice predictor to tell it which one was correct if + // there was a prediction. + if (history->localPredTaken != history->globalPredTaken) { + // If the local prediction matches the actual outcome, + // decerement the counter. Otherwise increment the + // counter. + if (history->localPredTaken == taken) { + choiceCtrs[history->globalHistory].decrement(); + } else if (history->globalPredTaken == taken) { + choiceCtrs[history->globalHistory].increment(); + } + + } + + // Update the counters and local history with the proper + // resolution of the branch. Global history is updated + // speculatively and restored upon squash() calls, so it does not + // need to be updated. + if (taken) { + globalCtrs[history->globalHistory].increment(); + if (old_local_pred_index != invalidPredictorIndex) { + localCtrs[old_local_pred_index].increment(); + } + } else { + globalCtrs[history->globalHistory].decrement(); + if (old_local_pred_index != invalidPredictorIndex) { + localCtrs[old_local_pred_index].decrement(); + } + } + } + if (squashed) { + if (taken) { + globalHistory = (history->globalHistory << 1) | 1; + globalHistory = globalHistory & globalHistoryMask; + if (old_local_pred_index != invalidPredictorIndex) { + localHistoryTable[old_local_pred_index] = (history->localHistory << 1) | 1; - } else { - globalHistory = (history->globalHistory << 1); - globalHistory = globalHistory & globalHistoryMask; - if (history->localHistory != invalidPredictorIndex) { - localHistoryTable[local_history_idx] = + } + } else { + globalHistory = (history->globalHistory << 1); + globalHistory = globalHistory & globalHistoryMask; + if (old_local_pred_index != invalidPredictorIndex) { + localHistoryTable[old_local_pred_index] = history->localHistory << 1; - } - } + } + } } // We're done with this history, now delete it. delete history; + } assert(globalHistory < globalPredictorSize && -- 2.30.2