path: root/src/cpu/pred/multiperspective_perceptron_tage.cc

/*
 * Copyright 2019 Texas A&M University
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. 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.
 *
 * 3. Neither the name of the copyright holder 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
 *  HOLDER 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: Daniel A. Jiménez
 *  Adapted to gem5 by: Javier Bueno Hedo
 *
 */

/*
 * Multiperspective Perceptron Predictor with TAGE (by Daniel A. Jiménez)
 */

#include "cpu/pred/multiperspective_perceptron_tage.hh"

#include "base/random.hh"

void
MPP_TAGE::calculateParameters()
{
   assert(tunedHistoryLengths.size() == (nHistoryTables+1));
   for (int i = 0; i <= nHistoryTables; i += 1) {
      histLengths[i] = tunedHistoryLengths[i];
   }
}

void
MPP_TAGE::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;
        }
    } 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++;
    }
}

void
MPP_TAGE::handleAllocAndUReset(bool alloc, bool taken,
                               TAGEBase::BranchInfo* bi, int nrand)
{
    if (!alloc) {
        return;
    }

    int a = 1;

    if ((random_mt.random<int>() & 127) < 32) {
        a = 2;
    }
    int dep = bi->hitBank + a;

    int penalty = 0;
    int numAllocated = 0;
    int T = 1;

    for (int i = dep; i <= nHistoryTables; i += 1) {
        if (noSkip[i]) {
            if (gtable[i][bi->tableIndices[i]].u == 0) {
                gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i];
                gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1;
                numAllocated++;
                if (T <= 0) {
                    break;
                }
                i += 1;
                T -= 1;
            } else {
                penalty++;
            }
        } else { assert(false); }
    }

    tCounter += (penalty - numAllocated);

    handleUReset();
}

void
MPP_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 i = 1; i <= nHistoryTables; i++) {
            for (int j = 0; j < (ULL(1) << logTagTableSizes[i]); j++) {
                resetUctr(gtable[i][j].u);
            }
        }

        tCounter = 0;
    }
}

void
MPP_TAGE::resetUctr(uint8_t &u)
{
    // On real HW it should be u >>= 1 instead of if > 0 then u--
    if (u > 0) {
        u--;
    }
}


int
MPP_TAGE::bindex(Addr pc_in) const
{
    uint32_t pc = (uint32_t) pc_in;
    return ((pc ^ (pc >> 4)) &
            ((ULL(1) << (logTagTableSizes[0])) - 1));
}

unsigned
MPP_TAGE::getUseAltIdx(TAGEBase::BranchInfo* bi, Addr branch_pc)
{
    uint32_t hpc = ((uint32_t) branch_pc);
    hpc = (hpc ^(hpc >> 4));
    return 2 * ((hpc & ((numUseAltOnNa/2)-1)) ^ bi->longestMatchPred) +
           ((bi->hitBank > (nHistoryTables / 3)) ? 1 : 0);
}

void
MPP_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;
    }
}

void
MPP_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);
}

void
MPP_TAGE::updatePathAndGlobalHistory(
    ThreadHistory& tHist, int brtype, bool taken, Addr branch_pc, Addr target)
{
    // TAGE update
    int tmp = (branch_pc << 1) + taken;
    int path = branch_pc;

    int maxt = (brtype & 1) ? 1 : 4;

    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;
        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);
        }
    }
}

bool
MPP_TAGE::isHighConfidence(TAGEBase::BranchInfo *bi) const
{
    if (bi->hitBank > 0) {
        return (abs(2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1)) >=
               ((1 << tagTableCounterBits) - 1);
    } else {
        int bim = (btablePrediction[bi->bimodalIndex] << 1)
            + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries];
        return (bim == 0) || (bim == 3);
    }

}

MPP_TAGE*
MPP_TAGEParams::create()
{
    return new MPP_TAGE(this);
}

bool
MPP_LoopPredictor::calcConf(int index) const
{
    return LoopPredictor::calcConf(index) ||
           (ltable[index].confidence * ltable[index].numIter > 128);
}

bool
MPP_LoopPredictor::optionalAgeInc() const
{
    return ((random_mt.random<int>() & 7) == 0);
}

MPP_LoopPredictor*
MPP_LoopPredictorParams::create()
{
    return new MPP_LoopPredictor(this);
}

MPP_StatisticalCorrector::MPP_StatisticalCorrector(
        const MPP_StatisticalCorrectorParams *p) : StatisticalCorrector(p),
    thirdH(0), pnb(p->pnb), logPnb(p->logPnb), pm(p->pm), gnb(p->gnb),
    logGnb(p->logGnb), gm(p->gm)
{
    initGEHLTable(pnb, pm, pgehl, logPnb, wp, -1);
    initGEHLTable(gnb, gm, ggehl, logGnb, wg, -1);

    for (int8_t &pos : wl) {
        pos = -1;
    }
}

