| /* | |
| * 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, 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) { | |
| scPredictorCorrect++; | |
| } else { | |
| scPredictorWrong++; | |
| } | |
| } | |
| void | |
| StatisticalCorrector::init() | |
| { | |
| scHistory = makeThreadHistory(); | |
| initBias(); | |
| } | |
| size_t | |
| StatisticalCorrector::getSizeInBits() const | |
| { | |
| // Not implemented | |
| return 0; | |
| } | |
| 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"); | |
| } |