ltage.hh revision 13443:a111cb197897
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#include <vector> 56 57#include "base/types.hh" 58#include "cpu/pred/bpred_unit.hh" 59#include "params/LTAGE.hh" 60 61class LTAGE: public BPredUnit 62{ 63 public: 64 LTAGE(const LTAGEParams *params); 65 66 // Base class methods. 67 void uncondBranch(ThreadID tid, Addr br_pc, void* &bp_history) override; 68 bool lookup(ThreadID tid, Addr branch_addr, void* &bp_history) override; 69 void btbUpdate(ThreadID tid, Addr branch_addr, void* &bp_history) override; 70 void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 71 bool squashed) override; 72 void squash(ThreadID tid, void *bp_history) override; 73 unsigned getGHR(ThreadID tid, void *bp_history) const 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; 83 uint8_t confidence; 84 uint16_t tag; 85 uint8_t age; 86 bool dir; 87 88 LoopEntry() : numIter(0), currentIter(0), currentIterSpec(0), 89 confidence(0), tag(0), age(0), dir(0) { } 90 }; 91 92 // Tage Entry 93 struct TageEntry 94 { 95 int8_t ctr; 96 uint16_t tag; 97 uint8_t u; 98 TageEntry() : ctr(0), tag(0), u(0) { } 99 }; 100 101 // Folded History Table - compressed history 102 // to mix with instruction PC to index partially 103 // tagged tables. 104 struct FoldedHistory 105 { 106 unsigned comp; 107 int compLength; 108 int origLength; 109 int outpoint; 110 111 void init(int original_length, int compressed_length) 112 { 113 comp = 0; 114 origLength = original_length; 115 compLength = compressed_length; 116 outpoint = original_length % compressed_length; 117 } 118 119 void update(uint8_t * h) 120 { 121 comp = (comp << 1) | h[0]; 122 comp ^= h[origLength] << outpoint; 123 comp ^= (comp >> compLength); 124 comp &= (ULL(1) << compLength) - 1; 125 } 126 }; 127 128 // Primary branch history entry 129 struct BranchInfo 130 { 131 int pathHist; 132 int ptGhist; 133 int hitBank; 134 int hitBankIndex; 135 int altBank; 136 int altBankIndex; 137 int bimodalIndex; 138 uint16_t loopTag; 139 uint16_t currentIter; 140 141 bool tagePred; 142 bool altTaken; 143 bool loopPred; 144 bool loopPredValid; 145 int loopIndex; 146 int loopHit; 147 bool condBranch; 148 bool longestMatchPred; 149 bool pseudoNewAlloc; 150 Addr branchPC; 151 152 // Pointer to dynamically allocated storage 153 // to save table indices and folded histories. 154 // To do one call to new instead of five. 155 int *storage; 156 157 // Pointers to actual saved array within the dynamically 158 // allocated storage. 159 int *tableIndices; 160 int *tableTags; 161 int *ci; 162 int *ct0; 163 int *ct1; 164 165 BranchInfo(int sz) 166 : pathHist(0), ptGhist(0), 167 hitBank(0), hitBankIndex(0), 168 altBank(0), altBankIndex(0), 169 bimodalIndex(0), loopTag(0), currentIter(0), 170 tagePred(false), altTaken(false), loopPred(false), 171 loopPredValid(false), loopIndex(0), loopHit(0), 172 condBranch(false), longestMatchPred(false), 173 pseudoNewAlloc(false), branchPC(0) 174 { 175 storage = new int [sz * 5]; 176 tableIndices = storage; 177 tableTags = storage + sz; 178 ci = tableTags + sz; 179 ct0 = ci + sz; 180 ct1 = ct0 + sz; 181 } 182 183 ~BranchInfo() 184 { 185 delete[] storage; 186 } 187 }; 188 189 /** 190 * Computes the index used to access the 191 * bimodal table. 192 * @param pc_in The unshifted branch PC. 193 */ 194 int bindex(Addr pc_in) const; 195 196 /** 197 * Computes the index used to access the 198 * loop predictor. 199 * @param pc_in The unshifted branch PC. 200 */ 201 int lindex(Addr pc_in) const; 202 203 /** 204 * Computes the index used to access a 205 * partially tagged table. 206 * @param tid The thread ID used to select the 207 * global histories to use. 208 * @param pc The unshifted branch PC. 209 * @param bank The partially tagged table to access. 210 */ 211 inline int gindex(ThreadID tid, Addr pc, int bank) const; 212 213 /** 214 * Utility function to shuffle the path history 215 * depending on which tagged table we are accessing. 216 * @param phist The path history. 217 * @param size Number of path history bits to use. 218 * @param bank The partially tagged table to access. 219 */ 220 int F(int phist, int size, int bank) const; 221 222 /** 223 * Computes the partial tag of a tagged table. 224 * @param tid the thread ID used to select the 225 * global histories to use. 226 * @param pc The unshifted branch PC. 227 * @param bank The partially tagged table to access. 228 */ 229 inline uint16_t gtag(ThreadID tid, Addr pc, int bank) const; 230 231 /** 232 * Updates a direction counter based on the actual 233 * branch outcome. 234 * @param ctr Reference to counter to update. 235 * @param taken Actual branch outcome. 236 * @param nbits Counter width. 237 */ 238 void ctrUpdate(int8_t & ctr, bool taken, int nbits); 239 240 /** 241 * Updates an unsigned counter based on up/down parameter 242 * @param ctr Reference to counter to update. 243 * @param up Boolean indicating if the counter is incremented/decremented 244 * If true it is incremented, if false it is decremented 245 * @param nbits Counter width. 246 */ 247 void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits); 248 249 /** 250 * Get a branch prediction from the bimodal 251 * predictor. 252 * @param pc The unshifted branch PC. 253 * @param bi Pointer to information on the 254 * prediction. 255 */ 256 bool getBimodePred(Addr pc, BranchInfo* bi) const; 257 258 /** 259 * Updates the bimodal predictor. 260 * @param pc The unshifted branch PC. 261 * @param taken The actual branch outcome. 262 * @param bi Pointer to information on the prediction 263 * recorded at prediction time. 264 */ 265 void baseUpdate(Addr pc, bool taken, BranchInfo* bi); 266 267 /** 268 * Get a branch prediction from the loop 269 * predictor. 270 * @param pc The unshifted branch PC. 271 * @param bi Pointer to information on the 272 * prediction. 273 */ 274 bool getLoop(Addr pc, BranchInfo* bi) const; 275 276 /** 277 * Updates the loop predictor. 278 * @param pc The unshifted branch PC. 279 * @param taken The actual branch outcome. 280 * @param bi Pointer to information on the 281 * prediction recorded at prediction time. 282 */ 283 void loopUpdate(Addr pc, bool Taken, BranchInfo* bi); 284 285 /** 286 * (Speculatively) updates the global branch history. 287 * @param h Reference to pointer to global branch history. 288 * @param dir (Predicted) outcome to update the histories 289 * with. 290 * @param tab 291 * @param PT Reference to path history. 292 */ 293 void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT); 294 295 /** 296 * Get a branch prediction from L-TAGE. *NOT* an override of 297 * BpredUnit::predict(). 298 * @param tid The thread ID to select the global 299 * histories to use. 300 * @param branch_pc The unshifted branch PC. 301 * @param cond_branch True if the branch is conditional. 302 * @param b Reference to wrapping pointer to allow storing 303 * derived class prediction information in the base class. 304 */ 305 bool predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b); 306 307 /** 308 * Update L-TAGE. Called at execute to repair histories on a misprediction 309 * and at commit to update the tables. 310 * @param tid The thread ID to select the global 311 * histories to use. 312 * @param branch_pc The unshifted branch PC. 313 * @param taken Actual branch outcome. 314 * @param bi Pointer to information on the prediction 315 * recorded at prediction time. 316 */ 317 void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi); 318 319 /** 320 * (Speculatively) updates global histories (path and direction). 321 * Also recomputes compressed (folded) histories based on the 322 * branch direction. 323 * @param tid The thread ID to select the histories 324 * to update. 325 * @param branch_pc The unshifted branch PC. 326 * @param taken (Predicted) branch direction. 327 * @param b Wrapping pointer to BranchInfo (to allow 328 * storing derived class prediction information in the 329 * base class). 330 */ 331 void updateHistories(ThreadID tid, Addr branch_pc, bool taken, void* b); 332 333 /** 334 * Restores speculatively updated path and direction histories. 335 * Also recomputes compressed (folded) histories based on the 336 * correct branch outcome. 337 * This version of squash() is called once on a branch misprediction. 338 * @param tid The Thread ID to select the histories to rollback. 339 * @param taken The correct branch outcome. 340 * @param bp_history Wrapping pointer to BranchInfo (to allow 341 * storing derived class prediction information in the 342 * base class). 343 * @post bp_history points to valid memory. 344 */ 345 void squash(ThreadID tid, bool taken, void *bp_history); 346 347 /** 348 * Speculatively updates the loop predictor 349 * iteration count. 350 * @param pc The unshifted branch PC. 351 * @param taken The predicted branch outcome. 352 * @param bi Pointer to information on the prediction 353 * recorded at prediction time. 354 */ 355 void specLoopUpdate(Addr pc, bool taken, BranchInfo* bi); 356 357 const unsigned logSizeBiMP; 358 const unsigned logRatioBiModalHystEntries; 359 const unsigned logSizeTagTables; 360 const unsigned logSizeLoopPred; 361 const unsigned nHistoryTables; 362 const unsigned tagTableCounterBits; 363 const unsigned tagTableUBits; 364 const unsigned histBufferSize; 365 const unsigned minHist; 366 const unsigned maxHist; 367 const unsigned minTagWidth; 368 const unsigned loopTableAgeBits; 369 const unsigned loopTableConfidenceBits; 370 const unsigned loopTableTagBits; 371 const unsigned loopTableIterBits; 372 373 const uint8_t confidenceThreshold; 374 const uint16_t loopTagMask; 375 const uint16_t loopNumIterMask; 376 377 std::vector<bool> btablePrediction; 378 std::vector<bool> btableHysteresis; 379 TageEntry **gtable; 380 LoopEntry *ltable; 381 382 // Keep per-thread histories to 383 // support SMT. 384 struct ThreadHistory { 385 // Speculative path history 386 // (LSB of branch address) 387 int pathHist; 388 389 // Speculative branch direction 390 // history (circular buffer) 391 // @TODO Convert to std::vector<bool> 392 uint8_t *globalHistory; 393 394 // Pointer to most recent branch outcome 395 uint8_t* gHist; 396 397 // Index to most recent branch outcome 398 int ptGhist; 399 400 // Speculative folded histories. 401 FoldedHistory *computeIndices; 402 FoldedHistory *computeTags[2]; 403 }; 404 405 std::vector<ThreadHistory> threadHistory; 406 407 int tagWidths[15]; 408 int tagTableSizes[15]; 409 int *histLengths; 410 int *tableIndices; 411 int *tableTags; 412 413 int8_t loopUseCounter; 414 int8_t useAltPredForNewlyAllocated; 415 int tCounter; 416 int logTick; 417}; 418 419#endif // __CPU_PRED_LTAGE 420