LLVM  10.0.0svn
InterferenceCache.cpp
Go to the documentation of this file.
1 //===- InterferenceCache.cpp - Caching per-block interference -------------===//
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 in LiveIntervalUnions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "InterferenceCache.h"
14 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/MC/MCRegisterInfo.h"
25 #include <cassert>
26 #include <cstdint>
27 #include <cstdlib>
28 #include <tuple>
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "regalloc"
33 
34 // Static member used for null interference cursors.
35 const InterferenceCache::BlockInterference
36  InterferenceCache::Cursor::NoInterference;
37 
38 // Initializes PhysRegEntries (instead of a SmallVector, PhysRegEntries is a
39 // buffer of size NumPhysRegs to speed up alloc/clear for targets with large
40 // reg files). Calloced memory is used for good form, and quites tools like
41 // Valgrind too, but zero initialized memory is not required by the algorithm:
42 // this is because PhysRegEntries works like a SparseSet and its entries are
43 // only valid when there is a corresponding CacheEntries assignment. There is
44 // also support for when pass managers are reused for targets with different
45 // numbers of PhysRegs: in this case PhysRegEntries is freed and reinitialized.
47  if (PhysRegEntriesCount == TRI->getNumRegs()) return;
48  free(PhysRegEntries);
49  PhysRegEntriesCount = TRI->getNumRegs();
50  PhysRegEntries = static_cast<unsigned char*>(
51  safe_calloc(PhysRegEntriesCount, sizeof(unsigned char)));
52 }
53 
55  LiveIntervalUnion *liuarray,
56  SlotIndexes *indexes,
57  LiveIntervals *lis,
58  const TargetRegisterInfo *tri) {
59  MF = mf;
60  LIUArray = liuarray;
61  TRI = tri;
63  for (unsigned i = 0; i != CacheEntries; ++i)
64  Entries[i].clear(mf, indexes, lis);
65 }
66 
67 InterferenceCache::Entry *InterferenceCache::get(unsigned PhysReg) {
68  unsigned E = PhysRegEntries[PhysReg];
69  if (E < CacheEntries && Entries[E].getPhysReg() == PhysReg) {
70  if (!Entries[E].valid(LIUArray, TRI))
71  Entries[E].revalidate(LIUArray, TRI);
72  return &Entries[E];
73  }
74  // No valid entry exists, pick the next round-robin entry.
75  E = RoundRobin;
76  if (++RoundRobin == CacheEntries)
77  RoundRobin = 0;
78  for (unsigned i = 0; i != CacheEntries; ++i) {
79  // Skip entries that are in use.
80  if (Entries[E].hasRefs()) {
81  if (++E == CacheEntries)
82  E = 0;
83  continue;
84  }
85  Entries[E].reset(PhysReg, LIUArray, TRI, MF);
86  PhysRegEntries[PhysReg] = E;
87  return &Entries[E];
88  }
89  llvm_unreachable("Ran out of interference cache entries.");
90 }
91 
92 /// revalidate - LIU contents have changed, update tags.
93 void InterferenceCache::Entry::revalidate(LiveIntervalUnion *LIUArray,
94  const TargetRegisterInfo *TRI) {
95  // Invalidate all block entries.
96  ++Tag;
97  // Invalidate all iterators.
98  PrevPos = SlotIndex();
99  unsigned i = 0;
100  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i)
101  RegUnits[i].VirtTag = LIUArray[*Units].getTag();
102 }
103 
104 void InterferenceCache::Entry::reset(unsigned physReg,
105  LiveIntervalUnion *LIUArray,
106  const TargetRegisterInfo *TRI,
107  const MachineFunction *MF) {
108  assert(!hasRefs() && "Cannot reset cache entry with references");
109  // LIU's changed, invalidate cache.
110  ++Tag;
111  PhysReg = physReg;
112  Blocks.resize(MF->getNumBlockIDs());
113 
114  // Reset iterators.
115  PrevPos = SlotIndex();
116  RegUnits.clear();
117  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
118  RegUnits.push_back(LIUArray[*Units]);
119  RegUnits.back().Fixed = &LIS->getRegUnit(*Units);
120  }
121 }
122 
123 bool InterferenceCache::Entry::valid(LiveIntervalUnion *LIUArray,
124  const TargetRegisterInfo *TRI) {
125  unsigned i = 0, e = RegUnits.size();
126  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units, ++i) {
127  if (i == e)
128  return false;
129  if (LIUArray[*Units].changedSince(RegUnits[i].VirtTag))
130  return false;
131  }
132  return i == e;
133 }
134 
135 void InterferenceCache::Entry::update(unsigned MBBNum) {
136  SlotIndex Start, Stop;
137  std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
138 
139  // Use advanceTo only when possible.
140  if (PrevPos != Start) {
141  if (!PrevPos.isValid() || Start < PrevPos) {
142  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
143  RegUnitInfo &RUI = RegUnits[i];
144  RUI.VirtI.find(Start);
145  RUI.FixedI = RUI.Fixed->find(Start);
146  }
147  } else {
148  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
149  RegUnitInfo &RUI = RegUnits[i];
150  RUI.VirtI.advanceTo(Start);
151  if (RUI.FixedI != RUI.Fixed->end())
152  RUI.FixedI = RUI.Fixed->advanceTo(RUI.FixedI, Start);
153  }
154  }
155  PrevPos = Start;
156  }
157 
159  MF->getBlockNumbered(MBBNum)->getIterator();
160  BlockInterference *BI = &Blocks[MBBNum];
161  ArrayRef<SlotIndex> RegMaskSlots;
162  ArrayRef<const uint32_t*> RegMaskBits;
163  while (true) {
164  BI->Tag = Tag;
165  BI->First = BI->Last = SlotIndex();
166 
167  // Check for first interference from virtregs.
168  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
169  LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
170  if (!I.valid())
171  continue;
172  SlotIndex StartI = I.start();
173  if (StartI >= Stop)
174  continue;
175  if (!BI->First.isValid() || StartI < BI->First)
176  BI->First = StartI;
177  }
178 
179  // Same thing for fixed interference.
180  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
181  LiveInterval::const_iterator I = RegUnits[i].FixedI;
182  LiveInterval::const_iterator E = RegUnits[i].Fixed->end();
183  if (I == E)
184  continue;
185  SlotIndex StartI = I->start;
186  if (StartI >= Stop)
187  continue;
188  if (!BI->First.isValid() || StartI < BI->First)
189  BI->First = StartI;
190  }
191 
192  // Also check for register mask interference.
193  RegMaskSlots = LIS->getRegMaskSlotsInBlock(MBBNum);
194  RegMaskBits = LIS->getRegMaskBitsInBlock(MBBNum);
195  SlotIndex Limit = BI->First.isValid() ? BI->First : Stop;
196  for (unsigned i = 0, e = RegMaskSlots.size();
197  i != e && RegMaskSlots[i] < Limit; ++i)
198  if (MachineOperand::clobbersPhysReg(RegMaskBits[i], PhysReg)) {
199  // Register mask i clobbers PhysReg before the LIU interference.
200  BI->First = RegMaskSlots[i];
201  break;
202  }
203 
204  PrevPos = Stop;
205  if (BI->First.isValid())
206  break;
207 
208  // No interference in this block? Go ahead and precompute the next block.
209  if (++MFI == MF->end())
210  return;
211  MBBNum = MFI->getNumber();
212  BI = &Blocks[MBBNum];
213  if (BI->Tag == Tag)
214  return;
215  std::tie(Start, Stop) = Indexes->getMBBRange(MBBNum);
216  }
217 
218  // Check for last interference in block.
219  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
220  LiveIntervalUnion::SegmentIter &I = RegUnits[i].VirtI;
221  if (!I.valid() || I.start() >= Stop)
222  continue;
223  I.advanceTo(Stop);
224  bool Backup = !I.valid() || I.start() >= Stop;
225  if (Backup)
226  --I;
227  SlotIndex StopI = I.stop();
228  if (!BI->Last.isValid() || StopI > BI->Last)
229  BI->Last = StopI;
230  if (Backup)
231  ++I;
232  }
233 
234  // Fixed interference.
235  for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) {
236  LiveInterval::iterator &I = RegUnits[i].FixedI;
237  LiveRange *LR = RegUnits[i].Fixed;
238  if (I == LR->end() || I->start >= Stop)
239  continue;
240  I = LR->advanceTo(I, Stop);
241  bool Backup = I == LR->end() || I->start >= Stop;
242  if (Backup)
243  --I;
244  SlotIndex StopI = I->end;
245  if (!BI->Last.isValid() || StopI > BI->Last)
246  BI->Last = StopI;
247  if (Backup)
248  ++I;
249  }
250 
251  // Also check for register mask interference.
252  SlotIndex Limit = BI->Last.isValid() ? BI->Last : Start;
253  for (unsigned i = RegMaskSlots.size();
254  i && RegMaskSlots[i-1].getDeadSlot() > Limit; --i)
255  if (MachineOperand::clobbersPhysReg(RegMaskBits[i-1], PhysReg)) {
256  // Register mask i-1 clobbers PhysReg after the LIU interference.
257  // Model the regmask clobber as a dead def.
258  BI->Last = RegMaskSlots[i-1].getDeadSlot();
259  break;
260  }
261 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
Segments::iterator iterator
Definition: LiveInterval.h:207
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position...
Definition: LiveInterval.h:258
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:151
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1358
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:156
void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)
init - Prepare cache for a new function.
iterator end()
Definition: LiveInterval.h:211
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1442
SlotIndexes pass.
Definition: SlotIndexes.h:314
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const KeyT & start() const
start - Return the beginning of the current interval.
Definition: IntervalMap.h:1364
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
self_iterator getIterator()
Definition: ilist_node.h:81
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Iterator for intrusive lists based on ilist_node.
Segments::const_iterator const_iterator
Definition: LiveInterval.h:208
static Optional< unsigned > getTag(const TargetRegisterInfo *TRI, const MachineInstr &MI, const LoadInfo &LI)
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1367
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
Definition: MemAlloc.h:38
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83