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.
Split(LiveRange * range,int pos)28 LiveRange* Split(LiveRange* range, int pos) {
29 return range->SplitAt(LifetimePosition::FromInt(pos), zone());
30 }
31
32
Splinter(TopLevelLiveRange * top,int start,int end,int new_id=0)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.
RangesMatch(LiveRange * first,LiveRange * second)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
TEST_F(LiveRangeUnitTest,InvalidConstruction)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
TEST_F(LiveRangeUnitTest,SplitInvalidStart)85 TEST_F(LiveRangeUnitTest, SplitInvalidStart) {
86 TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 1);
87 V8_ASSERT_DEBUG_DEATH(Split(range, 0), ".*");
88 }
89
90
TEST_F(LiveRangeUnitTest,DISABLE_IN_RELEASE (InvalidSplitEnd))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
TEST_F(LiveRangeUnitTest,DISABLE_IN_RELEASE (SplitInvalidPreStart))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
TEST_F(LiveRangeUnitTest,DISABLE_IN_RELEASE (SplitInvalidPostEnd))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
TEST_F(LiveRangeUnitTest,SplitSingleIntervalNoUsePositions)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalNoUsePositionsBetween)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalNoUsePositionsFront)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalNoUsePositionsAfter)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
TEST_F(LiveRangeUnitTest,SplitSingleIntervalUsePositions)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
TEST_F(LiveRangeUnitTest,SplitSingleIntervalUsePositionsAtPos)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalUsePositionsBetween)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalUsePositionsAtInterval)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalUsePositionsFront)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
TEST_F(LiveRangeUnitTest,SplitManyIntervalUsePositionsAfter)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
TEST_F(LiveRangeUnitTest,SplinterSingleInterval)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
TEST_F(LiveRangeUnitTest,MergeSingleInterval)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
TEST_F(LiveRangeUnitTest,SplinterMultipleIntervalsOutside)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
TEST_F(LiveRangeUnitTest,MergeMultipleIntervalsOutside)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
TEST_F(LiveRangeUnitTest,SplinterMultipleIntervalsInside)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
TEST_F(LiveRangeUnitTest,SplinterMultipleIntervalsLeft)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
TEST_F(LiveRangeUnitTest,MergeMultipleIntervalsLeft)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
TEST_F(LiveRangeUnitTest,SplinterMultipleIntervalsRight)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
TEST_F(LiveRangeUnitTest,SplinterMergeMultipleTimes)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
TEST_F(LiveRangeUnitTest,MergeMultipleIntervalsRight)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
TEST_F(LiveRangeUnitTest,MergeAfterSplitting)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
TEST_F(LiveRangeUnitTest,IDGeneration)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
465