tage_base.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2014 The University of Wisconsin
 * Copyright (c) 2024 Technical University of Munich
 *
 * 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.
 */
 
/* @file
 * Implementation of a TAGE branch predictor. TAGE is a global-history based
 * branch predictor. It features a PC-indexed bimodal predictor and N
 * partially tagged tables, indexed with a hash of the PC and the global
 * branch history. The different lengths of global branch history used to
 * index the partially tagged tables grow geometrically. A small path history
 * is also used in the hash.
 *
 * All TAGE tables are accessed in parallel, and the one using the longest
 * history that matches provides the prediction (some exceptions apply).
 * Entries are allocated in components using a longer history than the
 * one that predicted when the prediction is incorrect.
 */
 
#ifndef __CPU_PRED_TAGE_BASE_HH__
#define __CPU_PRED_TAGE_BASE_HH__
 
#include <vector>
 
#include "base/statistics.hh"
#include "cpu/null_static_inst.hh"
#include "cpu/static_inst.hh"
#include "params/TAGEBase.hh"
#include "sim/sim_object.hh"
 
namespace gem5
{
 
namespace branch_prediction
{
 
class TAGEBase : public SimObject
{
  public:
    TAGEBase(const TAGEBaseParams &p);
    void init() override;
 
  protected:
    // Prediction Structures
 
    // Tage Entry
    struct TageEntry
    {
        int8_t ctr;
        uint16_t tag;
        uint8_t u;
        TageEntry() : ctr(0), tag(0), u(0) { }
    };
 
    // Folded History Table - compressed history
    // to mix with instruction PC to index partially
    // tagged tables.
    struct FoldedHistory
    {
        unsigned comp;
        int compLength;
        int origLength;
        int outpoint;
        int bufferSize;
 
        FoldedHistory()
        {
            comp = 0;
        }
 
        void init(int original_length, int compressed_length)
        {
            origLength = original_length;
            compLength = compressed_length;
            outpoint = original_length % compressed_length;
        }
 
        void update(uint8_t * h)
        {
            comp = (comp << 1) | h[0];
            comp ^= h[origLength] << outpoint;
            comp ^= (comp >> compLength);
            comp &= (1ULL << compLength) - 1;
        }
 
        void restore(uint8_t * h)
        {
            comp ^= h[origLength] << outpoint;
            auto tmp = (comp & 1) ^ h[0];
            comp = (tmp << (compLength-1)) | (comp >> 1);
        }
    };
 
  public:
 
    // provider type
    enum
    {
        BIMODAL_ONLY = 0,
        TAGE_LONGEST_MATCH,
        BIMODAL_ALT_MATCH,
        TAGE_ALT_MATCH,
        LAST_TAGE_PROVIDER_TYPE = TAGE_ALT_MATCH
    };
 
    // Primary branch history entry
    struct BranchInfo
    {
        const Addr branchPC;
        const bool condBranch;
 
        int pathHist;
        int hitBank;
        int hitBankIndex;
        int altBank;
        int altBankIndex;
        int bimodalIndex;
 
        bool tagePred;
        bool altTaken;
        bool longestMatchPred;
        bool pseudoNewAlloc;
 
        // Pointer to dynamically allocated storage
        // to save table indices and folded histories.
        // To do one call to new instead of five.
        int *storage;
 
        // Pointers to actual saved array within the dynamically
        // allocated storage.
        int *tableIndices;
        int *tableTags;
        int *ci;
        int *ct0;
        int *ct1;
 
        // for stats purposes
        unsigned provider;
 
        // The bit vector and the number of bits of global
        // history used for this branch.
        uint64_t ghist;
        uint8_t nGhist;
 
        // A flag to indicate if this history entry has
        // modified the histories
        bool modified;
        // A flag to indicate if the indies and tags are valid.
        bool valid;
 
        BranchInfo(const TAGEBase &tage, Addr pc, bool conditional)
            : branchPC(pc), condBranch(conditional),
              hitBank(0), hitBankIndex(0),
              altBank(0), altBankIndex(0),
              bimodalIndex(0),
              tagePred(false), altTaken(false),
              longestMatchPred(false),
              pseudoNewAlloc(false),
              provider(-1),
              ghist(0), nGhist(0),
              modified(false),
              valid(false)
        {
            int sz = tage.nHistoryTables + 1;
            storage = new int [sz * 5];
            tableIndices = storage;
            tableTags = storage + sz;
            ci = tableTags + sz;
            ct0 = ci + sz;
            ct1 = ct0 + sz;
        }
 
        virtual ~BranchInfo()
        {
            delete[] storage;
        }
    };
 
    virtual BranchInfo *makeBranchInfo(Addr pc, bool conditional);
 

    virtual int bindex(Addr pc_in) const;

    virtual int gindex(ThreadID tid, Addr pc, int bank) const;

    virtual int F(int phist, int size, int bank) const;

    virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const;

    template<typename T>
    static void ctrUpdate(T & ctr, bool taken, int nbits);

    static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);

    virtual bool getBimodePred(Addr pc, BranchInfo* bi) const;

    void baseUpdate(Addr pc, bool taken, BranchInfo* bi);

