113627Sjavier.bueno@metempsy.com/* 213627Sjavier.bueno@metempsy.com * Copyright (c) 2014 The University of Wisconsin 313627Sjavier.bueno@metempsy.com * 413627Sjavier.bueno@metempsy.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 513627Sjavier.bueno@metempsy.com * Informatique et en Automatique / French National Research Institute 613627Sjavier.bueno@metempsy.com * for Computer Science and Applied Mathematics) 713627Sjavier.bueno@metempsy.com * 813627Sjavier.bueno@metempsy.com * All rights reserved. 913627Sjavier.bueno@metempsy.com * 1013627Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 1113627Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 1213627Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 1313627Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 1413627Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1513627Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1613627Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1713627Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1813627Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1913627Sjavier.bueno@metempsy.com * this software without specific prior written permission. 2013627Sjavier.bueno@metempsy.com * 2113627Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2213627Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2313627Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2413627Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2513627Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2613627Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2713627Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2813627Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2913627Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3013627Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3113627Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3213627Sjavier.bueno@metempsy.com * 3313627Sjavier.bueno@metempsy.com * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3413627Sjavier.bueno@metempsy.com * from André Seznec's code. 3513627Sjavier.bueno@metempsy.com */ 3613627Sjavier.bueno@metempsy.com 3713627Sjavier.bueno@metempsy.com#ifndef __CPU_PRED_LOOP_PREDICTOR_HH__ 3813627Sjavier.bueno@metempsy.com#define __CPU_PRED_LOOP_PREDICTOR_HH__ 3913627Sjavier.bueno@metempsy.com 4013627Sjavier.bueno@metempsy.com#include "base/statistics.hh" 4113627Sjavier.bueno@metempsy.com#include "base/types.hh" 4213627Sjavier.bueno@metempsy.com#include "sim/sim_object.hh" 4313627Sjavier.bueno@metempsy.com 4413627Sjavier.bueno@metempsy.comstruct LoopPredictorParams; 4513627Sjavier.bueno@metempsy.com 4613627Sjavier.bueno@metempsy.comclass LoopPredictor : public SimObject 4713627Sjavier.bueno@metempsy.com{ 4813627Sjavier.bueno@metempsy.com protected: 4913627Sjavier.bueno@metempsy.com const unsigned logSizeLoopPred; 5013627Sjavier.bueno@metempsy.com const unsigned loopTableAgeBits; 5113627Sjavier.bueno@metempsy.com const unsigned loopTableConfidenceBits; 5213627Sjavier.bueno@metempsy.com const unsigned loopTableTagBits; 5313627Sjavier.bueno@metempsy.com const unsigned loopTableIterBits; 5413627Sjavier.bueno@metempsy.com const unsigned logLoopTableAssoc; 5513627Sjavier.bueno@metempsy.com const uint8_t confidenceThreshold; 5613627Sjavier.bueno@metempsy.com const uint16_t loopTagMask; 5713627Sjavier.bueno@metempsy.com const uint16_t loopNumIterMask; 5813627Sjavier.bueno@metempsy.com const int loopSetMask; 5913627Sjavier.bueno@metempsy.com 6013627Sjavier.bueno@metempsy.com // Prediction Structures 6113627Sjavier.bueno@metempsy.com // Loop Predictor Entry 6213627Sjavier.bueno@metempsy.com struct LoopEntry 6313627Sjavier.bueno@metempsy.com { 6413627Sjavier.bueno@metempsy.com uint16_t numIter; 6513627Sjavier.bueno@metempsy.com uint16_t currentIter; 6613627Sjavier.bueno@metempsy.com uint16_t currentIterSpec; // only for useSpeculation 6713627Sjavier.bueno@metempsy.com uint8_t confidence; 6813627Sjavier.bueno@metempsy.com uint16_t tag; 6913627Sjavier.bueno@metempsy.com uint8_t age; 7013627Sjavier.bueno@metempsy.com bool dir; // only for useDirectionBit 7113627Sjavier.bueno@metempsy.com 7213627Sjavier.bueno@metempsy.com LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0), 7313627Sjavier.bueno@metempsy.com confidence(0), tag(0), age(0), dir(0) { } 7413627Sjavier.bueno@metempsy.com }; 7513627Sjavier.bueno@metempsy.com 7613627Sjavier.bueno@metempsy.com LoopEntry *ltable; 7713627Sjavier.bueno@metempsy.com 7813627Sjavier.bueno@metempsy.com int8_t loopUseCounter; 7913627Sjavier.bueno@metempsy.com unsigned withLoopBits; 8013627Sjavier.bueno@metempsy.com 8113627Sjavier.bueno@metempsy.com const bool useDirectionBit; 8213627Sjavier.bueno@metempsy.com const bool useSpeculation; 8313627Sjavier.bueno@metempsy.com const bool useHashing; 8413627Sjavier.bueno@metempsy.com const bool restrictAllocation; 8513627Sjavier.bueno@metempsy.com const unsigned initialLoopIter; 8613627Sjavier.bueno@metempsy.com const unsigned initialLoopAge; 8713627Sjavier.bueno@metempsy.com const bool optionalAgeReset; 8813627Sjavier.bueno@metempsy.com 8913627Sjavier.bueno@metempsy.com // stats 9013627Sjavier.bueno@metempsy.com Stats::Scalar loopPredictorCorrect; 9113627Sjavier.bueno@metempsy.com Stats::Scalar loopPredictorWrong; 9213627Sjavier.bueno@metempsy.com 9313627Sjavier.bueno@metempsy.com /** 9413627Sjavier.bueno@metempsy.com * Updates an unsigned counter based on up/down parameter 9513627Sjavier.bueno@metempsy.com * @param ctr Reference to counter to update. 9613627Sjavier.bueno@metempsy.com * @param up Boolean indicating if the counter is incremented/decremented 9713627Sjavier.bueno@metempsy.com * If true it is incremented, if false it is decremented 9813627Sjavier.bueno@metempsy.com * @param nbits Counter width. 9913627Sjavier.bueno@metempsy.com */ 10013627Sjavier.bueno@metempsy.com static inline void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned nbits) 10113627Sjavier.bueno@metempsy.com { 10213627Sjavier.bueno@metempsy.com assert(nbits <= sizeof(uint8_t) << 3); 10313627Sjavier.bueno@metempsy.com if (up) { 10413627Sjavier.bueno@metempsy.com if (ctr < ((1 << nbits) - 1)) 10513627Sjavier.bueno@metempsy.com ctr++; 10613627Sjavier.bueno@metempsy.com } else { 10713627Sjavier.bueno@metempsy.com if (ctr) 10813627Sjavier.bueno@metempsy.com ctr--; 10913627Sjavier.bueno@metempsy.com } 11013627Sjavier.bueno@metempsy.com } 11113627Sjavier.bueno@metempsy.com static inline void signedCtrUpdate(int8_t &ctr, bool up, unsigned nbits) 11213627Sjavier.bueno@metempsy.com { 11313627Sjavier.bueno@metempsy.com if (up) { 11413627Sjavier.bueno@metempsy.com if (ctr < ((1 << (nbits - 1)) - 1)) 11513627Sjavier.bueno@metempsy.com ctr++; 11613627Sjavier.bueno@metempsy.com } else { 11713627Sjavier.bueno@metempsy.com if (ctr > -(1 << (nbits - 1))) 11813627Sjavier.bueno@metempsy.com ctr--; 11913627Sjavier.bueno@metempsy.com } 12013627Sjavier.bueno@metempsy.com } 12113627Sjavier.bueno@metempsy.com public: 12213627Sjavier.bueno@metempsy.com // Primary branch history entry 12313627Sjavier.bueno@metempsy.com struct BranchInfo 12413627Sjavier.bueno@metempsy.com { 12513627Sjavier.bueno@metempsy.com uint16_t loopTag; 12613627Sjavier.bueno@metempsy.com uint16_t currentIter; 12713627Sjavier.bueno@metempsy.com 12813627Sjavier.bueno@metempsy.com bool loopPred; 12913627Sjavier.bueno@metempsy.com bool loopPredValid; 13013627Sjavier.bueno@metempsy.com bool loopPredUsed; 13113627Sjavier.bueno@metempsy.com int loopIndex; 13213627Sjavier.bueno@metempsy.com int loopIndexB; // only for useHashing 13313627Sjavier.bueno@metempsy.com int loopHit; 13413627Sjavier.bueno@metempsy.com bool predTaken; 13513627Sjavier.bueno@metempsy.com 13613627Sjavier.bueno@metempsy.com BranchInfo() 13713627Sjavier.bueno@metempsy.com : loopTag(0), currentIter(0), 13813627Sjavier.bueno@metempsy.com loopPred(false), 13913627Sjavier.bueno@metempsy.com loopPredValid(false), loopIndex(0), loopIndexB(0), loopHit(0), 14013627Sjavier.bueno@metempsy.com predTaken(false) 14113627Sjavier.bueno@metempsy.com {} 14213627Sjavier.bueno@metempsy.com }; 14313627Sjavier.bueno@metempsy.com 14413627Sjavier.bueno@metempsy.com /** 14513627Sjavier.bueno@metempsy.com * Computes the index used to access the 14613627Sjavier.bueno@metempsy.com * loop predictor. 14713627Sjavier.bueno@metempsy.com * @param pc_in The unshifted branch PC. 14813627Sjavier.bueno@metempsy.com * @param instShiftAmt Shift the pc by as many bits 14913627Sjavier.bueno@metempsy.com */ 15013627Sjavier.bueno@metempsy.com int lindex(Addr pc_in, unsigned instShiftAmt) const; 15113627Sjavier.bueno@metempsy.com 15213627Sjavier.bueno@metempsy.com /** 15313627Sjavier.bueno@metempsy.com * Computes the index used to access the 15413627Sjavier.bueno@metempsy.com * ltable structures. 15513627Sjavier.bueno@metempsy.com * It may take hashing into account 15613627Sjavier.bueno@metempsy.com * @param index Result of lindex function 15713627Sjavier.bueno@metempsy.com * @param lowPcBits PC bits masked with set size 15813627Sjavier.bueno@metempsy.com * @param way Way to be used 15913627Sjavier.bueno@metempsy.com */ 16013627Sjavier.bueno@metempsy.com int finallindex(int lindex, int lowPcBits, int way) const; 16113627Sjavier.bueno@metempsy.com 16213627Sjavier.bueno@metempsy.com /** 16313627Sjavier.bueno@metempsy.com * Get a branch prediction from the loop 16413627Sjavier.bueno@metempsy.com * predictor. 16513627Sjavier.bueno@metempsy.com * @param pc The unshifted branch PC. 16613627Sjavier.bueno@metempsy.com * @param bi Pointer to information on the 16713627Sjavier.bueno@metempsy.com * prediction. 16813627Sjavier.bueno@metempsy.com * @param speculative Use speculative number of iterations 16913627Sjavier.bueno@metempsy.com * @param instShiftAmt Shift the pc by as many bits (if hashing is not 17013627Sjavier.bueno@metempsy.com * used) 17113627Sjavier.bueno@metempsy.com * @result the result of the prediction, if it could be predicted 17213627Sjavier.bueno@metempsy.com */ 17313627Sjavier.bueno@metempsy.com bool getLoop(Addr pc, BranchInfo* bi, bool speculative, 17413627Sjavier.bueno@metempsy.com unsigned instShiftAmt) const; 17513627Sjavier.bueno@metempsy.com 17613627Sjavier.bueno@metempsy.com /** 17713627Sjavier.bueno@metempsy.com * Updates the loop predictor. 17813627Sjavier.bueno@metempsy.com * @param pc The unshifted branch PC. 17913627Sjavier.bueno@metempsy.com * @param taken The actual branch outcome. 18013627Sjavier.bueno@metempsy.com * @param bi Pointer to information on the 18113627Sjavier.bueno@metempsy.com * prediction recorded at prediction time. 18213627Sjavier.bueno@metempsy.com * @param tage_pred tage prediction of the branch 18313627Sjavier.bueno@metempsy.com */ 18413685Sjavier.bueno@metempsy.com void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred); 18513627Sjavier.bueno@metempsy.com 18613627Sjavier.bueno@metempsy.com /** 18713627Sjavier.bueno@metempsy.com * Speculatively updates the loop predictor 18813627Sjavier.bueno@metempsy.com * iteration count (only for useSpeculation). 18913627Sjavier.bueno@metempsy.com * @param taken The predicted branch outcome. 19013627Sjavier.bueno@metempsy.com * @param bi Pointer to information on the prediction 19113627Sjavier.bueno@metempsy.com * recorded at prediction time. 19213627Sjavier.bueno@metempsy.com */ 19313627Sjavier.bueno@metempsy.com void specLoopUpdate(bool taken, BranchInfo* bi); 19413627Sjavier.bueno@metempsy.com 19513627Sjavier.bueno@metempsy.com /** 19613627Sjavier.bueno@metempsy.com * Update LTAGE for conditional branches. 19713627Sjavier.bueno@metempsy.com * @param branch_pc The unshifted branch PC. 19813627Sjavier.bueno@metempsy.com * @param taken Actual branch outcome. 19913627Sjavier.bueno@metempsy.com * @param tage_pred Prediction from TAGE 20013627Sjavier.bueno@metempsy.com * @param bi Pointer to information on the prediction 20113627Sjavier.bueno@metempsy.com * recorded at prediction time. 20213627Sjavier.bueno@metempsy.com * @param instShiftAmt Number of bits to shift instructions 20313627Sjavier.bueno@metempsy.com */ 20413685Sjavier.bueno@metempsy.com void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, 20513685Sjavier.bueno@metempsy.com bool tage_pred, BranchInfo* bi, unsigned instShiftAmt); 20613627Sjavier.bueno@metempsy.com 20713627Sjavier.bueno@metempsy.com /** 20813627Sjavier.bueno@metempsy.com * Get the loop prediction 20913627Sjavier.bueno@metempsy.com * @param tid The thread ID to select the global 21013627Sjavier.bueno@metempsy.com * histories to use. 21113627Sjavier.bueno@metempsy.com * @param branch_pc The unshifted branch PC. 21213627Sjavier.bueno@metempsy.com * @param cond_branch True if the branch is conditional. 21313627Sjavier.bueno@metempsy.com * @param bi Reference to wrapping pointer to allow storing 21413627Sjavier.bueno@metempsy.com * derived class prediction information in the base class. 21513627Sjavier.bueno@metempsy.com * @param prev_pred_taken Result of the TAGE prediction 21613627Sjavier.bueno@metempsy.com * @param instShiftAmt Shift the pc by as many bits 21713627Sjavier.bueno@metempsy.com * @param instShiftAmt Shift the pc by as many bits 21813627Sjavier.bueno@metempsy.com * @result the prediction, true if taken 21913627Sjavier.bueno@metempsy.com */ 22013627Sjavier.bueno@metempsy.com bool loopPredict( 22113627Sjavier.bueno@metempsy.com ThreadID tid, Addr branch_pc, bool cond_branch, 22213627Sjavier.bueno@metempsy.com BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt); 22313627Sjavier.bueno@metempsy.com 22413627Sjavier.bueno@metempsy.com /** 22513627Sjavier.bueno@metempsy.com * Update the stats 22613627Sjavier.bueno@metempsy.com * @param taken Actual branch outcome 22713627Sjavier.bueno@metempsy.com * @param bi Pointer to information on the prediction 22813627Sjavier.bueno@metempsy.com * recorded at prediction time. 22913627Sjavier.bueno@metempsy.com */ 23013627Sjavier.bueno@metempsy.com void updateStats(bool taken, BranchInfo* bi); 23113627Sjavier.bueno@metempsy.com 23213627Sjavier.bueno@metempsy.com void squashLoop(BranchInfo * bi); 23313627Sjavier.bueno@metempsy.com 23413627Sjavier.bueno@metempsy.com void squash(ThreadID tid, BranchInfo *bi); 23513627Sjavier.bueno@metempsy.com 23613627Sjavier.bueno@metempsy.com virtual bool calcConf(int index) const; 23713627Sjavier.bueno@metempsy.com 23813685Sjavier.bueno@metempsy.com virtual bool optionalAgeInc() const; 23913627Sjavier.bueno@metempsy.com 24013627Sjavier.bueno@metempsy.com virtual BranchInfo *makeBranchInfo(); 24113627Sjavier.bueno@metempsy.com 24213627Sjavier.bueno@metempsy.com /** 24313627Sjavier.bueno@metempsy.com * Gets the value of the loop use counter 24413627Sjavier.bueno@metempsy.com * @return the loop use counter value 24513627Sjavier.bueno@metempsy.com */ 24613627Sjavier.bueno@metempsy.com int8_t getLoopUseCounter() const 24713627Sjavier.bueno@metempsy.com { 24813627Sjavier.bueno@metempsy.com return loopUseCounter; 24913627Sjavier.bueno@metempsy.com } 25013627Sjavier.bueno@metempsy.com 25113627Sjavier.bueno@metempsy.com /** 25213627Sjavier.bueno@metempsy.com * Initialize the loop predictor 25313627Sjavier.bueno@metempsy.com */ 25413627Sjavier.bueno@metempsy.com void init() override; 25513627Sjavier.bueno@metempsy.com 25613627Sjavier.bueno@metempsy.com /** 25713627Sjavier.bueno@metempsy.com * Register stats for this object 25813627Sjavier.bueno@metempsy.com */ 25913627Sjavier.bueno@metempsy.com void regStats() override; 26013627Sjavier.bueno@metempsy.com 26113627Sjavier.bueno@metempsy.com LoopPredictor(LoopPredictorParams *p); 26214081Sjavier.bueno@metempsy.com 26314081Sjavier.bueno@metempsy.com size_t getSizeInBits() const; 26413627Sjavier.bueno@metempsy.com}; 26513627Sjavier.bueno@metempsy.com#endif//__CPU_PRED_LOOP_PREDICTOR_HH__ 266