OLD | NEW |
| (Empty) |
1 // Copyright 2015 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 | |
6 #include "test/unittests/compiler/live-range-builder.h" | |
7 #include "test/unittests/test-utils.h" | |
8 | |
9 | |
10 // TODO(mtrofin): would we want to centralize this definition? | |
11 #ifdef DEBUG | |
12 #define V8_ASSERT_DEBUG_DEATH(statement, regex) \ | |
13 ASSERT_DEATH_IF_SUPPORTED(statement, regex) | |
14 #define DISABLE_IN_RELEASE(Name) Name | |
15 | |
16 #else | |
17 #define V8_ASSERT_DEBUG_DEATH(statement, regex) statement | |
18 #define DISABLE_IN_RELEASE(Name) DISABLED_##Name | |
19 #endif // DEBUG | |
20 | |
21 namespace v8 { | |
22 namespace internal { | |
23 namespace compiler { | |
24 | |
25 class LiveRangeUnitTest : public TestWithZone { | |
26 public: | |
27 // Split helper, to avoid int->LifetimePosition conversion nuisance. | |
28 LiveRange* Split(LiveRange* range, int pos) { | |
29 return range->SplitAt(LifetimePosition::FromInt(pos), zone()); | |
30 } | |
31 | |
32 | |
33 TopLevelLiveRange* Splinter(TopLevelLiveRange* top, int start, int end, | |
34 int new_id = 0) { | |
35 if (top->splinter() == nullptr) { | |
36 TopLevelLiveRange* ret = new (zone()) | |
37 TopLevelLiveRange(new_id, MachineRepresentation::kTagged); | |
38 top->SetSplinter(ret); | |
39 } | |
40 top->Splinter(LifetimePosition::FromInt(start), | |
41 LifetimePosition::FromInt(end), zone()); | |
42 return top->splinter(); | |
43 } | |
44 | |
45 // Ranges first and second match structurally. | |
46 bool RangesMatch(LiveRange* first, LiveRange* second) { | |
47 if (first->Start() != second->Start() || first->End() != second->End()) { | |
48 return false; | |
49 } | |
50 UseInterval* i1 = first->first_interval(); | |
51 UseInterval* i2 = second->first_interval(); | |
52 | |
53 while (i1 != nullptr && i2 != nullptr) { | |
54 if (i1->start() != i2->start() || i1->end() != i2->end()) return false; | |
55 i1 = i1->next(); | |
56 i2 = i2->next(); | |
57 } | |
58 if (i1 != nullptr || i2 != nullptr) return false; | |
59 | |
60 UsePosition* p1 = first->first_pos(); | |
61 UsePosition* p2 = second->first_pos(); | |
62 | |
63 while (p1 != nullptr && p2 != nullptr) { | |
64 if (p1->pos() != p2->pos()) return false; | |
65 p1 = p1->next(); | |
66 p2 = p2->next(); | |
67 } | |
68 if (p1 != nullptr || p2 != nullptr) return false; | |
69 return true; | |
70 } | |
71 }; | |
72 | |
73 | |
74 TEST_F(LiveRangeUnitTest, InvalidConstruction) { | |
75 // Build a range manually, because the builder guards against empty cases. | |
76 TopLevelLiveRange* range = | |
77 new (zone()) TopLevelLiveRange(1, MachineRepresentation::kTagged); | |
78 V8_ASSERT_DEBUG_DEATH( | |
79 range->AddUseInterval(LifetimePosition::FromInt(0), | |
80 LifetimePosition::FromInt(0), zone()), | |
81 ".*"); | |
82 } | |
83 | |
84 | |
85 TEST_F(LiveRangeUnitTest, SplitInvalidStart) { | |
86 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 1); | |
87 V8_ASSERT_DEBUG_DEATH(Split(range, 0), ".*"); | |
88 } | |
89 | |
90 | |
91 TEST_F(LiveRangeUnitTest, DISABLE_IN_RELEASE(InvalidSplitEnd)) { | |
92 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 1); | |
93 ASSERT_DEATH_IF_SUPPORTED(Split(range, 1), ".*"); | |
94 } | |
95 | |
96 | |
97 TEST_F(LiveRangeUnitTest, DISABLE_IN_RELEASE(SplitInvalidPreStart)) { | |
98 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(1, 2); | |
99 ASSERT_DEATH_IF_SUPPORTED(Split(range, 0), ".*"); | |
100 } | |
101 | |
102 | |
103 TEST_F(LiveRangeUnitTest, DISABLE_IN_RELEASE(SplitInvalidPostEnd)) { | |
104 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 1); | |
105 ASSERT_DEATH_IF_SUPPORTED(Split(range, 2), ".*"); | |
106 } | |
107 | |
108 | |
109 TEST_F(LiveRangeUnitTest, SplitSingleIntervalNoUsePositions) { | |
110 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 2); | |
111 LiveRange* child = Split(range, 1); | |
112 | |
113 EXPECT_NE(nullptr, range->next()); | |
114 EXPECT_EQ(child, range->next()); | |
115 | |
116 LiveRange* expected_top = TestRangeBuilder(zone()).Build(0, 1); | |
117 LiveRange* expected_bottom = TestRangeBuilder(zone()).Build(1, 2); | |
118 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
119 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
120 } | |
121 | |
122 | |
123 TEST_F(LiveRangeUnitTest, SplitManyIntervalNoUsePositionsBetween) { | |
124 TopLevelLiveRange* range = | |
125 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).Build(); | |
126 LiveRange* child = Split(range, 3); | |
127 | |
128 EXPECT_NE(nullptr, range->next()); | |
129 EXPECT_EQ(child, range->next()); | |
130 | |
131 LiveRange* expected_top = TestRangeBuilder(zone()).Build(0, 2); | |
132 LiveRange* expected_bottom = TestRangeBuilder(zone()).Build(4, 6); | |
133 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
134 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
135 } | |
136 | |
137 | |
138 TEST_F(LiveRangeUnitTest, SplitManyIntervalNoUsePositionsFront) { | |
139 TopLevelLiveRange* range = | |
140 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).Build(); | |
141 LiveRange* child = Split(range, 1); | |
142 | |
143 EXPECT_NE(nullptr, range->next()); | |
144 EXPECT_EQ(child, range->next()); | |
145 | |
146 LiveRange* expected_top = TestRangeBuilder(zone()).Build(0, 1); | |
147 LiveRange* expected_bottom = | |
148 TestRangeBuilder(zone()).Add(1, 2).Add(4, 6).Build(); | |
149 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
150 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
151 } | |
152 | |
153 | |
154 TEST_F(LiveRangeUnitTest, SplitManyIntervalNoUsePositionsAfter) { | |
155 TopLevelLiveRange* range = | |
156 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).Build(); | |
157 LiveRange* child = Split(range, 5); | |
158 | |
159 EXPECT_NE(nullptr, range->next()); | |
160 EXPECT_EQ(child, range->next()); | |
161 | |
162 LiveRange* expected_top = | |
163 TestRangeBuilder(zone()).Add(0, 2).Add(4, 5).Build(); | |
164 LiveRange* expected_bottom = TestRangeBuilder(zone()).Build(5, 6); | |
165 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
166 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
167 } | |
168 | |
169 | |
170 TEST_F(LiveRangeUnitTest, SplitSingleIntervalUsePositions) { | |
171 TopLevelLiveRange* range = | |
172 TestRangeBuilder(zone()).Add(0, 3).AddUse(0).AddUse(2).Build(); | |
173 | |
174 LiveRange* child = Split(range, 1); | |
175 | |
176 EXPECT_NE(nullptr, range->next()); | |
177 EXPECT_EQ(child, range->next()); | |
178 | |
179 LiveRange* expected_top = | |
180 TestRangeBuilder(zone()).Add(0, 1).AddUse(0).Build(); | |
181 LiveRange* expected_bottom = | |
182 TestRangeBuilder(zone()).Add(1, 3).AddUse(2).Build(); | |
183 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
184 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
185 } | |
186 | |
187 | |
188 TEST_F(LiveRangeUnitTest, SplitSingleIntervalUsePositionsAtPos) { | |
189 TopLevelLiveRange* range = | |
190 TestRangeBuilder(zone()).Add(0, 3).AddUse(0).AddUse(2).Build(); | |
191 | |
192 LiveRange* child = Split(range, 2); | |
193 | |
194 EXPECT_NE(nullptr, range->next()); | |
195 EXPECT_EQ(child, range->next()); | |
196 | |
197 LiveRange* expected_top = | |
198 TestRangeBuilder(zone()).Add(0, 2).AddUse(0).AddUse(2).Build(); | |
199 LiveRange* expected_bottom = TestRangeBuilder(zone()).Build(2, 3); | |
200 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
201 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
202 } | |
203 | |
204 | |
205 TEST_F(LiveRangeUnitTest, SplitManyIntervalUsePositionsBetween) { | |
206 TopLevelLiveRange* range = | |
207 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).AddUse(1).AddUse(5).Build(); | |
208 LiveRange* child = Split(range, 3); | |
209 | |
210 EXPECT_NE(nullptr, range->next()); | |
211 EXPECT_EQ(child, range->next()); | |
212 | |
213 LiveRange* expected_top = | |
214 TestRangeBuilder(zone()).Add(0, 2).AddUse(1).Build(); | |
215 LiveRange* expected_bottom = | |
216 TestRangeBuilder(zone()).Add(4, 6).AddUse(5).Build(); | |
217 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
218 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
219 } | |
220 | |
221 | |
222 TEST_F(LiveRangeUnitTest, SplitManyIntervalUsePositionsAtInterval) { | |
223 TopLevelLiveRange* range = | |
224 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).AddUse(1).AddUse(4).Build(); | |
225 LiveRange* child = Split(range, 4); | |
226 | |
227 EXPECT_NE(nullptr, range->next()); | |
228 EXPECT_EQ(child, range->next()); | |
229 | |
230 LiveRange* expected_top = | |
231 TestRangeBuilder(zone()).Add(0, 2).AddUse(1).Build(); | |
232 LiveRange* expected_bottom = | |
233 TestRangeBuilder(zone()).Add(4, 6).AddUse(4).Build(); | |
234 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
235 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
236 } | |
237 | |
238 | |
239 TEST_F(LiveRangeUnitTest, SplitManyIntervalUsePositionsFront) { | |
240 TopLevelLiveRange* range = | |
241 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).AddUse(1).AddUse(5).Build(); | |
242 LiveRange* child = Split(range, 1); | |
243 | |
244 EXPECT_NE(nullptr, range->next()); | |
245 EXPECT_EQ(child, range->next()); | |
246 | |
247 LiveRange* expected_top = | |
248 TestRangeBuilder(zone()).Add(0, 1).AddUse(1).Build(); | |
249 LiveRange* expected_bottom = | |
250 TestRangeBuilder(zone()).Add(1, 2).Add(4, 6).AddUse(5).Build(); | |
251 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
252 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
253 } | |
254 | |
255 | |
256 TEST_F(LiveRangeUnitTest, SplitManyIntervalUsePositionsAfter) { | |
257 TopLevelLiveRange* range = | |
258 TestRangeBuilder(zone()).Add(0, 2).Add(4, 6).AddUse(1).AddUse(5).Build(); | |
259 LiveRange* child = Split(range, 5); | |
260 | |
261 EXPECT_NE(nullptr, range->next()); | |
262 EXPECT_EQ(child, range->next()); | |
263 | |
264 LiveRange* expected_top = | |
265 TestRangeBuilder(zone()).Add(0, 2).Add(4, 5).AddUse(1).AddUse(5).Build(); | |
266 LiveRange* expected_bottom = TestRangeBuilder(zone()).Build(5, 6); | |
267 EXPECT_TRUE(RangesMatch(expected_top, range)); | |
268 EXPECT_TRUE(RangesMatch(expected_bottom, child)); | |
269 } | |
270 | |
271 | |
272 TEST_F(LiveRangeUnitTest, SplinterSingleInterval) { | |
273 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 6); | |
274 TopLevelLiveRange* splinter = Splinter(range, 3, 5); | |
275 EXPECT_EQ(nullptr, range->next()); | |
276 EXPECT_EQ(nullptr, splinter->next()); | |
277 EXPECT_EQ(range, splinter->splintered_from()); | |
278 | |
279 TopLevelLiveRange* expected_source = | |
280 TestRangeBuilder(zone()).Add(0, 3).Add(5, 6).Build(); | |
281 TopLevelLiveRange* expected_splinter = TestRangeBuilder(zone()).Build(3, 5); | |
282 EXPECT_TRUE(RangesMatch(expected_source, range)); | |
283 EXPECT_TRUE(RangesMatch(expected_splinter, splinter)); | |
284 } | |
285 | |
286 | |
287 TEST_F(LiveRangeUnitTest, MergeSingleInterval) { | |
288 TopLevelLiveRange* original = TestRangeBuilder(zone()).Build(0, 6); | |
289 TopLevelLiveRange* splinter = Splinter(original, 3, 5); | |
290 | |
291 original->Merge(splinter, zone()); | |
292 TopLevelLiveRange* result = TestRangeBuilder(zone()).Build(0, 6); | |
293 LiveRange* child_1 = Split(result, 3); | |
294 Split(child_1, 5); | |
295 | |
296 EXPECT_TRUE(RangesMatch(result, original)); | |
297 } | |
298 | |
299 | |
300 TEST_F(LiveRangeUnitTest, SplinterMultipleIntervalsOutside) { | |
301 TopLevelLiveRange* range = | |
302 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
303 TopLevelLiveRange* splinter = Splinter(range, 2, 6); | |
304 EXPECT_EQ(nullptr, range->next()); | |
305 EXPECT_EQ(nullptr, splinter->next()); | |
306 EXPECT_EQ(range, splinter->splintered_from()); | |
307 | |
308 TopLevelLiveRange* expected_source = | |
309 TestRangeBuilder(zone()).Add(0, 2).Add(6, 8).Build(); | |
310 TopLevelLiveRange* expected_splinter = | |
311 TestRangeBuilder(zone()).Add(2, 3).Add(5, 6).Build(); | |
312 EXPECT_TRUE(RangesMatch(expected_source, range)); | |
313 EXPECT_TRUE(RangesMatch(expected_splinter, splinter)); | |
314 } | |
315 | |
316 | |
317 TEST_F(LiveRangeUnitTest, MergeMultipleIntervalsOutside) { | |
318 TopLevelLiveRange* original = | |
319 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
320 TopLevelLiveRange* splinter = Splinter(original, 2, 6); | |
321 original->Merge(splinter, zone()); | |
322 | |
323 TopLevelLiveRange* result = | |
324 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
325 LiveRange* child_1 = Split(result, 2); | |
326 Split(child_1, 6); | |
327 EXPECT_TRUE(RangesMatch(result, original)); | |
328 } | |
329 | |
330 | |
331 TEST_F(LiveRangeUnitTest, SplinterMultipleIntervalsInside) { | |
332 TopLevelLiveRange* range = | |
333 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
334 V8_ASSERT_DEBUG_DEATH(Splinter(range, 3, 5), ".*"); | |
335 } | |
336 | |
337 | |
338 TEST_F(LiveRangeUnitTest, SplinterMultipleIntervalsLeft) { | |
339 TopLevelLiveRange* range = | |
340 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
341 TopLevelLiveRange* splinter = Splinter(range, 2, 4); | |
342 EXPECT_EQ(nullptr, range->next()); | |
343 EXPECT_EQ(nullptr, splinter->next()); | |
344 EXPECT_EQ(range, splinter->splintered_from()); | |
345 | |
346 TopLevelLiveRange* expected_source = | |
347 TestRangeBuilder(zone()).Add(0, 2).Add(5, 8).Build(); | |
348 TopLevelLiveRange* expected_splinter = TestRangeBuilder(zone()).Build(2, 3); | |
349 EXPECT_TRUE(RangesMatch(expected_source, range)); | |
350 EXPECT_TRUE(RangesMatch(expected_splinter, splinter)); | |
351 } | |
352 | |
353 | |
354 TEST_F(LiveRangeUnitTest, MergeMultipleIntervalsLeft) { | |
355 TopLevelLiveRange* original = | |
356 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
357 TopLevelLiveRange* splinter = Splinter(original, 2, 4); | |
358 original->Merge(splinter, zone()); | |
359 | |
360 TopLevelLiveRange* result = | |
361 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
362 Split(result, 2); | |
363 EXPECT_TRUE(RangesMatch(result, original)); | |
364 } | |
365 | |
366 | |
367 TEST_F(LiveRangeUnitTest, SplinterMultipleIntervalsRight) { | |
368 TopLevelLiveRange* range = | |
369 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
370 TopLevelLiveRange* splinter = Splinter(range, 4, 6); | |
371 EXPECT_EQ(nullptr, range->next()); | |
372 EXPECT_EQ(nullptr, splinter->next()); | |
373 EXPECT_EQ(range, splinter->splintered_from()); | |
374 | |
375 TopLevelLiveRange* expected_source = | |
376 TestRangeBuilder(zone()).Add(0, 3).Add(6, 8).Build(); | |
377 TopLevelLiveRange* expected_splinter = TestRangeBuilder(zone()).Build(5, 6); | |
378 EXPECT_TRUE(RangesMatch(expected_source, range)); | |
379 EXPECT_TRUE(RangesMatch(expected_splinter, splinter)); | |
380 } | |
381 | |
382 | |
383 TEST_F(LiveRangeUnitTest, SplinterMergeMultipleTimes) { | |
384 TopLevelLiveRange* range = | |
385 TestRangeBuilder(zone()).Add(0, 3).Add(5, 10).Add(12, 16).Build(); | |
386 Splinter(range, 4, 6); | |
387 Splinter(range, 8, 14); | |
388 TopLevelLiveRange* splinter = range->splinter(); | |
389 EXPECT_EQ(nullptr, range->next()); | |
390 EXPECT_EQ(nullptr, splinter->next()); | |
391 EXPECT_EQ(range, splinter->splintered_from()); | |
392 | |
393 TopLevelLiveRange* expected_source = | |
394 TestRangeBuilder(zone()).Add(0, 3).Add(6, 8).Add(14, 16).Build(); | |
395 TopLevelLiveRange* expected_splinter = | |
396 TestRangeBuilder(zone()).Add(5, 6).Add(8, 10).Add(12, 14).Build(); | |
397 EXPECT_TRUE(RangesMatch(expected_source, range)); | |
398 EXPECT_TRUE(RangesMatch(expected_splinter, splinter)); | |
399 } | |
400 | |
401 | |
402 TEST_F(LiveRangeUnitTest, MergeMultipleIntervalsRight) { | |
403 TopLevelLiveRange* original = | |
404 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
405 TopLevelLiveRange* splinter = Splinter(original, 4, 6); | |
406 original->Merge(splinter, zone()); | |
407 | |
408 TopLevelLiveRange* result = | |
409 TestRangeBuilder(zone()).Add(0, 3).Add(5, 8).Build(); | |
410 LiveRange* child_1 = Split(result, 5); | |
411 Split(child_1, 6); | |
412 | |
413 EXPECT_TRUE(RangesMatch(result, original)); | |
414 } | |
415 | |
416 | |
417 TEST_F(LiveRangeUnitTest, MergeAfterSplitting) { | |
418 TopLevelLiveRange* original = TestRangeBuilder(zone()).Build(0, 8); | |
419 TopLevelLiveRange* splinter = Splinter(original, 4, 6); | |
420 LiveRange* original_child = Split(original, 2); | |
421 Split(original_child, 7); | |
422 original->Merge(splinter, zone()); | |
423 | |
424 TopLevelLiveRange* result = TestRangeBuilder(zone()).Build(0, 8); | |
425 LiveRange* child_1 = Split(result, 2); | |
426 LiveRange* child_2 = Split(child_1, 4); | |
427 LiveRange* child_3 = Split(child_2, 6); | |
428 Split(child_3, 7); | |
429 | |
430 EXPECT_TRUE(RangesMatch(result, original)); | |
431 } | |
432 | |
433 | |
434 TEST_F(LiveRangeUnitTest, IDGeneration) { | |
435 TopLevelLiveRange* vreg = TestRangeBuilder(zone()).Id(2).Build(0, 100); | |
436 EXPECT_EQ(2, vreg->vreg()); | |
437 EXPECT_EQ(0, vreg->relative_id()); | |
438 | |
439 TopLevelLiveRange* splinter = | |
440 new (zone()) TopLevelLiveRange(101, MachineRepresentation::kTagged); | |
441 vreg->SetSplinter(splinter); | |
442 vreg->Splinter(LifetimePosition::FromInt(4), LifetimePosition::FromInt(12), | |
443 zone()); | |
444 | |
445 EXPECT_EQ(101, splinter->vreg()); | |
446 EXPECT_EQ(1, splinter->relative_id()); | |
447 | |
448 LiveRange* child = vreg->SplitAt(LifetimePosition::FromInt(50), zone()); | |
449 | |
450 EXPECT_EQ(2, child->relative_id()); | |
451 | |
452 LiveRange* splinter_child = | |
453 splinter->SplitAt(LifetimePosition::FromInt(8), zone()); | |
454 | |
455 EXPECT_EQ(1, splinter->relative_id()); | |
456 EXPECT_EQ(3, splinter_child->relative_id()); | |
457 | |
458 vreg->Merge(splinter, zone()); | |
459 EXPECT_EQ(1, splinter->relative_id()); | |
460 } | |
461 | |
462 } // namespace compiler | |
463 } // namespace internal | |
464 } // namespace v8 | |
OLD | NEW |