1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "base/arena_allocator.h"
18 #include "optimizing_unit_test.h"
19 #include "ssa_liveness_analysis.h"
20 
21 #include "gtest/gtest.h"
22 
23 namespace art {
24 
TEST(LiveInterval,GetStart)25 TEST(LiveInterval, GetStart) {
26   ArenaPool pool;
27   ArenaAllocator allocator(&pool);
28 
29   {
30     static constexpr size_t ranges[][2] = {{0, 42}};
31     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
32     ASSERT_EQ(0u, interval->GetStart());
33   }
34 
35   {
36     static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}};
37     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
38     ASSERT_EQ(4u, interval->GetStart());
39   }
40 }
41 
TEST(LiveInterval,IsDeadAt)42 TEST(LiveInterval, IsDeadAt) {
43   ArenaPool pool;
44   ArenaAllocator allocator(&pool);
45 
46   {
47     static constexpr size_t ranges[][2] = {{0, 42}};
48     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
49     ASSERT_TRUE(interval->IsDeadAt(42));
50     ASSERT_TRUE(interval->IsDeadAt(43));
51     ASSERT_FALSE(interval->IsDeadAt(41));
52     ASSERT_FALSE(interval->IsDeadAt(0));
53     ASSERT_FALSE(interval->IsDeadAt(22));
54   }
55 
56   {
57     static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}};
58     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
59     ASSERT_TRUE(interval->IsDeadAt(16));
60     ASSERT_TRUE(interval->IsDeadAt(32));
61     ASSERT_FALSE(interval->IsDeadAt(0));
62     ASSERT_FALSE(interval->IsDeadAt(4));
63     ASSERT_FALSE(interval->IsDeadAt(12));
64     ASSERT_FALSE(interval->IsDeadAt(13));
65     ASSERT_FALSE(interval->IsDeadAt(14));
66     ASSERT_FALSE(interval->IsDeadAt(15));
67   }
68 }
69 
TEST(LiveInterval,Covers)70 TEST(LiveInterval, Covers) {
71   ArenaPool pool;
72   ArenaAllocator allocator(&pool);
73 
74   {
75     static constexpr size_t ranges[][2] = {{0, 42}};
76     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
77     ASSERT_TRUE(interval->Covers(0));
78     ASSERT_TRUE(interval->Covers(4));
79     ASSERT_TRUE(interval->Covers(41));
80     ASSERT_FALSE(interval->Covers(42));
81     ASSERT_FALSE(interval->Covers(54));
82   }
83 
84   {
85     static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}};
86     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
87     ASSERT_FALSE(interval->Covers(0));
88     ASSERT_TRUE(interval->Covers(4));
89     ASSERT_TRUE(interval->Covers(11));
90     ASSERT_FALSE(interval->Covers(12));
91     ASSERT_FALSE(interval->Covers(13));
92     ASSERT_TRUE(interval->Covers(14));
93     ASSERT_TRUE(interval->Covers(15));
94     ASSERT_FALSE(interval->Covers(16));
95   }
96 }
97 
TEST(LiveInterval,FirstIntersectionWith)98 TEST(LiveInterval, FirstIntersectionWith) {
99   ArenaPool pool;
100   ArenaAllocator allocator(&pool);
101 
102   {
103     static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}};
104     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
105     static constexpr size_t ranges2[][2] = {{5, 6}};
106     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
107 
108     ASSERT_EQ(kNoLifetime, interval1->FirstIntersectionWith(interval2));
109   }
110 
111   {
112     static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}};
113     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
114     static constexpr size_t ranges2[][2] = {{5, 42}};
115     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
116 
117     ASSERT_EQ(8u, interval1->FirstIntersectionWith(interval2));
118   }
119 
120   {
121     static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}};
122     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
123     static constexpr size_t ranges2[][2] = {{5, 6}, {7, 8}, {11, 12}};
124     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
125 
126     ASSERT_EQ(kNoLifetime, interval1->FirstIntersectionWith(interval2));
127   }
128 
129   {
130     static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}};
131     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
132     static constexpr size_t ranges2[][2] = {{5, 6}, {7, 8}, {9, 10}};
133     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
134 
135     ASSERT_EQ(9u, interval1->FirstIntersectionWith(interval2));
136   }
137 
138   {
139     static constexpr size_t ranges1[][2] = {{0, 1}, {2, 7}, {8, 10}};
140     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
141     static constexpr size_t ranges2[][2] = {{1, 2}, {6, 7}, {9, 10}};
142     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
143 
144     ASSERT_EQ(6u, interval1->FirstIntersectionWith(interval2));
145   }
146 
147   {
148     static constexpr size_t ranges1[][2] = {{0, 1}, {2, 8}, {55, 58}};
149     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
150     static constexpr size_t ranges2[][2] = {{1, 2}, {11, 42}, {43, 48}, {54, 56}};
151     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
152 
153     ASSERT_EQ(55u, interval1->FirstIntersectionWith(interval2));
154   }
155 
156   {
157     static constexpr size_t ranges1[][2] = {{0, 1}, {2, 8}, {15, 18}, {27, 32}, {41, 53}, {54, 60}};
158     LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator);
159     static constexpr size_t ranges2[][2] = {{1, 2}, {11, 12}, {19, 25}, {34, 42}, {52, 60}};
160     LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator);
161 
162     ASSERT_EQ(41u, interval1->FirstIntersectionWith(interval2));
163   }
164 }
165 
RangesEquals(LiveInterval * interval,const size_t expected[][2],size_t number_of_expected_ranges)166 static bool RangesEquals(LiveInterval* interval,
167                          const size_t expected[][2],
168                          size_t number_of_expected_ranges) {
169   LiveRange* current = interval->GetFirstRange();
170 
171   size_t i = 0;
172   for (;
173        i < number_of_expected_ranges && current != nullptr;
174        ++i, current = current->GetNext()) {
175     if (expected[i][0] != current->GetStart()) {
176       return false;
177     }
178     if (expected[i][1] != current->GetEnd()) {
179       return false;
180     }
181   }
182 
183   if (current != nullptr || i != number_of_expected_ranges) {
184     return false;
185   }
186 
187   return true;
188 }
189 
TEST(LiveInterval,SplitAt)190 TEST(LiveInterval, SplitAt) {
191   ArenaPool pool;
192   ArenaAllocator allocator(&pool);
193 
194   {
195     // Test within one range.
196     static constexpr size_t ranges[][2] = {{0, 4}};
197     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
198     LiveInterval* split = interval->SplitAt(1);
199     static constexpr size_t expected[][2] = {{0, 1}};
200     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
201     static constexpr size_t expected_split[][2] = {{1, 4}};
202     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
203   }
204 
205   {
206     // Test just before the end of one range.
207     static constexpr size_t ranges[][2] = {{0, 4}};
208     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
209     LiveInterval* split = interval->SplitAt(3);
210     static constexpr size_t expected[][2] = {{0, 3}};
211     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
212     static constexpr size_t expected_split[][2] = {{3, 4}};
213     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
214   }
215 
216   {
217     // Test withing the first range.
218     static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}};
219     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
220     LiveInterval* split = interval->SplitAt(1);
221     static constexpr size_t expected[][2] = {{0, 1}};
222     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
223     static constexpr size_t expected_split[][2] = {{1, 4}, {8, 12}};
224     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
225   }
226 
227   {
228     // Test in a hole.
229     static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}};
230     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
231     LiveInterval* split = interval->SplitAt(5);
232     static constexpr size_t expected[][2] = {{0, 4}};
233     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
234     static constexpr size_t expected_split[][2] = {{8, 12}};
235     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
236   }
237 
238   {
239     // Test withing the second range.
240     static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}};
241     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
242     LiveInterval* split = interval->SplitAt(9);
243     static constexpr size_t expected[][2] = {{0, 4}, {8, 9}};
244     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
245     static constexpr size_t expected_split[][2] = {{9, 12}};
246     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
247   }
248 
249   {
250     // Test at the beginning of the second range.
251     static constexpr size_t ranges[][2] = {{0, 4}, {6, 10}};
252     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
253     LiveInterval* split = interval->SplitAt(6);
254     static constexpr size_t expected[][2] = {{0, 4}};
255     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
256     static constexpr size_t expected_split[][2] = {{6, 10}};
257     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
258   }
259 
260   {
261     // Test at the end of the first range.
262     static constexpr size_t ranges[][2] = {{0, 4}, {6, 10}};
263     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
264     LiveInterval* split = interval->SplitAt(4);
265     static constexpr size_t expected[][2] = {{0, 4}};
266     ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected)));
267     static constexpr size_t expected_split[][2] = {{6, 10}};
268     ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split)));
269   }
270 
271   {
272     // Test that we get null if we split at a position where the interval is dead.
273     static constexpr size_t ranges[][2] = {{0, 4}};
274     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
275     LiveInterval* split = interval->SplitAt(5);
276     ASSERT_TRUE(split == nullptr);
277     ASSERT_TRUE(RangesEquals(interval, ranges, arraysize(ranges)));
278   }
279 }
280 
TEST(LiveInterval,AddLoopRange)281 TEST(LiveInterval, AddLoopRange) {
282   ArenaPool pool;
283   ArenaAllocator allocator(&pool);
284 
285   {
286     // Test when only used in a loop.
287     static constexpr size_t ranges[][2] = {{0, 4}};
288     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
289     interval->AddLoopRange(0, 8);
290     LiveRange* range = interval->GetFirstRange();
291     ASSERT_TRUE(range->GetNext() == nullptr);
292     ASSERT_EQ(range->GetStart(), 0u);
293     ASSERT_EQ(range->GetEnd(), 8u);
294   }
295 
296   {
297     // Test when only used in a loop.
298     static constexpr size_t ranges[][2] = {{2, 4}};
299     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
300     interval->AddLoopRange(0, 8);
301     LiveRange* range = interval->GetFirstRange();
302     ASSERT_TRUE(range->GetNext() == nullptr);
303     ASSERT_EQ(range->GetStart(), 0u);
304     ASSERT_EQ(range->GetEnd(), 8u);
305   }
306 
307   {
308     // Test when used just after the loop.
309     static constexpr size_t ranges[][2] = {{2, 4}, {8, 10}};
310     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
311     interval->AddLoopRange(0, 8);
312     LiveRange* range = interval->GetFirstRange();
313     ASSERT_TRUE(range->GetNext() == nullptr);
314     ASSERT_EQ(range->GetStart(), 0u);
315     ASSERT_EQ(range->GetEnd(), 10u);
316   }
317 
318   {
319     // Test when use after the loop is after a lifetime hole.
320     static constexpr size_t ranges[][2] = {{2, 4}, {10, 12}};
321     LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
322     interval->AddLoopRange(0, 8);
323     LiveRange* range = interval->GetFirstRange();
324     ASSERT_EQ(range->GetStart(), 0u);
325     ASSERT_EQ(range->GetEnd(), 8u);
326     range = range->GetNext();
327     ASSERT_EQ(range->GetStart(), 10u);
328     ASSERT_EQ(range->GetEnd(), 12u);
329   }
330 }
331 
332 }  // namespace art
333