tage_sc_l_8KB.cc

Go to the documentation of this file.

/*
 * 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"
 
namespace gem5
{
 
namespace branch_prediction
{
 
TAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector(
    const 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(instShiftAmt);
    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)
{
    lsum += gPredict(
        branch_pc, bi->globalHist, gm, ggehl, gnb, logGnb, wg);
 
    lsum += gPredict(
        branch_pc, bi->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw);
 
    // only 1 local history here
    lsum += gPredict(
        branch_pc, bi->localHistories[1], lm,
        lgehl, lnb, logLnb, wl);
 
    lsum += gPredict(
        branch_pc, bi->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,
                                                    const StaticInstPtr &inst,
                                                    bool taken, Addr target,
                                                    int64_t phist)
{
    int brtype = inst->isDirectCtrl() ? 0 : 2;
    if (! inst->isUncondCtrl()) {
        ++brtype;
    }
    // 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, inst, taken,
                                          target, phist);
}
 
void
TAGE_SC_L_8KB_StatisticalCorrector::scRecordHistState(Addr branch_pc,
                                                      BranchInfo *bi)
{
    StatisticalCorrector::scRecordHistState(branch_pc, bi);
    auto sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
    bi->globalHist = sh->globalHist;
}
 
bool
TAGE_SC_L_8KB_StatisticalCorrector::scRestoreHistState(BranchInfo *bi)
{
    if (!StatisticalCorrector::scRestoreHistState(bi)) {
        return false;
    }
    auto sh = static_cast<SC_8KB_ThreadHistory *>(scHistory);
    sh->globalHist = bi->globalHist;
    return true;
}
 
void
TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken,
                                             BranchInfo *bi)
{
    gUpdate(pc, taken, bi->globalHist, gm, ggehl, gnb, logGnb, wg, bi);
    gUpdate(pc, taken, bi->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi);
    gUpdate(pc, taken, bi->localHistories[1], lm, lgehl, lnb, logLnb, wl,
            bi);
    gUpdate(pc, taken, bi->imliCount, im, igehl, inb, logInb, wi, bi);
}
 
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
{
    Addr shifted_pc = pc >> instShiftAmt;
    int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2)
            ^ shifted_pc ^ (shifted_pc >> 2) ^
              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]))
            & ((1ULL << 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 =
                        ((rng->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 ((rng->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++;
    }
}
 
} // namespace branch_prediction
} // namespace gem5