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;
| 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;
|
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; // only for useSpeculation 80 uint8_t confidence; 81 uint16_t tag; 82 uint8_t age; 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 {
| 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 {
|
91 LOOP = LAST_TAGE_PROVIDER_TYPE + 1
| 94 LOOP = TAGEBase::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
| 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
|
106 LTageBranchInfo(int sz) 107 : TageBranchInfo(sz),
| 109 LTageBranchInfo(TAGEBase &tage) 110 : TageBranchInfo(tage),
|
108 loopTag(0), currentIter(0), 109 loopPred(false), 110 loopPredValid(false), loopIndex(0), loopLowPcBits(0), loopHit(0) 111 {}
| 111 loopTag(0), currentIter(0), 112 loopPred(false), 113 loopPredValid(false), loopIndex(0), loopLowPcBits(0), loopHit(0) 114 {}
|
| 115 116 virtual ~LTageBranchInfo() 117 {}
|
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 */ 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 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 */ 157 void specLoopUpdate(bool taken, LTageBranchInfo* bi); 158 159 /**
| 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 /**
|
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.
| 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.
|
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.
| 182 * @param bi Branch information.
|
194 */
| 183 */
|
195 void squash( 196 ThreadID tid, bool taken, void *bp_history) override;
| 184 void squashLoop(LTageBranchInfo * bi);
|
197
| 185
|
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
| 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
|