blob: 305959504046cfb57c55a3f79d3d14854684b97b [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
*
*/
/*
* 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),
stats(this)
{
wb.resize(1 << logSizeUps, 4);
initGEHLTable(lnb, lm, lgehl, logLnb, wl, p->lWeightInitValue);
initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, p->bwWeightInitValue);
initGEHLTable(inb, im, igehl, logInb, wi, p->iWeightInitValue);
updateThreshold = 35 << 3;
pUpdateThreshold.resize(1 << logSizeUp, p->initialUpdateThresholdValue);
bias.resize(1 << logBias);
biasSK.resize(1 << logBias);
biasBank.resize(1 << logBias);
}
StatisticalCorrector::BranchInfo*
StatisticalCorrector::makeBranchInfo()
{
return new BranchInfo();
}
StatisticalCorrector::SCThreadHistory*
StatisticalCorrector::makeThreadHistory()
{
return new SCThreadHistory();
}
void
StatisticalCorrector::initBias()
{
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;
}
}
}
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, int init_lsum)
{
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 = init_lsum;
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,
const StaticInstPtr &inst, bool taken, BranchInfo * tage_bi,
Addr corrTarget)
{
int brtype = inst->isDirectCtrl() ? 0 : 2;
if (! inst->isUncondCtrl()) {
++brtype;
}
// 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) {
stats.correct++;
} else {
stats.wrong++;
}
}
void
StatisticalCorrector::init()
{
scHistory = makeThreadHistory();
initBias();
}
size_t
StatisticalCorrector::getSizeInBits() const
{
// Not implemented
return 0;
}
StatisticalCorrector::StatisticalCorrectorStats::StatisticalCorrectorStats(
Stats::Group *parent)
: Stats::Group(parent),
ADD_STAT(correct, "Number of time the SC predictor is the"
" provider and the prediction is correct"),
ADD_STAT(wrong, "Number of time the SC predictor is the"
" provider and the prediction is wrong")
{
}