ltage.hh revision 13493
111784Sarthur.perais@inria.fr/* 211784Sarthur.perais@inria.fr * Copyright (c) 2014 The University of Wisconsin 311784Sarthur.perais@inria.fr * 411784Sarthur.perais@inria.fr * Copyright (c) 2006 INRIA (Institut National de Recherche en 511784Sarthur.perais@inria.fr * Informatique et en Automatique / French National Research Institute 611784Sarthur.perais@inria.fr * for Computer Science and Applied Mathematics) 711784Sarthur.perais@inria.fr * 811784Sarthur.perais@inria.fr * All rights reserved. 911784Sarthur.perais@inria.fr * 1011784Sarthur.perais@inria.fr * Redistribution and use in source and binary forms, with or without 1111784Sarthur.perais@inria.fr * modification, are permitted provided that the following conditions are 1211784Sarthur.perais@inria.fr * met: redistributions of source code must retain the above copyright 1311784Sarthur.perais@inria.fr * notice, this list of conditions and the following disclaimer; 1411784Sarthur.perais@inria.fr * redistributions in binary form must reproduce the above copyright 1511784Sarthur.perais@inria.fr * notice, this list of conditions and the following disclaimer in the 1611784Sarthur.perais@inria.fr * documentation and/or other materials provided with the distribution; 1711784Sarthur.perais@inria.fr * neither the name of the copyright holders nor the names of its 1811784Sarthur.perais@inria.fr * contributors may be used to endorse or promote products derived from 1911784Sarthur.perais@inria.fr * this software without specific prior written permission. 2011784Sarthur.perais@inria.fr * 2111784Sarthur.perais@inria.fr * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2211784Sarthur.perais@inria.fr * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2311784Sarthur.perais@inria.fr * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2411784Sarthur.perais@inria.fr * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2511784Sarthur.perais@inria.fr * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2611784Sarthur.perais@inria.fr * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2711784Sarthur.perais@inria.fr * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2811784Sarthur.perais@inria.fr * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2911784Sarthur.perais@inria.fr * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3011784Sarthur.perais@inria.fr * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3111784Sarthur.perais@inria.fr * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3211784Sarthur.perais@inria.fr * 3311784Sarthur.perais@inria.fr * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3411784Sarthur.perais@inria.fr * from André Seznec's code. 3511784Sarthur.perais@inria.fr */ 3611784Sarthur.perais@inria.fr 3711784Sarthur.perais@inria.fr/* @file 3811784Sarthur.perais@inria.fr * Implementation of a L-TAGE branch predictor. TAGE is a global-history based 3911784Sarthur.perais@inria.fr * branch predictor. It features a PC-indexed bimodal predictor and N 4011784Sarthur.perais@inria.fr * partially tagged tables, indexed with a hash of the PC and the global 4111784Sarthur.perais@inria.fr * branch history. The different lengths of global branch history used to 4211784Sarthur.perais@inria.fr * index the partially tagged tables grow geometrically. A small path history 4311784Sarthur.perais@inria.fr * is also used in the hash. L-TAGE also features a loop predictor that records 4411784Sarthur.perais@inria.fr * iteration count of loops and predicts accordingly. 4511784Sarthur.perais@inria.fr * 4611784Sarthur.perais@inria.fr * All TAGE tables are accessed in parallel, and the one using the longest 4711784Sarthur.perais@inria.fr * history that matches provides the prediction (some exceptions apply). 4811784Sarthur.perais@inria.fr * Entries are allocated in components using a longer history than the 4911784Sarthur.perais@inria.fr * one that predicted when the prediction is incorrect. 5011784Sarthur.perais@inria.fr */ 5111784Sarthur.perais@inria.fr 5211784Sarthur.perais@inria.fr#ifndef __CPU_PRED_LTAGE 5311784Sarthur.perais@inria.fr#define __CPU_PRED_LTAGE 5411784Sarthur.perais@inria.fr 5513454Spau.cabre@metempsy.com 5611784Sarthur.perais@inria.fr#include <vector> 5711784Sarthur.perais@inria.fr 5811784Sarthur.perais@inria.fr#include "base/types.hh" 5913454Spau.cabre@metempsy.com#include "cpu/pred/tage.hh" 6011784Sarthur.perais@inria.fr#include "params/LTAGE.hh" 6111784Sarthur.perais@inria.fr 6213454Spau.cabre@metempsy.comclass LTAGE: public TAGE 6311784Sarthur.perais@inria.fr{ 6411784Sarthur.perais@inria.fr public: 6511784Sarthur.perais@inria.fr LTAGE(const LTAGEParams *params); 6611784Sarthur.perais@inria.fr 6711784Sarthur.perais@inria.fr // Base class methods. 6811784Sarthur.perais@inria.fr void squash(ThreadID tid, void *bp_history) override; 6911784Sarthur.perais@inria.fr 7013455Spau.cabre@metempsy.com void regStats() override; 7113455Spau.cabre@metempsy.com 7211784Sarthur.perais@inria.fr private: 7311784Sarthur.perais@inria.fr // Prediction Structures 7411784Sarthur.perais@inria.fr // Loop Predictor Entry 7511784Sarthur.perais@inria.fr struct LoopEntry 7611784Sarthur.perais@inria.fr { 7711784Sarthur.perais@inria.fr uint16_t numIter; 7811784Sarthur.perais@inria.fr uint16_t currentIter; 7913493Spau.cabre@metempsy.com uint16_t currentIterSpec; // only for useSpeculation 8011784Sarthur.perais@inria.fr uint8_t confidence; 8111784Sarthur.perais@inria.fr uint16_t tag; 8211784Sarthur.perais@inria.fr uint8_t age; 8313493Spau.cabre@metempsy.com bool dir; // only for useDirectionBit 8411784Sarthur.perais@inria.fr 8511784Sarthur.perais@inria.fr LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0), 8611784Sarthur.perais@inria.fr confidence(0), tag(0), age(0), dir(0) { } 8711784Sarthur.perais@inria.fr }; 8811784Sarthur.perais@inria.fr 8913455Spau.cabre@metempsy.com // more provider types 9013455Spau.cabre@metempsy.com enum { 9113455Spau.cabre@metempsy.com LOOP = LAST_TAGE_PROVIDER_TYPE + 1 9213455Spau.cabre@metempsy.com }; 9313455Spau.cabre@metempsy.com 9413454Spau.cabre@metempsy.com // Primary branch history entry 9513454Spau.cabre@metempsy.com struct LTageBranchInfo : public TageBranchInfo 9611784Sarthur.perais@inria.fr { 9713442Spau.cabre@metempsy.com uint16_t loopTag; 9811784Sarthur.perais@inria.fr uint16_t currentIter; 9911784Sarthur.perais@inria.fr 10011784Sarthur.perais@inria.fr bool loopPred; 10111784Sarthur.perais@inria.fr bool loopPredValid; 10211784Sarthur.perais@inria.fr int loopIndex; 10313493Spau.cabre@metempsy.com int loopLowPcBits; // only for useHashing 10411784Sarthur.perais@inria.fr int loopHit; 10511784Sarthur.perais@inria.fr 10613454Spau.cabre@metempsy.com LTageBranchInfo(int sz) 10713454Spau.cabre@metempsy.com : TageBranchInfo(sz), 10813454Spau.cabre@metempsy.com loopTag(0), currentIter(0), 10913454Spau.cabre@metempsy.com loopPred(false), 11013493Spau.cabre@metempsy.com loopPredValid(false), loopIndex(0), loopLowPcBits(0), loopHit(0) 11113454Spau.cabre@metempsy.com {} 11211784Sarthur.perais@inria.fr }; 11311784Sarthur.perais@inria.fr 11411784Sarthur.perais@inria.fr /** 11511784Sarthur.perais@inria.fr * Computes the index used to access the 11611784Sarthur.perais@inria.fr * loop predictor. 11711784Sarthur.perais@inria.fr * @param pc_in The unshifted branch PC. 11811784Sarthur.perais@inria.fr */ 11911784Sarthur.perais@inria.fr int lindex(Addr pc_in) const; 12011784Sarthur.perais@inria.fr 12111784Sarthur.perais@inria.fr /** 12213493Spau.cabre@metempsy.com * Computes the index used to access the 12313493Spau.cabre@metempsy.com * ltable structures. 12413493Spau.cabre@metempsy.com * It may take hashing into account 12513493Spau.cabre@metempsy.com * @param index Result of lindex function 12613493Spau.cabre@metempsy.com * @param lowPcBits PC bits masked with set size 12713493Spau.cabre@metempsy.com * @param way Way to be used 12813493Spau.cabre@metempsy.com */ 12913493Spau.cabre@metempsy.com int finallindex(int lindex, int lowPcBits, int way) const; 13013493Spau.cabre@metempsy.com 13113493Spau.cabre@metempsy.com /** 13211784Sarthur.perais@inria.fr * Get a branch prediction from the loop 13311784Sarthur.perais@inria.fr * predictor. 13411784Sarthur.perais@inria.fr * @param pc The unshifted branch PC. 13511784Sarthur.perais@inria.fr * @param bi Pointer to information on the 13611784Sarthur.perais@inria.fr * prediction. 13713493Spau.cabre@metempsy.com * @param speculative Use speculative number of iterations 13811784Sarthur.perais@inria.fr */ 13913493Spau.cabre@metempsy.com bool getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const; 14011784Sarthur.perais@inria.fr 14111784Sarthur.perais@inria.fr /** 14211784Sarthur.perais@inria.fr * Updates the loop predictor. 14311784Sarthur.perais@inria.fr * @param pc The unshifted branch PC. 14411784Sarthur.perais@inria.fr * @param taken The actual branch outcome. 14511784Sarthur.perais@inria.fr * @param bi Pointer to information on the 14611784Sarthur.perais@inria.fr * prediction recorded at prediction time. 14711784Sarthur.perais@inria.fr */ 14813454Spau.cabre@metempsy.com void loopUpdate(Addr pc, bool Taken, LTageBranchInfo* bi); 14911784Sarthur.perais@inria.fr 15011784Sarthur.perais@inria.fr /** 15111784Sarthur.perais@inria.fr * Speculatively updates the loop predictor 15213493Spau.cabre@metempsy.com * iteration count (only for useSpeculation). 15311784Sarthur.perais@inria.fr * @param taken The predicted branch outcome. 15411784Sarthur.perais@inria.fr * @param bi Pointer to information on the prediction 15511784Sarthur.perais@inria.fr * recorded at prediction time. 15611784Sarthur.perais@inria.fr */ 15713493Spau.cabre@metempsy.com void specLoopUpdate(bool taken, LTageBranchInfo* bi); 15811784Sarthur.perais@inria.fr 15913454Spau.cabre@metempsy.com /** 16013454Spau.cabre@metempsy.com * Update LTAGE for conditional branches. 16113454Spau.cabre@metempsy.com * @param branch_pc The unshifted branch PC. 16213454Spau.cabre@metempsy.com * @param taken Actual branch outcome. 16313454Spau.cabre@metempsy.com * @param bi Pointer to information on the prediction 16413454Spau.cabre@metempsy.com * recorded at prediction time. 16513454Spau.cabre@metempsy.com * @nrand Random int number from 0 to 3 16613454Spau.cabre@metempsy.com */ 16713454Spau.cabre@metempsy.com void condBranchUpdate( 16813454Spau.cabre@metempsy.com Addr branch_pc, bool taken, TageBranchInfo* bi, int nrand) override; 16913454Spau.cabre@metempsy.com 17013454Spau.cabre@metempsy.com /** 17113454Spau.cabre@metempsy.com * Get a branch prediction from LTAGE. *NOT* an override of 17213454Spau.cabre@metempsy.com * BpredUnit::predict(). 17313454Spau.cabre@metempsy.com * @param tid The thread ID to select the global 17413454Spau.cabre@metempsy.com * histories to use. 17513454Spau.cabre@metempsy.com * @param branch_pc The unshifted branch PC. 17613454Spau.cabre@metempsy.com * @param cond_branch True if the branch is conditional. 17713454Spau.cabre@metempsy.com * @param b Reference to wrapping pointer to allow storing 17813454Spau.cabre@metempsy.com * derived class prediction information in the base class. 17913454Spau.cabre@metempsy.com */ 18013454Spau.cabre@metempsy.com bool predict( 18113454Spau.cabre@metempsy.com ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override; 18213454Spau.cabre@metempsy.com 18313454Spau.cabre@metempsy.com /** 18413454Spau.cabre@metempsy.com * Restores speculatively updated path and direction histories. 18513454Spau.cabre@metempsy.com * Also recomputes compressed (folded) histories based on the 18613454Spau.cabre@metempsy.com * correct branch outcome. 18713454Spau.cabre@metempsy.com * This version of squash() is called once on a branch misprediction. 18813454Spau.cabre@metempsy.com * @param tid The Thread ID to select the histories to rollback. 18913454Spau.cabre@metempsy.com * @param taken The correct branch outcome. 19013454Spau.cabre@metempsy.com * @param bp_history Wrapping pointer to TageBranchInfo (to allow 19113454Spau.cabre@metempsy.com * storing derived class prediction information in the 19213454Spau.cabre@metempsy.com * base class). 19313454Spau.cabre@metempsy.com * @post bp_history points to valid memory. 19413454Spau.cabre@metempsy.com */ 19513454Spau.cabre@metempsy.com void squash( 19613454Spau.cabre@metempsy.com ThreadID tid, bool taken, void *bp_history) override; 19713454Spau.cabre@metempsy.com 19813455Spau.cabre@metempsy.com /** 19913455Spau.cabre@metempsy.com * Update the stats 20013455Spau.cabre@metempsy.com * @param taken Actual branch outcome 20113455Spau.cabre@metempsy.com * @param bi Pointer to information on the prediction 20213455Spau.cabre@metempsy.com * recorded at prediction time. 20313455Spau.cabre@metempsy.com */ 20413455Spau.cabre@metempsy.com void updateStats(bool taken, TageBranchInfo* bi) override; 20513455Spau.cabre@metempsy.com 20611784Sarthur.perais@inria.fr const unsigned logSizeLoopPred; 20713442Spau.cabre@metempsy.com const unsigned loopTableAgeBits; 20813442Spau.cabre@metempsy.com const unsigned loopTableConfidenceBits; 20913442Spau.cabre@metempsy.com const unsigned loopTableTagBits; 21013442Spau.cabre@metempsy.com const unsigned loopTableIterBits; 21113444Spau.cabre@metempsy.com const unsigned logLoopTableAssoc; 21213442Spau.cabre@metempsy.com const uint8_t confidenceThreshold; 21313442Spau.cabre@metempsy.com const uint16_t loopTagMask; 21413442Spau.cabre@metempsy.com const uint16_t loopNumIterMask; 21513493Spau.cabre@metempsy.com const int loopSetMask; 21611784Sarthur.perais@inria.fr 21711784Sarthur.perais@inria.fr LoopEntry *ltable; 21811784Sarthur.perais@inria.fr 21911784Sarthur.perais@inria.fr int8_t loopUseCounter; 22013444Spau.cabre@metempsy.com unsigned withLoopBits; 22113455Spau.cabre@metempsy.com 22213493Spau.cabre@metempsy.com const bool useDirectionBit; 22313493Spau.cabre@metempsy.com const bool useSpeculation; 22413493Spau.cabre@metempsy.com const bool useHashing; 22513493Spau.cabre@metempsy.com 22613455Spau.cabre@metempsy.com // stats 22713455Spau.cabre@metempsy.com Stats::Scalar loopPredictorCorrect; 22813455Spau.cabre@metempsy.com Stats::Scalar loopPredictorWrong; 22911784Sarthur.perais@inria.fr}; 23011784Sarthur.perais@inria.fr 23111784Sarthur.perais@inria.fr#endif // __CPU_PRED_LTAGE 232