tage_base.hh revision 13626:d6a6358aa6db
112837Sgabeblack@google.com/* 212837Sgabeblack@google.com * Copyright (c) 2014 The University of Wisconsin 312837Sgabeblack@google.com * 412837Sgabeblack@google.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 512837Sgabeblack@google.com * Informatique et en Automatique / French National Research Institute 612837Sgabeblack@google.com * for Computer Science and Applied Mathematics) 712837Sgabeblack@google.com * 812837Sgabeblack@google.com * All rights reserved. 912837Sgabeblack@google.com * 1012837Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 1112837Sgabeblack@google.com * modification, are permitted provided that the following conditions are 1212837Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 1312837Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 1412837Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1512837Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1612837Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1712837Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1812837Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1912837Sgabeblack@google.com * this software without specific prior written permission. 2012837Sgabeblack@google.com * 2112837Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2212837Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2312837Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2412837Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2512837Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2612837Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2712837Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2812837Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2912837Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3012837Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3113059Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3213203Sgabeblack@google.com * 3312837Sgabeblack@google.com * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais, 3413203Sgabeblack@google.com * from André Seznec's code. 3512837Sgabeblack@google.com */ 3612837Sgabeblack@google.com 3712837Sgabeblack@google.com/* @file 3812837Sgabeblack@google.com * Implementation of a TAGE branch predictor. TAGE is a global-history based 3913203Sgabeblack@google.com * branch predictor. It features a PC-indexed bimodal predictor and N 4013203Sgabeblack@google.com * partially tagged tables, indexed with a hash of the PC and the global 4113203Sgabeblack@google.com * branch history. The different lengths of global branch history used to 4213203Sgabeblack@google.com * index the partially tagged tables grow geometrically. A small path history 4313203Sgabeblack@google.com * is also used in the hash. 4413203Sgabeblack@google.com * 4513203Sgabeblack@google.com * All TAGE tables are accessed in parallel, and the one using the longest 4613203Sgabeblack@google.com * history that matches provides the prediction (some exceptions apply). 4713203Sgabeblack@google.com * Entries are allocated in components using a longer history than the 4813203Sgabeblack@google.com * one that predicted when the prediction is incorrect. 4913203Sgabeblack@google.com */ 5013203Sgabeblack@google.com 5113203Sgabeblack@google.com#ifndef __CPU_PRED_TAGE_BASE 5213203Sgabeblack@google.com#define __CPU_PRED_TAGE_BASE 5313203Sgabeblack@google.com 5413203Sgabeblack@google.com#include <vector> 5513203Sgabeblack@google.com 5613203Sgabeblack@google.com#include "base/statistics.hh" 5713059Sgabeblack@google.com#include "cpu/static_inst.hh" 5813059Sgabeblack@google.com#include "params/TAGEBase.hh" 5913203Sgabeblack@google.com#include "sim/sim_object.hh" 6013203Sgabeblack@google.com 6113238Sgabeblack@google.comclass TAGEBase : public SimObject 6213203Sgabeblack@google.com{ 6313203Sgabeblack@google.com public: 6413203Sgabeblack@google.com TAGEBase(const TAGEBaseParams *p); 6513238Sgabeblack@google.com void regStats() override; 6613203Sgabeblack@google.com void init() override; 6713203Sgabeblack@google.com 6813059Sgabeblack@google.com protected: 6913203Sgabeblack@google.com // Prediction Structures 7013203Sgabeblack@google.com 7113238Sgabeblack@google.com // Tage Entry 7213203Sgabeblack@google.com struct TageEntry 7313203Sgabeblack@google.com { 7413203Sgabeblack@google.com int8_t ctr; 7513059Sgabeblack@google.com uint16_t tag; 7613048Sgabeblack@google.com uint8_t u; 7712837Sgabeblack@google.com TageEntry() : ctr(0), tag(0), u(0) { } 7812837Sgabeblack@google.com }; 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 */ 321 virtual void condBranchUpdate( 322 ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi, 323 int nrand, Addr corrTarget); 324 325 /** 326 * TAGE prediction called from TAGE::predict 327 * @param tid The thread ID to select the global 328 * histories to use. 329 * @param branch_pc The unshifted branch PC. 330 * @param cond_branch True if the branch is conditional. 331 * @param bi Pointer to the BranchInfo 332 */ 333 bool tagePredict( 334 ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi); 335 336 /** 337 * Update the stats 338 * @param taken Actual branch outcome 339 * @param bi Pointer to information on the prediction 340 * recorded at prediction time. 341 */ 342 virtual void updateStats(bool taken, BranchInfo* bi); 343 344 /** 345 * Instantiates the TAGE table entries 346 */ 347 virtual void buildTageTables(); 348 349 /** 350 * Calculates the history lengths 351 * and some other paramters in derived classes 352 */ 353 virtual void calculateParameters(); 354 355 /** 356 * On a prediction, calculates the TAGE indices and tags for 357 * all the different history lengths 358 */ 359 virtual void calculateIndicesAndTags( 360 ThreadID tid, Addr branch_pc, BranchInfo* bi); 361 362 /** 363 * Calculation of the index for useAltPredForNewlyAllocated 364 * On this base TAGE implementation it is always 0 365 */ 366 virtual unsigned getUseAltIdx(BranchInfo* bi); 367 368 /** 369 * Extra calculation to tell whether TAGE allocaitons may happen or not 370 * on an update 371 * For this base TAGE implementation it does nothing 372 */ 373 virtual void adjustAlloc(bool & alloc, bool taken); 374 375 /** 376 * Handles Allocation and U bits reset on an update 377 */ 378 virtual void handleAllocAndUReset( 379 bool alloc, bool taken, BranchInfo* bi, int nrand); 380 381 /** 382 * Handles the U bits reset 383 */ 384 virtual void handleUReset(); 385 386 /** 387 * Handles the update of the TAGE entries 388 */ 389 virtual void handleTAGEUpdate( 390 Addr branch_pc, bool taken, BranchInfo* bi); 391 392 /** 393 * Algorithm for resetting a single U counter 394 */ 395 virtual void resetUctr(uint8_t & u); 396 397 /** 398 * Extra steps for calculating altTaken 399 * For this base TAGE class it does nothing 400 */ 401 virtual void extraAltCalc(BranchInfo* bi); 402 403 /** 404 * Algorithm for returning a random number 405 * This base TAGE class just uses random_mt, but some derived classes 406 * may want to use a more realistic implementation or force some values 407 */ 408 static int getRandom(); 409 410 void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi); 411 unsigned getGHR(ThreadID tid, BranchInfo *bi) const; 412 int8_t getCtr(int hitBank, int hitBankIndex) const; 413 unsigned getTageCtrBits() const; 414 int getPathHist(ThreadID tid) const; 415 bool isSpeculativeUpdateEnabled() const; 416 417 protected: 418 const unsigned logRatioBiModalHystEntries; 419 const unsigned nHistoryTables; 420 const unsigned tagTableCounterBits; 421 const unsigned tagTableUBits; 422 const unsigned histBufferSize; 423 const unsigned minHist; 424 const unsigned maxHist; 425 const unsigned pathHistBits; 426 427 std::vector<unsigned> tagTableTagWidths; 428 std::vector<int> logTagTableSizes; 429 430 std::vector<bool> btablePrediction; 431 std::vector<bool> btableHysteresis; 432 TageEntry **gtable; 433 434 // Keep per-thread histories to 435 // support SMT. 436 struct ThreadHistory { 437 // Speculative path history 438 // (LSB of branch address) 439 int pathHist; 440 441 // Speculative branch direction 442 // history (circular buffer) 443 // @TODO Convert to std::vector<bool> 444 uint8_t *globalHistory; 445 446 // Pointer to most recent branch outcome 447 uint8_t* gHist; 448 449 // Index to most recent branch outcome 450 int ptGhist; 451 452 // Speculative folded histories. 453 FoldedHistory *computeIndices; 454 FoldedHistory *computeTags[2]; 455 }; 456 457 std::vector<ThreadHistory> threadHistory; 458 459 /** 460 * Initialization of the folded histories 461 */ 462 virtual void initFoldedHistories(ThreadHistory & history); 463 464 int *histLengths; 465 int *tableIndices; 466 int *tableTags; 467 468 std::vector<int8_t> useAltPredForNewlyAllocated; 469 int64_t tCounter; 470 uint64_t logUResetPeriod; 471 unsigned numUseAltOnNa; 472 unsigned useAltOnNaBits; 473 unsigned maxNumAlloc; 474 475 // Tells which tables are active 476 // (for the base TAGE implementation all are active) 477 // Some other classes use this for handling associativity 478 std::vector<bool> noSkip; 479 480 const bool speculativeHistUpdate; 481 482 const unsigned instShiftAmt; 483 484 // stats 485 Stats::Scalar tageLongestMatchProviderCorrect; 486 Stats::Scalar tageAltMatchProviderCorrect; 487 Stats::Scalar bimodalAltMatchProviderCorrect; 488 Stats::Scalar tageBimodalProviderCorrect; 489 Stats::Scalar tageLongestMatchProviderWrong; 490 Stats::Scalar tageAltMatchProviderWrong; 491 Stats::Scalar bimodalAltMatchProviderWrong; 492 Stats::Scalar tageBimodalProviderWrong; 493 Stats::Scalar tageAltMatchProviderWouldHaveHit; 494 Stats::Scalar tageLongestMatchProviderWouldHaveHit; 495 496 Stats::Vector tageLongestMatchProvider; 497 Stats::Vector tageAltMatchProvider; 498}; 499 500#endif // __CPU_PRED_TAGE_BASE 501