void
MPP_StatisticalCorrector::initBias()
{
    for (int j = 0; j < (1 << logBias); j++) {
        if (j & 1) {
            bias[j] = 15;
            biasSK[j] = 15;
        } else {
            bias[j] = -16;
            biasSK[j] = -16;
        }
    }
}

unsigned
MPP_StatisticalCorrector::getIndBias(Addr branch_pc,
        StatisticalCorrector::BranchInfo* bi, bool bias) const
{
    unsigned int truncated_pc = branch_pc;
    return ((truncated_pc << 1) + bi->predBeforeSC) & ((1 << logBias) - 1);
}

unsigned
MPP_StatisticalCorrector::getIndBiasSK(Addr branch_pc,
        StatisticalCorrector::BranchInfo* bi) const
{
    return (((branch_pc ^ (branch_pc >> (logBias - 1))) << 1)
            + bi->predBeforeSC) & ((1 << logBias) - 1);
}

unsigned
MPP_StatisticalCorrector::getIndBiasBank(Addr branch_pc,
        StatisticalCorrector::BranchInfo* bi, int hitBank, int altBank) const
{
    return 0;
}

int
MPP_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i)
{
    return (i >= (nbr - 2)) ? 1 : 0;
}

unsigned
MPP_StatisticalCorrector::getIndUpd(Addr branch_pc) const
{
    return ((branch_pc ^ (branch_pc >> 4)) & ((1 << (logSizeUp)) - 1));
}

void
MPP_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,
                   StatisticalCorrector::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 - (i < (nbr - 1)));
    }
}

bool
MPP_StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc,
        bool cond_branch, StatisticalCorrector::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;

        int lsum = init_lsum;

        getBiasLSUM(branch_pc, bi, lsum);

        int thres = gPredictions(tid, branch_pc, bi, lsum, phist);

        // These will be needed at update time
        bi->lsum = lsum;
        bi->thres = thres;
        bi->scPred = (lsum >= 0);

        if (pred_taken != bi->scPred) {
            pred_taken = bi->scPred;

            if (bi->highConf /* comes from tage prediction */) {
              if ((abs(lsum) < thres / 3))
                pred_taken = (firstH < 0) ? bi->scPred : prev_pred_taken;
              else if ((abs(lsum) < 2 * thres / 3))
                pred_taken = (secondH < 0) ? bi->scPred : prev_pred_taken;
              else if ((abs(lsum) < thres))
                pred_taken = (thirdH < 0) ? bi->scPred : prev_pred_taken;
            }
        }
    }

    return pred_taken;
}

MultiperspectivePerceptronTAGE::MultiperspectivePerceptronTAGE(
    const MultiperspectivePerceptronTAGEParams *p)
  : MultiperspectivePerceptron(p), tage(p->tage),
    loopPredictor(p->loop_predictor),
    statisticalCorrector(p->statistical_corrector)
{
    fatal_if(tage->isSpeculativeUpdateEnabled(),
        "Speculative updates support is not implemented");
}

void
MultiperspectivePerceptronTAGE::init()
{
    tage->init();
    int numBitsTage = tage->getSizeInBits();
    int numBitsLoopPred = loopPredictor->getSizeInBits();
    int numBitsStatisticalCorrector = statisticalCorrector->getSizeInBits();

    setExtraBits(numBitsTage + numBitsLoopPred + numBitsStatisticalCorrector);
    MultiperspectivePerceptron::init();
}


unsigned int
MultiperspectivePerceptronTAGE::getIndex(ThreadID tid, MPPTAGEBranchInfo &bi,
        const HistorySpec &spec, int index) const
{
    // get the hash for the feature
    unsigned int g = spec.getHash(tid, bi.getPC(), bi.getPC() >> 2, index);
    // shift it and xor it with the hashed PC
    unsigned long long int h = g;
    h <<= 20;
    h ^= (bi.getPC() ^ (bi.getPC() >> 2));

    // maybe xor in an IMLI counter
    if ((1ull << index) & imli_mask1) {
        h += threadData[tid]->imli_counter[0];
    }
    if ((1ull << index) & imli_mask4) {
        h += threadData[tid]->imli_counter[3];
    }

    // return it modulo the table size
    return h % table_sizes[index];
}


