Javier Bueno Hedo has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/15775
Change subject: cpu: Move the Loop Predictor from LTAGE to an external class
......................................................................
cpu: Move the Loop Predictor from LTAGE to an external class
This code could be reused by other predictors requiring a loop predictor.
Change-Id: I60ad079a2c49b00a1f84d5cfd3611631883a4b57
---
M src/cpu/pred/SConscript
A src/cpu/pred/loop_predictor.cc
A src/cpu/pred/loop_predictor.hh
M src/cpu/pred/ltage.cc
M src/cpu/pred/ltage.hh
M src/cpu/pred/tage_sc_l.cc
6 files changed, 648 insertions(+), 419 deletions(-)
diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript
index 0028445..168a99b 100644
--- a/src/cpu/pred/SConscript
+++ b/src/cpu/pred/SConscript
@@ -45,6 +45,7 @@
Source ('bi_mode.cc')
Source('tage_base.cc')
Source('tage.cc')
+Source('loop_predictor.cc')
Source('ltage.cc')
Source('tage_sc_l.cc')
Source('tage_sc_l_8KB.cc')
diff --git a/src/cpu/pred/loop_predictor.cc b/src/cpu/pred/loop_predictor.cc
new file mode 100644
index 0000000..fd97943
--- /dev/null
+++ b/src/cpu/pred/loop_predictor.cc
@@ -0,0 +1,359 @@
+/*
+ * Copyright (c) 2014 The University of Wisconsin
+ *
+ * Copyright (c) 2006 INRIA (Institut National de Recherche en
+ * Informatique et en Automatique / French National Research Institute
+ * for Computer Science and Applied Mathematics)
+ *
+ * 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: Vignyan Reddy, Dibakar Gope and Arthur Perais,
+ * from André Seznec's code.
+ */
+
+#include "cpu/pred/loop_predictor.hh"
+
+#include "base/trace.hh"
+
+LoopPredictor::LoopPredictor(unsigned log_size_loop_pred,
+ unsigned loop_table_age_bits, unsigned loop_table_confidence_bits,
+ unsigned loop_table_tag_bits, unsigned loop_table_iter_bits,
+ unsigned log_loop_table_assoc, unsigned with_loop_bits,
+ bool use_direction_bit, bool use_speculation, bool use_hashing,
+ bool restrict_allocation, unsigned initial_loop_iter,
+ unsigned initial_loop_age, bool optional_age_reset)
+ : logSizeLoopPred(log_size_loop_pred),
+ loopTableAgeBits(loop_table_age_bits),
+ loopTableConfidenceBits(loop_table_confidence_bits),
+ loopTableTagBits(loop_table_tag_bits),
+ loopTableIterBits(loop_table_iter_bits),
+ logLoopTableAssoc(log_loop_table_assoc),
+ confidenceThreshold((1 << loopTableConfidenceBits) - 1),
+ loopTagMask((1 << loopTableTagBits) - 1),
+ loopNumIterMask((1 << loopTableIterBits) - 1),
+ loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1),
+ loopUseCounter(-1),
+ withLoopBits(with_loop_bits),
+ useDirectionBit(use_direction_bit),
+ useSpeculation(use_speculation),
+ useHashing(use_hashing),
+ restrictAllocation(restrict_allocation),
+ initialLoopIter(initial_loop_iter),
+ initialLoopAge(initial_loop_age),
+ optionalAgeReset(optional_age_reset)
+{
+ assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1));
+}
+
+void
+LoopPredictor::init()
+{
+ // we use uint16_t type for these vales, so they cannot be more than
+ // 16 bits
+ assert(loopTableTagBits <= 16);
+ assert(loopTableIterBits <= 16);
+
+ assert(logSizeLoopPred >= logLoopTableAssoc);
+
+ ltable = new LoopEntry[ULL(1) << logSizeLoopPred];
+}
+
+int
+LoopPredictor::lindex(Addr pc_in, unsigned instShiftAmt) const
+{
+ // The loop table is implemented as a linear table
+ // If associativity is N (N being 1 << logLoopTableAssoc),
+ // the first N entries are for set 0, the next N entries are for set 1,
+ // and so on.
+ // Thus, this function calculates the set and then it gets left shifted
+ // by logLoopTableAssoc in order to return the index of the first of
the
+ // N entries of the set
+ Addr pc = pc_in >> instShiftAmt;
+ if (useHashing) {
+ // copied from TAGE-SC-L
+ // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
+ pc ^= pc_in;
+ }
+ return ((pc & loopSetMask) << logLoopTableAssoc);
+}
+
+int
+LoopPredictor::finallindex(int index, int lowPcBits, int way) const
+{
+ // copied from TAGE-SC-L
+ // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
+ return (useHashing ? (index ^ ((lowPcBits >> way) <<
logLoopTableAssoc)) :
+ (index))
+ + way;
+}
+
+//loop prediction: only used if high confidence
+bool
+LoopPredictor::getLoop(Addr pc, BranchInfo* bi, bool speculative,
+ unsigned instShiftAmt) const
+{
+ bi->loopHit = -1;
+ bi->loopPredValid = false;
+ bi->loopIndex = lindex(pc, instShiftAmt);
+
+ if (useHashing) {
+ unsigned pcShift = logSizeLoopPred - logLoopTableAssoc;
+ bi->loopIndexB = (pc >> pcShift) & loopSetMask;
+ bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift +
loopTableTagBits));
+ bi->loopTag &= loopTagMask;
+ } else {
+ unsigned pcShift = instShiftAmt + logSizeLoopPred -
logLoopTableAssoc;
+ bi->loopTag = (pc >> pcShift) & loopTagMask;
+ // bi->loopIndexB is not used without hash
+ }
+
+ for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
+ int idx = finallindex(bi->loopIndex, bi->loopIndexB, i);
+ if (ltable[idx].tag == bi->loopTag) {
+ bi->loopHit = i;
+ bi->loopPredValid = calcConf(idx);
+
+ uint16_t iter = speculative ? ltable[idx].currentIterSpec
+ : ltable[idx].currentIter;
+
+ if ((iter + 1) == ltable[idx].numIter) {
+ return useDirectionBit ? !(ltable[idx].dir) : false;
+ } else {
+ return useDirectionBit ? (ltable[idx].dir) : true;
+ }
+ }
+ }
+ return false;
+}
+
+bool
+LoopPredictor::calcConf(int index) const
+{
+ return ltable[index].confidence == confidenceThreshold;
+}
+
+void
+LoopPredictor::specLoopUpdate(bool taken, BranchInfo* bi)
+{
+ if (bi->loopHit>=0) {
+ int index = finallindex(bi->loopIndex, bi->loopIndexB,
bi->loopHit);
+ if (taken != ltable[index].dir) {
+ ltable[index].currentIterSpec = 0;
+ } else {
+ ltable[index].currentIterSpec =
+ (ltable[index].currentIterSpec + 1) & loopNumIterMask;
+ }
+ }
+}
+
+bool
+LoopPredictor::optionalAgeInc() const
+{
+ return false;
+}
+
+void
+LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool
tage_pred,
+ int random0, int random1)
+{
+ int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
+ if (bi->loopHit >= 0) {
+ //already a hit
+ if (bi->loopPredValid) {
+ if (taken != bi->loopPred) {
+ // free the entry
+ ltable[idx].numIter = 0;
+ ltable[idx].age = 0;
+ ltable[idx].confidence = 0;
+ ltable[idx].currentIter = 0;
+ return;
+ } else if (bi->loopPred != tage_pred || optionalAgeInc()) {
+ unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
+ }
+ }
+
+ ltable[idx].currentIter =
+ (ltable[idx].currentIter + 1) & loopNumIterMask;
+ if (ltable[idx].currentIter > ltable[idx].numIter) {
+ ltable[idx].confidence = 0;
+ if (ltable[idx].numIter != 0) {
+ // free the entry
+ ltable[idx].numIter = 0;
+ if (optionalAgeReset) {
+ ltable[idx].age = 0;
+ }
+ }
+ }
+
+ if (taken != (useDirectionBit ? ltable[idx].dir : true)) {
+ if (ltable[idx].currentIter == ltable[idx].numIter) {
+ unsignedCtrUpdate(ltable[idx].confidence, true,
+ loopTableConfidenceBits);
+ //just do not predict when the loop count is 1 or 2
+ if (ltable[idx].numIter < 3) {
+ // free the entry
+ ltable[idx].dir = taken; // ignored if no
useDirectionBit
+ ltable[idx].numIter = 0;
+ ltable[idx].age = 0;
+ ltable[idx].confidence = 0;
+ }
+ } else {
+ //DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n",
pc);
+ if (ltable[idx].numIter == 0) {
+ // first complete nest;
+ ltable[idx].confidence = 0;
+ ltable[idx].numIter = ltable[idx].currentIter;
+ } else {
+ //not the same number of iterations as last time: free
the
+ //entry
+ ltable[idx].numIter = 0;
+ if (optionalAgeReset) {
+ ltable[idx].age = 0;
+ }
+ ltable[idx].confidence = 0;
+ }
+ }
+ ltable[idx].currentIter = 0;
+ }
+
+ } else if (useDirectionBit ? (bi->predTaken != taken) : taken) {
+ if ((random1 & 3) == 0 || !restrictAllocation) {
+ //try to allocate an entry on taken branch
+ int nrand = random0;
+ for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
+ int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) -
1);
+ idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit);
+ if (ltable[idx].age == 0) {
+ ltable[idx].dir = !taken; // ignored if no
useDirectionBit
+ ltable[idx].tag = bi->loopTag;
+ ltable[idx].numIter = 0;
+ ltable[idx].age = initialLoopAge;
+ ltable[idx].confidence = 0;
+ ltable[idx].currentIter = initialLoopIter;
+ break;
+
+ } else {
+ ltable[idx].age--;
+ }
+ if (restrictAllocation) {
+ break;
+ }
+ }
+ }
+ }
+}
+
+bool
+LoopPredictor::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
+ BranchInfo* bi, bool prev_pred_taken, unsigned
instShiftAmt)
+{
+ bool pred_taken = prev_pred_taken;
+ if (cond_branch) {
+ // loop prediction
+ bi->loopPred = getLoop(branch_pc, bi, useSpeculation,
instShiftAmt);
+
+ if ((loopUseCounter >= 0) && bi->loopPredValid) {
+ pred_taken = bi->loopPred;
+ bi->loopPredUsed = true;
+ }
+
+ if (useSpeculation) {
+ specLoopUpdate(pred_taken, bi);
+ }
+ }
+
+ return pred_taken;
+}
+
+void
+LoopPredictor::squash(ThreadID tid, BranchInfo *bi)
+{
+ if (bi->loopHit >= 0) {
+ int idx = finallindex(bi->loopIndex,
+ bi->loopIndexB,
+ bi->loopHit);
+ ltable[idx].currentIterSpec = bi->currentIter;
+ }
+}
+
+void
+LoopPredictor::squashLoop(BranchInfo* bi)
+{
+ if (bi->loopHit >= 0) {
+ int idx = finallindex(bi->loopIndex,
+ bi->loopIndexB,
+ bi->loopHit);
+ ltable[idx].currentIterSpec = bi->currentIter;
+ }
+}
+
+void
+LoopPredictor::updateStats(bool taken, BranchInfo* bi)
+{
+ if (taken == bi->loopPred) {
+ loopPredictorCorrect++;
+ } else {
+ loopPredictorWrong++;
+ }
+}
+
+void
+LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
+ bool tage_pred, BranchInfo* bi,
+ unsigned instShiftAmt, int rand0, int
rand1)
+{
+ if (useSpeculation) {
+ // recalculate loop prediction without speculation
+ // It is ok to overwrite the loop prediction fields in bi
+ // as the stats have already been updated with the previous
+ // values
+ bi->loopPred = getLoop(branch_pc, bi, false, instShiftAmt);
+ }
+
+ if (bi->loopPredValid) {
+ if (bi->predTaken != bi->loopPred) {
+ signedCtrUpdate(loopUseCounter,
+ (bi->loopPred == taken),
+ withLoopBits);
+ }
+ }
+
+ loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1);
+}
+
+void
+LoopPredictor::regStats()
+{
+ loopPredictorCorrect
+ .name(name() + ".loopPredictorCorrect")
+ .desc("Number of times the loop predictor is the provider and "
+ "the prediction is correct");
+
+ loopPredictorWrong
+ .name(name() + ".loopPredictorWrong")
+ .desc("Number of times the loop predictor is the provider and "
+ "the prediction is wrong");
+}
diff --git a/src/cpu/pred/loop_predictor.hh b/src/cpu/pred/loop_predictor.hh
new file mode 100644
index 0000000..f31ea49
--- /dev/null
+++ b/src/cpu/pred/loop_predictor.hh
@@ -0,0 +1,251 @@
+/*
+ * Copyright (c) 2014 The University of Wisconsin
+ *
+ * Copyright (c) 2006 INRIA (Institut National de Recherche en
+ * Informatique et en Automatique / French National Research Institute
+ * for Computer Science and Applied Mathematics)
+ *
+ * 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: Vignyan Reddy, Dibakar Gope and Arthur Perais,
+ * from André Seznec's code.
+ */
+
+#ifndef __CPU_PRED_LOOP_PREDICTOR_HH__
+#define __CPU_PRED_LOOP_PREDICTOR_HH__
+
+#include "base/statistics.hh"
+#include "base/types.hh"
+
+class LoopPredictor {
+ protected:
+ /**
+ * Updates an unsigned counter based on up/down parameter
+ * @param ctr Reference to counter to update.
+ * @param up Boolean indicating if the counter is
incremented/decremented
+ * If true it is incremented, if false it is decremented
+ * @param nbits Counter width.
+ */
+ static inline void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned
nbits)
+ {
+ assert(nbits <= sizeof(uint8_t) << 3);
+ if (up) {
+ if (ctr < ((1 << nbits) - 1))
+ ctr++;
+ } else {
+ if (ctr)
+ ctr--;
+ }
+ }
+ static inline void signedCtrUpdate(int8_t &ctr, bool up, unsigned
nbits)
+ {
+ if (up) {
+ if (ctr < ((1 << (nbits - 1)) - 1))
+ ctr++;
+ } else {
+ if (ctr > -(1 << (nbits - 1)))
+ ctr--;
+ }
+ }
+ // Prediction Structures
+ // Loop Predictor Entry
+ struct LoopEntry
+ {
+ uint16_t numIter;
+ uint16_t currentIter;
+ uint16_t currentIterSpec; // only for useSpeculation
+ uint8_t confidence;
+ uint16_t tag;
+ uint8_t age;
+ bool dir; // only for useDirectionBit
+
+ LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
+ confidence(0), tag(0), age(0), dir(0) { }
+ };
+
+ // Primary branch history entry
+ struct BranchInfo
+ {
+ uint16_t loopTag;
+ uint16_t currentIter;
+
+ bool loopPred;
+ bool loopPredValid;
+ bool loopPredUsed;
+ int loopIndex;
+ int loopIndexB; // only for useHashing
+ int loopHit;
+ bool predTaken;
+
+ BranchInfo()
+ : loopTag(0), currentIter(0),
+ loopPred(false),
+ loopPredValid(false), loopIndex(0), loopIndexB(0),
loopHit(0),
+ predTaken(false)
+ {}
+ };
+
+ /**
+ * Computes the index used to access the
+ * loop predictor.
+ * @param pc_in The unshifted branch PC.
+ * @param instShiftAmt Shift the pc by as many bits
+ */
+ int lindex(Addr pc_in, unsigned instShiftAmt) const;
+
+ /**
+ * Computes the index used to access the
+ * ltable structures.
+ * It may take hashing into account
+ * @param index Result of lindex function
+ * @param lowPcBits PC bits masked with set size
+ * @param way Way to be used
+ */
+ int finallindex(int lindex, int lowPcBits, int way) const;
+
+ /**
+ * Get a branch prediction from the loop
+ * predictor.
+ * @param pc The unshifted branch PC.
+ * @param bi Pointer to information on the
+ * prediction.
+ * @param speculative Use speculative number of iterations
+ * @param instShiftAmt Shift the pc by as many bits (if hashing is not
+ * used)
+ * @result the result of the prediction, if it could be predicted
+ */
+ bool getLoop(Addr pc, BranchInfo* bi, bool speculative,
+ unsigned instShiftAmt) const;
+
+ /**
+ * Updates the loop predictor.
+ * @param pc The unshifted branch PC.
+ * @param taken The actual branch outcome.
+ * @param bi Pointer to information on the
+ * prediction recorded at prediction time.
+ * @param tage_pred tage prediction of the branch
+ * @param random0 random value
+ * @param random1 random value
+ */
+ void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred,
+ int random0, int random1);
+
+ /**
+ * Speculatively updates the loop predictor
+ * iteration count (only for useSpeculation).
+ * @param taken The predicted branch outcome.
+ * @param bi Pointer to information on the prediction
+ * recorded at prediction time.
+ */
+ void specLoopUpdate(bool taken, BranchInfo* bi);
+
+ /**
+ * Update LTAGE for conditional branches.
+ * @param branch_pc The unshifted branch PC.
+ * @param taken Actual branch outcome.
+ * @param tage_pred Prediction from TAGE
+ * @param bi Pointer to information on the prediction
+ * recorded at prediction time.
+ * @param instShiftAmt Number of bits to shift instructions
+ * @param rand0 Random integer value
+ * @param rand1 Random integer value
+ */
+ void condBranchUpdate(
+ ThreadID tid, Addr branch_pc, bool taken, bool tage_pred,
+ BranchInfo* bi, unsigned instShiftAmt, int rand0, int rand1);
+
+ /**
+ * Get the loop prediction
+ * @param tid The thread ID to select the global
+ * histories to use.
+ * @param branch_pc The unshifted branch PC.
+ * @param cond_branch True if the branch is conditional.
+ * @param bi Reference to wrapping pointer to allow storing
+ * derived class prediction information in the base class.
+ * @param prev_pred_taken Result of the TAGE prediction
+ * @param instShiftAmt Shift the pc by as many bits
+ * @param instShiftAmt Shift the pc by as many bits
+ * @result the prediction, true if taken
+ */
+ bool loopPredict(
+ ThreadID tid, Addr branch_pc, bool cond_branch,
+ BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt);
+
+ /**
+ * Update the stats
+ * @param taken Actual branch outcome
+ * @param bi Pointer to information on the prediction
+ * recorded at prediction time.
+ */
+ void updateStats(bool taken, BranchInfo* bi);
+
+ void squashLoop(BranchInfo * bi);
+
+ void squash(ThreadID tid, BranchInfo *bi);
+
+ virtual bool calcConf(int index) const;
+ virtual bool optionalAgeInc() const;
+
+ const unsigned logSizeLoopPred;
+ const unsigned loopTableAgeBits;
+ const unsigned loopTableConfidenceBits;
+ const unsigned loopTableTagBits;
+ const unsigned loopTableIterBits;
+ const unsigned logLoopTableAssoc;
+ const uint8_t confidenceThreshold;
+ const uint16_t loopTagMask;
+ const uint16_t loopNumIterMask;
+ const int loopSetMask;
+
+ LoopEntry *ltable;
+
+ int8_t loopUseCounter;
+ unsigned withLoopBits;
+
+ const bool useDirectionBit;
+ const bool useSpeculation;
+ const bool useHashing;
+ const bool restrictAllocation;
+ const unsigned initialLoopIter;
+ const unsigned initialLoopAge;
+ const bool optionalAgeReset;
+
+ // stats
+ Stats::Scalar loopPredictorCorrect;
+ Stats::Scalar loopPredictorWrong;
+
+ void init();
+ void regStats();
+
+ LoopPredictor(unsigned log_size_loop_pred,
+ unsigned loop_table_age_bits, unsigned loop_table_confidence_bits,
+ unsigned loop_table_tag_bits, unsigned loop_table_iter_bits,
+ unsigned log_loop_table_assoc, unsigned with_loop_bits,
+ bool use_direction_bit, bool use_speculation, bool use_hashing,
+ bool restrict_allocation, unsigned initial_loop_iter,
+ unsigned initial_loop_age, bool optional_age_reset);
+};
+#endif//__CPU_PRED_LOOP_PREDICTOR_HH__
diff --git a/src/cpu/pred/ltage.cc b/src/cpu/pred/ltage.cc
index 4c2ec9e..e615ffa 100644
--- a/src/cpu/pred/ltage.cc
+++ b/src/cpu/pred/ltage.cc
@@ -47,26 +47,21 @@
#include "debug/LTage.hh"
LTAGE::LTAGE(const LTAGEParams *params)
- : TAGE(params),
- logSizeLoopPred(params->logSizeLoopPred),
- loopTableAgeBits(params->loopTableAgeBits),
- loopTableConfidenceBits(params->loopTableConfidenceBits),
- loopTableTagBits(params->loopTableTagBits),
- loopTableIterBits(params->loopTableIterBits),
- logLoopTableAssoc(params->logLoopTableAssoc),
- confidenceThreshold((1 << loopTableConfidenceBits) - 1),
- loopTagMask((1 << loopTableTagBits) - 1),
- loopNumIterMask((1 << loopTableIterBits) - 1),
- loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1),
- loopUseCounter(-1),
- withLoopBits(params->withLoopBits),
- useDirectionBit(params->useDirectionBit),
- useSpeculation(params->useSpeculation),
- useHashing(params->useHashing),
- restrictAllocation(params->restrictAllocation),
- initialLoopIter(params->initialLoopIter),
- initialLoopAge(params->initialLoopAge),
- optionalAgeReset(params->optionalAgeReset)
+ : TAGE(params), LoopPredictor(
+ params->logSizeLoopPred,
+ params->loopTableAgeBits,
+ params->loopTableConfidenceBits,
+ params->loopTableTagBits,
+ params->loopTableIterBits,
+ params->logLoopTableAssoc,
+ params->withLoopBits,
+ params->useDirectionBit,
+ params->useSpeculation,
+ params->useHashing,
+ params->restrictAllocation,
+ params->initialLoopIter,
+ params->initialLoopAge,
+ params->optionalAgeReset)
{
assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1));
}
@@ -76,206 +71,9 @@
{
TAGE::init();
- // we use uint16_t type for these vales, so they cannot be more than
- // 16 bits
- assert(loopTableTagBits <= 16);
- assert(loopTableIterBits <= 16);
-
- assert(logSizeLoopPred >= logLoopTableAssoc);
-
- ltable = new LoopEntry[ULL(1) << logSizeLoopPred];
+ LoopPredictor::init();
}
-int
-LTAGE::lindex(Addr pc_in) const
-{
- // The loop table is implemented as a linear table
- // If associativity is N (N being 1 << logLoopTableAssoc),
- // the first N entries are for set 0, the next N entries are for set 1,
- // and so on.
- // Thus, this function calculates the set and then it gets left shifted
- // by logLoopTableAssoc in order to return the index of the first of
the
- // N entries of the set
- Addr pc = pc_in >> instShiftAmt;
- if (useHashing) {
- // copied from TAGE-SC-L
- // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
- pc ^= pc_in;
- }
- return ((pc & loopSetMask) << logLoopTableAssoc);
-}
-
-int
-LTAGE::finallindex(int index, int lowPcBits, int way) const
-{
- // copied from TAGE-SC-L
- // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
- return (useHashing ? (index ^ ((lowPcBits >> way) <<
logLoopTableAssoc)) :
- (index))
- + way;
-}
-
-//loop prediction: only used if high confidence
-bool
-LTAGE::getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const
-{
- bi->loopHit = -1;
- bi->loopPredValid = false;
- bi->loopIndex = lindex(pc);
-
- if (useHashing) {
- unsigned pcShift = logSizeLoopPred - logLoopTableAssoc;
- bi->loopIndexB = (pc >> pcShift) & loopSetMask;
- bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift +
loopTableTagBits));
- bi->loopTag &= loopTagMask;
- } else {
- unsigned pcShift = instShiftAmt + logSizeLoopPred -
logLoopTableAssoc;
- bi->loopTag = (pc >> pcShift) & loopTagMask;
- // bi->loopIndexB is not used without hash
- }
-
- for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
- int idx = finallindex(bi->loopIndex, bi->loopIndexB, i);
- if (ltable[idx].tag == bi->loopTag) {
- bi->loopHit = i;
- bi->loopPredValid = calcConf(idx);
-
- uint16_t iter = speculative ? ltable[idx].currentIterSpec
- : ltable[idx].currentIter;
-
- if ((iter + 1) == ltable[idx].numIter) {
- return useDirectionBit ? !(ltable[idx].dir) : false;
- } else {
- return useDirectionBit ? (ltable[idx].dir) : true;
- }
- }
- }
- return false;
-}
-
-bool
-LTAGE::calcConf(int index) const
-{
- return ltable[index].confidence == confidenceThreshold;
-}
-
-void
-LTAGE::specLoopUpdate(bool taken, LTageBranchInfo* bi)
-{
- if (bi->loopHit>=0) {
- int index = finallindex(bi->loopIndex, bi->loopIndexB,
bi->loopHit);
- if (taken != ltable[index].dir) {
- ltable[index].currentIterSpec = 0;
- } else {
- ltable[index].currentIterSpec =
- (ltable[index].currentIterSpec + 1) & loopNumIterMask;
- }
- }
-}
-
-bool
-LTAGE::optionalAgeInc() const
-{
- return false;
-}
-
-void
-LTAGE::loopUpdate(Addr pc, bool taken, LTageBranchInfo* bi)
-{
- int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
- if (bi->loopHit >= 0) {
- //already a hit
- if (bi->loopPredValid) {
- if (taken != bi->loopPred) {
- // free the entry
- ltable[idx].numIter = 0;
- ltable[idx].age = 0;
- ltable[idx].confidence = 0;
- ltable[idx].currentIter = 0;
- return;
- } else if (bi->loopPred != bi->tagePred || optionalAgeInc()) {
- DPRINTF(LTage, "Loop Prediction success:%lx\n",pc);
- unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
- }
- }
-
- ltable[idx].currentIter =
- (ltable[idx].currentIter + 1) & loopNumIterMask;
- if (ltable[idx].currentIter > ltable[idx].numIter) {
- ltable[idx].confidence = 0;
- if (ltable[idx].numIter != 0) {
- // free the entry
- ltable[idx].numIter = 0;
- if (optionalAgeReset) {
- ltable[idx].age = 0;
- }
- ltable[idx].confidence = 0;
- }
- }
-
- if (taken != (useDirectionBit ? ltable[idx].dir : true)) {
- if (ltable[idx].currentIter == ltable[idx].numIter) {
- DPRINTF(LTage, "Loop End predicted successfully:%lx\n",
pc);
-
- unsignedCtrUpdate(ltable[idx].confidence, true,
- loopTableConfidenceBits);
- //just do not predict when the loop count is 1 or 2
- if (ltable[idx].numIter < 3) {
- // free the entry
- ltable[idx].dir = taken; // ignored if no
useDirectionBit
- ltable[idx].numIter = 0;
- ltable[idx].age = 0;
- ltable[idx].confidence = 0;
- }
- } else {
- DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc);
- if (ltable[idx].numIter == 0) {
- // first complete nest;
- ltable[idx].confidence = 0;
- ltable[idx].numIter = ltable[idx].currentIter;
- } else {
- //not the same number of iterations as last time: free
the
- //entry
- ltable[idx].numIter = 0;
- if (optionalAgeReset) {
- ltable[idx].age = 0;
- }
- ltable[idx].confidence = 0;
- }
- }
- ltable[idx].currentIter = 0;
- }
-
- } else if (useDirectionBit ? (bi->predTaken != taken) : taken) {
- if ((getRandom() & 3) == 0 || ! restrictAllocation) {
- //try to allocate an entry on taken branch
- int nrand = getRandom();
- for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
- int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) -
1);
- idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit);
- if (ltable[idx].age == 0) {
- DPRINTF(LTage,
- "Allocating loop pred entry for branch %lx\n",
- pc);
- ltable[idx].dir = !taken; // ignored if no
useDirectionBit
- ltable[idx].tag = bi->loopTag;
- ltable[idx].numIter = 0;
- ltable[idx].age = initialLoopAge;
- ltable[idx].confidence = 0;
- ltable[idx].currentIter = initialLoopIter;
- break;
-
- } else {
- ltable[idx].age--;
- }
- if (restrictAllocation) {
- break;
- }
- }
- }
- }
-
-}
//prediction
bool
@@ -286,37 +84,22 @@
bool pred_taken = tagePredict(tid, branch_pc, cond_branch, bi);
- pred_taken = loopPredict(tid, branch_pc, cond_branch, bi, pred_taken);
+ pred_taken = loopPredict(tid, branch_pc, cond_branch, bi, pred_taken,
+ instShiftAmt);
- // record final prediction
- bi->predTaken = pred_taken;
-
- return pred_taken;
-}
-
-bool
-LTAGE::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
- LTageBranchInfo* bi, bool prev_pred_taken)
-{
- bool pred_taken = prev_pred_taken;
if (cond_branch) {
- // loop prediction
- bi->loopPred = getLoop(branch_pc, bi, useSpeculation);
-
- if ((loopUseCounter >= 0) && bi->loopPredValid) {
- pred_taken = bi->loopPred;
+ if (bi->loopPredUsed) {
bi->provider = LOOP;
}
DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, "
"loopValid?:%d, loopUseCounter:%d, tagePred:%d,
altPred:%d\n",
branch_pc, pred_taken, bi->loopPred, bi->loopPredValid,
loopUseCounter, bi->tagePred, bi->altTaken);
-
- if (useSpeculation) {
- specLoopUpdate(pred_taken, bi);
- }
}
+ // record final prediction
+ bi->predTaken = pred_taken;
+
return pred_taken;
}
@@ -326,23 +109,8 @@
{
LTageBranchInfo* bi = static_cast<LTageBranchInfo*>(tage_bi);
- if (useSpeculation) {
- // recalculate loop prediction without speculation
- // It is ok to overwrite the loop prediction fields in bi
- // as the stats have already been updated with the previous
- // values
- bi->loopPred = getLoop(branch_pc, bi, false);
- }
-
- if (bi->loopPredValid) {
- if (bi->predTaken != bi->loopPred) {
- ctrUpdate(loopUseCounter,
- (bi->loopPred == taken),
- withLoopBits);
- }
- }
-
- loopUpdate(branch_pc, taken, bi);
+ LoopPredictor::condBranchUpdate(tid, branch_pc, taken, bi->tagePred,
bi,
+ instShiftAmt, getRandom(), getRandom());
TAGE::condBranchUpdate(tid, branch_pc, taken, bi, nrand, corrTarget);
}
@@ -354,19 +122,8 @@
LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history);
- squashLoop(bi);
-}
-
-void
-LTAGE::squashLoop(LTageBranchInfo* bi)
-{
if (bi->condBranch) {
- if (bi->loopHit >= 0) {
- int idx = finallindex(bi->loopIndex,
- bi->loopIndexB,
- bi->loopHit);
- ltable[idx].currentIterSpec = bi->currentIter;
- }
+ squashLoop(bi);
}
}
@@ -374,19 +131,14 @@
LTAGE::squash(ThreadID tid, void *bp_history)
{
LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history);
+
if (bi->condBranch) {
- if (bi->loopHit >= 0) {
- int idx = finallindex(bi->loopIndex,
- bi->loopIndexB,
- bi->loopHit);
- ltable[idx].currentIterSpec = bi->currentIter;
- }
+ LoopPredictor::squash(tid, bi);
}
TAGE::squash(tid, bp_history);
}
-
void
LTAGE::updateStats(bool taken, TageBranchInfo* bi)
{
@@ -395,34 +147,18 @@
LTageBranchInfo * ltage_bi = static_cast<LTageBranchInfo *>(bi);
if (ltage_bi->provider == LOOP) {
- if (taken == ltage_bi->loopPred) {
- loopPredictorCorrect++;
- } else {
- loopPredictorWrong++;
- }
+ LoopPredictor::updateStats(taken, ltage_bi);
}
}
-
-
void
LTAGE::regStats()
{
TAGE::regStats();
- loopPredictorCorrect
- .name(name() + ".loopPredictorCorrect")
- .desc("Number of times the loop predictor is the provider and "
- "the prediction is correct");
-
- loopPredictorWrong
- .name(name() + ".loopPredictorWrong")
- .desc("Number of times the loop predictor is the provider and "
- "the prediction is wrong");
+ LoopPredictor::regStats();
}
-
-
LTAGE*
LTAGEParams::create()
{
diff --git a/src/cpu/pred/ltage.hh b/src/cpu/pred/ltage.hh
index 39362d2..413a80b 100644
--- a/src/cpu/pred/ltage.hh
+++ b/src/cpu/pred/ltage.hh
@@ -56,10 +56,11 @@
#include <vector>
#include "base/types.hh"
+#include "cpu/pred/loop_predictor.hh"
#include "cpu/pred/tage.hh"
#include "params/LTAGE.hh"
-class LTAGE: public TAGE
+class LTAGE: public TAGE, public LoopPredictor
{
public:
LTAGE(const LTAGEParams *params);
@@ -71,96 +72,22 @@
virtual void regStats() override;
protected:
- // Prediction Structures
- // Loop Predictor Entry
- struct LoopEntry
- {
- uint16_t numIter;
- uint16_t currentIter;
- uint16_t currentIterSpec; // only for useSpeculation
- uint8_t confidence;
- uint16_t tag;
- uint8_t age;
- bool dir; // only for useDirectionBit
-
- LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
- confidence(0), tag(0), age(0), dir(0) { }
- };
// more provider types
enum {
LOOP = LAST_TAGE_PROVIDER_TYPE + 1,
LAST_LTAGE_PROVIDER_TYPE = LOOP
};
-
// Primary branch history entry
- struct LTageBranchInfo : public TageBranchInfo
+ struct LTageBranchInfo : public TageBranchInfo,
+ public LoopPredictor::BranchInfo
{
- uint16_t loopTag;
- uint16_t currentIter;
-
- bool loopPred;
- bool loopPredValid;
- int loopIndex;
- int loopIndexB; // only for useHashing
- int loopHit;
- bool predTaken;
-
- LTageBranchInfo(int sz)
- : TageBranchInfo(sz),
- loopTag(0), currentIter(0),
- loopPred(false),
- loopPredValid(false), loopIndex(0), loopIndexB(0),
loopHit(0),
- predTaken(false)
+ LTageBranchInfo(int sz) : TageBranchInfo(sz),
+ LoopPredictor::BranchInfo()
{}
};
/**
- * Computes the index used to access the
- * loop predictor.
- * @param pc_in The unshifted branch PC.
- */
- int lindex(Addr pc_in) const;
-
- /**
- * Computes the index used to access the
- * ltable structures.
- * It may take hashing into account
- * @param index Result of lindex function
- * @param lowPcBits PC bits masked with set size
- * @param way Way to be used
- */
- int finallindex(int lindex, int lowPcBits, int way) const;
-
- /**
- * Get a branch prediction from the loop
- * predictor.
- * @param pc The unshifted branch PC.
- * @param bi Pointer to information on the
- * prediction.
- * @param speculative Use speculative number of iterations
- */
- bool getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const;
-
- /**
- * Updates the loop predictor.
- * @param pc The unshifted branch PC.
- * @param taken The actual branch outcome.
- * @param bi Pointer to information on the
- * prediction recorded at prediction time.
- */
- void loopUpdate(Addr pc, bool Taken, LTageBranchInfo* bi);
-
- /**
- * Speculatively updates the loop predictor
- * iteration count (only for useSpeculation).
- * @param taken The predicted branch outcome.
- * @param bi Pointer to information on the prediction
- * recorded at prediction time.
- */
- void specLoopUpdate(bool taken, LTageBranchInfo* bi);
-
- /**
* Update LTAGE for conditional branches.
* @param branch_pc The unshifted branch PC.
* @param taken Actual branch outcome.
@@ -187,20 +114,6 @@
ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override;
/**
- * Get the loop prediction
- * @param tid The thread ID to select the global
- * histories to use.
- * @param branch_pc The unshifted branch PC.
- * @param cond_branch True if the branch is conditional.
- * @param bi Reference to wrapping pointer to allow storing
- * derived class prediction information in the base class.
- * @param prev_pred_taken Result of the TAGE prediction
- */
- bool loopPredict(
- ThreadID tid, Addr branch_pc, bool cond_branch,
- LTageBranchInfo* bi, bool prev_pred_taken);
-
- /**
* Restores speculatively updated path and direction histories.
* Also recomputes compressed (folded) histories based on the
* correct branch outcome.
@@ -224,38 +137,6 @@
*/
virtual void updateStats(bool taken, TageBranchInfo* bi) override;
- void squashLoop(LTageBranchInfo * bi);
-
- virtual bool calcConf(int index) const;
- virtual bool optionalAgeInc() const;
-
- const unsigned logSizeLoopPred;
- const unsigned loopTableAgeBits;
- const unsigned loopTableConfidenceBits;
- const unsigned loopTableTagBits;
- const unsigned loopTableIterBits;
- const unsigned logLoopTableAssoc;
- const uint8_t confidenceThreshold;
- const uint16_t loopTagMask;
- const uint16_t loopNumIterMask;
- const int loopSetMask;
-
- LoopEntry *ltable;
-
- int8_t loopUseCounter;
- unsigned withLoopBits;
-
- const bool useDirectionBit;
- const bool useSpeculation;
- const bool useHashing;
- const bool restrictAllocation;
- const unsigned initialLoopIter;
- const unsigned initialLoopAge;
- const bool optionalAgeReset;
-
- // stats
- Stats::Scalar loopPredictorCorrect;
- Stats::Scalar loopPredictorWrong;
};
#endif // __CPU_PRED_LTAGE
diff --git a/src/cpu/pred/tage_sc_l.cc b/src/cpu/pred/tage_sc_l.cc
index 25c1a1a..16d3a34 100644
--- a/src/cpu/pred/tage_sc_l.cc
+++ b/src/cpu/pred/tage_sc_l.cc
@@ -405,7 +405,8 @@
bool pred_taken = tagePredict(tid, branch_pc, cond_branch, bi);
- pred_taken = loopPredict(tid, branch_pc, cond_branch, bi, pred_taken);
+ pred_taken = loopPredict(tid, branch_pc, cond_branch, bi, pred_taken,
+ instShiftAmt);
pred_taken = scPredict(tid, branch_pc, cond_branch, bi, pred_taken);
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/15775
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I60ad079a2c49b00a1f84d5cfd3611631883a4b57
Gerrit-Change-Number: 15775
Gerrit-PatchSet: 1
Gerrit-Owner: Javier Bueno Hedo <javier.bu...@metempsy.com>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
gem5-dev@gem5.org
http://m5sim.org/mailman/listinfo/gem5-dev
