From a7062e05e6048c7f817d784a5b94e3122e25b1ec Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Thu, 22 May 2014 12:50:17 +0100 Subject: Add a linear scan register allocator to the optimizing compiler. This is a "by-the-book" implementation. It currently only deals with allocating registers, with no hint optimizations. The changes remaining to make it functional are: - Allocate spill slots. - Resolution and placements of Move instructions. - Connect it to the code generator. Change-Id: Ie0b2f6ba1b98da85425be721ce4afecd6b4012a4 --- compiler/optimizing/live_interval_test.cc | 281 ++++++++++++++++++++++++++++++ 1 file changed, 281 insertions(+) create mode 100644 compiler/optimizing/live_interval_test.cc (limited to 'compiler/optimizing/live_interval_test.cc') diff --git a/compiler/optimizing/live_interval_test.cc b/compiler/optimizing/live_interval_test.cc new file mode 100644 index 0000000000..3e4b83b0b1 --- /dev/null +++ b/compiler/optimizing/live_interval_test.cc @@ -0,0 +1,281 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "optimizing_unit_test.h" +#include "ssa_liveness_analysis.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +TEST(LiveInterval, GetStart) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + static constexpr size_t ranges[][2] = {{0, 42}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_EQ(0u, interval->GetStart()); + } + + { + static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_EQ(4u, interval->GetStart()); + } +} + +TEST(LiveInterval, IsDeadAt) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + static constexpr size_t ranges[][2] = {{0, 42}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_TRUE(interval->IsDeadAt(42)); + ASSERT_TRUE(interval->IsDeadAt(43)); + ASSERT_FALSE(interval->IsDeadAt(41)); + ASSERT_FALSE(interval->IsDeadAt(0)); + ASSERT_FALSE(interval->IsDeadAt(22)); + } + + { + static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_TRUE(interval->IsDeadAt(16)); + ASSERT_TRUE(interval->IsDeadAt(32)); + ASSERT_FALSE(interval->IsDeadAt(0)); + ASSERT_FALSE(interval->IsDeadAt(4)); + ASSERT_FALSE(interval->IsDeadAt(12)); + ASSERT_FALSE(interval->IsDeadAt(13)); + ASSERT_FALSE(interval->IsDeadAt(14)); + ASSERT_FALSE(interval->IsDeadAt(15)); + } +} + +TEST(LiveInterval, Covers) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + static constexpr size_t ranges[][2] = {{0, 42}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_TRUE(interval->Covers(0)); + ASSERT_TRUE(interval->Covers(4)); + ASSERT_TRUE(interval->Covers(41)); + ASSERT_FALSE(interval->Covers(42)); + ASSERT_FALSE(interval->Covers(54)); + } + + { + static constexpr size_t ranges[][2] = {{4, 12}, {14, 16}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + ASSERT_TRUE(interval->Covers(4)); + ASSERT_TRUE(interval->Covers(11)); + ASSERT_TRUE(interval->Covers(14)); + ASSERT_TRUE(interval->Covers(15)); + ASSERT_FALSE(interval->Covers(0)); + ASSERT_FALSE(interval->Covers(12)); + ASSERT_FALSE(interval->Covers(13)); + ASSERT_FALSE(interval->Covers(16)); + } +} + +TEST(LiveInterval, FirstIntersectionWith) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{5, 6}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(kNoLifetime, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{5, 42}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(8u, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{5, 6}, {7, 8}, {11, 12}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(kNoLifetime, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 4}, {8, 10}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{5, 6}, {7, 8}, {9, 10}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(9u, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 1}, {2, 7}, {8, 10}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{1, 2}, {6, 7}, {9, 10}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(6u, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 1}, {2, 8}, {55, 58}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{1, 2}, {11, 42}, {43, 48}, {54, 56}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(55u, interval1->FirstIntersectionWith(interval2)); + } + + { + static constexpr size_t ranges1[][2] = {{0, 1}, {2, 8}, {15, 18}, {27, 32}, {41, 53}, {54, 60}}; + LiveInterval* interval1 = BuildInterval(ranges1, arraysize(ranges1), &allocator); + static constexpr size_t ranges2[][2] = {{1, 2}, {11, 12}, {19, 25}, {34, 42}, {52, 60}}; + LiveInterval* interval2 = BuildInterval(ranges2, arraysize(ranges2), &allocator); + + ASSERT_EQ(41u, interval1->FirstIntersectionWith(interval2)); + } +} + +static bool RangesEquals(LiveInterval* interval, + const size_t expected[][2], + size_t number_of_expected_ranges) { + LiveRange* current = interval->GetFirstRange(); + + size_t i = 0; + for (; + i < number_of_expected_ranges && current != nullptr; + ++i, current = current->GetNext()) { + if (expected[i][0] != current->GetStart()) { + return false; + } + if (expected[i][1] != current->GetEnd()) { + return false; + } + } + + if (current != nullptr || i != number_of_expected_ranges) { + return false; + } + + return true; +} + +TEST(LiveInterval, SplitAt) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + // Test within one range. + static constexpr size_t ranges[][2] = {{0, 4}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(1); + static constexpr size_t expected[][2] = {{0, 1}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{1, 4}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test just before the end of one range. + static constexpr size_t ranges[][2] = {{0, 4}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(3); + static constexpr size_t expected[][2] = {{0, 3}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{3, 4}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test withing the first range. + static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(1); + static constexpr size_t expected[][2] = {{0, 1}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{1, 4}, {8, 12}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test in a hole. + static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(5); + static constexpr size_t expected[][2] = {{0, 4}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{8, 12}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test withing the second range. + static constexpr size_t ranges[][2] = {{0, 4}, {8, 12}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(9); + static constexpr size_t expected[][2] = {{0, 4}, {8, 9}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{9, 12}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test at the beginning of the second range. + static constexpr size_t ranges[][2] = {{0, 4}, {6, 10}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(6); + static constexpr size_t expected[][2] = {{0, 4}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{6, 10}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test at the end of the first range. + static constexpr size_t ranges[][2] = {{0, 4}, {6, 10}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(4); + static constexpr size_t expected[][2] = {{0, 4}}; + ASSERT_TRUE(RangesEquals(interval, expected, arraysize(expected))); + static constexpr size_t expected_split[][2] = {{6, 10}}; + ASSERT_TRUE(RangesEquals(split, expected_split, arraysize(expected_split))); + } + + { + // Test that we get null if we split at a position where the interval is dead. + static constexpr size_t ranges[][2] = {{0, 4}}; + LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator); + LiveInterval* split = interval->SplitAt(5); + ASSERT_TRUE(split == nullptr); + ASSERT_TRUE(RangesEquals(interval, ranges, arraysize(ranges))); + } +} + +} // namespace art -- cgit v1.2.3-59-g8ed1b