blob: 3579c5763e88be3996d7f56f1f154414e2a71cdc [file] [log] [blame]
/*
* 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
* @param random0 random value
* @param random1 random value
* @param random2 random value
*/
void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred,
int random0, int random1, int random2);
/**
* 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
* @param rand0 Random integer value
* @param rand1 Random integer value
* @param rand2 Random integer value
*/
void condBranchUpdate(
ThreadID tid, Addr branch_pc, bool taken, bool tage_pred,
BranchInfo* bi, unsigned instShiftAmt, int rand0, int rand1,
int rand2);
/**
* 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(int nrand) 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);
};
#endif//__CPU_PRED_LOOP_PREDICTOR_HH__