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