cpu: Added 8KB and 64KB TAGE-SC-L branch predictor
The original paper of the branch predictor can be found here:
http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
Change-Id: I684863752407685adaacedebb699205c3559c528
Reviewed-on: https://gem5-review.googlesource.com/c/14855
Reviewed-by: Sudhanshu Jha <sudhanshu.jha@arm.com>
Reviewed-by: Andreas Sandberg <andreas.sandberg@arm.com>
Maintainer: Andreas Sandberg <andreas.sandberg@arm.com>
diff --git a/src/cpu/pred/BranchPredictor.py b/src/cpu/pred/BranchPredictor.py
index 1d5fd5e..85b225c 100644
--- a/src/cpu/pred/BranchPredictor.py
+++ b/src/cpu/pred/BranchPredictor.py
@@ -118,7 +118,7 @@
logUResetPeriod = Param.Unsigned(18,
"Log period in number of branches to reset TAGE useful counters")
numUseAltOnNa = Param.Unsigned(1, "Number of USE_ALT_ON_NA counters")
- useAltOnNaBits = Param.Unsigned(4, "Size of the USE_ALT_ON_NA counter")
+ useAltOnNaBits = Param.Unsigned(4, "Size of the USE_ALT_ON_NA counter(s)")
maxNumAlloc = Param.Unsigned(1,
"Max number of TAGE entries allocted on mispredict")
@@ -185,6 +185,96 @@
optionalAgeReset = Param.Bool(True,
"Reset age bits optionally in some cases")
+class TAGE_SC_L_TAGE(TAGEBase):
+ type = 'TAGE_SC_L_TAGE'
+ cxx_class = 'TAGE_SC_L_TAGE'
+ cxx_header = "cpu/pred/tage_sc_l.hh"
+ abstract = True
+ tagTableTagWidths = [0]
+ numUseAltOnNa = 16
+ pathHistBits = 27
+ maxNumAlloc = 2
+ logUResetPeriod = 10
+ useAltOnNaBits = 5
+ # TODO No speculation implemented as of now
+ speculativeHistUpdate = False
+
+ # This size does not set the final sizes of the tables (it is just used
+ # for some calculations)
+ # Instead, the number of TAGE entries comes from shortTagsTageEntries and
+ # longTagsTageEntries
+ logTagTableSize = Param.Unsigned("Log size of each tag table")
+
+ shortTagsTageFactor = Param.Unsigned(
+ "Factor for calculating the total number of short tags TAGE entries")
+
+ longTagsTageFactor = Param.Unsigned(
+ "Factor for calculating the total number of long tags TAGE entries")
+
+ shortTagsSize = Param.Unsigned(8, "Size of the short tags")
+
+ longTagsSize = Param.Unsigned("Size of the long tags")
+
+ firstLongTagTable = Param.Unsigned("First table with long tags")
+
+ truncatePathHist = Param.Bool(True,
+ "Truncate the path history to its configured size")
+
+
+class TAGE_SC_L_TAGE_64KB(TAGE_SC_L_TAGE):
+ type = 'TAGE_SC_L_TAGE_64KB'
+ cxx_class = 'TAGE_SC_L_TAGE_64KB'
+ cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
+ nHistoryTables = 36
+
+ minHist = 6
+ maxHist = 3000
+
+ tagTableUBits = 1
+
+ logTagTableSizes = [13]
+
+ # This is used to handle the 2-way associativity
+ # (all odd entries are set to one, and if the corresponding even entry
+ # is set to one, then there is a 2-way associativity for this pair)
+ # Entry 0 is for the bimodal and it is ignored
+ # Note: For this implementation, some odd entries are also set to 0 to save
+ # some bits
+ noSkip = [0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,
+ 1,1,1,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1]
+
+ logTagTableSize = 10
+ shortTagsTageFactor = 10
+ longTagsTageFactor = 20
+
+ longTagsSize = 12
+
+ firstLongTagTable = 13
+
+class TAGE_SC_L_TAGE_8KB(TAGE_SC_L_TAGE):
+ type = 'TAGE_SC_L_TAGE_8KB'
+ cxx_class = 'TAGE_SC_L_TAGE_8KB'
+ cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
+
+ nHistoryTables = 30
+
+ minHist = 4
+ maxHist = 1000
+
+ logTagTableSize = 7
+ shortTagsTageFactor = 9
+ longTagsTageFactor = 17
+ longTagsSize = 12
+
+ logTagTableSizes = [12]
+
+ firstLongTagTable = 11
+
+ truncatePathHist = False
+
+ noSkip = [0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1]
+
+ tagTableUBits = 2
# LTAGE branch predictor as described in
# https://www.irisa.fr/caps/people/seznec/L-TAGE.pdf
@@ -196,4 +286,177 @@
cxx_header = "cpu/pred/ltage.hh"
tage = LTAGE_TAGE()
+
loop_predictor = Param.LoopPredictor(LoopPredictor(), "Loop predictor")
+
+class TAGE_SC_L_LoopPredictor(LoopPredictor):
+ type = 'TAGE_SC_L_LoopPredictor'
+ cxx_class = 'TAGE_SC_L_LoopPredictor'
+ cxx_header = "cpu/pred/tage_sc_l.hh"
+ loopTableAgeBits = 4
+ loopTableConfidenceBits = 4
+ loopTableTagBits = 10
+ loopTableIterBits = 10
+ useSpeculation = False
+ useHashing = True
+ useDirectionBit = True
+ restrictAllocation = True
+ initialLoopIter = 0
+ initialLoopAge = 7
+ optionalAgeReset = False
+
+class StatisticalCorrector(SimObject):
+ type = 'StatisticalCorrector'
+ cxx_class = 'StatisticalCorrector'
+ cxx_header = "cpu/pred/statistical_corrector.hh"
+ abstract = True
+
+ # Statistical corrector parameters
+
+ numEntriesFirstLocalHistories = Param.Unsigned(
+ "Number of entries for first local histories")
+
+ bwnb = Param.Unsigned("Num global backward branch GEHL lengths")
+ bwm = VectorParam.Int("Global backward branch GEHL lengths")
+ logBwnb = Param.Unsigned("Log num of global backward branch GEHL entries")
+
+ lnb = Param.Unsigned("Num first local history GEHL lenghts")
+ lm = VectorParam.Int("First local history GEHL lengths")
+ logLnb = Param.Unsigned("Log number of first local history GEHL entries")
+
+ inb = Param.Unsigned(1, "Num IMLI GEHL lenghts")
+ im = VectorParam.Int([8], "IMLI history GEHL lengths")
+ logInb = Param.Unsigned("Log number of IMLI GEHL entries")
+
+ logBias = Param.Unsigned("Log size of Bias tables")
+
+ logSizeUp = Param.Unsigned(6,
+ "Log size of update threshold counters tables")
+
+ chooserConfWidth = Param.Unsigned(7,
+ "Number of bits for the chooser counters")
+
+ updateThresholdWidth = Param.Unsigned(12,
+ "Number of bits for the update threshold counter")
+
+ pUpdateThresholdWidth = Param.Unsigned(8,
+ "Number of bits for the pUpdate threshold counters")
+
+ extraWeightsWidth = Param.Unsigned(6,
+ "Number of bits for the extra weights")
+
+ scCountersWidth = Param.Unsigned(6, "Statistical corrector counters width")
+
+# TAGE-SC-L branch predictor as desribed in
+# https://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
+# It is a modified LTAGE predictor plus a statistical corrector predictor
+# The TAGE modifications include bank interleaving and partial associativity
+# Two different sizes are proposed in the paper:
+# 8KB => See TAGE_SC_L_8KB below
+# 64KB => See TAGE_SC_L_64KB below
+# The TAGE_SC_L_8KB and TAGE_SC_L_64KB classes differ not only on the values
+# of some parameters, but also in some implementation details
+# Given this, the TAGE_SC_L class is left abstract
+# Note that as it is now, this branch predictor does not handle any type
+# of speculation: All the structures/histories are updated at commit time
+class TAGE_SC_L(LTAGE):
+ type = 'TAGE_SC_L'
+ cxx_class = 'TAGE_SC_L'
+ cxx_header = "cpu/pred/tage_sc_l.hh"
+ abstract = True
+
+ statistical_corrector = Param.StatisticalCorrector(
+ "Statistical Corrector")
+
+class TAGE_SC_L_64KB_LoopPredictor(TAGE_SC_L_LoopPredictor):
+ logSizeLoopPred = 5
+
+class TAGE_SC_L_8KB_LoopPredictor(TAGE_SC_L_LoopPredictor):
+ logSizeLoopPred = 3
+
+class TAGE_SC_L_64KB_StatisticalCorrector(StatisticalCorrector):
+ type = 'TAGE_SC_L_64KB_StatisticalCorrector'
+ cxx_class = 'TAGE_SC_L_64KB_StatisticalCorrector'
+ cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
+
+ pnb = Param.Unsigned(3, "Num variation global branch GEHL lengths")
+ pm = VectorParam.Int([25, 16, 9], "Variation global branch GEHL lengths")
+ logPnb = Param.Unsigned(9,
+ "Log number of variation global branch GEHL entries")
+
+ snb = Param.Unsigned(3, "Num second local history GEHL lenghts")
+ sm = VectorParam.Int([16, 11, 6], "Second local history GEHL lengths")
+ logSnb = Param.Unsigned(9,
+ "Log number of second local history GEHL entries")
+
+ tnb = Param.Unsigned(2, "Num third local history GEHL lenghts")
+ tm = VectorParam.Int([9, 4], "Third local history GEHL lengths")
+ logTnb = Param.Unsigned(10,
+ "Log number of third local history GEHL entries")
+
+ imnb = Param.Unsigned(2, "Num second IMLI GEHL lenghts")
+ imm = VectorParam.Int([10, 4], "Second IMLI history GEHL lengths")
+ logImnb = Param.Unsigned(9, "Log number of second IMLI GEHL entries")
+
+ numEntriesSecondLocalHistories = Param.Unsigned(16,
+ "Number of entries for second local histories")
+ numEntriesThirdLocalHistories = Param.Unsigned(16,
+ "Number of entries for second local histories")
+
+ numEntriesFirstLocalHistories = 256
+
+ logBias = 8
+
+ bwnb = 3
+ bwm = [40, 24, 10]
+ logBwnb = 10
+
+ lnb = 3
+ lm = [11, 6, 3]
+ logLnb = 10
+
+ logInb = 8
+
+class TAGE_SC_L_8KB_StatisticalCorrector(StatisticalCorrector):
+ type = 'TAGE_SC_L_8KB_StatisticalCorrector'
+ cxx_class = 'TAGE_SC_L_8KB_StatisticalCorrector'
+ cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
+ gnb = Param.Unsigned(2, "Num global branch GEHL lengths")
+ gm = VectorParam.Int([6, 3], "Global branch GEHL lengths")
+ logGnb = Param.Unsigned(7, "Log number of global branch GEHL entries")
+
+ numEntriesFirstLocalHistories = 64
+
+ logBias = 7
+
+ bwnb = 2
+ logBwnb = 7
+ bwm = [16, 8]
+
+ lnb = 2
+ logLnb = 7
+ lm = [6, 3]
+
+ logInb = 7
+
+# 64KB TAGE-SC-L branch predictor as described in
+# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
+class TAGE_SC_L_64KB(TAGE_SC_L):
+ type = 'TAGE_SC_L_64KB'
+ cxx_class = 'TAGE_SC_L_64KB'
+ cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
+
+ tage = TAGE_SC_L_TAGE_64KB()
+ loop_predictor = TAGE_SC_L_64KB_LoopPredictor()
+ statistical_corrector = TAGE_SC_L_64KB_StatisticalCorrector()
+
+# 8KB TAGE-SC-L branch predictor as described in
+# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
+class TAGE_SC_L_8KB(TAGE_SC_L):
+ type = 'TAGE_SC_L_8KB'
+ cxx_class = 'TAGE_SC_L_8KB'
+ cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
+
+ tage = TAGE_SC_L_TAGE_8KB()
+ loop_predictor = TAGE_SC_L_8KB_LoopPredictor()
+ statistical_corrector = TAGE_SC_L_8KB_StatisticalCorrector()
diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript
index 9e7e166..e3a5219 100644
--- a/src/cpu/pred/SConscript
+++ b/src/cpu/pred/SConscript
@@ -47,7 +47,12 @@
Source('tage.cc')
Source('loop_predictor.cc')
Source('ltage.cc')
+Source('statistical_corrector.cc')
+Source('tage_sc_l.cc')
+Source('tage_sc_l_8KB.cc')
+Source('tage_sc_l_64KB.cc')
DebugFlag('FreeList')
DebugFlag('Branch')
DebugFlag('Tage')
DebugFlag('LTage')
+DebugFlag('TageSCL')
diff --git a/src/cpu/pred/loop_predictor.cc b/src/cpu/pred/loop_predictor.cc
index 2e709f3..bd32e41 100644
--- a/src/cpu/pred/loop_predictor.cc
+++ b/src/cpu/pred/loop_predictor.cc
@@ -36,6 +36,8 @@
#include "cpu/pred/loop_predictor.hh"
+#include "base/random.hh"
+#include "debug/LTage.hh"
#include "params/LoopPredictor.hh"
LoopPredictor::LoopPredictor(LoopPredictorParams *p)
@@ -166,14 +168,13 @@
}
bool
-LoopPredictor::optionalAgeInc(int nrand) const
+LoopPredictor::optionalAgeInc() const
{
return false;
}
void
-LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred,
- int random0, int random1, int random2)
+LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred)
{
int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
if (bi->loopHit >= 0) {
@@ -186,7 +187,8 @@
ltable[idx].confidence = 0;
ltable[idx].currentIter = 0;
return;
- } else if (bi->loopPred != tage_pred || optionalAgeInc(random0)) {
+ } else if (bi->loopPred != tage_pred || optionalAgeInc()) {
+ DPRINTF(LTage, "Loop Prediction success:%lx\n",pc);
unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
}
}
@@ -206,6 +208,7 @@
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
@@ -217,6 +220,7 @@
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;
@@ -235,13 +239,16 @@
}
} else if (useDirectionBit ? (bi->predTaken != taken) : taken) {
- if ((random2 & 3) == 0 || !restrictAllocation) {
+ if ((random_mt.random<int>() & 3) == 0 || !restrictAllocation) {
//try to allocate an entry on taken branch
- int nrand = random1;
+ int nrand = random_mt.random<int>();
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;
@@ -318,8 +325,7 @@
void
LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
bool tage_pred, BranchInfo* bi,
- unsigned instShiftAmt, int rand0, int rand1,
- int rand2)
+ unsigned instShiftAmt)
{
if (useSpeculation) {
// recalculate loop prediction without speculation
@@ -337,7 +343,7 @@
}
}
- loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1, rand2);
+ loopUpdate(branch_pc, taken, bi, tage_pred);
}
void
diff --git a/src/cpu/pred/loop_predictor.hh b/src/cpu/pred/loop_predictor.hh
index 3579c57..bc62698 100644
--- a/src/cpu/pred/loop_predictor.hh
+++ b/src/cpu/pred/loop_predictor.hh
@@ -180,12 +180,8 @@
* @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
- * @param random2 random value
*/
- void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred,
- int random0, int random1, int random2);
+ void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred);
/**
* Speculatively updates the loop predictor
@@ -204,14 +200,9 @@
* @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
- * @param rand2 Random integer value
*/
- void condBranchUpdate(
- ThreadID tid, Addr branch_pc, bool taken, bool tage_pred,
- BranchInfo* bi, unsigned instShiftAmt, int rand0, int rand1,
- int rand2);
+ void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
+ bool tage_pred, BranchInfo* bi, unsigned instShiftAmt);
/**
* Get the loop prediction
@@ -244,7 +235,7 @@
virtual bool calcConf(int index) const;
- virtual bool optionalAgeInc(int nrand) const;
+ virtual bool optionalAgeInc() const;
virtual BranchInfo *makeBranchInfo();
diff --git a/src/cpu/pred/ltage.cc b/src/cpu/pred/ltage.cc
index cab86e4..44fce43 100644
--- a/src/cpu/pred/ltage.cc
+++ b/src/cpu/pred/ltage.cc
@@ -42,6 +42,7 @@
#include "base/intmath.hh"
#include "base/logging.hh"
+#include "base/random.hh"
#include "base/trace.hh"
#include "debug/Fetch.hh"
#include "debug/LTage.hh"
@@ -51,6 +52,12 @@
{
}
+void
+LTAGE::init()
+{
+ TAGE::init();
+}
+
//prediction
bool
LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
@@ -82,6 +89,7 @@
return pred_taken;
}
+// PREDICTOR UPDATE
void
LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history,
bool squashed, const StaticInstPtr & inst, Addr corrTarget)
@@ -105,7 +113,7 @@
return;
}
- int nrand = TAGEBase::getRandom() & 3;
+ int nrand = random_mt.random<int>() & 3;
if (bi->tageBranchInfo->condBranch) {
DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n",
branch_pc, taken);
@@ -114,12 +122,10 @@
loopPredictor->updateStats(taken, bi->lpBranchInfo);
loopPredictor->condBranchUpdate(tid, branch_pc, taken,
- bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt,
- TAGEBase::getRandom(), TAGEBase::getRandom(),
- TAGEBase::getRandom());
+ bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt);
tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo,
- nrand, corrTarget);
+ nrand, corrTarget, bi->lpBranchInfo->predTaken);
}
tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
diff --git a/src/cpu/pred/ltage.hh b/src/cpu/pred/ltage.hh
index caddbc6..13ee5e9 100644
--- a/src/cpu/pred/ltage.hh
+++ b/src/cpu/pred/ltage.hh
@@ -70,6 +70,8 @@
void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
bool squashed, const StaticInstPtr & inst,
Addr corrTarget = MaxAddr) override;
+
+ void init() override;
virtual void regStats() override;
protected:
diff --git a/src/cpu/pred/statistical_corrector.cc b/src/cpu/pred/statistical_corrector.cc
new file mode 100644
index 0000000..ebacd4d
--- /dev/null
+++ b/src/cpu/pred/statistical_corrector.cc
@@ -0,0 +1,393 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * Statistical corrector base class
+ */
+
+ #include "cpu/pred/statistical_corrector.hh"
+
+ #include "params/StatisticalCorrector.hh"
+
+ StatisticalCorrector::StatisticalCorrector(
+ const StatisticalCorrectorParams *p)
+ : SimObject(p),
+ logBias(p->logBias),
+ logSizeUp(p->logSizeUp),
+ logSizeUps(logSizeUp / 2),
+ numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories),
+ bwnb(p->bwnb),
+ logBwnb(p->logBwnb),
+ bwm(p->bwm),
+ lnb(p->lnb),
+ logLnb(p->logLnb),
+ lm(p->lm),
+ inb(p->inb),
+ logInb(p->logInb),
+ im(p->im),
+ chooserConfWidth(p->chooserConfWidth),
+ updateThresholdWidth(p->updateThresholdWidth),
+ pUpdateThresholdWidth(p->pUpdateThresholdWidth),
+ extraWeightsWidth(p->extraWeightsWidth),
+ scCountersWidth(p->scCountersWidth),
+ firstH(0),
+ secondH(0)
+{
+ wb.resize(1 << logSizeUps, 4);
+
+ initGEHLTable(lnb, lm, lgehl, logLnb, wl, 7);
+ initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, 7);
+ initGEHLTable(inb, im, igehl, logInb, wi, 7);
+
+ updateThreshold = 35 << 3;
+
+ pUpdateThreshold.resize(1 << logSizeUp, 0);
+
+ bias.resize(1 << logBias);
+ biasSK.resize(1 << logBias);
+ biasBank.resize(1 << logBias);
+ for (int j = 0; j < (1 << logBias); j++) {
+ switch (j & 3) {
+ case 0:
+ bias[j] = -32;
+ biasSK[j] = -8;
+ biasBank[j] = -32;
+ break;
+ case 1:
+ bias[j] = 31;
+ biasSK[j] = 7;
+ biasBank[j] = 31;
+ break;
+ case 2:
+ bias[j] = -1;
+ biasSK[j] = -32;
+ biasBank[j] = -1;
+ break;
+ case 3:
+ bias[j] = 0;
+ biasSK[j] = 31;
+ biasBank[j] = 0;
+ break;
+ }
+ }
+}
+
+StatisticalCorrector::BranchInfo*
+StatisticalCorrector::makeBranchInfo()
+{
+ return new BranchInfo();
+}
+
+StatisticalCorrector::SCThreadHistory*
+StatisticalCorrector::makeThreadHistory()
+{
+ return new SCThreadHistory();
+}
+
+void
+StatisticalCorrector::initGEHLTable(unsigned numLenghts,
+ std::vector<int> lengths, std::vector<int8_t> * & table,
+ unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue)
+{
+ assert(lengths.size() == numLenghts);
+ if (numLenghts == 0) {
+ return;
+ }
+ table = new std::vector<int8_t> [numLenghts];
+ for (int i = 0; i < numLenghts; ++i) {
+ table[i].resize(1 << logNumEntries, 0);
+ for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) {
+ if (! (j & 1)) {
+ table[i][j] = -1;
+ }
+ }
+ }
+
+ w.resize(1 << logSizeUps, wInitValue);
+}
+
+unsigned
+StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi,
+ bool bias) const
+{
+ return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1)
+ + bi->predBeforeSC) & ((1<<logBias) -1);
+}
+
+unsigned
+StatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const
+{
+ return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^
+ (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1);
+}
+
+unsigned
+StatisticalCorrector::getIndUpd(Addr branch_pc) const
+{
+ return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1));
+}
+
+unsigned
+StatisticalCorrector::getIndUpds(Addr branch_pc) const
+{
+ return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1));
+}
+
+int64_t
+StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr,
+ int i)
+{
+ return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^
+ (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^
+ (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) &
+ ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1);
+}
+
+int
+StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist,
+ std::vector<int> & length, std::vector<int8_t> * tab, int nbr,
+ int logs, std::vector<int8_t> & w)
+{
+ int percsum = 0;
+ for (int i = 0; i < nbr; i++) {
+ int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1));
+ int64_t index = gIndex(branch_pc, bhist, logs, nbr, i);
+ int8_t ctr = tab[i][index];
+ percsum += (2 * ctr + 1);
+ }
+ percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum;
+ return percsum;
+}
+
+void
+StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist,
+ std::vector<int> & length, std::vector<int8_t> * tab,
+ int nbr, int logs, std::vector<int8_t> & w,
+ BranchInfo* bi)
+{
+ int percsum = 0;
+ for (int i = 0; i < nbr; i++) {
+ int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1));
+ int64_t index = gIndex(branch_pc, bhist, logs, nbr, i);
+ percsum += (2 * tab[i][index] + 1);
+ ctrUpdate(tab[i][index], taken, scCountersWidth);
+ }
+
+ int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum;
+ if ((xsum + percsum >= 0) != (xsum >= 0)) {
+ ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken),
+ extraWeightsWidth);
+ }
+}
+
+bool
+StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
+ BranchInfo* bi, bool prev_pred_taken, bool bias_bit,
+ bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits,
+ int hitBank, int altBank, int64_t phist)
+{
+ bool pred_taken = prev_pred_taken;
+ if (cond_branch) {
+
+ bi->predBeforeSC = prev_pred_taken;
+
+ // first calc/update the confidences from the TAGE prediction
+ if (use_conf_ctr) {
+ bi->lowConf = (abs(2 * conf_ctr + 1) == 1);
+ bi->medConf = (abs(2 * conf_ctr + 1) == 5);
+ bi->highConf = (abs(2 * conf_ctr + 1) >= (1<<conf_bits) - 1);
+ }
+
+ int lsum = 0;
+
+ int8_t ctr = bias[getIndBias(branch_pc, bi, bias_bit)];
+ lsum += (2 * ctr + 1);
+ ctr = biasSK[getIndBiasSK(branch_pc, bi)];
+ lsum += (2 * ctr + 1);
+ ctr = biasBank[getIndBiasBank(branch_pc, bi, hitBank, altBank)];
+ lsum += (2 * ctr + 1);
+
+ lsum = (1 + (wb[getIndUpds(branch_pc)] >= 0)) * lsum;
+
+ int thres = gPredictions(tid, branch_pc, bi, lsum, phist);
+
+ // These will be needed at update time
+ bi->lsum = lsum;
+ bi->thres = thres;
+
+ bool scPred = (lsum >= 0);
+
+ if (pred_taken != scPred) {
+ bool useScPred = true;
+ //Choser uses TAGE confidence and |LSUM|
+ if (bi->highConf) {
+ if (abs (lsum) < (thres / 4)) {
+ useScPred = false;
+ } else if (abs (lsum) < (thres / 2)) {
+ useScPred = (secondH < 0);
+ }
+ }
+
+ if (bi->medConf) {
+ if (abs (lsum) < (thres / 4)) {
+ useScPred = (firstH < 0);
+ }
+ }
+
+ bi->usedScPred = useScPred;
+ if (useScPred) {
+ pred_taken = scPred;
+ bi->scPred = scPred;
+ }
+ }
+ }
+
+ return pred_taken;
+}
+
+void
+StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype, bool taken,
+ BranchInfo * tage_bi, Addr corrTarget)
+{
+ // Non speculative SC histories update
+ if (brtype & 1) {
+ if (corrTarget < branch_pc) {
+ //This branch corresponds to a loop
+ if (!taken) {
+ //exit of the "loop"
+ scHistory->imliCount = 0;
+ } else {
+ if (scHistory->imliCount < ((1 << im[0]) - 1)) {
+ scHistory->imliCount++;
+ }
+ }
+ }
+
+ scHistory->bwHist = (scHistory->bwHist << 1) +
+ (taken & (corrTarget < branch_pc));
+ scHistory->updateLocalHistory(1, branch_pc, taken);
+ }
+}
+
+void
+StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc,
+ bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank,
+ int altBank, int64_t phist)
+{
+ bool scPred = (bi->lsum >= 0);
+
+ if (bi->predBeforeSC != scPred) {
+ if (abs(bi->lsum) < bi->thres) {
+ if (bi->highConf) {
+ if ((abs(bi->lsum) < bi->thres / 2)) {
+ if ((abs(bi->lsum) >= bi->thres / 4)) {
+ ctrUpdate(secondH, (bi->predBeforeSC == taken),
+ chooserConfWidth);
+ }
+ }
+ }
+ }
+ if (bi->medConf) {
+ if ((abs(bi->lsum) < bi->thres / 4)) {
+ ctrUpdate(firstH, (bi->predBeforeSC == taken),
+ chooserConfWidth);
+ }
+ }
+ }
+
+ if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) {
+ ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth);
+ ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken),
+ pUpdateThresholdWidth);
+
+ unsigned indUpds = getIndUpds(branch_pc);
+ unsigned indBias = getIndBias(branch_pc, bi, b);
+ unsigned indBiasSK = getIndBiasSK(branch_pc, bi);
+ unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank);
+
+ int xsum = bi->lsum -
+ ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) +
+ (2 * biasSK[indBiasSK] + 1) +
+ (2 * biasBank[indBiasBank] + 1)));
+
+ if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) +
+ (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0))
+ {
+ ctrUpdate(wb[indUpds],
+ (((2 * bias[indBias] + 1) +
+ (2 * biasSK[indBiasSK] + 1) +
+ (2 * biasBank[indBiasBank] + 1) >= 0) == taken),
+ extraWeightsWidth);
+ }
+
+ ctrUpdate(bias[indBias], taken, scCountersWidth);
+ ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth);
+ ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth);
+
+ gUpdates(tid, branch_pc, taken, bi, phist);
+ }
+}
+
+void
+StatisticalCorrector::updateStats(bool taken, BranchInfo *bi)
+{
+ if (taken == bi->scPred) {
+ scPredictorCorrect++;
+ } else {
+ scPredictorWrong++;
+ }
+}
+
+void
+StatisticalCorrector::init()
+{
+ scHistory = makeThreadHistory();
+}
+
+void
+StatisticalCorrector::regStats()
+{
+ scPredictorCorrect
+ .name(name() + ".scPredictorCorrect")
+ .desc("Number of time the SC predictor is the provider and "
+ "the prediction is correct");
+
+ scPredictorWrong
+ .name(name() + ".scPredictorWrong")
+ .desc("Number of time the SC predictor is the provider and "
+ "the prediction is wrong");
+}
diff --git a/src/cpu/pred/statistical_corrector.hh b/src/cpu/pred/statistical_corrector.hh
new file mode 100644
index 0000000..f966843
--- /dev/null
+++ b/src/cpu/pred/statistical_corrector.hh
@@ -0,0 +1,265 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * Statistical corrector base class
+ */
+
+#ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH
+#define __CPU_PRED_STATISTICAL_CORRECTOR_HH
+
+#include "base/statistics.hh"
+#include "base/types.hh"
+#include "sim/sim_object.hh"
+
+struct StatisticalCorrectorParams;
+
+class StatisticalCorrector : public SimObject
+{
+ template<typename T>
+ inline void ctrUpdate(T & ctr, bool taken, int nbits) {
+ assert(nbits <= sizeof(T) << 3);
+ if (taken) {
+ if (ctr < ((1 << (nbits - 1)) - 1))
+ ctr++;
+ } else {
+ if (ctr > -(1 << (nbits - 1)))
+ ctr--;
+ }
+ }
+ protected:
+ // histories used for the statistical corrector
+ struct SCThreadHistory {
+ SCThreadHistory() {
+ bwHist = 0;
+ numOrdinalHistories = 0;
+ imliCount = 0;
+ }
+ int64_t bwHist; // backward global history
+ int64_t imliCount;
+
+ void setNumOrdinalHistories(unsigned num)
+ {
+ numOrdinalHistories = num;
+ assert(num > 0);
+ shifts.resize(num);
+ localHistories = new std::vector<int64_t> [num];
+ }
+
+ void initLocalHistory(int ordinal, int numHistories, int shift)
+ {
+ assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
+ shifts[ordinal - 1] = shift;
+ assert(isPowerOf2(numHistories));
+ localHistories[ordinal - 1].resize(numHistories, 0);
+ }
+
+ int64_t getLocalHistory(int ordinal, Addr pc)
+ {
+ assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
+ unsigned idx = ordinal - 1;
+ return localHistories[idx][getEntry(pc, idx)];
+ }
+
+ void updateLocalHistory(
+ int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0)
+ {
+ assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
+ unsigned idx = ordinal - 1;
+
+ unsigned entry = getEntry(branch_pc, idx);
+ int64_t hist = (localHistories[idx][entry] << 1) + taken;
+
+ if (extraXor) {
+ hist = hist ^ extraXor;
+ }
+
+ localHistories[idx][entry] = hist;
+ }
+
+ private:
+ std::vector<int64_t> * localHistories;
+ std::vector<int> shifts;
+ unsigned numOrdinalHistories;
+
+ unsigned getEntry(Addr pc, unsigned idx)
+ {
+ return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1);
+ }
+ };
+
+ // For SC history we use global (i.e. not per thread) non speculative
+ // histories, as some of the strucures needed are quite big and it is not
+ // reasonable to make them per thread and it would be difficult to
+ // rollback on miss-predictions
+ SCThreadHistory * scHistory;
+
+ const unsigned logBias;
+
+ const unsigned logSizeUp;
+ const unsigned logSizeUps;
+
+ const unsigned numEntriesFirstLocalHistories;
+
+ // global backward branch history GEHL
+ const unsigned bwnb;
+ const unsigned logBwnb;
+ std::vector<int> bwm;
+ std::vector<int8_t> * bwgehl;
+ std::vector<int8_t> wbw;
+
+ // First local history GEHL
+ const unsigned lnb;
+ const unsigned logLnb;
+ std::vector<int> lm;
+ std::vector<int8_t> * lgehl;
+ std::vector<int8_t> wl;
+
+ // IMLI GEHL
+ const unsigned inb;
+ const unsigned logInb;
+ std::vector<int> im;
+ std::vector<int8_t> * igehl;
+ std::vector<int8_t> wi;
+
+ std::vector<int8_t> bias;
+ std::vector<int8_t> biasSK;
+ std::vector<int8_t> biasBank;
+
+ std::vector<int8_t> wb;
+
+ int updateThreshold;
+ std::vector<int> pUpdateThreshold;
+
+ // The two counters used to choose between TAGE ang SC on High Conf
+ // TAGE/Low Conf SC
+ const unsigned chooserConfWidth;
+
+ const unsigned updateThresholdWidth;
+ const unsigned pUpdateThresholdWidth;
+
+ const unsigned extraWeightsWidth;
+
+ const unsigned scCountersWidth;
+
+ int8_t firstH;
+ int8_t secondH;
+
+ // stats
+ Stats::Scalar scPredictorCorrect;
+ Stats::Scalar scPredictorWrong;
+ public:
+ struct BranchInfo
+ {
+ BranchInfo() : lowConf(false), highConf(false), altConf(false),
+ medConf(false), scPred(false), lsum(0), thres(0),
+ predBeforeSC(false), usedScPred(false)
+ {}
+
+ // confidences calculated on tage and used on the statistical
+ // correction
+ bool lowConf;
+ bool highConf;
+ bool altConf;
+ bool medConf;
+
+ bool scPred;
+ int lsum;
+ int thres;
+ bool predBeforeSC;
+ bool usedScPred;
+ };
+
+ StatisticalCorrector(const StatisticalCorrectorParams *p);
+
+ virtual BranchInfo *makeBranchInfo();
+ virtual SCThreadHistory *makeThreadHistory();
+
+ bool scPredict(
+ ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi,
+ bool prev_pred_taken, bool bias_bit, bool use_conf_ctr,
+ int8_t conf_ctr, unsigned conf_bits, int hitBank, int altBank,
+ int64_t phist);
+
+ unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const;
+
+ unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const;
+
+ virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi,
+ int hitBank, int altBank) const = 0;
+
+ unsigned getIndUpd(Addr branch_pc) const;
+ unsigned getIndUpds(Addr branch_pc) const;
+
+ virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi,
+ int & lsum, int64_t phist) = 0;
+
+ int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i);
+
+ virtual int gIndexLogsSubstr(int nbr, int i) = 0;
+
+ int gPredict(
+ Addr branch_pc, int64_t hist, std::vector<int> & length,
+ std::vector<int8_t> * tab, int nbr, int logs,
+ std::vector<int8_t> & w);
+
+ void gUpdate(
+ Addr branch_pc, bool taken, int64_t hist, std::vector<int> & length,
+ std::vector<int8_t> * tab, int nbr, int logs,
+ std::vector<int8_t> & w, BranchInfo* bi);
+
+ void initGEHLTable(
+ unsigned numLenghts, std::vector<int> lengths,
+ std::vector<int8_t> * & table, unsigned logNumEntries,
+ std::vector<int8_t> & w, int8_t wInitValue);
+
+ virtual void scHistoryUpdate(
+ Addr branch_pc, int brtype, bool taken, BranchInfo * tage_bi,
+ Addr corrTarget);
+
+ virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
+ int64_t phist) = 0;
+
+ void init() override;
+ void regStats() override;
+ void updateStats(bool taken, BranchInfo *bi);
+
+ void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
+ BranchInfo *bi, Addr corrTarget, bool bias_bit,
+ int hitBank, int altBank, int64_t phist);
+};
+#endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH
diff --git a/src/cpu/pred/tage.cc b/src/cpu/pred/tage.cc
index 5702c04..9b75e6a 100644
--- a/src/cpu/pred/tage.cc
+++ b/src/cpu/pred/tage.cc
@@ -59,28 +59,29 @@
assert(bp_history);
TageBranchInfo *bi = static_cast<TageBranchInfo*>(bp_history);
+ TAGEBase::BranchInfo *tage_bi = bi->tageBranchInfo;
assert(corrTarget != MaxAddr);
if (squashed) {
// This restores the global history, then update it
// and recomputes the folded histories.
- tage->squash(tid, taken, bi->tageBranchInfo, corrTarget);
+ tage->squash(tid, taken, tage_bi, corrTarget);
return;
}
- int nrand = TAGEBase::getRandom() & 3;
+ int nrand = random_mt.random<int>() & 3;
if (bi->tageBranchInfo->condBranch) {
DPRINTF(Tage, "Updating tables for branch:%lx; taken?:%d\n",
branch_pc, taken);
tage->updateStats(taken, bi->tageBranchInfo);
- tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo,
- nrand, corrTarget);
+ tage->condBranchUpdate(tid, branch_pc, taken, tage_bi, nrand,
+ corrTarget, bi->tageBranchInfo->tagePred);
}
- tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
- inst, corrTarget);
-
+ // optional non speculative update of the histories
+ tage->updateHistories(tid, branch_pc, taken, tage_bi, false, inst,
+ corrTarget);
delete bi;
}
@@ -95,7 +96,7 @@
bool
TAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
{
- TageBranchInfo *bi = new TageBranchInfo(*tage);
+ TageBranchInfo *bi = new TageBranchInfo(*tage);//nHistoryTables+1);
b = (void*)(bi);
return tage->tagePredict(tid, branch_pc, cond_branch, bi->tageBranchInfo);
}
diff --git a/src/cpu/pred/tage.hh b/src/cpu/pred/tage.hh
index 0c5cde2..105999c 100644
--- a/src/cpu/pred/tage.hh
+++ b/src/cpu/pred/tage.hh
@@ -77,6 +77,7 @@
virtual bool predict(ThreadID tid, Addr branch_pc, bool cond_branch,
void* &b);
+
public:
TAGE(const TAGEParams *params);
@@ -87,7 +88,7 @@
void btbUpdate(ThreadID tid, Addr branch_addr, void* &bp_history) override;
void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
bool squashed, const StaticInstPtr & inst,
- Addr corrTarget) override;
+ Addr corrTarget = MaxAddr) override;
virtual void squash(ThreadID tid, void *bp_history) override;
};
diff --git a/src/cpu/pred/tage_base.cc b/src/cpu/pred/tage_base.cc
index 95be541..2d149ea 100644
--- a/src/cpu/pred/tage_base.cc
+++ b/src/cpu/pred/tage_base.cc
@@ -42,7 +42,6 @@
#include "base/intmath.hh"
#include "base/logging.hh"
-#include "base/random.hh"
#include "debug/Fetch.hh"
#include "debug/Tage.hh"
@@ -425,7 +424,7 @@
}
void
-TAGEBase::adjustAlloc(bool & alloc, bool taken)
+TAGEBase::adjustAlloc(bool & alloc, bool taken, bool pred_taken)
{
// Nothing for this base class implementation
}
@@ -502,7 +501,7 @@
void
TAGEBase::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
- BranchInfo* bi, int nrand, Addr corrTarget)
+ BranchInfo* bi, int nrand, Addr corrTarget, bool pred)
{
// TAGE UPDATE
// try to allocate a new entries only if prediction was wrong
@@ -526,7 +525,7 @@
}
}
- adjustAlloc(alloc, taken);
+ adjustAlloc(alloc, taken, pred);
handleAllocAndUReset(alloc, taken, bi, nrand);
@@ -640,12 +639,6 @@
return;
}
-int
-TAGEBase::getRandom()
-{
- return random_mt.random<int>();
-}
-
void
TAGEBase::updateStats(bool taken, BranchInfo* bi)
{
diff --git a/src/cpu/pred/tage_base.hh b/src/cpu/pred/tage_base.hh
index ea1d827..48daaf9 100644
--- a/src/cpu/pred/tage_base.hh
+++ b/src/cpu/pred/tage_base.hh
@@ -317,10 +317,11 @@
* recorded at prediction time.
* @nrand Random int number from 0 to 3
* @param corrTarget The correct branch target
+ * @param pred Final prediction for this branch
*/
virtual void condBranchUpdate(
ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi,
- int nrand, Addr corrTarget);
+ int nrand, Addr corrTarget, bool pred);
/**
* TAGE prediction called from TAGE::predict
@@ -370,7 +371,7 @@
* on an update
* For this base TAGE implementation it does nothing
*/
- virtual void adjustAlloc(bool & alloc, bool taken);
+ virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken);
/**
* Handles Allocation and U bits reset on an update
@@ -400,13 +401,6 @@
*/
virtual void extraAltCalc(BranchInfo* bi);
- /**
- * Algorithm for returning a random number
- * This base TAGE class just uses random_mt, but some derived classes
- * may want to use a more realistic implementation or force some values
- */
- static int getRandom();
-
void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi);
unsigned getGHR(ThreadID tid, BranchInfo *bi) const;
int8_t getCtr(int hitBank, int hitBankIndex) const;
diff --git a/src/cpu/pred/tage_sc_l.cc b/src/cpu/pred/tage_sc_l.cc
new file mode 100644
index 0000000..5f17b81
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l.cc
@@ -0,0 +1,479 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * TAGE-SC-L branch predictor base class (devised by Andre Seznec)
+ * It consits of a TAGE + a statistical corrector (SC) + a loop predictor (L)
+ */
+
+#include "cpu/pred/tage_sc_l.hh"
+
+#include "base/random.hh"
+#include "debug/TageSCL.hh"
+
+bool
+TAGE_SC_L_LoopPredictor::calcConf(int index) const
+{
+ return LoopPredictor::calcConf(index) ||
+ (ltable[index].confidence * ltable[index].numIter > 128);
+}
+
+bool
+TAGE_SC_L_LoopPredictor::optionalAgeInc() const
+{
+ return (random_mt.random<int>() & 7) == 0;
+}
+
+TAGE_SC_L_LoopPredictor *
+TAGE_SC_L_LoopPredictorParams::create()
+{
+ return new TAGE_SC_L_LoopPredictor(this);
+}
+
+TAGE_SC_L::TAGE_SC_L(const TAGE_SC_LParams *p)
+ : LTAGE(p), statisticalCorrector(p->statistical_corrector)
+{
+}
+
+TAGEBase::BranchInfo*
+TAGE_SC_L_TAGE::makeBranchInfo()
+{
+ return new BranchInfo(*this);
+}
+void
+TAGE_SC_L_TAGE::calculateParameters()
+{
+ unsigned numHistLengths = nHistoryTables/2;
+ histLengths[1] = minHist;
+ histLengths[numHistLengths] = maxHist;
+
+ // This calculates the different history lenghts
+ // there are only numHistLengths different lengths
+ // They are initially set to the lower half of histLengths
+ for (int i = 2; i <= numHistLengths; i++) {
+ histLengths[i] = (int) (((double) minHist *
+ pow ((double) (maxHist) / (double) minHist,
+ (double) (i - 1) / (double) ((numHistLengths - 1))))
+ + 0.5);
+ }
+
+ // This copies and duplicates the values from the lower half of the table
+ // Ex: 4, 6, 9, 13 would get exanded to 4, 4, 6, 6, 9, 9, 13, 13
+ for (int i = nHistoryTables; i > 1; i--)
+ {
+ histLengths[i] = histLengths[(i + 1) / 2];
+ }
+
+ for (int i = 1; i <= nHistoryTables; i++)
+ {
+ tagTableTagWidths.push_back(
+ (i < firstLongTagTable) ? shortTagsSize : longTagsSize);
+
+ logTagTableSizes.push_back(logTagTableSize);
+ }
+}
+
+void
+TAGE_SC_L_TAGE::buildTageTables()
+{
+ // Trick! We only allocate entries for tables 1 and firstLongTagTable and
+ // make the other tables point to these allocated entries
+
+ gtable[1] = new TageEntry[shortTagsTageFactor * (1 << logTagTableSize)];
+ gtable[firstLongTagTable] =
+ new TageEntry[longTagsTageFactor * (1 << logTagTableSize)];
+ for (int i = 2; i < firstLongTagTable; ++i) {
+ gtable[i] = gtable[1];
+ }
+ for (int i = firstLongTagTable + 1; i <= nHistoryTables; ++i) {
+ gtable[i] = gtable[firstLongTagTable];
+ }
+}
+
+void
+TAGE_SC_L_TAGE::calculateIndicesAndTags(
+ ThreadID tid, Addr pc, TAGEBase::BranchInfo* bi)
+{
+ // computes the table addresses and the partial tags
+
+ for (int i = 1; i <= nHistoryTables; i += 2) {
+ tableIndices[i] = gindex(tid, pc, i);
+ tableTags[i] = gtag(tid, pc, i);
+ tableTags[i + 1] = tableTags[i];
+ tableIndices[i + 1] = tableIndices[i] ^
+ (tableTags[i] & ((1 << logTagTableSizes[i]) - 1));
+
+ bi->tableTags[i] = tableTags[i];
+ bi->tableTags[i+1] = tableTags[i+1];
+ }
+
+ Addr t = (pc ^ (threadHistory[tid].pathHist &
+ ((1 << histLengths[firstLongTagTable]) - 1)))
+ % longTagsTageFactor;
+
+ for (int i = firstLongTagTable; i <= nHistoryTables; i++) {
+ if (noSkip[i]) {
+ tableIndices[i] += (t << logTagTableSizes[i]);
+ bi->tableIndices[i] = tableIndices[i];
+ t++;
+ t = t % longTagsTageFactor;
+ }
+ }
+
+ t = (pc ^ (threadHistory[tid].pathHist & ((1 << histLengths[1]) - 1)))
+ % shortTagsTageFactor;
+
+ for (int i = 1; i <= firstLongTagTable - 1; i++) {
+ if (noSkip[i]) {
+ tableIndices[i] += (t << logTagTableSizes[i]);
+ bi->tableIndices[i] = tableIndices[i];
+ t++;
+ t = t % shortTagsTageFactor;
+ }
+ }
+}
+
+unsigned
+TAGE_SC_L_TAGE::getUseAltIdx(TAGEBase::BranchInfo* bi)
+{
+ BranchInfo *tbi = static_cast<BranchInfo *>(bi);
+ unsigned idx;
+ idx = ((((bi->hitBank-1)/8)<<1)+tbi->altConf) % (numUseAltOnNa-1);
+ return idx;
+}
+
+int
+TAGE_SC_L_TAGE::gindex(ThreadID tid, Addr pc, int bank) const
+{
+ int index;
+ int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
+ histLengths[bank];
+ unsigned int shortPc = pc;
+
+ // pc is not shifted by instShiftAmt in this implementation
+ index = shortPc ^
+ (shortPc >> ((int) abs(logTagTableSizes[bank] - bank) + 1)) ^
+ threadHistory[tid].computeIndices[bank].comp ^
+ F(threadHistory[tid].pathHist, hlen, bank);
+
+ index = gindex_ext(index, bank);
+
+ return (index & ((ULL(1) << (logTagTableSizes[bank])) - 1));
+}
+
+int
+TAGE_SC_L_TAGE::F(int a, int size, int bank) const
+{
+ int a1, a2;
+
+ a = a & ((ULL(1) << size) - 1);
+ a1 = (a & ((ULL(1) << logTagTableSizes[bank]) - 1));
+ a2 = (a >> logTagTableSizes[bank]);
+
+ if (bank < logTagTableSizes[bank]) {
+ a2 = ((a2 << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
+ + (a2 >> (logTagTableSizes[bank] - bank));
+ }
+
+ a = a1 ^ a2;
+
+ if (bank < logTagTableSizes[bank]) {
+ a = ((a << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1))
+ + (a >> (logTagTableSizes[bank] - bank));
+ }
+
+ return a;
+}
+
+int
+TAGE_SC_L_TAGE::bindex(Addr pc) const
+{
+ return ((pc ^ (pc >> instShiftAmt)) &
+ ((ULL(1) << (logTagTableSizes[0])) - 1));
+}
+
+void
+TAGE_SC_L_TAGE::updatePathAndGlobalHistory(
+ ThreadHistory& tHist, int brtype, bool taken, Addr branch_pc, Addr target)
+{
+ // TAGE update
+ int tmp = ((branch_pc ^ (branch_pc >> instShiftAmt))) ^ taken;
+ int path = branch_pc ^ (branch_pc >> instShiftAmt)
+ ^ (branch_pc >> (instShiftAmt+2));
+ if ((brtype == 3) & taken) {
+ tmp = (tmp ^ (target >> instShiftAmt));
+ path = path ^ (target >> instShiftAmt) ^ (target >> (instShiftAmt+2));
+ }
+
+ // some branch types use 3 bits in global history, the others just 2
+ int maxt = (brtype == 2) ? 3 : 2;
+
+ for (int t = 0; t < maxt; t++) {
+ bool dir = (tmp & 1);
+ tmp >>= 1;
+ int pathbit = (path & 127);
+ path >>= 1;
+ updateGHist(tHist.gHist, dir, tHist.globalHistory, tHist.ptGhist);
+ tHist.pathHist = (tHist.pathHist << 1) ^ pathbit;
+ if (truncatePathHist) {
+ // The 8KB implementation does not do this truncation
+ tHist.pathHist = (tHist.pathHist & ((ULL(1) << pathHistBits) - 1));
+ }
+ for (int i = 1; i <= nHistoryTables; i++) {
+ tHist.computeIndices[i].update(tHist.gHist);
+ tHist.computeTags[0][i].update(tHist.gHist);
+ tHist.computeTags[1][i].update(tHist.gHist);
+ }
+ }
+}
+
+void
+TAGE_SC_L_TAGE::updateHistories(
+ ThreadID tid, Addr branch_pc, bool taken, TAGEBase::BranchInfo* b,
+ bool speculative, const StaticInstPtr &inst, Addr target)
+{
+ if (speculative != speculativeHistUpdate) {
+ return;
+ }
+ // speculation is not implemented
+ assert(! speculative);
+
+ ThreadHistory& tHist = threadHistory[tid];
+
+ int brtype = inst->isDirectCtrl() ? 0 : 2;
+ if (! inst->isUncondCtrl()) {
+ ++brtype;
+ }
+ updatePathAndGlobalHistory(tHist, brtype, taken, branch_pc, target);
+
+ DPRINTF(TageSCL, "Updating global histories with branch:%lx; taken?:%d, "
+ "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist,
+ tHist.ptGhist);
+}
+
+void
+TAGE_SC_L_TAGE::squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi,
+ Addr target)
+{
+ fatal("Speculation is not implemented");
+}
+
+void
+TAGE_SC_L_TAGE::adjustAlloc(bool & alloc, bool taken, bool pred_taken)
+{
+ // Do not allocate too often if the prediction is ok
+ if ((taken == pred_taken) && ((random_mt.random<int>() & 31) != 0)) {
+ alloc = false;
+ }
+}
+
+int
+TAGE_SC_L_TAGE::calcDep(TAGEBase::BranchInfo* bi)
+{
+ int a = 1;
+ if ((random_mt.random<int>() & 127) < 32) {
+ a = 2;
+ }
+ return ((((bi->hitBank - 1 + 2 * a) & 0xffe)) ^
+ (random_mt.random<int>() & 1));
+}
+
+void
+TAGE_SC_L_TAGE::handleUReset()
+{
+ //just the best formula for the Championship:
+ //In practice when one out of two entries are useful
+ if (tCounter < 0) {
+ tCounter = 0;
+ }
+
+ if (tCounter >= ((ULL(1) << logUResetPeriod))) {
+ // Update the u bits for the short tags table
+ for (int j = 0; j < (shortTagsTageFactor*(1<<logTagTableSize)); j++) {
+ resetUctr(gtable[1][j].u);
+ }
+
+ // Update the u bits for the long tags table
+ for (int j = 0; j < (longTagsTageFactor*(1<<logTagTableSize)); j++) {
+ resetUctr(gtable[firstLongTagTable][j].u);
+ }
+
+ tCounter = 0;
+ }
+}
+
+bool
+TAGE_SC_L_TAGE::getBimodePred(Addr pc, TAGEBase::BranchInfo* tage_bi) const
+{
+ TAGE_SC_L_TAGE::BranchInfo *bi =
+ static_cast<TAGE_SC_L_TAGE::BranchInfo *>(tage_bi);
+
+ int bim = (btablePrediction[bi->bimodalIndex] << 1)
+ + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries];
+
+ bi->highConf = (bim == 0) || (bim == 3);
+ bi->lowConf = ! bi->highConf;
+ bi->altConf = bi->highConf;
+ bi->medConf = false;
+ return TAGEBase::getBimodePred(pc, tage_bi);
+}
+
+void
+TAGE_SC_L_TAGE::extraAltCalc(TAGEBase::BranchInfo* bi)
+{
+ TAGE_SC_L_TAGE::BranchInfo *tage_scl_bi =
+ static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi);
+ int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
+ tage_scl_bi->altConf = (abs(2*ctr + 1) > 1);
+}
+
+bool
+TAGE_SC_L::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
+{
+ TageSCLBranchInfo *bi = new TageSCLBranchInfo(*tage,
+ *statisticalCorrector,
+ *loopPredictor);
+ b = (void*)(bi);
+
+ bool pred_taken = tage->tagePredict(tid, branch_pc, cond_branch,
+ bi->tageBranchInfo);
+ pred_taken = loopPredictor->loopPredict(tid, branch_pc, cond_branch,
+ bi->lpBranchInfo, pred_taken,
+ instShiftAmt);
+
+ if (bi->lpBranchInfo->loopPredUsed) {
+ bi->tageBranchInfo->provider = LOOP;
+ }
+
+ TAGE_SC_L_TAGE::BranchInfo* tage_scl_bi =
+ static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi->tageBranchInfo);
+
+ // Copy the confidences computed by TAGE
+ bi->scBranchInfo->lowConf = tage_scl_bi->lowConf;
+ bi->scBranchInfo->highConf = tage_scl_bi->highConf;
+ bi->scBranchInfo->altConf = tage_scl_bi->altConf;
+ bi->scBranchInfo->medConf = tage_scl_bi->medConf;
+
+ bool use_tage_ctr = bi->tageBranchInfo->hitBank > 0;
+ int8_t tage_ctr = use_tage_ctr ?
+ tage->getCtr(tage_scl_bi->hitBank, tage_scl_bi->hitBankIndex) : 0;
+ bool bias = (bi->tageBranchInfo->longestMatchPred !=
+ bi->tageBranchInfo->altTaken);
+
+ pred_taken = statisticalCorrector->scPredict(tid, branch_pc, cond_branch,
+ bi->scBranchInfo, pred_taken, bias, use_tage_ctr, tage_ctr,
+ tage->getTageCtrBits(), bi->tageBranchInfo->hitBank,
+ bi->tageBranchInfo->altBank, tage->getPathHist(tid));
+
+ if (bi->scBranchInfo->usedScPred) {
+ bi->tageBranchInfo->provider = SC;
+ }
+
+ // record final prediction
+ bi->lpBranchInfo->predTaken = pred_taken;
+
+ return pred_taken;
+}
+
+void
+TAGE_SC_L::update(ThreadID tid, Addr branch_pc, bool taken, void *bp_history,
+ bool squashed, const StaticInstPtr & inst, Addr corrTarget)
+{
+ assert(bp_history);
+
+ TageSCLBranchInfo* bi = static_cast<TageSCLBranchInfo*>(bp_history);
+ TAGE_SC_L_TAGE::BranchInfo* tage_bi =
+ static_cast<TAGE_SC_L_TAGE::BranchInfo *>(bi->tageBranchInfo);
+
+ assert(corrTarget != MaxAddr);
+
+ if (squashed) {
+ if (tage->isSpeculativeUpdateEnabled()) {
+ // This restores the global history, then update it
+ // and recomputes the folded histories.
+ tage->squash(tid, taken, tage_bi, corrTarget);
+ if (bi->tageBranchInfo->condBranch) {
+ loopPredictor->squashLoop(bi->lpBranchInfo);
+ }
+ }
+ return;
+ }
+
+ int nrand = random_mt.random<int>() & 3;
+ if (tage_bi->condBranch) {
+ DPRINTF(TageSCL, "Updating tables for branch:%lx; taken?:%d\n",
+ branch_pc, taken);
+ tage->updateStats(taken, bi->tageBranchInfo);
+
+ loopPredictor->updateStats(taken, bi->lpBranchInfo);
+
+ statisticalCorrector->updateStats(taken, bi->scBranchInfo);
+
+ bool bias = (bi->tageBranchInfo->longestMatchPred !=
+ bi->tageBranchInfo->altTaken);
+ statisticalCorrector->condBranchUpdate(tid, branch_pc, taken,
+ bi->scBranchInfo, corrTarget, bias, bi->tageBranchInfo->hitBank,
+ bi->tageBranchInfo->altBank, tage->getPathHist(tid));
+
+ loopPredictor->condBranchUpdate(tid, branch_pc, taken,
+ bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt);
+
+ tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo,
+ nrand, corrTarget, bi->lpBranchInfo->predTaken);
+ }
+
+ if (!tage->isSpeculativeUpdateEnabled()) {
+ int brtype = inst->isDirectCtrl() ? 0 : 2;
+ if (! inst->isUncondCtrl()) {
+ ++brtype;
+ }
+
+ statisticalCorrector->scHistoryUpdate(branch_pc, brtype, taken,
+ bi->scBranchInfo, corrTarget);
+
+ tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
+ inst, corrTarget);
+ }
+
+ delete bi;
+}
+
+void
+TAGE_SC_L::regStats()
+{
+ LTAGE::regStats();
+}
diff --git a/src/cpu/pred/tage_sc_l.hh b/src/cpu/pred/tage_sc_l.hh
new file mode 100644
index 0000000..c96cc89
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l.hh
@@ -0,0 +1,188 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * TAGE-SC-L branch predictor base class (devised by Andre Seznec)
+ * It consits of a TAGE + a statistical corrector (SC) + a loop predictor (L)
+ */
+
+#ifndef __CPU_PRED_TAGE_SC_L
+#define __CPU_PRED_TAGE_SC_L
+
+#include "cpu/pred/ltage.hh"
+#include "cpu/pred/statistical_corrector.hh"
+#include "params/TAGE_SC_L.hh"
+#include "params/TAGE_SC_L_LoopPredictor.hh"
+#include "params/TAGE_SC_L_TAGE.hh"
+
+class TAGE_SC_L_TAGE : public TAGEBase {
+ const unsigned firstLongTagTable;
+ const unsigned longTagsSize;
+ const unsigned shortTagsSize;
+
+ const unsigned logTagTableSize;
+
+ const unsigned shortTagsTageFactor;
+ const unsigned longTagsTageFactor;
+
+ const bool truncatePathHist;
+
+ public:
+ struct BranchInfo : public TAGEBase::BranchInfo {
+ bool lowConf;
+ bool highConf;
+ bool altConf;
+ bool medConf;
+ BranchInfo(TAGEBase &tage) : TAGEBase::BranchInfo(tage),
+ lowConf(false), highConf(false), altConf(false), medConf(false)
+ {}
+ virtual ~BranchInfo()
+ {}
+ };
+
+ virtual TAGEBase::BranchInfo *makeBranchInfo() override;
+
+ TAGE_SC_L_TAGE(const TAGE_SC_L_TAGEParams *p)
+ : TAGEBase(p),
+ firstLongTagTable(p->firstLongTagTable),
+ longTagsSize(p->longTagsSize),
+ shortTagsSize(p->shortTagsSize),
+ logTagTableSize(p->logTagTableSize),
+ shortTagsTageFactor(p->shortTagsTageFactor),
+ longTagsTageFactor(p->longTagsTageFactor),
+ truncatePathHist(p->truncatePathHist)
+ {}
+
+ void calculateParameters() override;
+
+ void buildTageTables() override;
+
+ void calculateIndicesAndTags(
+ ThreadID tid, Addr branch_pc, TAGEBase::BranchInfo* bi) override;
+
+ unsigned getUseAltIdx(TAGEBase::BranchInfo* bi) override;
+
+ void updateHistories(
+ ThreadID tid, Addr branch_pc, bool taken, TAGEBase::BranchInfo* b,
+ bool speculative, const StaticInstPtr &inst,
+ Addr target) override;
+
+ int bindex(Addr pc_in) const override;
+ int gindex(ThreadID tid, Addr pc, int bank) const override;
+ virtual int gindex_ext(int index, int bank) const = 0;
+ int F(int phist, int size, int bank) const override;
+
+ virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const override = 0;
+
+ void squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi,
+ Addr target) override;
+
+ void updatePathAndGlobalHistory(
+ ThreadHistory & tHist, int brtype, bool taken,
+ Addr branch_pc, Addr target);
+
+ void adjustAlloc(bool & alloc, bool taken, bool pred_taken) override;
+
+ virtual void handleAllocAndUReset(bool alloc, bool taken,
+ TAGEBase::BranchInfo* bi, int nrand) override = 0;
+
+ void handleUReset() override;
+
+ virtual void handleTAGEUpdate(
+ Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override = 0;
+
+ int calcDep(TAGEBase::BranchInfo* bi);
+
+ bool getBimodePred(Addr branch_pc,
+ TAGEBase::BranchInfo* tage_bi) const override;
+
+ void extraAltCalc(TAGEBase::BranchInfo* bi) override;
+
+};
+
+class TAGE_SC_L_LoopPredictor : public LoopPredictor
+{
+ public:
+ TAGE_SC_L_LoopPredictor(TAGE_SC_L_LoopPredictorParams *p)
+ : LoopPredictor(p)
+ {}
+
+ virtual bool calcConf(int index) const override;
+ virtual bool optionalAgeInc() const override;
+};
+
+class TAGE_SC_L: public LTAGE
+{
+ StatisticalCorrector *statisticalCorrector;
+ public:
+ TAGE_SC_L(const TAGE_SC_LParams *params);
+
+ bool predict(
+ ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override;
+
+ void regStats() override;
+
+ void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
+ bool squashed, const StaticInstPtr & inst,
+ Addr corrTarget = MaxAddr) override;
+
+ protected:
+
+ struct TageSCLBranchInfo : public LTageBranchInfo
+ {
+ StatisticalCorrector::BranchInfo *scBranchInfo;
+
+ TageSCLBranchInfo(TAGEBase &tage, StatisticalCorrector &sc,
+ LoopPredictor &lp)
+ : LTageBranchInfo(tage, lp), scBranchInfo(sc.makeBranchInfo())
+ {}
+
+ virtual ~TageSCLBranchInfo()
+ {
+ delete scBranchInfo;
+ }
+ };
+
+ // more provider types
+ enum {
+ SC = LAST_LTAGE_PROVIDER_TYPE + 1
+ };
+
+};
+
+#endif // __CPU_PRED_TAGE_SC_L
+
diff --git a/src/cpu/pred/tage_sc_l_64KB.cc b/src/cpu/pred/tage_sc_l_64KB.cc
new file mode 100644
index 0000000..164d587
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l_64KB.cc
@@ -0,0 +1,322 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec)
+ */
+
+#include "cpu/pred/tage_sc_l_64KB.hh"
+
+TAGE_SC_L_64KB_StatisticalCorrector::TAGE_SC_L_64KB_StatisticalCorrector(
+ TAGE_SC_L_64KB_StatisticalCorrectorParams *p)
+ : StatisticalCorrector(p),
+ numEntriesSecondLocalHistories(p->numEntriesSecondLocalHistories),
+ numEntriesThirdLocalHistories(p->numEntriesThirdLocalHistories),
+ pnb(p->pnb),
+ logPnb(p->logPnb),
+ pm(p->pm),
+ snb(p->snb),
+ logSnb(p->logSnb),
+ sm(p->sm),
+ tnb(p->tnb),
+ logTnb(p->logTnb),
+ tm(p->tm),
+ imnb(p->imnb),
+ logImnb(p->logImnb),
+ imm(p->imm)
+{
+ initGEHLTable(pnb, pm, pgehl, logPnb, wp, 7);
+ initGEHLTable(snb, sm, sgehl, logSnb, ws, 7);
+ initGEHLTable(tnb, tm, tgehl, logTnb, wt, 7);
+ initGEHLTable(imnb, imm, imgehl, logImnb, wim, 0);
+
+}
+
+TAGE_SC_L_64KB_StatisticalCorrector::SCThreadHistory*
+TAGE_SC_L_64KB_StatisticalCorrector::makeThreadHistory()
+{
+ SC_64KB_ThreadHistory *sh = new SC_64KB_ThreadHistory();
+
+ sh->setNumOrdinalHistories(3);
+ sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2);
+ sh->initLocalHistory(2, numEntriesSecondLocalHistories, 5);
+ sh->initLocalHistory(3, numEntriesThirdLocalHistories, logTnb);
+
+ sh->imHist.resize(1 << im[0]);
+ return sh;
+}
+
+unsigned
+TAGE_SC_L_64KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc,
+ BranchInfo* bi, int hitBank, int altBank) const
+{
+ return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) +
+ (bi->lowConf <<2) + ((altBank!=0)<<3) +
+ ((branch_pc^(branch_pc>>2))<<7)) & ((1<<logBias) -1);
+}
+
+int
+TAGE_SC_L_64KB_StatisticalCorrector::gPredictions(ThreadID tid, Addr branch_pc,
+ BranchInfo* bi, int & lsum, int64_t pathHist)
+{
+ SC_64KB_ThreadHistory *sh =
+ static_cast<SC_64KB_ThreadHistory *>(scHistory);
+
+ lsum += gPredict(
+ (branch_pc << 1) + bi->predBeforeSC, sh->bwHist, bwm,
+ bwgehl, bwnb, logBwnb, wbw);
+
+ lsum += gPredict(
+ branch_pc, pathHist, pm, pgehl, pnb, logPnb, wp);
+
+ lsum += gPredict(
+ branch_pc, sh->getLocalHistory(1, branch_pc), lm,
+ lgehl, lnb, logLnb, wl);
+
+ lsum += gPredict(
+ branch_pc, sh->getLocalHistory(2, branch_pc), sm,
+ sgehl, snb, logSnb, ws);
+
+ lsum += gPredict(
+ branch_pc, sh->getLocalHistory(3, branch_pc), tm,
+ tgehl, tnb, logTnb, wt);
+
+ lsum += gPredict(
+ branch_pc, sh->imHist[scHistory->imliCount], imm,
+ imgehl, imnb, logImnb, wim);
+
+ lsum += gPredict(
+ branch_pc, sh->imliCount, im, igehl, inb, logInb, wi);
+
+ int thres = (updateThreshold>>3) + pUpdateThreshold[getIndUpd(branch_pc)]
+ + 12*((wb[getIndUpds(branch_pc)] >= 0) + (wp[getIndUpds(branch_pc)] >= 0)
+ + (ws[getIndUpds(branch_pc)] >= 0) + (wt[getIndUpds(branch_pc)] >= 0)
+ + (wl[getIndUpds(branch_pc)] >= 0) + (wbw[getIndUpds(branch_pc)] >= 0)
+ + (wi[getIndUpds(branch_pc)] >= 0));
+
+ return thres;
+}
+
+int
+TAGE_SC_L_64KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
+{
+ return (i >= (nbr - 2)) ? 1 : 0;
+}
+
+void
+TAGE_SC_L_64KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc,
+ int brtype, bool taken, BranchInfo* tage_bi, Addr corrTarget)
+{
+ // Non speculative SC histories update
+ if (brtype & 1) {
+ SC_64KB_ThreadHistory *sh =
+ static_cast<SC_64KB_ThreadHistory *>(scHistory);
+ int64_t imliCount = sh->imliCount;
+ sh->imHist[imliCount] = (sh->imHist[imliCount] << 1)
+ + taken;
+ sh->updateLocalHistory(2, branch_pc, taken, branch_pc & 15);
+ sh->updateLocalHistory(3, branch_pc, taken);
+ }
+
+ StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi,
+ corrTarget);
+}
+
+void
+TAGE_SC_L_64KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc,
+ bool taken, BranchInfo* bi, int64_t phist)
+{
+ SC_64KB_ThreadHistory *sh =
+ static_cast<SC_64KB_ThreadHistory *>(scHistory);
+
+ gUpdate((pc << 1) + bi->predBeforeSC, taken, sh->bwHist, bwm,
+ bwgehl, bwnb, logBwnb, wbw, bi);
+
+ gUpdate(pc, taken, phist, pm,
+ pgehl, pnb, logPnb, wp, bi);
+
+ gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm,
+ lgehl, lnb, logLnb, wl, bi);
+
+ gUpdate(pc, taken, sh->getLocalHistory(2, pc), sm,
+ sgehl, snb, logSnb, ws, bi);
+
+ gUpdate(pc, taken, sh->getLocalHistory(3, pc), tm,
+ tgehl, tnb, logTnb, wt, bi);
+
+ gUpdate(pc, taken, sh->imHist[scHistory->imliCount], imm,
+ imgehl, imnb, logImnb, wim, bi);
+
+ gUpdate(pc, taken, sh->imliCount, im,
+ igehl, inb, logInb, wi, bi);
+}
+
+TAGE_SC_L_64KB_StatisticalCorrector*
+TAGE_SC_L_64KB_StatisticalCorrectorParams::create()
+{
+ return new TAGE_SC_L_64KB_StatisticalCorrector(this);
+}
+
+int
+TAGE_SC_L_TAGE_64KB::gindex_ext(int index, int bank) const
+{
+ return index;
+}
+
+uint16_t
+TAGE_SC_L_TAGE_64KB::gtag(ThreadID tid, Addr pc, int bank) const
+{
+ // very similar to the TAGE implementation, but w/o shifting the pc
+ int tag = pc ^ threadHistory[tid].computeTags[0][bank].comp ^
+ (threadHistory[tid].computeTags[1][bank].comp << 1);
+
+ return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1));
+}
+
+void
+TAGE_SC_L_TAGE_64KB::handleAllocAndUReset(
+ bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
+{
+ if (! alloc) {
+ return;
+ }
+
+ int penalty = 0;
+ int numAllocated = 0;
+ bool maxAllocReached = false;
+
+ for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
+ // Handle the 2-way associativity for allocation
+ for (int j = 0; j < 2; ++j) {
+ int i = ((j == 0) ? I : (I ^ 1)) + 1;
+ if (noSkip[i]) {
+ if (gtable[i][bi->tableIndices[i]].u == 0) {
+ int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
+ if (abs (2 * ctr + 1) <= 3) {
+ gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
+ gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
+ numAllocated++;
+ maxAllocReached = (numAllocated == maxNumAlloc);
+ I += 2;
+ break;
+ } else {
+ if (gtable[i][bi->tableIndices[i]].ctr > 0) {
+ gtable[i][bi->tableIndices[i]].ctr--;
+ } else {
+ gtable[i][bi->tableIndices[i]].ctr++;
+ }
+ }
+ } else {
+ penalty++;
+ }
+ }
+ }
+ if (maxAllocReached) {
+ break;
+ }
+ }
+
+ tCounter += (penalty - 2 * numAllocated);
+
+ handleUReset();
+}
+
+void
+TAGE_SC_L_TAGE_64KB::handleTAGEUpdate(Addr branch_pc, bool taken,
+ TAGEBase::BranchInfo* bi)
+{
+ if (bi->hitBank > 0) {
+ if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
+ if (bi->longestMatchPred != taken) {
+ // acts as a protection
+ if (bi->altBank > 0) {
+ ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
+ tagTableCounterBits);
+ }
+ if (bi->altBank == 0){
+ baseUpdate(branch_pc, taken, bi);
+ }
+ }
+ }
+
+ ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
+ tagTableCounterBits);
+
+ //sign changes: no way it can have been useful
+ if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
+ gtable[bi->hitBank][bi->hitBankIndex].u = 0;
+ }
+
+ if (bi->altTaken == taken) {
+ if (bi->altBank > 0) {
+ int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
+ if (abs (2 * ctr + 1) == 7) {
+ if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
+ if (bi->longestMatchPred == taken) {
+ gtable[bi->hitBank][bi->hitBankIndex].u = 0;
+ }
+ }
+ }
+ }
+ }
+ } else {
+ baseUpdate(branch_pc, taken, bi);
+ }
+
+ if ((bi->longestMatchPred != bi->altTaken) &&
+ (bi->longestMatchPred == taken) &&
+ (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
+ gtable[bi->hitBank][bi->hitBankIndex].u++;
+ }
+}
+
+TAGE_SC_L_TAGE_64KB*
+TAGE_SC_L_TAGE_64KBParams::create()
+{
+ return new TAGE_SC_L_TAGE_64KB(this);
+}
+
+TAGE_SC_L_64KB::TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params)
+ : TAGE_SC_L(params)
+{
+}
+
+TAGE_SC_L_64KB*
+TAGE_SC_L_64KBParams::create()
+{
+ return new TAGE_SC_L_64KB(this);
+}
diff --git a/src/cpu/pred/tage_sc_l_64KB.hh b/src/cpu/pred/tage_sc_l_64KB.hh
new file mode 100644
index 0000000..21dd170
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l_64KB.hh
@@ -0,0 +1,135 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec)
+ *
+ * Most of the code in this file has been adapted from cbp64KB/predictor.h in
+ * http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz
+ */
+
+#ifndef __CPU_PRED_TAGE_SC_L_64KB
+#define __CPU_PRED_TAGE_SC_L_64KB
+
+#include "cpu/pred/tage_sc_l.hh"
+#include "params/TAGE_SC_L_64KB.hh"
+#include "params/TAGE_SC_L_64KB_StatisticalCorrector.hh"
+#include "params/TAGE_SC_L_TAGE_64KB.hh"
+
+class TAGE_SC_L_TAGE_64KB : public TAGE_SC_L_TAGE {
+ public:
+ TAGE_SC_L_TAGE_64KB(const TAGE_SC_L_TAGE_64KBParams *p) : TAGE_SC_L_TAGE(p)
+ {}
+
+ int gindex_ext(int index, int bank) const override;
+
+ uint16_t gtag(ThreadID tid, Addr pc, int bank) const override;
+
+ void handleAllocAndUReset(
+ bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) override;
+
+ void handleTAGEUpdate(
+ Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override;
+};
+
+class TAGE_SC_L_64KB_StatisticalCorrector : public StatisticalCorrector
+{
+ const unsigned numEntriesSecondLocalHistories;
+ const unsigned numEntriesThirdLocalHistories;
+
+ // global branch history variation GEHL
+ const unsigned pnb;
+ const unsigned logPnb;
+ std::vector<int> pm;
+ std::vector<int8_t> * pgehl;
+ std::vector<int8_t> wp;
+
+ // Second local history GEHL
+ const unsigned snb;
+ const unsigned logSnb;
+ std::vector<int> sm;
+ std::vector<int8_t> * sgehl;
+ std::vector<int8_t> ws;
+
+ // Third local history GEHL
+ const unsigned tnb;
+ const unsigned logTnb;
+ std::vector<int> tm;
+ std::vector<int8_t> * tgehl;
+ std::vector<int8_t> wt;
+
+ // Second IMLI GEHL
+ const unsigned imnb;
+ const unsigned logImnb;
+ std::vector<int> imm;
+ std::vector<int8_t> * imgehl;
+ std::vector<int8_t> wim;
+
+ struct SC_64KB_ThreadHistory : public SCThreadHistory
+ {
+ std::vector<int64_t> imHist;
+ };
+
+ SCThreadHistory *makeThreadHistory() override;
+
+ public:
+ TAGE_SC_L_64KB_StatisticalCorrector(
+ TAGE_SC_L_64KB_StatisticalCorrectorParams *p);
+
+ unsigned getIndBiasBank(Addr branch_pc, BranchInfo* bi, int hitBank,
+ int altBank) const override;
+
+ int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi,
+ int & lsum, int64_t phist) override;
+
+ int gIndexLogsSubstr(int nbr, int i) override;
+
+ void scHistoryUpdate(Addr branch_pc, int brtype, bool taken,
+ BranchInfo * tage_bi, Addr corrTarget) override;
+
+ void gUpdates(ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
+ int64_t phist) override;
+};
+
+class TAGE_SC_L_64KB : public TAGE_SC_L
+{
+ public:
+ TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params);
+};
+
+#endif // __CPU_PRED_TAGE_SC_L_64KB
+
diff --git a/src/cpu/pred/tage_sc_l_8KB.cc b/src/cpu/pred/tage_sc_l_8KB.cc
new file mode 100644
index 0000000..9af21e1
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l_8KB.cc
@@ -0,0 +1,325 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec)
+ */
+
+#include "cpu/pred/tage_sc_l_8KB.hh"
+
+#include "base/random.hh"
+#include "debug/TageSCL.hh"
+
+TAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector(
+ TAGE_SC_L_8KB_StatisticalCorrectorParams *p)
+ : StatisticalCorrector(p),
+ gnb(p->gnb),
+ logGnb(p->logGnb),
+ gm(p->gm)
+{
+ initGEHLTable(gnb, gm, ggehl, logGnb, wg, 7);
+}
+
+TAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory *
+TAGE_SC_L_8KB_StatisticalCorrector::makeThreadHistory()
+{
+ SC_8KB_ThreadHistory *sh = new SC_8KB_ThreadHistory();
+ sh->setNumOrdinalHistories(1);
+ sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2);
+ return sh;
+}
+
+unsigned
+TAGE_SC_L_8KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc,
+ BranchInfo* bi, int hitBank, int altBank) const
+{
+ return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) +
+ (bi->lowConf <<2) +((altBank!=0)<<3)) & ((1<<logBias) -1);
+}
+
+int
+TAGE_SC_L_8KB_StatisticalCorrector::gPredictions(
+ ThreadID tid, Addr branch_pc, BranchInfo* bi, int & lsum, int64_t phist)
+{
+ SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
+ lsum += gPredict(
+ branch_pc, sh->globalHist, gm, ggehl, gnb, logGnb, wg);
+
+ lsum += gPredict(
+ branch_pc, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw);
+
+ // only 1 local history here
+ lsum += gPredict(
+ branch_pc, sh->getLocalHistory(1, branch_pc), lm,
+ lgehl, lnb, logLnb, wl);
+
+ lsum += gPredict(
+ branch_pc, sh->imliCount, im, igehl, inb, logInb, wi);
+
+ int thres = (updateThreshold>>3)+pUpdateThreshold[getIndUpd(branch_pc)];
+
+ return thres;
+}
+
+int TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
+{
+ return 0;
+}
+
+void
+TAGE_SC_L_8KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype,
+ bool taken, BranchInfo * tage_bi, Addr corrTarget)
+{
+ // Non speculative SC histories update
+ if (brtype & 1) {
+ SC_8KB_ThreadHistory *sh =
+ static_cast<SC_8KB_ThreadHistory *>(scHistory);
+ sh->globalHist = (sh->globalHist << 1) + taken;
+ }
+
+ StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi,
+ corrTarget);
+}
+
+void
+TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken,
+ BranchInfo* bi, int64_t phist)
+{
+ SC_8KB_ThreadHistory *sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
+ gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi);
+ gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi);
+ gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl,
+ bi);
+ gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi);
+}
+
+TAGE_SC_L_8KB_StatisticalCorrector*
+TAGE_SC_L_8KB_StatisticalCorrectorParams::create()
+{
+ return new TAGE_SC_L_8KB_StatisticalCorrector(this);
+}
+
+TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params)
+ : TAGE_SC_L(params)
+{
+}
+
+void
+TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history)
+{
+ // Some hardcoded values are used here
+ // (they do not seem to depend on any parameter)
+ for (int i = 1; i <= nHistoryTables; i++) {
+ history.computeIndices[i].init(
+ histLengths[i], 17 + (2 * ((i - 1) / 2) % 4));
+ history.computeTags[0][i].init(
+ history.computeIndices[i].origLength, 13);
+ history.computeTags[1][i].init(
+ history.computeIndices[i].origLength, 11);
+ DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
+ histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]);
+ }
+}
+
+int
+TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const
+{
+ return (index ^ (index >> logTagTableSizes[bank])
+ ^ (index >> 2 * logTagTableSizes[bank]));
+}
+
+uint16_t
+TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const
+{
+ int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^
+ (pc >> instShiftAmt) ^
+ threadHistory[tid].computeIndices[bank].comp;
+ int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits :
+ histLengths[bank];
+
+ tag = (tag >> 1) ^ ((tag & 1) << 10) ^
+ F(threadHistory[tid].pathHist, hlen, bank);
+ tag ^= threadHistory[tid].computeTags[0][bank].comp ^
+ (threadHistory[tid].computeTags[1][bank].comp << 1);
+
+ return ((tag ^ (tag >> tagTableTagWidths[bank]))
+ & ((ULL(1) << tagTableTagWidths[bank]) - 1));
+}
+
+void
+TAGE_SC_L_TAGE_8KB::handleAllocAndUReset(
+ bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand)
+{
+ if (!alloc) {
+ return;
+ }
+
+ int penalty = 0;
+ int truePen = 0;
+ int numAllocated = 0;
+ bool maxAllocReached = false;
+
+ for (int I = calcDep(bi); I < nHistoryTables; I += 2) {
+ // Handle the 2-way associativity for allocation
+ for (int j = 0; j < 2; ++j) {
+ int i = ((j == 0) ? I : (I ^ 1)) + 1;
+ if (i > nHistoryTables) {
+ break;
+ }
+ if (noSkip[i]) {
+ if (gtable[i][bi->tableIndices[i]].u == 0) {
+ gtable[i][bi->tableIndices[i]].u =
+ ((random_mt.random<int>() & 31) == 0);
+ // protect randomly from fast replacement
+ gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
+ gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
+ numAllocated++;
+
+ if (numAllocated == maxNumAlloc) {
+ maxAllocReached = true;
+ break;
+ }
+ I += 2;
+ } else {
+ int8_t ctr = gtable[i][bi->tableIndices[i]].ctr;
+ if ((gtable[i][bi->tableIndices[i]].u == 1) &
+ (abs (2 * ctr + 1) == 1)) {
+ if ((random_mt.random<int>() & 7) == 0) {
+ gtable[i][bi->tableIndices[i]].u = 0;
+ }
+ } else {
+ truePen++;
+ }
+ penalty++;
+ }
+ } else {
+ break;
+ }
+ }
+ if (maxAllocReached) {
+ break;
+ }
+ }
+
+ tCounter += (truePen + penalty - 5 * numAllocated);
+
+ handleUReset();
+}
+
+void
+TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u)
+{
+ // On real HW it should be u >>= 1 instead of if > 0 then u--
+ if (u > 0) {
+ u--;
+ }
+}
+
+void
+TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken,
+ TAGEBase::BranchInfo* bi)
+{
+ if (bi->hitBank > 0) {
+ if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
+ if (bi->longestMatchPred != taken) { // acts as a protection
+ if (bi->altBank > 0) {
+ int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
+ if (abs (2 * ctr + 1) == 1) {
+ gtable[bi->altBank][bi->altBankIndex].u = 0;
+ }
+
+ //just mute from protected to unprotected
+ ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken,
+ tagTableCounterBits);
+ ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
+ if (abs (2 * ctr + 1) == 1) {
+ gtable[bi->altBank][bi->altBankIndex].u = 0;
+ }
+ }
+ if (bi->altBank == 0) {
+ baseUpdate(branch_pc, taken, bi);
+ }
+ }
+ }
+
+ //just mute from protected to unprotected
+ if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
+ gtable[bi->hitBank][bi->hitBankIndex].u = 0;
+ }
+
+ ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken,
+ tagTableCounterBits);
+
+ //sign changes: no way it can have been useful
+ if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) {
+ gtable[bi->hitBank][bi->hitBankIndex].u = 0;
+ }
+
+ if (bi->altTaken == taken) {
+ if (bi->altBank > 0) {
+ int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr;
+ if (abs (2*ctr + 1) == 7) {
+ if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) {
+ if (bi->longestMatchPred == taken) {
+ gtable[bi->hitBank][bi->hitBankIndex].u = 0;
+ }
+ }
+ }
+ }
+ }
+ } else {
+ baseUpdate(branch_pc, taken, bi);
+ }
+
+ if ((bi->longestMatchPred != bi->altTaken) &&
+ (bi->longestMatchPred == taken) &&
+ (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) {
+ gtable[bi->hitBank][bi->hitBankIndex].u++;
+ }
+}
+
+TAGE_SC_L_TAGE_8KB*
+TAGE_SC_L_TAGE_8KBParams::create()
+{
+ return new TAGE_SC_L_TAGE_8KB(this);
+}
+
+TAGE_SC_L_8KB*
+TAGE_SC_L_8KBParams::create()
+{
+ return new TAGE_SC_L_8KB(this);
+}
diff --git a/src/cpu/pred/tage_sc_l_8KB.hh b/src/cpu/pred/tage_sc_l_8KB.hh
new file mode 100644
index 0000000..74193b0
--- /dev/null
+++ b/src/cpu/pred/tage_sc_l_8KB.hh
@@ -0,0 +1,116 @@
+/*
+ * Copyright (c) 2018 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * 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.
+ *
+ * Author: André Seznec, Pau Cabre, Javier Bueno
+ *
+ */
+
+/*
+ * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec)
+ */
+
+#ifndef __CPU_PRED_TAGE_SC_L_8KB
+#define __CPU_PRED_TAGE_SC_L_8KB
+
+#include "cpu/pred/tage_sc_l.hh"
+#include "params/TAGE_SC_L_8KB.hh"
+#include "params/TAGE_SC_L_8KB_StatisticalCorrector.hh"
+#include "params/TAGE_SC_L_TAGE_8KB.hh"
+
+class TAGE_SC_L_TAGE_8KB : public TAGE_SC_L_TAGE
+{
+ public:
+ TAGE_SC_L_TAGE_8KB(const TAGE_SC_L_TAGE_8KBParams *p) : TAGE_SC_L_TAGE(p)
+ {}
+
+ void initFoldedHistories(ThreadHistory & history) override;
+ int gindex_ext(int index, int bank) const override;
+
+ uint16_t gtag(ThreadID tid, Addr pc, int bank) const override;
+
+ void handleAllocAndUReset(
+ bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) override;
+
+ void handleTAGEUpdate(
+ Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override;
+
+ void resetUctr(uint8_t & u) override;
+};
+
+class TAGE_SC_L_8KB_StatisticalCorrector : public StatisticalCorrector
+{
+ // global branch history GEHL
+ const unsigned gnb;
+ const unsigned logGnb;
+ std::vector<int> gm;
+ std::vector<int8_t> * ggehl;
+ std::vector<int8_t> wg;
+
+ struct SC_8KB_ThreadHistory : public SCThreadHistory
+ {
+ SC_8KB_ThreadHistory() {
+ globalHist = 0;
+ }
+ int64_t globalHist; // global history
+ };
+
+ SCThreadHistory *makeThreadHistory() override;
+
+ public:
+ TAGE_SC_L_8KB_StatisticalCorrector(
+ TAGE_SC_L_8KB_StatisticalCorrectorParams *p);
+
+ unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi, int hitBank,
+ int altBank) const override;
+
+ int gPredictions( ThreadID tid, Addr branch_pc,
+ BranchInfo* bi, int & lsum, int64_t phist) override;
+
+ int gIndexLogsSubstr(int nbr, int i) override;
+
+ void scHistoryUpdate(
+ Addr branch_pc, int brtype, bool taken, BranchInfo * tage_bi,
+ Addr corrTarget) override;
+
+ void gUpdates(ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
+ int64_t phist) override;
+};
+
+class TAGE_SC_L_8KB : public TAGE_SC_L
+{
+ public:
+ TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params);
+};
+
+#endif // __CPU_PRED_TAGE_SC_L_8KB
+
