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