diff options
Diffstat (limited to 'cpu/o3/tournament_pred.cc')
| -rw-r--r-- | cpu/o3/tournament_pred.cc | 232 |
1 files changed, 134 insertions, 98 deletions
diff --git a/cpu/o3/tournament_pred.cc b/cpu/o3/tournament_pred.cc index 89da7b9f5..f8c95abd8 100644 --- a/cpu/o3/tournament_pred.cc +++ b/cpu/o3/tournament_pred.cc @@ -1,5 +1,5 @@ /* - * Copyright (c) 2004-2005 The Regents of The University of Michigan + * Copyright (c) 2004-2006 The Regents of The University of Michigan * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -26,6 +26,7 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ +#include "base/intmath.hh" #include "cpu/o3/tournament_pred.hh" TournamentBP::TournamentBP(unsigned _localPredictorSize, @@ -49,7 +50,9 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize, choiceCtrBits(_choiceCtrBits), instShiftAmt(_instShiftAmt) { - //Should do checks here to make sure sizes are correct (powers of 2) + if (!isPowerOf2(localPredictorSize)) { + fatal("Invalid local predictor size!\n"); + } //Setup the array of counters for the local predictor localCtrs.resize(localPredictorSize); @@ -57,6 +60,10 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize, for (int i = 0; i < localPredictorSize; ++i) localCtrs[i].setBits(localCtrBits); + if (!isPowerOf2(localHistoryTableSize)) { + fatal("Invalid local history table size!\n"); + } + //Setup the history table for the local table localHistoryTable.resize(localHistoryTableSize); @@ -66,6 +73,10 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize, // Setup the local history mask localHistoryMask = (1 << localHistoryBits) - 1; + if (!isPowerOf2(globalPredictorSize)) { + fatal("Invalid global predictor size!\n"); + } + //Setup the array of counters for the global predictor globalCtrs.resize(globalPredictorSize); @@ -77,12 +88,17 @@ TournamentBP::TournamentBP(unsigned _localPredictorSize, // Setup the global history mask globalHistoryMask = (1 << globalHistoryBits) - 1; + if (!isPowerOf2(choicePredictorSize)) { + fatal("Invalid choice predictor size!\n"); + } + //Setup the array of counters for the choice predictor choiceCtrs.resize(choicePredictorSize); for (int i = 0; i < choicePredictorSize; ++i) choiceCtrs[i].setBits(choiceCtrBits); + // @todo: Allow for different thresholds between the predictors. threshold = (1 << (localCtrBits - 1)) - 1; threshold = threshold / 2; } @@ -91,165 +107,185 @@ inline unsigned TournamentBP::calcLocHistIdx(Addr &branch_addr) { + // Get low order bits after removing instruction offset. return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); } inline void -TournamentBP::updateHistoriesTaken(unsigned local_history_idx) +TournamentBP::updateGlobalHistTaken() { globalHistory = (globalHistory << 1) | 1; globalHistory = globalHistory & globalHistoryMask; - - localHistoryTable[local_history_idx] = - (localHistoryTable[local_history_idx] << 1) | 1; } inline void -TournamentBP::updateHistoriesNotTaken(unsigned local_history_idx) +TournamentBP::updateGlobalHistNotTaken() { globalHistory = (globalHistory << 1); globalHistory = globalHistory & globalHistoryMask; +} +inline +void +TournamentBP::updateLocalHistTaken(unsigned local_history_idx) +{ + localHistoryTable[local_history_idx] = + (localHistoryTable[local_history_idx] << 1) | 1; +} + +inline +void +TournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) +{ localHistoryTable[local_history_idx] = (localHistoryTable[local_history_idx] << 1); } bool -TournamentBP::lookup(Addr &branch_addr) +TournamentBP::lookup(Addr &branch_addr, void * &bp_history) { - uint8_t local_prediction; + bool local_prediction; unsigned local_history_idx; unsigned local_predictor_idx; - uint8_t global_prediction; - uint8_t choice_prediction; + bool global_prediction; + bool choice_prediction; //Lookup in the local predictor to get its branch prediction local_history_idx = calcLocHistIdx(branch_addr); local_predictor_idx = localHistoryTable[local_history_idx] & localHistoryMask; - local_prediction = localCtrs[local_predictor_idx].read(); + local_prediction = localCtrs[local_predictor_idx].read() > threshold; //Lookup in the global predictor to get its branch prediction - global_prediction = globalCtrs[globalHistory].read(); + global_prediction = globalCtrs[globalHistory].read() > threshold; //Lookup in the choice predictor to see which one to use - choice_prediction = choiceCtrs[globalHistory].read(); - - //@todo Put a threshold value in for the three predictors that can - // be set through the constructor (so this isn't hard coded). - //Also should put some of this code into functions. - if (choice_prediction > threshold) { - if (global_prediction > threshold) { - updateHistoriesTaken(local_history_idx); - - assert(globalHistory < globalPredictorSize && - local_history_idx < localPredictorSize); - - globalCtrs[globalHistory].increment(); - localCtrs[local_history_idx].increment(); - + choice_prediction = choiceCtrs[globalHistory].read() > threshold; + + // Create BPHistory and pass it back to be recorded. + BPHistory *history = new BPHistory; + history->globalHistory = globalHistory; + history->localPredTaken = local_prediction; + history->globalPredTaken = global_prediction; + history->globalUsed = choice_prediction; + bp_history = (void *)history; + + assert(globalHistory < globalPredictorSize && + local_history_idx < localPredictorSize); + + // Commented code is for doing speculative update of counters and + // all histories. + if (choice_prediction) { + if (global_prediction) { +// updateHistoriesTaken(local_history_idx); +// globalCtrs[globalHistory].increment(); +// localCtrs[local_history_idx].increment(); + updateGlobalHistTaken(); return true; } else { - updateHistoriesNotTaken(local_history_idx); - - assert(globalHistory < globalPredictorSize && - local_history_idx < localPredictorSize); - - globalCtrs[globalHistory].decrement(); - localCtrs[local_history_idx].decrement(); - +// updateHistoriesNotTaken(local_history_idx); +// globalCtrs[globalHistory].decrement(); +// localCtrs[local_history_idx].decrement(); + updateGlobalHistNotTaken(); return false; } } else { - if (local_prediction > threshold) { - updateHistoriesTaken(local_history_idx); - - assert(globalHistory < globalPredictorSize && - local_history_idx < localPredictorSize); - - globalCtrs[globalHistory].increment(); - localCtrs[local_history_idx].increment(); - + if (local_prediction) { +// updateHistoriesTaken(local_history_idx); +// globalCtrs[globalHistory].increment(); +// localCtrs[local_history_idx].increment(); + updateGlobalHistTaken(); return true; } else { - updateHistoriesNotTaken(local_history_idx); - - assert(globalHistory < globalPredictorSize && - local_history_idx < localPredictorSize); - - globalCtrs[globalHistory].decrement(); - localCtrs[local_history_idx].decrement(); - +// updateHistoriesNotTaken(local_history_idx); +// globalCtrs[globalHistory].decrement(); +// localCtrs[local_history_idx].decrement(); + updateGlobalHistNotTaken(); return false; } } } -// Update the branch predictor if it predicted a branch wrong. void -TournamentBP::update(Addr &branch_addr, unsigned correct_gh, bool taken) +TournamentBP::uncondBr(void * &bp_history) { + // Create BPHistory and pass it back to be recorded. + BPHistory *history = new BPHistory; + history->globalHistory = globalHistory; + history->localPredTaken = true; + history->globalPredTaken = true; + bp_history = static_cast<void *>(history); + + updateGlobalHistTaken(); +} - uint8_t local_prediction; +void +TournamentBP::update(Addr &branch_addr, bool taken, void *bp_history) +{ unsigned local_history_idx; unsigned local_predictor_idx; - bool local_pred_taken; + unsigned local_predictor_hist; - uint8_t global_prediction; - bool global_pred_taken; - - // Load the correct global history into the register. - globalHistory = correct_gh; - - // Get the local predictor's current prediction, remove the incorrect - // update, and update the local predictor + // Get the local predictor's current prediction local_history_idx = calcLocHistIdx(branch_addr); - local_predictor_idx = localHistoryTable[local_history_idx]; - local_predictor_idx = (local_predictor_idx >> 1) & localHistoryMask; - - local_prediction = localCtrs[local_predictor_idx].read(); - local_pred_taken = local_prediction > threshold; - - //Get the global predictor's current prediction, and update the - //global predictor - global_prediction = globalCtrs[globalHistory].read(); - global_pred_taken = global_prediction > threshold; - - //Update the choice predictor to tell it which one was correct - if (local_pred_taken != global_pred_taken) { - //If the local prediction matches the actual outcome, decerement - //the counter. Otherwise increment the counter. - if (local_pred_taken == taken) { - choiceCtrs[globalHistory].decrement(); - } else { - choiceCtrs[globalHistory].increment(); + local_predictor_hist = localHistoryTable[local_history_idx]; + local_predictor_idx = local_predictor_hist & localHistoryMask; + + // Update the choice predictor to tell it which one was correct if + // there was a prediction. + if (bp_history) { + BPHistory *history = static_cast<BPHistory *>(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[globalHistory].decrement(); + } else if (history->globalPredTaken == taken){ + choiceCtrs[globalHistory].increment(); + } } + + // We're done with this history, now delete it. + delete history; } - if (taken) { - assert(globalHistory < globalPredictorSize && - local_predictor_idx < localPredictorSize); + assert(globalHistory < globalPredictorSize && + local_predictor_idx < localPredictorSize); + // 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) { localCtrs[local_predictor_idx].increment(); globalCtrs[globalHistory].increment(); - globalHistory = (globalHistory << 1) | 1; - globalHistory = globalHistory & globalHistoryMask; - - localHistoryTable[local_history_idx] |= 1; + updateLocalHistTaken(local_history_idx); } else { - assert(globalHistory < globalPredictorSize && - local_predictor_idx < localPredictorSize); - localCtrs[local_predictor_idx].decrement(); globalCtrs[globalHistory].decrement(); - globalHistory = (globalHistory << 1); - globalHistory = globalHistory & globalHistoryMask; - - localHistoryTable[local_history_idx] &= ~1; + updateLocalHistNotTaken(local_history_idx); } } + +void +TournamentBP::squash(void *bp_history) +{ + BPHistory *history = static_cast<BPHistory *>(bp_history); + + // Restore global history to state prior to this branch. + globalHistory = history->globalHistory; + + // Delete this BPHistory now that we're done with it. + delete history; +} + +#ifdef DEBUG +int +TournamentBP::BPHistory::newCount = 0; +#endif |