blob: 615c6230c856c4ee730d84f894f5d3035a66ea6c [file] [log] [blame]
/*
* 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"
namespace gem5
{
namespace branch_prediction
{
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::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, Addr branch_pc)
{
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 & ((1ULL << (logTagTableSizes[bank])) - 1));
}
int
TAGE_SC_L_TAGE::F(int a, int size, int bank) const
{
int a1, a2;
a = a & ((1ULL << size) - 1);
a1 = (a & ((1ULL << logTagTableSizes[bank]) - 1));
a2 = (a >> logTagTableSizes[bank]);
if (bank < logTagTableSizes[bank]) {
a2 = ((a2 << bank) & ((1ULL << logTagTableSizes[bank]) - 1))
+ (a2 >> (logTagTableSizes[bank] - bank));
}
a = a1 ^ a2;
if (bank < logTagTableSizes[bank]) {
a = ((a << bank) & ((1ULL << logTagTableSizes[bank]) - 1))
+ (a >> (logTagTableSizes[bank] - bank));
}
return a;
}
int
TAGE_SC_L_TAGE::bindex(Addr pc) const
{
return ((pc ^ (pc >> instShiftAmt)) &
((1ULL << (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 & ((1ULL << 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 >= ((1ULL << 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);
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()) {
statisticalCorrector->scHistoryUpdate(branch_pc, inst, taken,
bi->scBranchInfo, corrTarget);
tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
inst, corrTarget);
}
delete bi;
}
} // namespace branch_prediction
} // namespace gem5