LLVM  10.0.0svn
LiveIntervalUnion.cpp
Go to the documentation of this file.
1 //===- LiveIntervalUnion.cpp - Live interval union data structure ---------===//
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 // LiveIntervalUnion represents a coalesced set of live intervals. This may be
10 // used during coalescing to represent a congruence class, or during register
11 // allocation to model liveness of a physical register.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/STLExtras.h"
21 #include <cassert>
22 #include <cstdlib>
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "regalloc"
27 
28 // Merge a LiveInterval's segments. Guarantee no overlaps.
29 void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) {
30  if (Range.empty())
31  return;
32  ++Tag;
33 
34  // Insert each of the virtual register's live segments into the map.
35  LiveRange::const_iterator RegPos = Range.begin();
36  LiveRange::const_iterator RegEnd = Range.end();
37  SegmentIter SegPos = Segments.find(RegPos->start);
38 
39  while (SegPos.valid()) {
40  SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
41  if (++RegPos == RegEnd)
42  return;
43  SegPos.advanceTo(RegPos->start);
44  }
45 
46  // We have reached the end of Segments, so it is no longer necessary to search
47  // for the insertion position.
48  // It is faster to insert the end first.
49  --RegEnd;
50  SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg);
51  for (; RegPos != RegEnd; ++RegPos, ++SegPos)
52  SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
53 }
54 
55 // Remove a live virtual register's segments from this union.
56 void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) {
57  if (Range.empty())
58  return;
59  ++Tag;
60 
61  // Remove each of the virtual register's live segments from the map.
62  LiveRange::const_iterator RegPos = Range.begin();
63  LiveRange::const_iterator RegEnd = Range.end();
64  SegmentIter SegPos = Segments.find(RegPos->start);
65 
66  while (true) {
67  assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
68  SegPos.erase();
69  if (!SegPos.valid())
70  return;
71 
72  // Skip all segments that may have been coalesced.
73  RegPos = Range.advanceTo(RegPos, SegPos.start());
74  if (RegPos == RegEnd)
75  return;
76 
77  SegPos.advanceTo(RegPos->start);
78  }
79 }
80 
81 void
83  if (empty()) {
84  OS << " empty\n";
85  return;
86  }
87  for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
88  OS << " [" << SI.start() << ' ' << SI.stop() << "):"
89  << printReg(SI.value()->reg, TRI);
90  }
91  OS << '\n';
92 }
93 
94 #ifndef NDEBUG
95 // Verify the live intervals in this union and add them to the visited set.
97  for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
98  VisitedVRegs.set(SI.value()->reg);
99 }
100 #endif //!NDEBUG
101 
102 // Scan the vector of interfering virtual registers in this union. Assume it's
103 // quite small.
105  return is_contained(InterferingVRegs, VirtReg);
106 }
107 
108 // Collect virtual registers in this union that interfere with this
109 // query's live virtual register.
110 //
111 // The query state is one of:
112 //
113 // 1. CheckedFirstInterference == false: Iterators are uninitialized.
114 // 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused.
115 // 3. Iterators left at the last seen intersection.
116 //
118 collectInterferingVRegs(unsigned MaxInterferingRegs) {
119  // Fast path return if we already have the desired information.
120  if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
121  return InterferingVRegs.size();
122 
123  // Set up iterators on the first call.
124  if (!CheckedFirstInterference) {
125  CheckedFirstInterference = true;
126 
127  // Quickly skip interference check for empty sets.
128  if (LR->empty() || LiveUnion->empty()) {
129  SeenAllInterferences = true;
130  return 0;
131  }
132 
133  // In most cases, the union will start before LR.
134  LRI = LR->begin();
135  LiveUnionI.setMap(LiveUnion->getMap());
136  LiveUnionI.find(LRI->start);
137  }
138 
139  LiveRange::const_iterator LREnd = LR->end();
140  LiveInterval *RecentReg = nullptr;
141  while (LiveUnionI.valid()) {
142  assert(LRI != LREnd && "Reached end of LR");
143 
144  // Check for overlapping interference.
145  while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) {
146  // This is an overlap, record the interfering register.
147  LiveInterval *VReg = LiveUnionI.value();
148  if (VReg != RecentReg && !isSeenInterference(VReg)) {
149  RecentReg = VReg;
150  InterferingVRegs.push_back(VReg);
151  if (InterferingVRegs.size() >= MaxInterferingRegs)
152  return InterferingVRegs.size();
153  }
154  // This LiveUnion segment is no longer interesting.
155  if (!(++LiveUnionI).valid()) {
156  SeenAllInterferences = true;
157  return InterferingVRegs.size();
158  }
159  }
160 
161  // The iterators are now not overlapping, LiveUnionI has been advanced
162  // beyond LRI.
163  assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap");
164 
165  // Advance the iterator that ends first.
166  LRI = LR->advanceTo(LRI, LiveUnionI.start());
167  if (LRI == LREnd)
168  break;
169 
170  // Detect overlap, handle above.
171  if (LRI->start < LiveUnionI.stop())
172  continue;
173 
174  // Still not overlapping. Catch up LiveUnionI.
175  LiveUnionI.advanceTo(LRI->start);
176  }
177  SeenAllInterferences = true;
178  return InterferingVRegs.size();
179 }
180 
182  unsigned NSize) {
183  // Reuse existing allocation.
184  if (NSize == Size)
185  return;
186  clear();
187  Size = NSize;
188  LIUs = static_cast<LiveIntervalUnion*>(
189  safe_malloc(sizeof(LiveIntervalUnion)*NSize));
190  for (unsigned i = 0; i != Size; ++i)
191  new(LIUs + i) LiveIntervalUnion(Alloc);
192 }
193 
195  if (!LIUs)
196  return;
197  for (unsigned i = 0; i != Size; ++i)
198  LIUs[i].~LiveIntervalUnion();
199  free(LIUs);
200  Size = 0;
201  LIUs = nullptr;
202 }
bool empty() const
Definition: LiveInterval.h:369
LiveIntervalUnion(Allocator &a)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void set(unsigned Idx)
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:675
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position...
Definition: LiveInterval.h:258
unsigned const TargetRegisterInfo * TRI
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1358
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
const_iterator begin() const
Definition: IntervalMap.h:1099
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:156
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
void erase()
erase - Erase the current interval.
Definition: IntervalMap.h:1870
size_t size() const
Definition: LiveInterval.h:292
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end()...
Definition: IntervalMap.h:1125
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
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...
LiveSegments::Allocator Allocator
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:25
void unify(LiveInterval &VirtReg, const LiveRange &Range)
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
Segments::const_iterator const_iterator
Definition: LiveInterval.h:208
void init(LiveIntervalUnion::Allocator &, unsigned Size)
const ValT & value() const
value - Return the mapped value at the current interval.
Definition: IntervalMap.h:1370
void insert(KeyT a, KeyT b, ValT y)
insert - Insert mapping [a;b] -> y before the current position.
Definition: IntervalMap.h:1781
void verify(LiveVirtRegBitSet &VisitedVRegs)
uint32_t Size
Definition: Profile.cpp:46
void extract(LiveInterval &VirtReg, const LiveRange &Range)
bool isSeenInterference(LiveInterval *VirtReg) const
NDEBUG.
iterator begin()
Definition: LiveInterval.h:210
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1224