• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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