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 70 void regStats() override; 71 72 private: 73 // Prediction Structures 74 // Loop Predictor Entry 75 struct LoopEntry 76 { 77 uint16_t numIter; 78 uint16_t currentIter;
|
79 uint16_t currentIterSpec;
|
79 uint16_t currentIterSpec; // only for useSpeculation |
80 uint8_t confidence; 81 uint16_t tag; 82 uint8_t age;
|
83 bool dir;
|
83 bool dir; // only for useDirectionBit |
84 85 LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0), 86 confidence(0), tag(0), age(0), dir(0) { } 87 }; 88 89 // more provider types 90 enum { 91 LOOP = LAST_TAGE_PROVIDER_TYPE + 1 92 }; 93 94 // Primary branch history entry 95 struct LTageBranchInfo : public TageBranchInfo 96 { 97 uint16_t loopTag; 98 uint16_t currentIter; 99 100 bool loopPred; 101 bool loopPredValid; 102 int loopIndex;
|
103 int loopLowPcBits; // only for useHashing |
104 int loopHit; 105 106 LTageBranchInfo(int sz) 107 : TageBranchInfo(sz), 108 loopTag(0), currentIter(0), 109 loopPred(false),
|
109 loopPredValid(false), loopIndex(0), loopHit(0)
|
110 loopPredValid(false), loopIndex(0), loopLowPcBits(0), loopHit(0) |
111 {} 112 }; 113 114 /** 115 * Computes the index used to access the 116 * loop predictor. 117 * @param pc_in The unshifted branch PC. 118 */ 119 int lindex(Addr pc_in) const; 120 121 /**
|
122 * Computes the index used to access the 123 * ltable structures. 124 * It may take hashing into account 125 * @param index Result of lindex function 126 * @param lowPcBits PC bits masked with set size 127 * @param way Way to be used 128 */ 129 int finallindex(int lindex, int lowPcBits, int way) const; 130 131 /** |
132 * Get a branch prediction from the loop 133 * predictor. 134 * @param pc The unshifted branch PC. 135 * @param bi Pointer to information on the 136 * prediction.
|
137 * @param speculative Use speculative number of iterations |
138 */
|
127 bool getLoop(Addr pc, LTageBranchInfo* bi) const;
|
139 bool getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const; |
140 141 /** 142 * Updates the loop predictor. 143 * @param pc The unshifted branch PC. 144 * @param taken The actual branch outcome. 145 * @param bi Pointer to information on the 146 * prediction recorded at prediction time. 147 */ 148 void loopUpdate(Addr pc, bool Taken, LTageBranchInfo* bi); 149 150 /** 151 * Speculatively updates the loop predictor
|
140 * iteration count.
141 * @param pc The unshifted branch PC.
|
152 * iteration count (only for useSpeculation). |
153 * @param taken The predicted branch outcome. 154 * @param bi Pointer to information on the prediction 155 * recorded at prediction time. 156 */
|
146 void specLoopUpdate(Addr pc, bool taken, LTageBranchInfo* bi);
|
157 void specLoopUpdate(bool taken, LTageBranchInfo* bi); |
158 159 /** 160 * Update LTAGE for conditional branches. 161 * @param branch_pc The unshifted branch PC. 162 * @param taken Actual branch outcome. 163 * @param bi Pointer to information on the prediction 164 * recorded at prediction time. 165 * @nrand Random int number from 0 to 3 166 */ 167 void condBranchUpdate( 168 Addr branch_pc, bool taken, TageBranchInfo* bi, int nrand) override; 169 170 /** 171 * Get a branch prediction from LTAGE. *NOT* an override of 172 * BpredUnit::predict(). 173 * @param tid The thread ID to select the global 174 * histories to use. 175 * @param branch_pc The unshifted branch PC. 176 * @param cond_branch True if the branch is conditional. 177 * @param b Reference to wrapping pointer to allow storing 178 * derived class prediction information in the base class. 179 */ 180 bool predict( 181 ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override; 182 183 /** 184 * Restores speculatively updated path and direction histories. 185 * Also recomputes compressed (folded) histories based on the 186 * correct branch outcome. 187 * This version of squash() is called once on a branch misprediction. 188 * @param tid The Thread ID to select the histories to rollback. 189 * @param taken The correct branch outcome. 190 * @param bp_history Wrapping pointer to TageBranchInfo (to allow 191 * storing derived class prediction information in the 192 * base class). 193 * @post bp_history points to valid memory. 194 */ 195 void squash( 196 ThreadID tid, bool taken, void *bp_history) override; 197 198 /** 199 * Update the stats 200 * @param taken Actual branch outcome 201 * @param bi Pointer to information on the prediction 202 * recorded at prediction time. 203 */ 204 void updateStats(bool taken, TageBranchInfo* bi) override; 205 206 const unsigned logSizeLoopPred; 207 const unsigned loopTableAgeBits; 208 const unsigned loopTableConfidenceBits; 209 const unsigned loopTableTagBits; 210 const unsigned loopTableIterBits; 211 const unsigned logLoopTableAssoc; 212 const uint8_t confidenceThreshold; 213 const uint16_t loopTagMask; 214 const uint16_t loopNumIterMask;
|
215 const int loopSetMask; |
216 217 LoopEntry *ltable; 218 219 int8_t loopUseCounter; 220 unsigned withLoopBits; 221
|
222 const bool useDirectionBit; 223 const bool useSpeculation; 224 const bool useHashing; 225 |
226 // stats 227 Stats::Scalar loopPredictorCorrect; 228 Stats::Scalar loopPredictorWrong; 229}; 230 231#endif // __CPU_PRED_LTAGE
|