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 ArenaPoolAndAllocator pool;
27 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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 ArenaPoolAndAllocator pool;
44 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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 ArenaPoolAndAllocator pool;
72 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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 ArenaPoolAndAllocator pool;
100 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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 ArenaPoolAndAllocator pool;
192 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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 ArenaPoolAndAllocator pool;
283 ScopedArenaAllocator* allocator = pool.GetScopedAllocator();
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