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 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 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 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 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 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 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 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
