LLVM  14.0.0git
InterferenceCache.h
Go to the documentation of this file.
1 //===- InterferenceCache.h - Caching per-block interference ----*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // InterferenceCache remembers per-block interference from LiveIntervalUnions,
10 // fixed RegUnit interference, and register masks.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
15 #define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
16 
17 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Support/Compiler.h"
22 #include <cassert>
23 #include <cstddef>
24 #include <cstdlib>
25 
26 namespace llvm {
27 
28 class LiveIntervals;
29 class MachineFunction;
30 class TargetRegisterInfo;
31 
33  /// BlockInterference - information about the interference in a single basic
34  /// block.
35  struct BlockInterference {
36  unsigned Tag = 0;
38  SlotIndex Last;
39 
40  BlockInterference() {}
41  };
42 
43  /// Entry - A cache entry containing interference information for all aliases
44  /// of PhysReg in all basic blocks.
45  class Entry {
46  /// PhysReg - The register currently represented.
47  MCRegister PhysReg = 0;
48 
49  /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
50  /// change.
51  unsigned Tag = 0;
52 
53  /// RefCount - The total number of Cursor instances referring to this Entry.
54  unsigned RefCount = 0;
55 
56  /// MF - The current function.
57  MachineFunction *MF;
58 
59  /// Indexes - Mapping block numbers to SlotIndex ranges.
60  SlotIndexes *Indexes = nullptr;
61 
62  /// LIS - Used for accessing register mask interference maps.
63  LiveIntervals *LIS = nullptr;
64 
65  /// PrevPos - The previous position the iterators were moved to.
66  SlotIndex PrevPos;
67 
68  /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.
69  /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)
70  /// had just been called.
71  struct RegUnitInfo {
72  /// Iterator pointing into the LiveIntervalUnion containing virtual
73  /// register interference.
75 
76  /// Tag of the LIU last time we looked.
77  unsigned VirtTag;
78 
79  /// Fixed interference in RegUnit.
80  LiveRange *Fixed = nullptr;
81 
82  /// Iterator pointing into the fixed RegUnit interference.
84 
85  RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
86  VirtI.setMap(LIU.getMap());
87  }
88  };
89 
90  /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
91  /// more than 4 RegUnits.
93 
94  /// Blocks - Interference for each block in the function.
96 
97  /// update - Recompute Blocks[MBBNum]
98  void update(unsigned MBBNum);
99 
100  public:
101  Entry() = default;
102 
103  void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
104  assert(!hasRefs() && "Cannot clear cache entry with references");
105  PhysReg = MCRegister::NoRegister;
106  MF = mf;
107  Indexes = indexes;
108  LIS = lis;
109  }
110 
111  MCRegister getPhysReg() const { return PhysReg; }
112 
113  void addRef(int Delta) { RefCount += Delta; }
114 
115  bool hasRefs() const { return RefCount > 0; }
116 
117  void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
118 
119  /// valid - Return true if this is a valid entry for physReg.
120  bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
121 
122  /// reset - Initialize entry to represent physReg's aliases.
123  void reset(MCRegister physReg, LiveIntervalUnion *LIUArray,
124  const TargetRegisterInfo *TRI, const MachineFunction *MF);
125 
126  /// get - Return an up to date BlockInterference.
127  BlockInterference *get(unsigned MBBNum) {
128  if (Blocks[MBBNum].Tag != Tag)
129  update(MBBNum);
130  return &Blocks[MBBNum];
131  }
132  };
133 
134  // We don't keep a cache entry for every physical register, that would use too
135  // much memory. Instead, a fixed number of cache entries are used in a round-
136  // robin manner.
137  enum { CacheEntries = 32 };
138 
139  const TargetRegisterInfo *TRI = nullptr;
140  LiveIntervalUnion *LIUArray = nullptr;
141  MachineFunction *MF = nullptr;
142 
143  // Point to an entry for each physreg. The entry pointed to may not be up to
144  // date, and it may have been reused for a different physreg.
145  unsigned char* PhysRegEntries = nullptr;
146  size_t PhysRegEntriesCount = 0;
147 
148  // Next round-robin entry to be picked.
149  unsigned RoundRobin = 0;
150 
151  // The actual cache entries.
152  Entry Entries[CacheEntries];
153 
154  // get - Get a valid entry for PhysReg.
155  Entry *get(MCRegister PhysReg);
156 
157 public:
158  InterferenceCache() = default;
159 
161  free(PhysRegEntries);
162  }
163 
164  void reinitPhysRegEntries();
165 
166  /// init - Prepare cache for a new function.
167  void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
168  SlotIndexes *indexes, LiveIntervals *lis,
169  const TargetRegisterInfo *tri);
170 
171  /// getMaxCursors - Return the maximum number of concurrent cursors that can
172  /// be supported.
173  unsigned getMaxCursors() const { return CacheEntries; }
174 
175  /// Cursor - The primary query interface for the block interference cache.
176  class Cursor {
177  Entry *CacheEntry = nullptr;
178  const BlockInterference *Current = nullptr;
179  static const BlockInterference NoInterference;
180 
181  void setEntry(Entry *E) {
182  Current = nullptr;
183  // Update reference counts. Nothing happens when RefCount reaches 0, so
184  // we don't have to check for E == CacheEntry etc.
185  if (CacheEntry)
186  CacheEntry->addRef(-1);
187  CacheEntry = E;
188  if (CacheEntry)
189  CacheEntry->addRef(+1);
190  }
191 
192  public:
193  /// Cursor - Create a dangling cursor.
194  Cursor() = default;
195 
196  Cursor(const Cursor &O) {
197  setEntry(O.CacheEntry);
198  }
199 
201  setEntry(O.CacheEntry);
202  return *this;
203  }
204 
205  ~Cursor() { setEntry(nullptr); }
206 
207  /// setPhysReg - Point this cursor to PhysReg's interference.
208  void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg) {
209  // Release reference before getting a new one. That guarantees we can
210  // actually have CacheEntries live cursors.
211  setEntry(nullptr);
212  if (PhysReg.isValid())
213  setEntry(Cache.get(PhysReg));
214  }
215 
216  /// moveTo - Move cursor to basic block MBBNum.
217  void moveToBlock(unsigned MBBNum) {
218  Current = CacheEntry ? CacheEntry->get(MBBNum) : &NoInterference;
219  }
220 
221  /// hasInterference - Return true if the current block has any interference.
223  return Current->First.isValid();
224  }
225 
226  /// first - Return the starting index of the first interfering range in the
227  /// current block.
229  return Current->First;
230  }
231 
232  /// last - Return the ending index of the last interfering range in the
233  /// current block.
235  return Current->Last;
236  }
237  };
238 };
239 
240 } // end namespace llvm
241 
242 #endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::SmallVector< RegUnitInfo, 4 >
llvm::MCRegister::isValid
bool isValid() const
Definition: MCRegister.h:76
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::InterferenceCache::Cursor::Cursor
Cursor(const Cursor &O)
Definition: InterferenceCache.h:196
llvm::MCRegister::NoRegister
static constexpr unsigned NoRegister
Definition: MCRegister.h:43
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:234
llvm::InterferenceCache::Cursor::~Cursor
~Cursor()
Definition: InterferenceCache.h:205
llvm::InterferenceCache::Cursor::operator=
Cursor & operator=(const Cursor &O)
Definition: InterferenceCache.h:200
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LiveIntervalUnion::getTag
unsigned getTag() const
getTag - Return an opaque tag representing the current state of the union.
Definition: LiveIntervalUnion.h:85
llvm::LiveIntervalUnion::getMap
const Map & getMap() const
Definition: LiveIntervalUnion.h:82
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
LiveIntervalUnion.h
llvm::InterferenceCache::Cursor::setPhysReg
void setPhysReg(InterferenceCache &Cache, MCRegister PhysReg)
setPhysReg - Point this cursor to PhysReg's interference.
Definition: InterferenceCache.h:208
llvm::InterferenceCache::Cursor::first
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
Definition: InterferenceCache.h:228
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:197
llvm::InterferenceCache
Definition: InterferenceCache.h:32
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::InterferenceCache::Cursor::moveToBlock
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
Definition: InterferenceCache.h:217
llvm::LiveIntervalUnion
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
Definition: LiveIntervalUnion.h:42
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InterferenceCache::Cursor::last
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
Definition: InterferenceCache.h:234
llvm::LiveIntervalUnion::SegmentIter
LiveSegments::iterator SegmentIter
Definition: LiveIntervalUnion.h:52
llvm::MachineFunction
Definition: MachineFunction.h:234
Compiler.h
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
llvm::InterferenceCache::Cursor
Cursor - The primary query interface for the block interference cache.
Definition: InterferenceCache.h:176
llvm::LiveRange::iterator
Segments::iterator iterator
Definition: LiveInterval.h:212
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::LiveIntervals
Definition: LiveIntervals.h:54
LiveInterval.h
llvm::InterferenceCache::getMaxCursors
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
Definition: InterferenceCache.h:173
SmallVector.h
llvm::InterferenceCache::Cursor::hasInterference
bool hasInterference()
hasInterference - Return true if the current block has any interference.
Definition: InterferenceCache.h:222
llvm::InterferenceCache::~InterferenceCache
~InterferenceCache()
Definition: InterferenceCache.h:160
SlotIndexes.h
llvm::FloatStyle::Fixed
@ Fixed
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24