/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveIntervalUnion.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | #include "llvm/CodeGen/LiveIntervalUnion.h" |
17 | | #include "llvm/ADT/STLExtras.h" |
18 | | #include "llvm/ADT/SparseBitVector.h" |
19 | | #include "llvm/CodeGen/LiveInterval.h" |
20 | | #include "llvm/Support/raw_ostream.h" |
21 | | #include "llvm/Target/TargetRegisterInfo.h" |
22 | | #include <cassert> |
23 | | #include <cstdlib> |
24 | | |
25 | | using namespace llvm; |
26 | | |
27 | | #define DEBUG_TYPE "regalloc" |
28 | | |
29 | | // Merge a LiveInterval's segments. Guarantee no overlaps. |
30 | 10.7M | void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) { |
31 | 10.7M | if (Range.empty()) |
32 | 9.43k | return; |
33 | 10.7M | ++Tag; |
34 | 10.7M | |
35 | 10.7M | // Insert each of the virtual register's live segments into the map. |
36 | 10.7M | LiveRange::const_iterator RegPos = Range.begin(); |
37 | 10.7M | LiveRange::const_iterator RegEnd = Range.end(); |
38 | 10.7M | SegmentIter SegPos = Segments.find(RegPos->start); |
39 | 10.7M | |
40 | 12.3M | while (SegPos.valid()12.3M ) { |
41 | 5.06M | SegPos.insert(RegPos->start, RegPos->end, &VirtReg); |
42 | 5.06M | if (++RegPos == RegEnd) |
43 | 3.47M | return; |
44 | 1.58M | SegPos.advanceTo(RegPos->start); |
45 | 1.58M | } |
46 | 10.7M | |
47 | 10.7M | // We have reached the end of Segments, so it is no longer necessary to search |
48 | 10.7M | // for the insertion position. |
49 | 10.7M | // It is faster to insert the end first. |
50 | 7.30M | --RegEnd; |
51 | 7.30M | SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg); |
52 | 12.2M | for (; RegPos != RegEnd12.2M ; ++RegPos, ++SegPos4.93M ) |
53 | 4.93M | SegPos.insert(RegPos->start, RegPos->end, &VirtReg); |
54 | 10.7M | } |
55 | | |
56 | | // Remove a live virtual register's segments from this union. |
57 | 620k | void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) { |
58 | 620k | if (Range.empty()) |
59 | 0 | return; |
60 | 620k | ++Tag; |
61 | 620k | |
62 | 620k | // Remove each of the virtual register's live segments from the map. |
63 | 620k | LiveRange::const_iterator RegPos = Range.begin(); |
64 | 620k | LiveRange::const_iterator RegEnd = Range.end(); |
65 | 620k | SegmentIter SegPos = Segments.find(RegPos->start); |
66 | 620k | |
67 | 1.08M | while (true1.08M ) { |
68 | 1.08M | assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval"); |
69 | 1.08M | SegPos.erase(); |
70 | 1.08M | if (!SegPos.valid()) |
71 | 428k | return; |
72 | 653k | |
73 | 653k | // Skip all segments that may have been coalesced. |
74 | 653k | RegPos = Range.advanceTo(RegPos, SegPos.start()); |
75 | 653k | if (RegPos == RegEnd) |
76 | 192k | return; |
77 | 461k | |
78 | 461k | SegPos.advanceTo(RegPos->start); |
79 | 461k | } |
80 | 620k | } |
81 | | |
82 | | void |
83 | 0 | LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { |
84 | 0 | if (empty()0 ) { |
85 | 0 | OS << " empty\n"; |
86 | 0 | return; |
87 | 0 | } |
88 | 0 | for (LiveSegments::const_iterator SI = Segments.begin(); 0 SI.valid()0 ; ++SI0 ) { |
89 | 0 | OS << " [" << SI.start() << ' ' << SI.stop() << "):" |
90 | 0 | << PrintReg(SI.value()->reg, TRI); |
91 | 0 | } |
92 | 0 | OS << '\n'; |
93 | 0 | } |
94 | | |
95 | | #ifndef NDEBUG |
96 | | // Verify the live intervals in this union and add them to the visited set. |
97 | | void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { |
98 | | for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI) |
99 | | VisitedVRegs.set(SI.value()->reg); |
100 | | } |
101 | | #endif //!NDEBUG |
102 | | |
103 | | // Scan the vector of interfering virtual registers in this union. Assume it's |
104 | | // quite small. |
105 | 222M | bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { |
106 | 222M | return is_contained(InterferingVRegs, VirtReg); |
107 | 222M | } |
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 | | // |
118 | | unsigned LiveIntervalUnion::Query:: |
119 | 240M | collectInterferingVRegs(unsigned MaxInterferingRegs) { |
120 | 240M | // Fast path return if we already have the desired information. |
121 | 240M | if (SeenAllInterferences || 240M InterferingVRegs.size() >= MaxInterferingRegs240M ) |
122 | 18.8M | return InterferingVRegs.size(); |
123 | 221M | |
124 | 221M | // Set up iterators on the first call. |
125 | 221M | if (221M !CheckedFirstInterference221M ) { |
126 | 204M | CheckedFirstInterference = true; |
127 | 204M | |
128 | 204M | // Quickly skip interference check for empty sets. |
129 | 204M | if (LR->empty() || 204M LiveUnion->empty()204M ) { |
130 | 3.70M | SeenAllInterferences = true; |
131 | 3.70M | return 0; |
132 | 3.70M | } |
133 | 200M | |
134 | 200M | // In most cases, the union will start before LR. |
135 | 200M | LRI = LR->begin(); |
136 | 200M | LiveUnionI.setMap(LiveUnion->getMap()); |
137 | 200M | LiveUnionI.find(LRI->start); |
138 | 200M | } |
139 | 221M | |
140 | 218M | LiveRange::const_iterator LREnd = LR->end(); |
141 | 218M | LiveInterval *RecentReg = nullptr; |
142 | 252M | while (LiveUnionI.valid()252M ) { |
143 | 249M | assert(LRI != LREnd && "Reached end of LR"); |
144 | 249M | |
145 | 249M | // Check for overlapping interference. |
146 | 266M | while (LRI->start < LiveUnionI.stop() && 266M LRI->end > LiveUnionI.start()266M ) { |
147 | 223M | // This is an overlap, record the interfering register. |
148 | 223M | LiveInterval *VReg = LiveUnionI.value(); |
149 | 223M | if (VReg != RecentReg && 223M !isSeenInterference(VReg)222M ) { |
150 | 197M | RecentReg = VReg; |
151 | 197M | InterferingVRegs.push_back(VReg); |
152 | 197M | if (InterferingVRegs.size() >= MaxInterferingRegs) |
153 | 193M | return InterferingVRegs.size(); |
154 | 29.6M | } |
155 | 29.6M | // This LiveUnion segment is no longer interesting. |
156 | 29.6M | if (29.6M !(++LiveUnionI).valid()29.6M ) { |
157 | 12.1M | SeenAllInterferences = true; |
158 | 12.1M | return InterferingVRegs.size(); |
159 | 12.1M | } |
160 | 223M | } |
161 | 249M | |
162 | 249M | // The iterators are now not overlapping, LiveUnionI has been advanced |
163 | 249M | // beyond LRI. |
164 | 43.7M | assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap"); |
165 | 43.7M | |
166 | 43.7M | // Advance the iterator that ends first. |
167 | 43.7M | LRI = LR->advanceTo(LRI, LiveUnionI.start()); |
168 | 43.7M | if (LRI == LREnd) |
169 | 8.95M | break; |
170 | 34.8M | |
171 | 34.8M | // Detect overlap, handle above. |
172 | 34.8M | if (34.8M LRI->start < LiveUnionI.stop()34.8M ) |
173 | 33.8M | continue; |
174 | 1.01M | |
175 | 1.01M | // Still not overlapping. Catch up LiveUnionI. |
176 | 1.01M | LiveUnionI.advanceTo(LRI->start); |
177 | 1.01M | } |
178 | 12.3M | SeenAllInterferences = true; |
179 | 12.3M | return InterferingVRegs.size(); |
180 | 240M | } |
181 | | |
182 | | void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, |
183 | 587k | unsigned NSize) { |
184 | 587k | // Reuse existing allocation. |
185 | 587k | if (NSize == Size) |
186 | 556k | return; |
187 | 30.8k | clear(); |
188 | 30.8k | Size = NSize; |
189 | 30.8k | LIUs = static_cast<LiveIntervalUnion*>( |
190 | 30.8k | malloc(sizeof(LiveIntervalUnion)*NSize)); |
191 | 5.86M | for (unsigned i = 0; i != Size5.86M ; ++i5.83M ) |
192 | 5.83M | new(LIUs + i) LiveIntervalUnion(Alloc); |
193 | 587k | } |
194 | | |
195 | 62.5k | void LiveIntervalUnion::Array::clear() { |
196 | 62.5k | if (!LIUs) |
197 | 31.7k | return; |
198 | 5.86M | for (unsigned i = 0; 30.8k i != Size5.86M ; ++i5.82M ) |
199 | 5.82M | LIUs[i].~LiveIntervalUnion(); |
200 | 62.5k | free(LIUs); |
201 | 62.5k | Size = 0; |
202 | 62.5k | LIUs = nullptr; |
203 | 62.5k | } |