tage_base.hh revision 13685:bb3377c81303
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 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. 44 * 45 * All TAGE tables are accessed in parallel, and the one using the longest 46 * history that matches provides the prediction (some exceptions apply). 47 * Entries are allocated in components using a longer history than the 48 * one that predicted when the prediction is incorrect. 49 */ 50 51#ifndef __CPU_PRED_TAGE_BASE 52#define __CPU_PRED_TAGE_BASE 53 54#include <vector> 55 56#include "base/statistics.hh" 57#include "cpu/static_inst.hh" 58#include "params/TAGEBase.hh" 59#include "sim/sim_object.hh" 60 61class TAGEBase : public SimObject 62{ 63 public: 64 TAGEBase(const TAGEBaseParams *p); 65 void regStats() override; 66 void init() override; 67 68 protected: 69 // Prediction Structures 70 71 // Tage Entry 72 struct TageEntry 73 { 74 int8_t ctr; 75 uint16_t tag; 76 uint8_t u; 77 TageEntry() : ctr(0), tag(0), u(0) { } 78 }; 79 80 // Folded History Table - compressed history 81 // to mix with instruction PC to index partially 82 // tagged tables. 83 struct FoldedHistory 84 { 85 unsigned comp; 86 int compLength; 87 int origLength; 88 int outpoint; 89 int bufferSize; 90 91 FoldedHistory() 92 { 93 comp = 0; 94 } 95 96 void init(int original_length, int compressed_length) 97 { 98 origLength = original_length; 99 compLength = compressed_length; 100 outpoint = original_length % compressed_length; 101 } 102 103 void update(uint8_t * h) 104 { 105 comp = (comp << 1) | h[0]; 106 comp ^= h[origLength] << outpoint; 107 comp ^= (comp >> compLength); 108 comp &= (ULL(1) << compLength) - 1; 109 } 110 }; 111 112 public: 113 114 // provider type 115 enum { 116 BIMODAL_ONLY = 0, 117 TAGE_LONGEST_MATCH, 118 BIMODAL_ALT_MATCH, 119 TAGE_ALT_MATCH, 120 LAST_TAGE_PROVIDER_TYPE = TAGE_ALT_MATCH 121 }; 122 123 // Primary branch history entry 124 struct BranchInfo 125 { 126 int pathHist; 127 int ptGhist; 128 int hitBank; 129 int hitBankIndex; 130 int altBank; 131 int altBankIndex; 132 int bimodalIndex; 133 134 bool tagePred; 135 bool altTaken; 136 bool condBranch; 137 bool longestMatchPred; 138 bool pseudoNewAlloc; 139 Addr branchPC; 140 141 // Pointer to dynamically allocated storage 142 // to save table indices and folded histories. 143 // To do one call to new instead of five. 144 int *storage; 145 146 // Pointers to actual saved array within the dynamically 147 // allocated storage. 148 int *tableIndices; 149 int *tableTags; 150 int *ci; 151 int *ct0; 152 int *ct1; 153 154 // for stats purposes 155 unsigned provider; 156 157 BranchInfo(const TAGEBase &tage) 158 : pathHist(0), ptGhist(0), 159 hitBank(0), hitBankIndex(0), 160 altBank(0), altBankIndex(0), 161 bimodalIndex(0), 162 tagePred(false), altTaken(false), 163 condBranch(false), longestMatchPred(false), 164 pseudoNewAlloc(false), branchPC(0), 165 provider(-1) 166 { 167 int sz = tage.nHistoryTables + 1; 168 storage = new int [sz * 5]; 169 tableIndices = storage; 170 tableTags = storage + sz; 171 ci = tableTags + sz; 172 ct0 = ci + sz; 173 ct1 = ct0 + sz; 174 } 175 176 virtual ~BranchInfo() 177 { 178 delete[] storage; 179 } 180 }; 181 182 virtual BranchInfo *makeBranchInfo(); 183 184 /** 185 * Computes the index used to access the 186 * bimodal table. 187 * @param pc_in The unshifted branch PC. 188 */ 189 virtual int bindex(Addr pc_in) const; 190 191 /** 192 * Computes the index used to access a 193 * partially tagged table. 194 * @param tid The thread ID used to select the 195 * global histories to use. 196 * @param pc The unshifted branch PC. 197 * @param bank The partially tagged table to access. 198 */ 199 virtual int gindex(ThreadID tid, Addr pc, int bank) const; 200 201 /** 202 * Utility function to shuffle the path history 203 * depending on which tagged table we are accessing. 204 * @param phist The path history. 205 * @param size Number of path history bits to use. 206 * @param bank The partially tagged table to access. 207 */ 208 virtual int F(int phist, int size, int bank) const; 209 210 /** 211 * Computes the partial tag of a tagged table. 212 * @param tid the thread ID used to select the 213 * global histories to use. 214 * @param pc The unshifted branch PC. 215 * @param bank The partially tagged table to access. 216 */ 217 virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const; 218 219 /** 220 * Updates a direction counter based on the actual 221 * branch outcome. 222 * @param ctr Reference to counter to update. 223 * @param taken Actual branch outcome. 224 * @param nbits Counter width. 225 */ 226 template<typename T> 227 static void ctrUpdate(T & ctr, bool taken, int nbits); 228 229 /** 230 * Updates an unsigned counter based on up/down parameter 231 * @param ctr Reference to counter to update. 232 * @param up Boolean indicating if the counter is incremented/decremented 233 * If true it is incremented, if false it is decremented 234 * @param nbits Counter width. 235 */ 236 static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits); 237 238 /** 239 * Get a branch prediction from the bimodal 240 * predictor. 241 * @param pc The unshifted branch PC. 242 * @param bi Pointer to information on the 243 * prediction. 244 */ 245 virtual bool getBimodePred(Addr pc, BranchInfo* bi) const; 246 247 /** 248 * Updates the bimodal predictor. 249 * @param pc The unshifted branch PC. 250 * @param taken The actual branch outcome. 251 * @param bi Pointer to information on the prediction 252 * recorded at prediction time. 253 */ 254 void baseUpdate(Addr pc, bool taken, BranchInfo* bi); 255 256 /** 257 * (Speculatively) updates the global branch history. 258 * @param h Reference to pointer to global branch history. 259 * @param dir (Predicted) outcome to update the histories 260 * with. 261 * @param tab 262 * @param PT Reference to path history. 263 */ 264 void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT); 265 266 /** 267 * Update TAGE. Called at execute to repair histories on a misprediction 268 * and at commit to update the tables. 269 * @param tid The thread ID to select the global 270 * histories to use. 271 * @param branch_pc The unshifted branch PC. 272 * @param taken Actual branch outcome. 273 * @param bi Pointer to information on the prediction 274 * recorded at prediction time. 275 */ 276 void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi); 277 278 /** 279 * (Speculatively) updates global histories (path and direction). 280 * Also recomputes compressed (folded) histories based on the 281 * branch direction. 282 * @param tid The thread ID to select the histories 283 * to update. 284 * @param branch_pc The unshifted branch PC. 285 * @param taken (Predicted) branch direction. 286 * @param b Wrapping pointer to BranchInfo (to allow 287 * storing derived class prediction information in the 288 * base class). 289 */ 290 virtual void updateHistories( 291 ThreadID tid, Addr branch_pc, bool taken, BranchInfo* b, 292 bool speculative, 293 const StaticInstPtr & inst = StaticInst::nullStaticInstPtr, 294 Addr target = MaxAddr); 295 296 /** 297 * Restores speculatively updated path and direction histories. 298 * Also recomputes compressed (folded) histories based on the 299 * correct branch outcome. 300 * This version of squash() is called once on a branch misprediction. 301 * @param tid The Thread ID to select the histories to rollback. 302 * @param taken The correct branch outcome. 303 * @param bp_history Wrapping pointer to BranchInfo (to allow 304 * storing derived class prediction information in the 305 * base class). 306 * @param target The correct branch target 307 * @post bp_history points to valid memory. 308 */ 309 virtual void squash( 310 ThreadID tid, bool taken, BranchInfo *bi, Addr target); 311 312 /** 313 * Update TAGE for conditional branches. 314 * @param branch_pc The unshifted branch PC. 315 * @param taken Actual branch outcome. 316 * @param bi Pointer to information on the prediction 317 * recorded at prediction time. 318 * @nrand Random int number from 0 to 3 319 * @param corrTarget The correct branch target 320 * @param pred Final prediction for this branch 321 */ 322 virtual void condBranchUpdate( 323 ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi, 324 int nrand, Addr corrTarget, bool pred); 325 326 /** 327 * TAGE prediction called from TAGE::predict 328 * @param tid The thread ID to select the global 329 * histories to use. 330 * @param branch_pc The unshifted branch PC. 331 * @param cond_branch True if the branch is conditional. 332 * @param bi Pointer to the BranchInfo 333 */ 334 bool tagePredict( 335 ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi); 336 337 /** 338 * Update the stats 339 * @param taken Actual branch outcome 340 * @param bi Pointer to information on the prediction 341 * recorded at prediction time. 342 */ 343 virtual void updateStats(bool taken, BranchInfo* bi); 344 345 /** 346 * Instantiates the TAGE table entries 347 */ 348 virtual void buildTageTables(); 349 350 /** 351 * Calculates the history lengths 352 * and some other paramters in derived classes 353 */ 354 virtual void calculateParameters(); 355 356 /** 357 * On a prediction, calculates the TAGE indices and tags for 358 * all the different history lengths 359 */ 360 virtual void calculateIndicesAndTags( 361 ThreadID tid, Addr branch_pc, BranchInfo* bi); 362 363 /** 364 * Calculation of the index for useAltPredForNewlyAllocated 365 * On this base TAGE implementation it is always 0 366 */ 367 virtual unsigned getUseAltIdx(BranchInfo* bi); 368 369 /** 370 * Extra calculation to tell whether TAGE allocaitons may happen or not 371 * on an update 372 * For this base TAGE implementation it does nothing 373 */ 374 virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken); 375 376 /** 377 * Handles Allocation and U bits reset on an update 378 */ 379 virtual void handleAllocAndUReset( 380 bool alloc, bool taken, BranchInfo* bi, int nrand); 381 382 /** 383 * Handles the U bits reset 384 */ 385 virtual void handleUReset(); 386 387 /** 388 * Handles the update of the TAGE entries 389 */ 390 virtual void handleTAGEUpdate( 391 Addr branch_pc, bool taken, BranchInfo* bi); 392 393 /** 394 * Algorithm for resetting a single U counter 395 */ 396 virtual void resetUctr(uint8_t & u); 397 398 /** 399 * Extra steps for calculating altTaken 400 * For this base TAGE class it does nothing 401 */ 402 virtual void extraAltCalc(BranchInfo* bi); 403 404 void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi); 405 unsigned getGHR(ThreadID tid, BranchInfo *bi) const; 406 int8_t getCtr(int hitBank, int hitBankIndex) const; 407 unsigned getTageCtrBits() const; 408 int getPathHist(ThreadID tid) const; 409 bool isSpeculativeUpdateEnabled() const; 410 411 protected: 412 const unsigned logRatioBiModalHystEntries; 413 const unsigned nHistoryTables; 414 const unsigned tagTableCounterBits; 415 const unsigned tagTableUBits; 416 const unsigned histBufferSize; 417 const unsigned minHist; 418 const unsigned maxHist; 419 const unsigned pathHistBits; 420 421 std::vector<unsigned> tagTableTagWidths; 422 std::vector<int> logTagTableSizes; 423 424 std::vector<bool> btablePrediction; 425 std::vector<bool> btableHysteresis; 426 TageEntry **gtable; 427 428 // Keep per-thread histories to 429 // support SMT. 430 struct ThreadHistory { 431 // Speculative path history 432 // (LSB of branch address) 433 int pathHist; 434 435 // Speculative branch direction 436 // history (circular buffer) 437 // @TODO Convert to std::vector<bool> 438 uint8_t *globalHistory; 439 440 // Pointer to most recent branch outcome 441 uint8_t* gHist; 442 443 // Index to most recent branch outcome 444 int ptGhist; 445 446 // Speculative folded histories. 447 FoldedHistory *computeIndices; 448 FoldedHistory *computeTags[2]; 449 }; 450 451 std::vector<ThreadHistory> threadHistory; 452 453 /** 454 * Initialization of the folded histories 455 */ 456 virtual void initFoldedHistories(ThreadHistory & history); 457 458 int *histLengths; 459 int *tableIndices; 460 int *tableTags; 461 462 std::vector<int8_t> useAltPredForNewlyAllocated; 463 int64_t tCounter; 464 uint64_t logUResetPeriod; 465 unsigned numUseAltOnNa; 466 unsigned useAltOnNaBits; 467 unsigned maxNumAlloc; 468 469 // Tells which tables are active 470 // (for the base TAGE implementation all are active) 471 // Some other classes use this for handling associativity 472 std::vector<bool> noSkip; 473 474 const bool speculativeHistUpdate; 475 476 const unsigned instShiftAmt; 477 478 // stats 479 Stats::Scalar tageLongestMatchProviderCorrect; 480 Stats::Scalar tageAltMatchProviderCorrect; 481 Stats::Scalar bimodalAltMatchProviderCorrect; 482 Stats::Scalar tageBimodalProviderCorrect; 483 Stats::Scalar tageLongestMatchProviderWrong; 484 Stats::Scalar tageAltMatchProviderWrong; 485 Stats::Scalar bimodalAltMatchProviderWrong; 486 Stats::Scalar tageBimodalProviderWrong; 487 Stats::Scalar tageAltMatchProviderWouldHaveHit; 488 Stats::Scalar tageLongestMatchProviderWouldHaveHit; 489 490 Stats::Vector tageLongestMatchProvider; 491 Stats::Vector tageAltMatchProvider; 492}; 493 494#endif // __CPU_PRED_TAGE_BASE 495