ltage.hh revision 13626
1/* 2 * Copyright (c) 2014 The University of Wisconsin 3 * 4 * Copyright (c) 2006 INRIA (Institut National de Recherche en 5 * Informatique et en Automatique / French National Research Institute 6 * for Computer Science and Applied Mathematics) 7 * 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions are 12 * met: redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer; 14 * redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution; 17 * neither the name of the copyright holders nor the names of its 18 * contributors may be used to endorse or promote products derived from 19 * this software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 * 33 * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 34 * from André Seznec's code. 35 */ 36 37/* @file 38 * Implementation of a L-TAGE branch predictor. TAGE is a global-history based 39 * branch predictor. It features a PC-indexed bimodal predictor and N 40 * partially tagged tables, indexed with a hash of the PC and the global 41 * branch history. The different lengths of global branch history used to 42 * index the partially tagged tables grow geometrically. A small path history 43 * is also used in the hash. L-TAGE also features a loop predictor that records 44 * iteration count of loops and predicts accordingly. 45 * 46 * All TAGE tables are accessed in parallel, and the one using the longest 47 * history that matches provides the prediction (some exceptions apply). 48 * Entries are allocated in components using a longer history than the 49 * one that predicted when the prediction is incorrect. 50 */ 51 52#ifndef __CPU_PRED_LTAGE 53#define __CPU_PRED_LTAGE 54 55 56#include <vector> 57 58#include "base/types.hh" 59#include "cpu/pred/tage.hh" 60#include "params/LTAGE.hh" 61 62class LTAGE: public TAGE 63{ 64 public: 65 LTAGE(const LTAGEParams *params); 66 67 // Base class methods. 68 void squash(ThreadID tid, void *bp_history) override; 69 void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 70 bool squashed, const StaticInstPtr & inst, 71 Addr corrTarget) override; 72 73 void regStats() override; 74 75 private: 76 // Prediction Structures 77 // Loop Predictor Entry 78 struct LoopEntry 79 { 80 uint16_t numIter; 81 uint16_t currentIter; 82 uint16_t currentIterSpec; // only for useSpeculation 83 uint8_t confidence; 84 uint16_t tag; 85 uint8_t age; 86 bool dir; // only for useDirectionBit 87 88 LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0), 89 confidence(0), tag(0), age(0), dir(0) { } 90 }; 91 92 // more provider types 93 enum { 94 LOOP = TAGEBase::LAST_TAGE_PROVIDER_TYPE + 1 95 }; 96 97 // Primary branch history entry 98 struct LTageBranchInfo : public TageBranchInfo 99 { 100 uint16_t loopTag; 101 uint16_t currentIter; 102 103 bool loopPred; 104 bool loopPredValid; 105 int loopIndex; 106 int loopLowPcBits; // only for useHashing 107 int loopHit; 108 109 LTageBranchInfo(TAGEBase &tage) 110 : TageBranchInfo(tage), 111 loopTag(0), currentIter(0), 112 loopPred(false), 113 loopPredValid(false), loopIndex(0), loopLowPcBits(0), loopHit(0) 114 {} 115 116 virtual ~LTageBranchInfo() 117 {} 118 }; 119 120 /** 121 * Computes the index used to access the 122 * loop predictor. 123 * @param pc_in The unshifted branch PC. 124 */ 125 int lindex(Addr pc_in) const; 126 127 /** 128 * Computes the index used to access the 129 * ltable structures. 130 * It may take hashing into account 131 * @param index Result of lindex function 132 * @param lowPcBits PC bits masked with set size 133 * @param way Way to be used 134 */ 135 int finallindex(int lindex, int lowPcBits, int way) const; 136 137 /** 138 * Get a branch prediction from the loop 139 * predictor. 140 * @param pc The unshifted branch PC. 141 * @param bi Pointer to information on the 142 * prediction. 143 * @param speculative Use speculative number of iterations 144 */ 145 bool getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const; 146 147 /** 148 * Updates the loop predictor. 149 * @param pc The unshifted branch PC. 150 * @param taken The actual branch outcome. 151 * @param bi Pointer to information on the 152 * prediction recorded at prediction time. 153 */ 154 void loopUpdate(Addr pc, bool Taken, LTageBranchInfo* bi); 155 156 /** 157 * Speculatively updates the loop predictor 158 * iteration count (only for useSpeculation). 159 * @param taken The predicted branch outcome. 160 * @param bi Pointer to information on the prediction 161 * recorded at prediction time. 162 */ 163 void specLoopUpdate(bool taken, LTageBranchInfo* bi); 164 165 /** 166 * Get a branch prediction from LTAGE. *NOT* an override of 167 * BpredUnit::predict(). 168 * @param tid The thread ID to select the global 169 * histories to use. 170 * @param branch_pc The unshifted branch PC. 171 * @param cond_branch True if the branch is conditional. 172 * @param b Reference to wrapping pointer to allow storing 173 * derived class prediction information in the base class. 174 */ 175 bool predict( 176 ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override; 177 178 /** 179 * Restores speculatively updated path and direction histories. 180 * Also recomputes compressed (folded) histories based on the 181 * correct branch outcome. 182 * @param bi Branch information. 183 */ 184 void squashLoop(LTageBranchInfo * bi); 185 186 const unsigned logSizeLoopPred; 187 const unsigned loopTableAgeBits; 188 const unsigned loopTableConfidenceBits; 189 const unsigned loopTableTagBits; 190 const unsigned loopTableIterBits; 191 const unsigned logLoopTableAssoc; 192 const uint8_t confidenceThreshold; 193 const uint16_t loopTagMask; 194 const uint16_t loopNumIterMask; 195 const int loopSetMask; 196 197 LoopEntry *ltable; 198 199 int8_t loopUseCounter; 200 unsigned withLoopBits; 201 202 const bool useDirectionBit; 203 const bool useSpeculation; 204 const bool useHashing; 205 206 // stats 207 Stats::Scalar loopPredictorCorrect; 208 Stats::Scalar loopPredictorWrong; 209}; 210 211#endif // __CPU_PRED_LTAGE 212