gem5  v22.1.0.0
tage_base.hh
Go to the documentation of this file.
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 
34 /* @file
35  * Implementation of a TAGE branch predictor. TAGE is a global-history based
36  * branch predictor. It features a PC-indexed bimodal predictor and N
37  * partially tagged tables, indexed with a hash of the PC and the global
38  * branch history. The different lengths of global branch history used to
39  * index the partially tagged tables grow geometrically. A small path history
40  * is also used in the hash.
41  *
42  * All TAGE tables are accessed in parallel, and the one using the longest
43  * history that matches provides the prediction (some exceptions apply).
44  * Entries are allocated in components using a longer history than the
45  * one that predicted when the prediction is incorrect.
46  */
47 
48 #ifndef __CPU_PRED_TAGE_BASE_HH__
49 #define __CPU_PRED_TAGE_BASE_HH__
50 
51 #include <vector>
52 
53 #include "base/statistics.hh"
54 #include "cpu/null_static_inst.hh"
55 #include "cpu/static_inst.hh"
56 #include "params/TAGEBase.hh"
57 #include "sim/sim_object.hh"
58 
59 namespace gem5
60 {
61 
62 namespace branch_prediction
63 {
64 
65 class TAGEBase : public SimObject
66 {
67  public:
68  TAGEBase(const TAGEBaseParams &p);
69  void init() override;
70 
71  protected:
72  // Prediction Structures
73 
74  // Tage Entry
75  struct TageEntry
76  {
77  int8_t ctr;
78  uint16_t tag;
79  uint8_t u;
80  TageEntry() : ctr(0), tag(0), u(0) { }
81  };
82 
83  // Folded History Table - compressed history
84  // to mix with instruction PC to index partially
85  // tagged tables.
87  {
88  unsigned comp;
91  int outpoint;
93 
95  {
96  comp = 0;
97  }
98 
99  void init(int original_length, int compressed_length)
100  {
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 &= (1ULL << compLength) - 1;
112  }
113  };
114 
115  public:
116 
117  // provider type
118  enum
119  {
125  };
126 
127  // Primary branch history entry
128  struct BranchInfo
129  {
130  int pathHist;
131  int ptGhist;
132  int hitBank;
134  int altBank;
137 
138  bool tagePred;
139  bool altTaken;
144 
145  // Pointer to dynamically allocated storage
146  // to save table indices and folded histories.
147  // To do one call to new instead of five.
148  int *storage;
149 
150  // Pointers to actual saved array within the dynamically
151  // allocated storage.
153  int *tableTags;
154  int *ci;
155  int *ct0;
156  int *ct1;
157 
158  // for stats purposes
159  unsigned provider;
160 
161  BranchInfo(const TAGEBase &tage)
162  : pathHist(0), ptGhist(0),
163  hitBank(0), hitBankIndex(0),
164  altBank(0), altBankIndex(0),
165  bimodalIndex(0),
166  tagePred(false), altTaken(false),
167  condBranch(false), longestMatchPred(false),
168  pseudoNewAlloc(false), branchPC(0),
169  provider(-1)
170  {
171  int sz = tage.nHistoryTables + 1;
172  storage = new int [sz * 5];
174  tableTags = storage + sz;
175  ci = tableTags + sz;
176  ct0 = ci + sz;
177  ct1 = ct0 + sz;
178  }
179 
180  virtual ~BranchInfo()
181  {
182  delete[] storage;
183  }
184  };
185 
186  virtual BranchInfo *makeBranchInfo();
187 
193  virtual int bindex(Addr pc_in) const;
194 
203  virtual int gindex(ThreadID tid, Addr pc, int bank) const;
204 
212  virtual int F(int phist, int size, int bank) const;
213 
221  virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const;
222 
230  template<typename T>
231  static void ctrUpdate(T & ctr, bool taken, int nbits);
232 
240  static void unsignedCtrUpdate(uint8_t & ctr, bool up, unsigned nbits);
241 
249  virtual bool getBimodePred(Addr pc, BranchInfo* bi) const;
250 
258  void baseUpdate(Addr pc, bool taken, BranchInfo* bi);
259 
268  void updateGHist(uint8_t * &h, bool dir, uint8_t * tab, int &PT);
269 
280  void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi);
281 
294  virtual void updateHistories(
295  ThreadID tid, Addr branch_pc, bool taken, BranchInfo* b,
296  bool speculative,
297  const StaticInstPtr & inst = nullStaticInstPtr,
298  Addr target = MaxAddr);
299 
313  virtual void squash(
314  ThreadID tid, bool taken, BranchInfo *bi, Addr target);
315 
328  virtual void condBranchUpdate(
329  ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi,
330  int nrand, Addr corrTarget, bool pred, bool preAdjustAlloc = false);
331 
340  bool tagePredict(
341  ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi);
342 
349  virtual void updateStats(bool taken, BranchInfo* bi);
350 
354  virtual void buildTageTables();
355 
360  virtual void calculateParameters();
361 
366  virtual void calculateIndicesAndTags(
367  ThreadID tid, Addr branch_pc, BranchInfo* bi);
368 
373  virtual unsigned getUseAltIdx(BranchInfo* bi, Addr branch_pc);
374 
380  virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken);
381 
385  virtual void handleAllocAndUReset(
386  bool alloc, bool taken, BranchInfo* bi, int nrand);
387 
391  virtual void handleUReset();
392 
396  virtual void handleTAGEUpdate(
397  Addr branch_pc, bool taken, BranchInfo* bi);
398 
402  virtual void resetUctr(uint8_t & u);
403 
408  virtual void extraAltCalc(BranchInfo* bi);
409 
410  virtual bool isHighConfidence(BranchInfo* bi) const
411  {
412  return false;
413  }
414 
415  void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi);
416  unsigned getGHR(ThreadID tid, BranchInfo *bi) const;
417  int8_t getCtr(int hitBank, int hitBankIndex) const;
418  unsigned getTageCtrBits() const;
419  int getPathHist(ThreadID tid) const;
420  bool isSpeculativeUpdateEnabled() const;
421  size_t getSizeInBits() const;
422 
423  protected:
425  const unsigned nHistoryTables;
426  const unsigned tagTableCounterBits;
427  const unsigned tagTableUBits;
428  const unsigned histBufferSize;
429  const unsigned minHist;
430  const unsigned maxHist;
431  const unsigned pathHistBits;
432 
435 
439 
440  // Keep per-thread histories to
441  // support SMT.
443  {
444  // Speculative path history
445  // (LSB of branch address)
446  int pathHist;
447 
448  // Speculative branch direction
449  // history (circular buffer)
450  // @TODO Convert to std::vector<bool>
451  uint8_t *globalHistory;
452 
453  // Pointer to most recent branch outcome
454  uint8_t* gHist;
455 
456  // Index to most recent branch outcome
457  int ptGhist;
458 
459  // Speculative folded histories.
462  };
463 
465 
469  virtual void initFoldedHistories(ThreadHistory & history);
470 
473  int *tableTags;
474 
476  int64_t tCounter;
477  uint64_t logUResetPeriod;
478  const int64_t initialTCounterValue;
479  unsigned numUseAltOnNa;
480  unsigned useAltOnNaBits;
481  unsigned maxNumAlloc;
482 
483  // Tells which tables are active
484  // (for the base TAGE implementation all are active)
485  // Some other classes use this for handling associativity
487 
489 
490  const unsigned instShiftAmt;
491 
493 
495  {
497  // stats
508 
511  } stats;
512 };
513 
514 } // namespace branch_prediction
515 } // namespace gem5
516 
517 #endif // __CPU_PRED_TAGE_BASE_HH__
Abstract superclass for simulation objects.
Definition: sim_object.hh:148
TAGEBase(const TAGEBaseParams &p)
Definition: tage_base.cc:51
virtual void updateHistories(ThreadID tid, Addr branch_pc, bool taken, BranchInfo *b, bool speculative, const StaticInstPtr &inst=nullStaticInstPtr, Addr target=MaxAddr)
(Speculatively) updates global histories (path and direction).
Definition: tage_base.cc:588
virtual void handleAllocAndUReset(bool alloc, bool taken, BranchInfo *bi, int nrand)
Handles Allocation and U bits reset on an update.
Definition: tage_base.cc:444
void update(ThreadID tid, Addr branch_pc, bool taken, BranchInfo *bi)
Update TAGE.
virtual void initFoldedHistories(ThreadHistory &history)
Initialization of the folded histories.
Definition: tage_base.cc:151
static void ctrUpdate(T &ctr, bool taken, int nbits)
Updates a direction counter based on the actual branch outcome.
Definition: tage_base.cc:261
void init() override
init() is called after all C++ SimObjects have been created and all ports are connected.
Definition: tage_base.cc:87
virtual unsigned getUseAltIdx(BranchInfo *bi, Addr branch_pc)
Calculation of the index for useAltPredForNewlyAllocated On this base TAGE implementation it is alway...
Definition: tage_base.cc:353
virtual void resetUctr(uint8_t &u)
Algorithm for resetting a single U counter.
Definition: tage_base.cc:508
virtual BranchInfo * makeBranchInfo()
Definition: tage_base.cc:82
virtual void extraAltCalc(BranchInfo *bi)
Extra steps for calculating altTaken For this base TAGE class it does nothing.
Definition: tage_base.cc:655
static void unsignedCtrUpdate(uint8_t &ctr, bool up, unsigned nbits)
Updates an unsigned counter based on up/down parameter.
Definition: tage_base.cc:279
virtual void handleUReset()
Handles the U bits reset.
Definition: tage_base.cc:493
virtual void updateStats(bool taken, BranchInfo *bi)
Update the stats.
Definition: tage_base.cc:662
virtual void calculateParameters()
Calculates the history lengths and some other paramters in derived classes.
Definition: tage_base.cc:174
const unsigned logRatioBiModalHystEntries
Definition: tage_base.hh:424
std::vector< bool > btableHysteresis
Definition: tage_base.hh:437
void updateGHist(uint8_t *&h, bool dir, uint8_t *tab, int &PT)
(Speculatively) updates the global branch history.
Definition: tage_base.cc:322
unsigned getGHR(ThreadID tid, BranchInfo *bi) const
Definition: tage_base.cc:711
std::vector< bool > btablePrediction
Definition: tage_base.hh:436
void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo *&bi)
Definition: tage_base.cc:188
virtual void adjustAlloc(bool &alloc, bool taken, bool pred_taken)
Extra calculation to tell whether TAGE allocaitons may happen or not on an update For this base TAGE ...
Definition: tage_base.cc:438
std::vector< ThreadHistory > threadHistory
Definition: tage_base.hh:464
virtual void calculateIndicesAndTags(ThreadID tid, Addr branch_pc, BranchInfo *bi)
On a prediction, calculates the TAGE indices and tags for all the different history lengths.
Definition: tage_base.cc:340
virtual bool getBimodePred(Addr pc, BranchInfo *bi) const
Get a branch prediction from the bimodal predictor.
Definition: tage_base.cc:293
int8_t getCtr(int hitBank, int hitBankIndex) const
Definition: tage_base.cc:768
virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const
Computes the partial tag of a tagged table.
Definition: tage_base.cc:248
std::vector< int > logTagTableSizes
Definition: tage_base.hh:434
void baseUpdate(Addr pc, bool taken, BranchInfo *bi)
Updates the bimodal predictor.
Definition: tage_base.cc:302
virtual void squash(ThreadID tid, bool taken, BranchInfo *bi, Addr target)
Restores speculatively updated path and direction histories.
Definition: tage_base.cc:629
virtual bool isHighConfidence(BranchInfo *bi) const
Definition: tage_base.hh:410
virtual int F(int phist, int size, int bank) const
Utility function to shuffle the path history depending on which tagged table we are accessing.
Definition: tage_base.cc:213
bool tagePredict(ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo *bi)
TAGE prediction called from TAGE::predict.
Definition: tage_base.cc:360
std::vector< int8_t > useAltPredForNewlyAllocated
Definition: tage_base.hh:475
std::vector< bool > noSkip
Definition: tage_base.hh:486
int getPathHist(ThreadID tid) const
Definition: tage_base.cc:780
std::vector< unsigned > tagTableTagWidths
Definition: tage_base.hh:433
gem5::branch_prediction::TAGEBase::TAGEBaseStats stats
virtual void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, BranchInfo *bi, int nrand, Addr corrTarget, bool pred, bool preAdjustAlloc=false)
Update TAGE for conditional branches.
Definition: tage_base.cc:514
virtual void buildTageTables()
Instantiates the TAGE table entries.
Definition: tage_base.cc:166
virtual int gindex(ThreadID tid, Addr pc, int bank) const
Computes the index used to access a partially tagged table.
Definition: tage_base.cc:230
virtual void handleTAGEUpdate(Addr branch_pc, bool taken, BranchInfo *bi)
Handles the update of the TAGE entries.
Definition: tage_base.cc:555
virtual int bindex(Addr pc_in) const
Computes the index used to access the bimodal table.
Definition: tage_base.cc:207
Statistics container.
Definition: group.hh:94
This is a simple scalar statistic, like a counter.
Definition: statistics.hh:1931
A vector of scalar stats.
Definition: statistics.hh:2007
Bitfield< 7 > b
Definition: misc_types.hh:388
Bitfield< 23 > up
Definition: types.hh:124
Bitfield< 22 > u
Definition: misc_types.hh:359
Bitfield< 4 > pc
Bitfield< 20, 16 > bi
Definition: types.hh:80
Bitfield< 54 > p
Definition: pagetable.hh:70
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:235
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
const StaticInstPtr nullStaticInstPtr
Statically allocated null StaticInstPtr.
const Addr MaxAddr
Definition: types.hh:171
Declaration of Statistics objects.
void init(int original_length, int compressed_length)
Definition: tage_base.hh:99
TAGEBaseStats(statistics::Group *parent, unsigned nHistoryTables)
Definition: tage_base.cc:725

Generated on Wed Dec 21 2022 10:22:31 for gem5 by doxygen 1.9.1