Line data Source code
1 : //===- LiveIntervalUnion.h - Live interval union data struct ---*- C++ -*--===//
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 is a union of live segments across multiple live virtual
11 : // registers. This may be used during coalescing to represent a congruence
12 : // class, or during register allocation to model liveness of a physical
13 : // register.
14 : //
15 : //===----------------------------------------------------------------------===//
16 :
17 : #ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H
18 : #define LLVM_CODEGEN_LIVEINTERVALUNION_H
19 :
20 : #include "llvm/ADT/IntervalMap.h"
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/CodeGen/LiveInterval.h"
23 : #include "llvm/CodeGen/SlotIndexes.h"
24 : #include <cassert>
25 : #include <limits>
26 :
27 : namespace llvm {
28 :
29 : class raw_ostream;
30 : class TargetRegisterInfo;
31 :
32 : #ifndef NDEBUG
33 : // forward declaration
34 : template <unsigned Element> class SparseBitVector;
35 :
36 : using LiveVirtRegBitSet = SparseBitVector<128>;
37 : #endif
38 :
39 : /// Union of live intervals that are strong candidates for coalescing into a
40 : /// single register (either physical or virtual depending on the context). We
41 : /// expect the constituent live intervals to be disjoint, although we may
42 : /// eventually make exceptions to handle value-based interference.
43 3740677 : class LiveIntervalUnion {
44 : // A set of live virtual register segments that supports fast insertion,
45 : // intersection, and removal.
46 : // Mapping SlotIndex intervals to virtual register numbers.
47 : using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
48 :
49 : public:
50 : // SegmentIter can advance to the next segment ordered by starting position
51 : // which may belong to a different live virtual register. We also must be able
52 : // to reach the current segment's containing virtual register.
53 : using SegmentIter = LiveSegments::iterator;
54 :
55 : /// Const version of SegmentIter.
56 : using ConstSegmentIter = LiveSegments::const_iterator;
57 :
58 : // LiveIntervalUnions share an external allocator.
59 : using Allocator = LiveSegments::Allocator;
60 :
61 : private:
62 : unsigned Tag = 0; // unique tag for current contents.
63 : LiveSegments Segments; // union of virtual reg segments
64 :
65 : public:
66 3742880 : explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
67 :
68 : // Iterate over all segments in the union of live virtual registers ordered
69 : // by their starting position.
70 : SegmentIter begin() { return Segments.begin(); }
71 : SegmentIter end() { return Segments.end(); }
72 147128 : SegmentIter find(SlotIndex x) { return Segments.find(x); }
73 : ConstSegmentIter begin() const { return Segments.begin(); }
74 : ConstSegmentIter end() const { return Segments.end(); }
75 : ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
76 :
77 22834131 : bool empty() const { return Segments.empty(); }
78 : SlotIndex startIndex() const { return Segments.start(); }
79 :
80 : // Provide public access to the underlying map to allow overlap iteration.
81 : using Map = LiveSegments;
82 21591082 : const Map &getMap() const { return Segments; }
83 :
84 : /// getTag - Return an opaque tag representing the current state of the union.
85 0 : unsigned getTag() const { return Tag; }
86 :
87 : /// changedSince - Return true if the union change since getTag returned tag.
88 0 : bool changedSince(unsigned tag) const { return tag != Tag; }
89 :
90 : // Add a live virtual register to this union and merge its segments.
91 : void unify(LiveInterval &VirtReg, const LiveRange &Range);
92 :
93 : // Remove a live virtual register's segments from this union.
94 : void extract(LiveInterval &VirtReg, const LiveRange &Range);
95 :
96 : // Remove all inserted virtual registers.
97 38657717 : void clear() { Segments.clear(); ++Tag; }
98 :
99 : // Print union, using TRI to translate register names
100 : void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
101 :
102 : #ifndef NDEBUG
103 : // Verify the live intervals in this union and add them to the visited set.
104 : void verify(LiveVirtRegBitSet& VisitedVRegs);
105 : #endif
106 :
107 : /// Query interferences between a single live virtual register and a live
108 : /// interval union.
109 : class Query {
110 : const LiveIntervalUnion *LiveUnion = nullptr;
111 : const LiveRange *LR = nullptr;
112 : LiveRange::const_iterator LRI; ///< current position in LR
113 : ConstSegmentIter LiveUnionI; ///< current position in LiveUnion
114 : SmallVector<LiveInterval*,4> InterferingVRegs;
115 : bool CheckedFirstInterference = false;
116 : bool SeenAllInterferences = false;
117 : unsigned Tag = 0;
118 : unsigned UserTag = 0;
119 :
120 : void reset(unsigned NewUserTag, const LiveRange &NewLR,
121 : const LiveIntervalUnion &NewLiveUnion) {
122 5701912 : LiveUnion = &NewLiveUnion;
123 5701912 : LR = &NewLR;
124 : InterferingVRegs.clear();
125 5701912 : CheckedFirstInterference = false;
126 5701912 : SeenAllInterferences = false;
127 5701912 : Tag = NewLiveUnion.getTag();
128 5701912 : UserTag = NewUserTag;
129 : }
130 :
131 : public:
132 7486960 : Query() = default;
133 17075173 : Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
134 17075173 : LiveUnion(&LIU), LR(&LR) {}
135 : Query(const Query &) = delete;
136 : Query &operator=(const Query &) = delete;
137 :
138 : void init(unsigned NewUserTag, const LiveRange &NewLR,
139 : const LiveIntervalUnion &NewLiveUnion) {
140 7534024 : if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
141 1832979 : !NewLiveUnion.changedSince(Tag)) {
142 : // Retain cached results, e.g. firstInterference.
143 : return;
144 : }
145 : reset(NewUserTag, NewLR, NewLiveUnion);
146 : }
147 :
148 : // Does this live virtual register interfere with the union?
149 17308753 : bool checkInterference() { return collectInterferingVRegs(1); }
150 :
151 : // Count the virtual registers in this union that interfere with this
152 : // query's live virtual register, up to maxInterferingRegs.
153 : unsigned collectInterferingVRegs(
154 : unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
155 :
156 : // Was this virtual register visited during collectInterferingVRegs?
157 : bool isSeenInterference(LiveInterval *VirtReg) const;
158 :
159 : // Did collectInterferingVRegs collect all interferences?
160 : bool seenAllInterferences() const { return SeenAllInterferences; }
161 :
162 : // Vector generated by collectInterferingVRegs.
163 : const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
164 : return InterferingVRegs;
165 : }
166 : };
167 :
168 : // Array of LiveIntervalUnions.
169 : class Array {
170 : unsigned Size = 0;
171 : LiveIntervalUnion *LIUs = nullptr;
172 :
173 : public:
174 19532 : Array() = default;
175 : ~Array() { clear(); }
176 :
177 : // Initialize the array to have Size entries.
178 : // Reuse an existing allocation if the size matches.
179 : void init(LiveIntervalUnion::Allocator&, unsigned Size);
180 :
181 0 : unsigned size() const { return Size; }
182 :
183 : void clear();
184 :
185 0 : LiveIntervalUnion& operator[](unsigned idx) {
186 : assert(idx < Size && "idx out of bounds");
187 48943627 : return LIUs[idx];
188 : }
189 :
190 0 : const LiveIntervalUnion& operator[](unsigned Idx) const {
191 : assert(Idx < Size && "Idx out of bounds");
192 102950 : return LIUs[Idx];
193 : }
194 : };
195 : };
196 :
197 : } // end namespace llvm
198 :
199 : #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H
|
