LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
LiveIntervalUnion.cpp
Go to the documentation of this file.
1 //===-- LiveIntervalUnion.cpp - Live interval union data structure --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // LiveIntervalUnion represents a coalesced set of live intervals. This may be
11 // used during coalescing to represent a congruence class, or during register
12 // allocation to model liveness of a physical register.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #define DEBUG_TYPE "regalloc"
19 #include "llvm/Support/Debug.h"
22 #include <algorithm>
23 
24 using namespace llvm;
25 
26 
27 // Merge a LiveInterval's segments. Guarantee no overlaps.
29  if (VirtReg.empty())
30  return;
31  ++Tag;
32 
33  // Insert each of the virtual register's live segments into the map.
34  LiveInterval::iterator RegPos = VirtReg.begin();
35  LiveInterval::iterator RegEnd = VirtReg.end();
36  SegmentIter SegPos = Segments.find(RegPos->start);
37 
38  while (SegPos.valid()) {
39  SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
40  if (++RegPos == RegEnd)
41  return;
42  SegPos.advanceTo(RegPos->start);
43  }
44 
45  // We have reached the end of Segments, so it is no longer necessary to search
46  // for the insertion position.
47  // It is faster to insert the end first.
48  --RegEnd;
49  SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg);
50  for (; RegPos != RegEnd; ++RegPos, ++SegPos)
51  SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
52 }
53 
54 // Remove a live virtual register's segments from this union.
56  if (VirtReg.empty())
57  return;
58  ++Tag;
59 
60  // Remove each of the virtual register's live segments from the map.
61  LiveInterval::iterator RegPos = VirtReg.begin();
62  LiveInterval::iterator RegEnd = VirtReg.end();
63  SegmentIter SegPos = Segments.find(RegPos->start);
64 
65  for (;;) {
66  assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
67  SegPos.erase();
68  if (!SegPos.valid())
69  return;
70 
71  // Skip all segments that may have been coalesced.
72  RegPos = VirtReg.advanceTo(RegPos, SegPos.start());
73  if (RegPos == RegEnd)
74  return;
75 
76  SegPos.advanceTo(RegPos->start);
77  }
78 }
79 
80 void
82  if (empty()) {
83  OS << " empty\n";
84  return;
85  }
86  for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
87  OS << " [" << SI.start() << ' ' << SI.stop() << "):"
88  << PrintReg(SI.value()->reg, TRI);
89  }
90  OS << '\n';
91 }
92 
93 #ifndef NDEBUG
94 // Verify the live intervals in this union and add them to the visited set.
96  for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
97  VisitedVRegs.set(SI.value()->reg);
98 }
99 #endif //!NDEBUG
100 
101 // Scan the vector of interfering virtual registers in this union. Assume it's
102 // quite small.
105  std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg);
106  return I != InterferingVRegs.end();
107 }
108 
109 // Collect virtual registers in this union that interfere with this
110 // query's live virtual register.
111 //
112 // The query state is one of:
113 //
114 // 1. CheckedFirstInterference == false: Iterators are uninitialized.
115 // 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused.
116 // 3. Iterators left at the last seen intersection.
117 //
119 collectInterferingVRegs(unsigned MaxInterferingRegs) {
120  // Fast path return if we already have the desired information.
121  if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
122  return InterferingVRegs.size();
123 
124  // Set up iterators on the first call.
125  if (!CheckedFirstInterference) {
126  CheckedFirstInterference = true;
127 
128  // Quickly skip interference check for empty sets.
129  if (VirtReg->empty() || LiveUnion->empty()) {
130  SeenAllInterferences = true;
131  return 0;
132  }
133 
134  // In most cases, the union will start before VirtReg.
135  VirtRegI = VirtReg->begin();
136  LiveUnionI.setMap(LiveUnion->getMap());
137  LiveUnionI.find(VirtRegI->start);
138  }
139 
140  LiveInterval::iterator VirtRegEnd = VirtReg->end();
141  LiveInterval *RecentReg = 0;
142  while (LiveUnionI.valid()) {
143  assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg");
144 
145  // Check for overlapping interference.
146  while (VirtRegI->start < LiveUnionI.stop() &&
147  VirtRegI->end > LiveUnionI.start()) {
148  // This is an overlap, record the interfering register.
149  LiveInterval *VReg = LiveUnionI.value();
150  if (VReg != RecentReg && !isSeenInterference(VReg)) {
151  RecentReg = VReg;
152  InterferingVRegs.push_back(VReg);
153  if (InterferingVRegs.size() >= MaxInterferingRegs)
154  return InterferingVRegs.size();
155  }
156  // This LiveUnion segment is no longer interesting.
157  if (!(++LiveUnionI).valid()) {
158  SeenAllInterferences = true;
159  return InterferingVRegs.size();
160  }
161  }
162 
163  // The iterators are now not overlapping, LiveUnionI has been advanced
164  // beyond VirtRegI.
165  assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap");
166 
167  // Advance the iterator that ends first.
168  VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start());
169  if (VirtRegI == VirtRegEnd)
170  break;
171 
172  // Detect overlap, handle above.
173  if (VirtRegI->start < LiveUnionI.stop())
174  continue;
175 
176  // Still not overlapping. Catch up LiveUnionI.
177  LiveUnionI.advanceTo(VirtRegI->start);
178  }
179  SeenAllInterferences = true;
180  return InterferingVRegs.size();
181 }
182 
184  unsigned NSize) {
185  // Reuse existing allocation.
186  if (NSize == Size)
187  return;
188  clear();
189  Size = NSize;
190  LIUs = static_cast<LiveIntervalUnion*>(
191  malloc(sizeof(LiveIntervalUnion)*NSize));
192  for (unsigned i = 0; i != Size; ++i)
193  new(LIUs + i) LiveIntervalUnion(Alloc);
194 }
195 
197  if (!LIUs)
198  return;
199  for (unsigned i = 0; i != Size; ++i)
200  LIUs[i].~LiveIntervalUnion();
201  free(LIUs);
202  Size = 0;
203  LIUs = 0;
204 }
const_iterator begin() const
Definition: IntervalMap.h:1110
LiveIntervalUnion(Allocator &a)
void set(unsigned Idx)
iterator advanceTo(iterator I, SlotIndex Pos)
Definition: LiveInterval.h:212
const_iterator find(KeyT x) const
Definition: IntervalMap.h:1136
size_t size() const
Definition: LiveInterval.h:238
void unify(LiveInterval &VirtReg)
bool empty() const
Definition: LiveInterval.h:311
iterator end()
Definition: LiveInterval.h:193
void free(void *ptr);
void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const
bool isSeenInterference(LiveInterval *VReg) const
NDEBUG.
void init(LiveIntervalUnion::Allocator &, unsigned Size)
LiveSegments::iterator SegmentIter
void extract(LiveInterval &VirtReg)
void verify(LiveVirtRegBitSet &VisitedVRegs)
void *malloc(size_t size);
#define I(x, y, z)
Definition: MD5.cpp:54
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=UINT_MAX)
iterator begin()
Definition: LiveInterval.h:192