diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/inorder/resources/bpred_unit.hh --- a/src/cpu/inorder/resources/bpred_unit.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/inorder/resources/bpred_unit.hh Tue Sep 13 21:19:20 2011 -0500 @@ -160,9 +160,10 @@ * @param taken Whether the branch was taken or not taken. * @param bp_history Pointer to the branch predictor state that is * associated with the branch lookup that is being updated. + * @param squashed if the branch in question was squashed or not * @todo Make this update flexible enough to handle a global predictor. */ - void BPUpdate(Addr instPC, bool taken, void *bp_history); + void BPUpdate(Addr instPC, bool taken, void *bp_history, bool squashed); /** * Updates the BTB with the target of a branch. diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/inorder/resources/bpred_unit.cc --- a/src/cpu/inorder/resources/bpred_unit.cc Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/inorder/resources/bpred_unit.cc Tue Sep 13 21:19:20 2011 -0500 @@ -284,7 +284,8 @@ // Update the branch predictor with the correct results. BPUpdate(predHist[tid].back().pc.instAddr(), predHist[tid].back().predTaken, - predHist[tid].back().bpHistory); + predHist[tid].back().bpHistory, + false); predHist[tid].pop_back(); } @@ -367,7 +368,7 @@ } BPUpdate((*hist_it).pc.instAddr(), actually_taken, - pred_hist.front().bpHistory); + pred_hist.front().bpHistory, true); // only update BTB on branch taken right??? if (actually_taken) @@ -425,12 +426,12 @@ void -BPredUnit::BPUpdate(Addr inst_PC, bool taken, void *bp_history) +BPredUnit::BPUpdate(Addr inst_PC, bool taken, void *bp_history, bool squashed) { if (predictor == Local) { localBP->update(inst_PC, taken, bp_history); } else if (predictor == Tournament) { - tournamentBP->update(inst_PC, taken, bp_history); + tournamentBP->update(inst_PC, taken, bp_history, squashed); } else { panic("Predictor type is unexpected value!"); } diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/o3/bpred_unit.hh --- a/src/cpu/o3/bpred_unit.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/o3/bpred_unit.hh Tue Sep 13 21:19:20 2011 -0500 @@ -137,6 +137,16 @@ */ bool BPLookup(Addr instPC, void * &bp_history); + /** + * If a branch is not taken, because the BTB address is invalid or missing, + * this function sets the appropriate counter in the global and local + * predictors to not taken. + * @param inst_PC The PC to look up the local predictor. + * @param bp_history Pointer that will be set to an object that + * has the branch predictor state associated with the lookup. + */ + void BPBTBUpdate(Addr instPC, void * &bp_history); + /** * Looks up a given PC in the BTB to see if a matching entry exists. * @param inst_PC The PC to look up. @@ -159,9 +169,11 @@ * @param taken Whether the branch was taken or not taken. * @param bp_history Pointer to the branch predictor state that is * associated with the branch lookup that is being updated. + * @param squashed Set to true when this function is called during a + * squash operation. * @todo Make this update flexible enough to handle a global predictor. */ - void BPUpdate(Addr instPC, bool taken, void *bp_history); + void BPUpdate(Addr instPC, bool taken, void *bp_history, bool squashed); /** * Updates the BTB with the target of a branch. diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/o3/bpred_unit_impl.hh --- a/src/cpu/o3/bpred_unit_impl.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/o3/bpred_unit_impl.hh Tue Sep 13 21:19:20 2011 -0500 @@ -166,12 +166,11 @@ BPUncond(bp_history); } else { ++condPredicted; - pred_taken = BPLookup(pc.instAddr(), bp_history); - DPRINTF(Fetch, "BranchPred: [tid:%i]: Branch predictor predicted %i " - "for PC %s\n", - tid, pred_taken, inst->pcState()); + DPRINTF(Fetch, "BranchPred:[tid:%i]: [sn:%i] Branch predictor" + " predicted %i for PC %s\n", + tid, inst->seqNum, pred_taken, inst->pcState()); } DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating prediction history " @@ -231,6 +230,15 @@ DPRINTF(Fetch, "BranchPred: [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()) { + BPBTBUpdate(pc.instAddr(), bp_history); + DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate" + " called for %s\n", + tid, inst->seqNum, inst->pcState()); + } TheISA::advancePC(target, inst->staticInst); } @@ -261,7 +269,7 @@ // Update the branch predictor with the correct results. BPUpdate(predHist[tid].back().pc, predHist[tid].back().predTaken, - predHist[tid].back().bpHistory); + predHist[tid].back().bpHistory, false); predHist[tid].pop_back(); } @@ -356,12 +364,15 @@ } BPUpdate((*hist_it).pc, actually_taken, - pred_hist.front().bpHistory); - - BTB.update((*hist_it).pc, corrTarget, tid); - - DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] " - "PC %s.\n", tid, (*hist_it).seqNum, (*hist_it).pc); + 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); + BTB.update((*hist_it).pc, corrTarget, tid); + } + 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); pred_hist.erase(hist_it); @@ -407,12 +418,26 @@ template void -BPredUnit::BPUpdate(Addr instPC, bool taken, void *bp_history) +BPredUnit::BPBTBUpdate(Addr instPC, void * &bp_history) +{ + if (predictor == Local) { + return localBP->BTBUpdate(instPC, bp_history); + } else if (predictor == Tournament) { + return tournamentBP->BTBUpdate(instPC, bp_history); + } else { + panic("Predictor type is unexpected value!"); + } +} + +template +void +BPredUnit::BPUpdate(Addr instPC, bool taken, void *bp_history, + bool squashed) { if (predictor == Local) { localBP->update(instPC, taken, bp_history); } else if (predictor == Tournament) { - tournamentBP->update(instPC, taken, bp_history); + tournamentBP->update(instPC, taken, bp_history, squashed); } else { panic("Predictor type is unexpected value!"); } diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/o3/commit_impl.hh --- a/src/cpu/o3/commit_impl.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/o3/commit_impl.hh Tue Sep 13 21:19:20 2011 -0500 @@ -855,6 +855,11 @@ fromIEW->mispredictInst[tid]; toIEW->commitInfo[tid].branchTaken = fromIEW->branchTaken[tid]; + if (toIEW->commitInfo[tid].mispredictInst) { + if (toIEW->commitInfo[tid].mispredictInst->isUncondCtrl()) { + toIEW->commitInfo[tid].branchTaken = true; + } + } toIEW->commitInfo[tid].squashInst = NULL; toIEW->commitInfo[tid].pc = fromIEW->pc[tid]; diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/o3/decode_impl.hh --- a/src/cpu/o3/decode_impl.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/o3/decode_impl.hh Tue Sep 13 21:19:20 2011 -0500 @@ -276,11 +276,15 @@ // Send back mispredict information. toFetch->decodeInfo[tid].branchMispredict = true; toFetch->decodeInfo[tid].predIncorrect = true; + toFetch->decodeInfo[tid].mispredictInst = inst; toFetch->decodeInfo[tid].squash = true; toFetch->decodeInfo[tid].doneSeqNum = inst->seqNum; toFetch->decodeInfo[tid].nextPC = inst->branchTarget(); toFetch->decodeInfo[tid].branchTaken = inst->pcState().branching(); toFetch->decodeInfo[tid].squashInst = inst; + if (toFetch->decodeInfo[tid].mispredictInst->isUncondCtrl()) { + toFetch->decodeInfo[tid].branchTaken = true; + } InstSeqNum squash_seq_num = inst->seqNum; diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/pred/2bit_local.hh --- a/src/cpu/pred/2bit_local.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/pred/2bit_local.hh Tue Sep 13 21:19:20 2011 -0500 @@ -65,6 +65,15 @@ bool lookup(Addr &branch_addr, void * &bp_history); /** + * Updates the branch predictor to Not Taken if a BTB entry is + * invalid or not found. + * @param branch_addr The address of the branch to look up. + * @param bp_history Pointer to any bp history state. + * @return Whether or not the branch is taken. + */ + void BTBUpdate(Addr &branch_addr, void * &bp_history); + + /** * Updates the branch predictor with the actual result of a branch. * @param branch_addr The address of the branch to update. * @param taken Whether or not the branch was taken. diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/pred/2bit_local.cc --- a/src/cpu/pred/2bit_local.cc Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/pred/2bit_local.cc Tue Sep 13 21:19:20 2011 -0500 @@ -79,6 +79,14 @@ } } +void +LocalBP::BTBUpdate(Addr &branch_addr, void * &bp_history) +{ +// Place holder for a function that is called to update predictor history when +// a BTB entry is invalid or not found. +} + + bool LocalBP::lookup(Addr &branch_addr, void * &bp_history) { diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/pred/tournament.hh --- a/src/cpu/pred/tournament.hh Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/pred/tournament.hh Tue Sep 13 21:19:20 2011 -0500 @@ -36,6 +36,8 @@ #include "base/types.hh" #include "cpu/o3/sat_counter.hh" + + /** * Implements a tournament branch predictor, hopefully identical to the one * used in the 21264. It has a local predictor, which uses a local history @@ -79,15 +81,24 @@ * @param bp_history Pointer that will be set to the BPHistory object. */ void uncondBr(void * &bp_history); - + /** + * Updates the branch predictor to Not Taken if a BTB entry is + * invalid or not found. + * @param branch_addr The address of the branch to look up. + * @param bp_history Pointer to any bp history state. + * @return Whether or not the branch is taken. + */ + void BTBUpdate(Addr &branch_addr, void * &bp_history); /** * Updates the branch predictor with the actual result of a branch. * @param branch_addr The address of the branch to update. * @param taken Whether or not the branch was taken. * @param bp_history Pointer to the BPHistory object that was created * when the branch was predicted. + * @param squashed is set when this function is called during a squash + * operation. */ - void update(Addr &branch_addr, bool taken, void *bp_history); + void update(Addr &branch_addr, bool taken, void *bp_history, bool squashed); /** * Restores the global branch history on a squash. @@ -149,11 +160,14 @@ static int newCount; #endif unsigned globalHistory; + unsigned localHistory; bool localPredTaken; bool globalPredTaken; bool globalUsed; }; + /** Flag for invalid predictor index */ + static const int invalidPredictorIndex = -1; /** Local counters. */ std::vector localCtrs; diff -r 5272eb9ee1c9 -r 25775387daee src/cpu/pred/tournament.cc --- a/src/cpu/pred/tournament.cc Tue Sep 13 21:17:10 2011 -0500 +++ b/src/cpu/pred/tournament.cc Tue Sep 13 21:19:20 2011 -0500 @@ -146,6 +146,18 @@ (localHistoryTable[local_history_idx] << 1); } + +void +TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history) +{ + unsigned local_history_idx = calcLocHistIdx(branch_addr); + //Update Global History to Not Taken + globalHistory = globalHistory & (globalHistoryMask - 1); + //Update Local History to Not Taken + localHistoryTable[local_history_idx] = + localHistoryTable[local_history_idx] & (localPredictorMask - 1); +} + bool TournamentBP::lookup(Addr &branch_addr, void * &bp_history) { @@ -174,6 +186,7 @@ history->localPredTaken = local_prediction; history->globalPredTaken = global_prediction; history->globalUsed = choice_prediction; + history->localHistory = local_predictor_idx; bp_history = (void *)history; assert(globalHistory < globalPredictorSize && @@ -184,30 +197,22 @@ // all histories. if (choice_prediction) { if (global_prediction) { -// updateHistoriesTaken(local_history_idx); -// globalCtrs[globalHistory].increment(); -// localCtrs[local_history_idx].increment(); updateGlobalHistTaken(); + updateLocalHistTaken(local_history_idx); return true; } else { -// updateHistoriesNotTaken(local_history_idx); -// globalCtrs[globalHistory].decrement(); -// localCtrs[local_history_idx].decrement(); updateGlobalHistNotTaken(); + updateLocalHistNotTaken(local_history_idx); return false; } } else { if (local_prediction) { -// updateHistoriesTaken(local_history_idx); -// globalCtrs[globalHistory].increment(); -// localCtrs[local_history_idx].increment(); updateGlobalHistTaken(); + updateLocalHistTaken(local_history_idx); return true; } else { -// updateHistoriesNotTaken(local_history_idx); -// globalCtrs[globalHistory].decrement(); -// localCtrs[local_history_idx].decrement(); updateGlobalHistNotTaken(); + updateLocalHistNotTaken(local_history_idx); return false; } } @@ -222,13 +227,15 @@ history->localPredTaken = true; history->globalPredTaken = true; history->globalUsed = true; + history->localHistory = invalidPredictorIndex; bp_history = static_cast(history); updateGlobalHistTaken(); } void -TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history) +TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history, + bool squashed) { unsigned local_history_idx; unsigned local_predictor_idx; @@ -259,33 +266,34 @@ // resolution of the branch. Global history is updated // speculatively and restored upon squash() calls, so it does not // need to be updated. + unsigned old_local_pred_index = history->localHistory + & localPredictorMask; if (taken) { - localCtrs[local_predictor_idx].increment(); globalCtrs[history->globalHistory].increment(); - - updateLocalHistTaken(local_history_idx); + if (old_local_pred_index != invalidPredictorIndex) { + localCtrs[old_local_pred_index].increment(); + } } else { - localCtrs[local_predictor_idx].decrement(); globalCtrs[history->globalHistory].decrement(); - - updateLocalHistNotTaken(local_history_idx); + if (old_local_pred_index != invalidPredictorIndex) { + localCtrs[old_local_pred_index].decrement(); + } } - bool mispredict = false; - - //global predictor used and mispredicted - if (history->globalUsed && history->globalPredTaken != taken) - mispredict = true; - //local predictor used and mispredicted - else if (!history->globalUsed && history->localPredTaken != taken) - mispredict = true; - - if (mispredict) { + if (squashed) { if (taken) { - globalHistory = globalHistory | 1; + globalHistory = (history->globalHistory << 1) | 1; + globalHistory = globalHistory & globalHistoryMask; + if (history->localHistory != invalidPredictorIndex) + localHistoryTable[local_history_idx] = + (history->localHistory << 1) | 1; } else { - unsigned mask = globalHistoryMask - 1; - globalHistory = globalHistory & mask; + globalHistory = (history->globalHistory << 1); + globalHistory = globalHistory & globalHistoryMask; + if (history->localHistory != invalidPredictorIndex) { + localHistoryTable[local_history_idx] = + history->localHistory << 1; + } } }