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
21namespace v8 {
22namespace internal {
23namespace compiler {
24
25class 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
74TEST_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
85TEST_F(LiveRangeUnitTest, SplitInvalidStart) {
86  TopLevelLiveRange* range = TestRangeBuilder(zone()).Build(0, 1);
87  V8_ASSERT_DEBUG_DEATH(Split(range, 0), ".*");
88}
89
90
91TEST_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
97TEST_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
103TEST_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
109TEST_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
123TEST_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
138TEST_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
154TEST_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
170TEST_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
188TEST_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
205TEST_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
222TEST_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
239TEST_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
256TEST_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
272TEST_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
287TEST_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
300TEST_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
317TEST_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
331TEST_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
338TEST_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
354TEST_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
367TEST_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
383TEST_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
402TEST_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
417TEST_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
434TEST_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