path: root/src/cpu/pred/loop_predictor.hh

/*
 * Copyright (c) 2014 The University of Wisconsin
 *
 * 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.
 *
 * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais,
 * from André Seznec's code.
 */

#ifndef __CPU_PRED_LOOP_PREDICTOR_HH__
#define __CPU_PRED_LOOP_PREDICTOR_HH__

#include "base/statistics.hh"
#include "base/types.hh"
#include "sim/sim_object.hh"

struct LoopPredictorParams;

class LoopPredictor : public SimObject
{
  protected:
    const unsigned logSizeLoopPred;
    const unsigned loopTableAgeBits;
    const unsigned loopTableConfidenceBits;
    const unsigned loopTableTagBits;
    const unsigned loopTableIterBits;
    const unsigned logLoopTableAssoc;
    const uint8_t confidenceThreshold;
    const uint16_t loopTagMask;
    const uint16_t loopNumIterMask;
    const int loopSetMask;

    // Prediction Structures
    // Loop Predictor Entry
    struct LoopEntry
    {
        uint16_t numIter;
        uint16_t currentIter;
        uint16_t currentIterSpec; // only for useSpeculation
        uint8_t confidence;
        uint16_t tag;
        uint8_t age;
        bool dir; // only for useDirectionBit

        LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0),
                      confidence(0), tag(0), age(0), dir(0) { }
    };

    LoopEntry *ltable;

    int8_t loopUseCounter;
    unsigned withLoopBits;

    const bool useDirectionBit;
    const bool useSpeculation;
    const bool useHashing;
    const bool restrictAllocation;
    const unsigned initialLoopIter;
    const unsigned initialLoopAge;
    const bool optionalAgeReset;

    // stats
    Stats::Scalar loopPredictorCorrect;
    Stats::Scalar loopPredictorWrong;

    /**
     * Updates an unsigned counter based on up/down parameter
     * @param ctr Reference to counter to update.
     * @param up Boolean indicating if the counter is incremented/decremented
     * If true it is incremented, if false it is decremented
     * @param nbits Counter width.
     */
    static inline void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned nbits)
    {
        assert(nbits <= sizeof(uint8_t) << 3);
        if (up) {
            if (ctr < ((1 << nbits) - 1))
                ctr++;
        } else {
            if (ctr)
                ctr--;
        }
    }
    static inline void signedCtrUpdate(int8_t &ctr, bool up, unsigned nbits)
    {
        if (up) {
            if (ctr < ((1 << (nbits - 1)) - 1))
                ctr++;
        } else {
            if (ctr > -(1 << (nbits - 1)))
                ctr--;
        }
    }
  public:
    // Primary branch history entry
    struct BranchInfo
    {
        uint16_t loopTag;
        uint16_t currentIter;

        bool loopPred;
        bool loopPredValid;
        bool loopPredUsed;
        int  loopIndex;
        int  loopIndexB;  // only for useHashing
        int loopHit;
        bool predTaken;

        BranchInfo()
            : loopTag(0), currentIter(0),
              loopPred(false),
              loopPredValid(false), loopIndex(0), loopIndexB(0), loopHit(0),
              predTaken(false)
        {}
    };

    /**
     * Computes the index used to access the
     * loop predictor.
     * @param pc_in The unshifted branch PC.
     * @param instShiftAmt Shift the pc by as many bits
     */
    int lindex(Addr pc_in, unsigned instShiftAmt) const;

    /**
     * Computes the index used to access the
     * ltable structures.
     * It may take hashing into account
     * @param index Result of lindex function
     * @param lowPcBits PC bits masked with set size
     * @param way Way to be used
     */
    int finallindex(int lindex, int lowPcBits, int way) const;

    /**
     * Get a branch prediction from the loop
     * predictor.
     * @param pc The unshifted branch PC.
     * @param bi Pointer to information on the
     * prediction.
     * @param speculative Use speculative number of iterations
     * @param instShiftAmt Shift the pc by as many bits (if hashing is not
     * used)
     * @result the result of the prediction, if it could be predicted
     */
    bool getLoop(Addr pc, BranchInfo* bi, bool speculative,
                 unsigned instShiftAmt) const;

   /**
    * Updates the loop predictor.
    * @param pc The unshifted branch PC.
    * @param taken The actual branch outcome.
    * @param bi Pointer to information on the
    * prediction recorded at prediction time.
    * @param tage_pred tage prediction of the branch
    */
    void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred);

    /**
     * Speculatively updates the loop predictor
     * iteration count (only for useSpeculation).
     * @param taken The predicted branch outcome.
     * @param bi Pointer to information on the prediction
     * recorded at prediction time.
     */
    void specLoopUpdate(bool taken, BranchInfo* bi);

    /**
     * Update LTAGE for conditional branches.
     * @param branch_pc The unshifted branch PC.
     * @param taken Actual branch outcome.
     * @param tage_pred Prediction from TAGE
     * @param bi Pointer to information on the prediction
     * recorded at prediction time.
     * @param instShiftAmt Number of bits to shift instructions
     */
    void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
        bool tage_pred, BranchInfo* bi, unsigned instShiftAmt);

    /**
     * Get the loop prediction
     * @param tid The thread ID to select the global
     * histories to use.
     * @param branch_pc The unshifted branch PC.
     * @param cond_branch True if the branch is conditional.
     * @param bi Reference to wrapping pointer to allow storing
     * derived class prediction information in the base class.
     * @param prev_pred_taken Result of the TAGE prediction
     * @param instShiftAmt Shift the pc by as many bits
     * @param instShiftAmt Shift the pc by as many bits
     * @result the prediction, true if taken
     */
    bool loopPredict(
        ThreadID tid, Addr branch_pc, bool cond_branch,
        BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt);

    /**
     * Update the stats
     * @param taken Actual branch outcome
     * @param bi Pointer to information on the prediction
     * recorded at prediction time.
     */
    void updateStats(bool taken, BranchInfo* bi);

    void squashLoop(BranchInfo * bi);

    void squash(ThreadID tid, BranchInfo *bi);

    virtual bool calcConf(int index) const;

    virtual bool optionalAgeInc() const;

    virtual BranchInfo *makeBranchInfo();

    /**
     * Gets the value of the loop use counter
     * @return the loop use counter value
     */
    int8_t getLoopUseCounter() const
    {
        return loopUseCounter;
    }

    /**
     * Initialize the loop predictor
     */
    void init() override;

    /**
     * Register stats for this object
     */
    void regStats() override;

    LoopPredictor(LoopPredictorParams *p);

    size_t getSizeInBits() const;
};
#endif//__CPU_PRED_LOOP_PREDICTOR_HH__