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