    void updateGHist(ThreadID tid, uint64_t bv, uint8_t n);

    void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);

    virtual void updateHistories(ThreadID tid, Addr branch_pc,
                            bool speculative, bool taken, Addr target,
                            const StaticInstPtr &inst, BranchInfo* bi);
    void recordHistState(ThreadID tid, BranchInfo* bi);

    void restoreHistState(ThreadID tid, BranchInfo* bi);

    virtual void updatePathAndGlobalHistory(ThreadID tid, int brtype,
                    bool taken, Addr branch_pc, Addr target, BranchInfo* bi);

    virtual int branchTypeExtra(const StaticInstPtr & inst) { return 0; }

    virtual void squash(ThreadID tid, bool taken, Addr target,
                        const StaticInstPtr &inst, BranchInfo *bi);

    virtual void condBranchUpdate(
        ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi,
        int nrand, Addr corrTarget, bool pred, bool preAdjustAlloc = false);

    bool tagePredict(
        ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi);

    virtual void updateStats(bool taken, BranchInfo* bi);

    virtual void buildTageTables();

    virtual void calculateParameters();

    virtual void calculateIndicesAndTags(
        ThreadID tid, Addr branch_pc, BranchInfo* bi);

    virtual unsigned getUseAltIdx(BranchInfo* bi, Addr branch_pc);

    virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken);

    virtual void handleAllocAndUReset(
        bool alloc, bool taken, BranchInfo* bi, int nrand);

    virtual void handleUReset();

    virtual void handleTAGEUpdate(
        Addr branch_pc, bool taken, BranchInfo* bi);

    virtual void resetUctr(uint8_t & u);

    virtual void extraAltCalc(BranchInfo* bi);
 
    virtual bool isHighConfidence(BranchInfo* bi) const
    {
        return false;
    }
 
    unsigned getGHR(ThreadID tid) const;
    int8_t getCtr(int hitBank, int hitBankIndex) const;
    unsigned getTageCtrBits() const;
    int getPathHist(ThreadID tid, bool speculative=true) const;
    virtual int calcNewPathHist(ThreadID tid, Addr pc, int cur_phist,
                                bool taken, int brtype, Addr target) const;
    bool isSpeculativeUpdateEnabled() const;
    size_t getSizeInBits() const;
 
  protected:
    const unsigned logRatioBiModalHystEntries;
    const unsigned nHistoryTables;
    const unsigned tagTableCounterBits;
    const unsigned tagTableUBits;
    const unsigned histBufferSize;
    const unsigned minHist;
    const unsigned maxHist;
    const unsigned pathHistBits;
 
    std::vector<unsigned> tagTableTagWidths;
    std::vector<int> logTagTableSizes;
 
    std::vector<bool> btablePrediction;
    std::vector<bool> btableHysteresis;
    TageEntry **gtable;
 
    // Keep per-thread histories to
    // support SMT.
    struct ThreadHistory
    {
        // Speculative path history
        // (LSB of branch address)
        int pathHist;
        // Non-speculative path history
        int nonSpecPathHist;
 
        // Speculative branch direction
        // history (circular buffer)
        std::vector<uint8_t> globalHist;
 
        // Index to most recent branch outcome
        int ptGhist;
 
        // Speculative folded histories.
        FoldedHistory *computeIndices;
        FoldedHistory *computeTags[2];
    };
 
    std::vector<ThreadHistory> threadHistory;

    virtual void initFoldedHistories(ThreadHistory & history);
 
    int *histLengths;
    int *tableIndices;
    int *tableTags;
 
    std::vector<int8_t> useAltPredForNewlyAllocated;
    int64_t tCounter;
    uint64_t logUResetPeriod;
    const int64_t initialTCounterValue;
    unsigned numUseAltOnNa;
    unsigned useAltOnNaBits;
    unsigned maxNumAlloc;
    const bool takenOnlyHistory;
 
    // Tells which tables are active
    // (for the base TAGE implementation all are active)
    // Some other classes use this for handling associativity
    std::vector<bool> noSkip;
 
    const bool speculativeHistUpdate;
 
    const unsigned instShiftAmt;
 
    bool initialized;
 
    struct TAGEBaseStats : public statistics::Group
    {
        TAGEBaseStats(statistics::Group *parent, unsigned nHistoryTables);
        // stats
        statistics::Scalar longestMatchProviderCorrect;
        statistics::Scalar altMatchProviderCorrect;
        statistics::Scalar bimodalAltMatchProviderCorrect;
        statistics::Scalar bimodalProviderCorrect;
        statistics::Scalar longestMatchProviderWrong;
        statistics::Scalar altMatchProviderWrong;
        statistics::Scalar bimodalAltMatchProviderWrong;
        statistics::Scalar bimodalProviderWrong;
        statistics::Scalar altMatchProviderWouldHaveHit;
        statistics::Scalar longestMatchProviderWouldHaveHit;
 
        statistics::Vector longestMatchProvider;
        statistics::Vector altMatchProvider;
    } stats;
};
 
} // namespace branch_prediction
} // namespace gem5
 
#endif // __CPU_PRED_TAGE_BASE_HH__