OLD | NEW |
| (Empty) |
1 // Copyright 2014 the V8 project authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "src/compiler/coalesced-live-ranges.h" | |
6 #include "test/unittests/compiler/live-range-builder.h" | |
7 #include "test/unittests/test-utils.h" | |
8 | |
9 namespace v8 { | |
10 namespace internal { | |
11 namespace compiler { | |
12 | |
13 | |
14 class CoalescedLiveRangesTest : public TestWithZone { | |
15 public: | |
16 CoalescedLiveRangesTest() : TestWithZone(), ranges_(zone()) {} | |
17 bool HasNoConflicts(const LiveRange* range); | |
18 bool ConflictsPreciselyWith(const LiveRange* range, int id); | |
19 bool ConflictsPreciselyWith(const LiveRange* range, int id1, int id2); | |
20 | |
21 CoalescedLiveRanges& ranges() { return ranges_; } | |
22 const CoalescedLiveRanges& ranges() const { return ranges_; } | |
23 bool AllocationsAreValid() const; | |
24 void RemoveConflicts(LiveRange* range); | |
25 | |
26 private: | |
27 typedef ZoneSet<int> LiveRangeIDs; | |
28 bool IsRangeConflictingWith(const LiveRange* range, const LiveRangeIDs& ids); | |
29 CoalescedLiveRanges ranges_; | |
30 }; | |
31 | |
32 | |
33 bool CoalescedLiveRangesTest::ConflictsPreciselyWith(const LiveRange* range, | |
34 int id) { | |
35 LiveRangeIDs set(zone()); | |
36 set.insert(id); | |
37 return IsRangeConflictingWith(range, set); | |
38 } | |
39 | |
40 | |
41 bool CoalescedLiveRangesTest::ConflictsPreciselyWith(const LiveRange* range, | |
42 int id1, int id2) { | |
43 LiveRangeIDs set(zone()); | |
44 set.insert(id1); | |
45 set.insert(id2); | |
46 return IsRangeConflictingWith(range, set); | |
47 } | |
48 | |
49 | |
50 bool CoalescedLiveRangesTest::HasNoConflicts(const LiveRange* range) { | |
51 LiveRangeIDs set(zone()); | |
52 return IsRangeConflictingWith(range, set); | |
53 } | |
54 | |
55 | |
56 void CoalescedLiveRangesTest::RemoveConflicts(LiveRange* range) { | |
57 auto conflicts = ranges().GetConflicts(range); | |
58 LiveRangeIDs seen(zone()); | |
59 for (auto c = conflicts.Current(); c != nullptr; | |
60 c = conflicts.RemoveCurrentAndGetNext()) { | |
61 int id = c->TopLevel()->vreg(); | |
62 EXPECT_FALSE(seen.count(id) > 0); | |
63 seen.insert(c->TopLevel()->vreg()); | |
64 } | |
65 } | |
66 | |
67 | |
68 bool CoalescedLiveRangesTest::AllocationsAreValid() const { | |
69 return ranges().VerifyAllocationsAreValidForTesting(); | |
70 } | |
71 | |
72 | |
73 bool CoalescedLiveRangesTest::IsRangeConflictingWith(const LiveRange* range, | |
74 const LiveRangeIDs& ids) { | |
75 LiveRangeIDs found_ids(zone()); | |
76 | |
77 auto conflicts = ranges().GetConflicts(range); | |
78 for (auto conflict = conflicts.Current(); conflict != nullptr; | |
79 conflict = conflicts.GetNext()) { | |
80 found_ids.insert(conflict->TopLevel()->vreg()); | |
81 } | |
82 return found_ids == ids; | |
83 } | |
84 | |
85 | |
86 TEST_F(CoalescedLiveRangesTest, VisitEmptyAllocations) { | |
87 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5); | |
88 ASSERT_TRUE(ranges().empty()); | |
89 ASSERT_TRUE(AllocationsAreValid()); | |
90 ASSERT_TRUE(HasNoConflicts(range)); | |
91 } | |
92 | |
93 | |
94 TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterAllocations) { | |
95 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(5, 6); | |
96 ranges().AllocateRange(range); | |
97 ASSERT_FALSE(ranges().empty()); | |
98 ASSERT_TRUE(AllocationsAreValid()); | |
99 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 2); | |
100 ASSERT_TRUE(HasNoConflicts(query)); | |
101 query = TestRangeBuilder(zone()).Id(3).Build(1, 5); | |
102 ASSERT_TRUE(HasNoConflicts(query)); | |
103 } | |
104 | |
105 | |
106 TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterManyAllocations) { | |
107 LiveRange* range = | |
108 TestRangeBuilder(zone()).Id(1).Add(5, 7).Add(10, 12).Build(); | |
109 ranges().AllocateRange(range); | |
110 ASSERT_FALSE(ranges().empty()); | |
111 ASSERT_TRUE(AllocationsAreValid()); | |
112 LiveRange* query = | |
113 TestRangeBuilder(zone()).Id(2).Add(1, 2).Add(13, 15).Build(); | |
114 ASSERT_TRUE(HasNoConflicts(query)); | |
115 query = TestRangeBuilder(zone()).Id(3).Add(1, 5).Add(12, 15).Build(); | |
116 ASSERT_TRUE(HasNoConflicts(query)); | |
117 } | |
118 | |
119 | |
120 TEST_F(CoalescedLiveRangesTest, SelfConflictsPreciselyWithSelf) { | |
121 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5); | |
122 ranges().AllocateRange(range); | |
123 ASSERT_FALSE(ranges().empty()); | |
124 ASSERT_TRUE(AllocationsAreValid()); | |
125 ASSERT_TRUE(ConflictsPreciselyWith(range, 1)); | |
126 range = TestRangeBuilder(zone()).Id(2).Build(8, 10); | |
127 ranges().AllocateRange(range); | |
128 ASSERT_TRUE(ConflictsPreciselyWith(range, 2)); | |
129 } | |
130 | |
131 | |
132 TEST_F(CoalescedLiveRangesTest, QueryStartsBeforeConflict) { | |
133 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5); | |
134 ranges().AllocateRange(range); | |
135 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 3); | |
136 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
137 range = TestRangeBuilder(zone()).Id(3).Build(8, 10); | |
138 ranges().AllocateRange(range); | |
139 query = TestRangeBuilder(zone()).Id(4).Build(6, 9); | |
140 ASSERT_TRUE(ConflictsPreciselyWith(query, 3)); | |
141 } | |
142 | |
143 | |
144 TEST_F(CoalescedLiveRangesTest, QueryStartsInConflict) { | |
145 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5); | |
146 ranges().AllocateRange(range); | |
147 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(3, 6); | |
148 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
149 range = TestRangeBuilder(zone()).Id(3).Build(8, 10); | |
150 ranges().AllocateRange(range); | |
151 query = TestRangeBuilder(zone()).Id(4).Build(9, 11); | |
152 ASSERT_TRUE(ConflictsPreciselyWith(query, 3)); | |
153 } | |
154 | |
155 | |
156 TEST_F(CoalescedLiveRangesTest, QueryContainedInConflict) { | |
157 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5); | |
158 ranges().AllocateRange(range); | |
159 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 3); | |
160 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
161 } | |
162 | |
163 | |
164 TEST_F(CoalescedLiveRangesTest, QueryContainsConflict) { | |
165 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 3); | |
166 ranges().AllocateRange(range); | |
167 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 5); | |
168 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
169 } | |
170 | |
171 | |
172 TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsSameRange) { | |
173 LiveRange* range = | |
174 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(7, 9).Add(20, 25).Build(); | |
175 ranges().AllocateRange(range); | |
176 LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 8); | |
177 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
178 } | |
179 | |
180 | |
181 TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsDifferentRanges) { | |
182 LiveRange* range = | |
183 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(20, 25).Build(); | |
184 ranges().AllocateRange(range); | |
185 range = TestRangeBuilder(zone()).Id(2).Build(7, 10); | |
186 ranges().AllocateRange(range); | |
187 LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(2, 22); | |
188 ASSERT_TRUE(ConflictsPreciselyWith(query, 1, 2)); | |
189 } | |
190 | |
191 | |
192 TEST_F(CoalescedLiveRangesTest, QueryFitsInGaps) { | |
193 LiveRange* range = | |
194 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 15).Add(20, 25).Build(); | |
195 ranges().AllocateRange(range); | |
196 LiveRange* query = | |
197 TestRangeBuilder(zone()).Id(3).Add(5, 10).Add(16, 19).Add(27, 30).Build(); | |
198 ASSERT_TRUE(HasNoConflicts(query)); | |
199 } | |
200 | |
201 | |
202 TEST_F(CoalescedLiveRangesTest, DeleteConflictBefore) { | |
203 LiveRange* range = TestRangeBuilder(zone()).Id(1).Add(1, 4).Add(5, 6).Build(); | |
204 ranges().AllocateRange(range); | |
205 range = TestRangeBuilder(zone()).Id(2).Build(40, 50); | |
206 ranges().AllocateRange(range); | |
207 LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(3, 7); | |
208 RemoveConflicts(query); | |
209 query = TestRangeBuilder(zone()).Id(4).Build(0, 60); | |
210 ASSERT_TRUE(ConflictsPreciselyWith(query, 2)); | |
211 } | |
212 | |
213 | |
214 TEST_F(CoalescedLiveRangesTest, DeleteConflictAfter) { | |
215 LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5); | |
216 ranges().AllocateRange(range); | |
217 range = TestRangeBuilder(zone()).Id(2).Add(40, 50).Add(60, 70).Build(); | |
218 ranges().AllocateRange(range); | |
219 LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(45, 60); | |
220 RemoveConflicts(query); | |
221 query = TestRangeBuilder(zone()).Id(4).Build(0, 60); | |
222 ASSERT_TRUE(ConflictsPreciselyWith(query, 1)); | |
223 } | |
224 | |
225 | |
226 TEST_F(CoalescedLiveRangesTest, DeleteConflictStraddle) { | |
227 LiveRange* range = | |
228 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 20).Build(); | |
229 ranges().AllocateRange(range); | |
230 range = TestRangeBuilder(zone()).Id(2).Build(40, 50); | |
231 ranges().AllocateRange(range); | |
232 LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15); | |
233 RemoveConflicts(query); | |
234 query = TestRangeBuilder(zone()).Id(4).Build(0, 60); | |
235 ASSERT_TRUE(ConflictsPreciselyWith(query, 2)); | |
236 } | |
237 | |
238 | |
239 TEST_F(CoalescedLiveRangesTest, DeleteConflictManyOverlapsBefore) { | |
240 LiveRange* range = | |
241 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(6, 10).Add(10, 20).Build(); | |
242 ranges().AllocateRange(range); | |
243 range = TestRangeBuilder(zone()).Id(2).Build(40, 50); | |
244 ranges().AllocateRange(range); | |
245 LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15); | |
246 RemoveConflicts(query); | |
247 query = TestRangeBuilder(zone()).Id(4).Build(0, 60); | |
248 ASSERT_TRUE(ConflictsPreciselyWith(query, 2)); | |
249 } | |
250 | |
251 | |
252 TEST_F(CoalescedLiveRangesTest, DeleteWhenConflictRepeatsAfterNonConflict) { | |
253 LiveRange* range = | |
254 TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(6, 10).Add(20, 30).Build(); | |
255 ranges().AllocateRange(range); | |
256 range = TestRangeBuilder(zone()).Id(2).Build(12, 15); | |
257 ranges().AllocateRange(range); | |
258 LiveRange* query = | |
259 TestRangeBuilder(zone()).Id(3).Add(1, 8).Add(22, 25).Build(); | |
260 RemoveConflicts(query); | |
261 query = TestRangeBuilder(zone()).Id(4).Build(0, 60); | |
262 ASSERT_TRUE(ConflictsPreciselyWith(query, 2)); | |
263 } | |
264 | |
265 | |
266 } // namespace compiler | |
267 } // namespace internal | |
268 } // namespace v8 | |
OLD | NEW |