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