/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/CodeGen/LiveIntervalUnion.h
Line | Count | Source (jump to first uncovered line) |
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 | | 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 | 5.83M | 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 | 0 | SegmentIter begin() { return Segments.begin(); } |
71 | 0 | SegmentIter end() { return Segments.end(); } |
72 | 472k | SegmentIter find(SlotIndex x) { return Segments.find(x); } |
73 | 0 | ConstSegmentIter begin() const { return Segments.begin(); } |
74 | 0 | ConstSegmentIter end() const { return Segments.end(); } |
75 | 0 | ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); } |
76 | | |
77 | 205M | bool empty() const { return Segments.empty(); } |
78 | 0 | SlotIndex startIndex() const { return Segments.start(); } |
79 | | |
80 | | // Provide public access to the underlying map to allow overlap iteration. |
81 | | using Map = LiveSegments; |
82 | 203M | const Map &getMap() const { return Segments; } |
83 | | |
84 | | /// getTag - Return an opaque tag representing the current state of the union. |
85 | 53.0M | unsigned getTag() const { return Tag; } |
86 | | |
87 | | /// changedSince - Return true if the union change since getTag returned tag. |
88 | 42.8M | 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 | 75.6M | 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 | 49.7M | const LiveIntervalUnion &NewLiveUnion) { |
122 | 49.7M | LiveUnion = &NewLiveUnion; |
123 | 49.7M | LR = &NewLR; |
124 | 49.7M | InterferingVRegs.clear(); |
125 | 49.7M | CheckedFirstInterference = false; |
126 | 49.7M | SeenAllInterferences = false; |
127 | 49.7M | Tag = NewLiveUnion.getTag(); |
128 | 49.7M | UserTag = NewUserTag; |
129 | 49.7M | } |
130 | | |
131 | | public: |
132 | 5.83M | Query() = default; |
133 | | Query(const LiveRange &LR, const LiveIntervalUnion &LIU): |
134 | 154M | 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 | 86.3M | const LiveIntervalUnion &NewLiveUnion) { |
140 | 86.3M | if (UserTag == NewUserTag && 86.3M LR == &NewLR36.7M && LiveUnion == &NewLiveUnion36.5M && |
141 | 86.3M | !NewLiveUnion.changedSince(Tag)36.5M ) { |
142 | 36.5M | // Retain cached results, e.g. firstInterference. |
143 | 36.5M | return; |
144 | 36.5M | } |
145 | 49.7M | reset(NewUserTag, NewLR, NewLiveUnion); |
146 | 49.7M | } |
147 | | |
148 | | // Does this live virtual register interfere with the union? |
149 | 222M | 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 *VReg) const; |
158 | | |
159 | | // Did collectInterferingVRegs collect all interferences? |
160 | 0 | bool seenAllInterferences() const { return SeenAllInterferences; } |
161 | | |
162 | | // Vector generated by collectInterferingVRegs. |
163 | 36.2M | const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { |
164 | 36.2M | return InterferingVRegs; |
165 | 36.2M | } |
166 | | }; |
167 | | |
168 | | // Array of LiveIntervalUnions. |
169 | | class Array { |
170 | | unsigned Size = 0; |
171 | | LiveIntervalUnion *LIUs = nullptr; |
172 | | |
173 | | public: |
174 | 31.8k | Array() = default; |
175 | 31.7k | ~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 | 1.17M | unsigned size() const { return Size; } |
182 | | |
183 | | void clear(); |
184 | | |
185 | 328M | LiveIntervalUnion& operator[](unsigned idx) { |
186 | 328M | assert(idx < Size && "idx out of bounds"); |
187 | 328M | return LIUs[idx]; |
188 | 328M | } |
189 | | |
190 | 1.85M | const LiveIntervalUnion& operator[](unsigned Idx) const { |
191 | 1.85M | assert(Idx < Size && "Idx out of bounds"); |
192 | 1.85M | return LIUs[Idx]; |
193 | 1.85M | } |
194 | | }; |
195 | | }; |
196 | | |
197 | | } // end namespace llvm |
198 | | |
199 | | #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H |