/*
- * 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
* Authors: Kevin Lim
*/
+#include "base/intmath.hh"
#include "cpu/o3/tournament_pred.hh"
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);
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);
// 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);
// 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;
}
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
projects / gem5.git / blobdiff