int
MultiperspectivePerceptronTAGE::computePartialSum(ThreadID tid,
                                                  MPPTAGEBranchInfo &bi) const
{
    int yout = 0;
    for (int i = 0; i < specs.size(); i += 1) {
        yout += specs[i]->coeff *
            threadData[tid]->tables[i][getIndex(tid, bi, *specs[i], i)];
    }
    return yout;
}

void
MultiperspectivePerceptronTAGE::updatePartial(ThreadID tid,
                                              MPPTAGEBranchInfo &bi,
                                              bool taken)
{
    // update tables
    for (int i = 0; i < specs.size(); i += 1) {
        unsigned int idx = getIndex(tid, bi, *specs[i], i);
        short int *c =
            &threadData[tid]->tables[i][idx];
        short int max_weight = (1 << (specs[i]->width - 1)) - 1;
        short int min_weight = -(1 << (specs[i]->width - 1));
        if (taken) {
            if (*c < max_weight) {
                *c += 1;
            }
        } else {
            if (*c > min_weight) {
                *c -= 1;
            }
        }
    }
}

void
MultiperspectivePerceptronTAGE::updateHistories(ThreadID tid,
                                                MPPTAGEBranchInfo &bi,
                                                bool taken)
{
    unsigned int hpc = (bi.getPC() ^ (bi.getPC() >> 2));
    unsigned int pc = bi.getPC();

    // update recency stack
    unsigned short recency_pc = pc >> 2;
    threadData[tid]->insertRecency(recency_pc, assoc);

    // update acyclic history
    threadData[tid]->updateAcyclic(taken, hpc);

    // update modpath histories
    for (int ii = 0; ii < modpath_indices.size(); ii +=1) {
        int i = modpath_indices[ii];
        if (hpc % (i + 2) == 0) {
            memmove(&threadData[tid]->modpath_histories[i][1],
                    &threadData[tid]->modpath_histories[i][0],
                    sizeof(unsigned short int) * (modpath_lengths[ii] - 1));
            threadData[tid]->modpath_histories[i][0] = hpc;
        }
    }

    // update modulo histories
    for (int ii = 0; ii < modhist_indices.size(); ii += 1) {
        int i = modhist_indices[ii];
        if (hpc % (i + 2) == 0) {
            for (int j = modhist_lengths[ii] - 1; j > 0; j -= 1) {
                threadData[tid]->mod_histories[i][j] =
                    threadData[tid]->mod_histories[i][j-1];
            }
            threadData[tid]->mod_histories[i][0] = taken;
        }
    }

    // update blurry history
    std::vector<std::vector<unsigned int>> &blurrypath_histories =
        threadData[tid]->blurrypath_histories;
    for (int i = 0; i < blurrypath_histories.size(); i += 1)
    {
        if (blurrypath_histories[i].size() > 0) {
            unsigned int z = pc >> i;
            if (blurrypath_histories[i][0] != z) {
                memmove(&blurrypath_histories[i][1],
                        &blurrypath_histories[i][0],
                        sizeof(unsigned int) *
                        (blurrypath_histories[i].size() - 1));
                blurrypath_histories[i][0] = z;
            }
        }
    }
}

bool
MultiperspectivePerceptronTAGE::lookup(ThreadID tid, Addr instPC,
                                   void * &bp_history)
{
    MPPTAGEBranchInfo *bi =
        new MPPTAGEBranchInfo(instPC, pcshift, true, *tage, *loopPredictor,
                              *statisticalCorrector);
    bp_history = (void *)bi;
    bool pred_taken = tage->tagePredict(tid, instPC, true, bi->tageBranchInfo);

    pred_taken = loopPredictor->loopPredict(tid, instPC, true,
            bi->lpBranchInfo, pred_taken, instShiftAmt);

    bi->scBranchInfo->highConf = tage->isHighConfidence(bi->tageBranchInfo);

    int init_lsum = 22;
    if (!pred_taken) {
        init_lsum = -init_lsum;
    }
    init_lsum += computePartialSum(tid, *bi);

    pred_taken = statisticalCorrector->scPredict(tid, instPC, true,
            bi->scBranchInfo, pred_taken, false /* bias_bit: unused */,
            false /* use_tage_ctr: unused */, 0 /* conf_ctr: unused */,
            0 /* conf_bits: unused */, 0 /* hitBank: unused */,
            0 /* altBank: unused */, tage->getPathHist(tid), init_lsum);
    bi->predictedTaken = pred_taken;
    bi->lpBranchInfo->predTaken = pred_taken;
    return pred_taken;
}


void
MPP_StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc,
        bool taken, StatisticalCorrector::BranchInfo *bi, Addr corrTarget,
        bool bias_bit, 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 / 3) {
                    ctrUpdate(firstH, (bi->predBeforeSC == taken),
                              chooserConfWidth);
                } else if (abs(bi->lsum) < 2 * bi->thres / 3) {
                    ctrUpdate(secondH, (bi->predBeforeSC == taken),
                              chooserConfWidth);
                } else if (abs(bi->lsum) < bi->thres) {
                    ctrUpdate(thirdH, (bi->predBeforeSC == taken),
                              chooserConfWidth);
                }
            }
        }
    }

    if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) {

        ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken),
                  pUpdateThresholdWidth + 1); //+1 because the sign is ignored
        if (pUpdateThreshold[getIndUpd(branch_pc)] < 0)
            pUpdateThreshold[getIndUpd(branch_pc)] = 0;

        unsigned indBias = getIndBias(branch_pc, bi, false);
        unsigned indBiasSK = getIndBiasSK(branch_pc, bi);

        ctrUpdate(bias[indBias], taken, scCountersWidth);
        ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth);

        gUpdates(tid, branch_pc, taken, bi, phist);
    }
}

void
MultiperspectivePerceptronTAGE::update(ThreadID tid, Addr instPC, bool taken,
                                   void *bp_history, bool squashed,
                                   const StaticInstPtr & inst,
                                   Addr corrTarget)
{
    assert(bp_history);
    MPPTAGEBranchInfo *bi = static_cast<MPPTAGEBranchInfo*>(bp_history);

    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, bi->tageBranchInfo, corrTarget);
            if (bi->tageBranchInfo->condBranch) {
                loopPredictor->squashLoop(bi->lpBranchInfo);
            }
        }
        return;
    }

    if (bi->isUnconditional()) {
        statisticalCorrector->scHistoryUpdate(instPC, inst, taken,
                bi->scBranchInfo, corrTarget);
        tage->updateHistories(tid, instPC, taken, bi->tageBranchInfo, false,
                inst, corrTarget);
    } else {
        tage->updateStats(taken, bi->tageBranchInfo);
        loopPredictor->updateStats(taken, bi->lpBranchInfo);
        statisticalCorrector->updateStats(taken, bi->scBranchInfo);

        loopPredictor->condBranchUpdate(tid, instPC, taken,
                bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt);

        bool scPred = (bi->scBranchInfo->lsum >= 0);
        if ((scPred != taken) ||
            ((abs(bi->scBranchInfo->lsum) < bi->scBranchInfo->thres))) {
            updatePartial(tid, *bi, taken);
        }
        statisticalCorrector->condBranchUpdate(tid, instPC, taken,
                bi->scBranchInfo, corrTarget, false /* bias_bit: unused */,
                0 /* hitBank: unused */, 0 /* altBank: unused*/,
                tage->getPathHist(tid));

        tage->condBranchUpdate(tid, instPC, taken, bi->tageBranchInfo,
                               random_mt.random<int>(), corrTarget,
                               bi->predictedTaken, true);

        updateHistories(tid, *bi, taken);

        if (!tage->isSpeculativeUpdateEnabled()) {
            if (inst->isCondCtrl() && inst->isDirectCtrl()
                && !inst->isCall() && !inst->isReturn()) {
                uint32_t truncated_target = corrTarget;
                uint32_t truncated_pc = instPC;
                if (truncated_target < truncated_pc) {
                    if (!taken) {
                        threadData[tid]->imli_counter[0] = 0;
                    } else {
                        threadData[tid]->imli_counter[0] += 1;
                    }
                } else {
                    if (taken) {
                        threadData[tid]->imli_counter[3] = 0;
                    } else {
                        threadData[tid]->imli_counter[3] += 1;
                    }
                }
            }

            statisticalCorrector->scHistoryUpdate(instPC, inst, taken,
                    bi->scBranchInfo, corrTarget);

            tage->updateHistories(tid, instPC, taken, bi->tageBranchInfo,
                                  false, inst, corrTarget);
        }
    }
    delete bi;
}

void
MultiperspectivePerceptronTAGE::uncondBranch(ThreadID tid, Addr pc,
                                             void * &bp_history)
{
    MPPTAGEBranchInfo *bi =
        new MPPTAGEBranchInfo(pc, pcshift, false, *tage, *loopPredictor,
                              *statisticalCorrector);
    bp_history = (void *) bi;
}

void
MultiperspectivePerceptronTAGE::squash(ThreadID tid, void *bp_history)
{
    assert(bp_history);
    MPPTAGEBranchInfo *bi = static_cast<MPPTAGEBranchInfo*>(bp_history);
    delete bi;
}