| /* |
| * 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 "builder.h" |
| #include "code_generator.h" |
| #include "dex_file.h" |
| #include "dex_instruction.h" |
| #include "nodes.h" |
| #include "optimizing_unit_test.h" |
| #include "register_allocator.h" |
| #include "ssa_liveness_analysis.h" |
| #include "utils/arena_allocator.h" |
| |
| #include "gtest/gtest.h" |
| |
| namespace art { |
| |
| // Note: the register allocator tests rely on the fact that constants have live |
| // intervals and registers get allocated to them. |
| |
| static bool Check(const uint16_t* data) { |
| ArenaPool pool; |
| ArenaAllocator allocator(&pool); |
| HGraphBuilder builder(&allocator); |
| const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); |
| HGraph* graph = builder.BuildGraph(*item); |
| graph->BuildDominatorTree(); |
| graph->TransformToSSA(); |
| graph->FindNaturalLoops(); |
| CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); |
| SsaLivenessAnalysis liveness(*graph, codegen); |
| liveness.Analyze(); |
| RegisterAllocator register_allocator(&allocator, codegen, liveness); |
| register_allocator.AllocateRegisters(); |
| return register_allocator.Validate(false); |
| } |
| |
| /** |
| * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator |
| * tests are based on this validation method. |
| */ |
| TEST(RegisterAllocatorTest, ValidateIntervals) { |
| ArenaPool pool; |
| ArenaAllocator allocator(&pool); |
| HGraph* graph = new (&allocator) HGraph(&allocator); |
| CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); |
| GrowableArray<LiveInterval*> intervals(&allocator, 0); |
| |
| // Test with two intervals of the same range. |
| { |
| static constexpr size_t ranges[][2] = {{0, 42}}; |
| intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0)); |
| intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1)); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(1)->SetRegister(0); |
| ASSERT_FALSE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| intervals.Reset(); |
| } |
| |
| // Test with two non-intersecting intervals. |
| { |
| static constexpr size_t ranges1[][2] = {{0, 42}}; |
| intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); |
| static constexpr size_t ranges2[][2] = {{42, 43}}; |
| intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(1)->SetRegister(0); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| intervals.Reset(); |
| } |
| |
| // Test with two non-intersecting intervals, with one with a lifetime hole. |
| { |
| static constexpr size_t ranges1[][2] = {{0, 42}, {45, 48}}; |
| intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); |
| static constexpr size_t ranges2[][2] = {{42, 43}}; |
| intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(1)->SetRegister(0); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| intervals.Reset(); |
| } |
| |
| // Test with intersecting intervals. |
| { |
| static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; |
| intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); |
| static constexpr size_t ranges2[][2] = {{42, 47}}; |
| intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(1)->SetRegister(0); |
| ASSERT_FALSE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| intervals.Reset(); |
| } |
| |
| // Test with siblings. |
| { |
| static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; |
| intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); |
| intervals.Get(0)->SplitAt(43); |
| static constexpr size_t ranges2[][2] = {{42, 47}}; |
| intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(1)->SetRegister(0); |
| // Sibling of the first interval has no register allocated to it. |
| ASSERT_TRUE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| |
| intervals.Get(0)->GetNextSibling()->SetRegister(0); |
| ASSERT_FALSE(RegisterAllocator::ValidateIntervals( |
| intervals, 0, *codegen, &allocator, true, false)); |
| } |
| } |
| |
| TEST(RegisterAllocatorTest, CFG1) { |
| /* |
| * Test the following snippet: |
| * return 0; |
| * |
| * Which becomes the following graph: |
| * constant0 |
| * goto |
| * | |
| * return |
| * | |
| * exit |
| */ |
| const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| Instruction::CONST_4 | 0 | 0, |
| Instruction::RETURN); |
| |
| ASSERT_TRUE(Check(data)); |
| } |
| |
| TEST(RegisterAllocatorTest, Loop1) { |
| /* |
| * Test the following snippet: |
| * int a = 0; |
| * while (a == a) { |
| * a = 4; |
| * } |
| * return 5; |
| * |
| * Which becomes the following graph: |
| * constant0 |
| * constant4 |
| * constant5 |
| * goto |
| * | |
| * goto |
| * | |
| * phi |
| * equal |
| * if +++++ |
| * | \ + |
| * | goto |
| * | |
| * return |
| * | |
| * exit |
| */ |
| |
| const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( |
| Instruction::CONST_4 | 0 | 0, |
| Instruction::IF_EQ, 4, |
| Instruction::CONST_4 | 4 << 12 | 0, |
| Instruction::GOTO | 0xFD00, |
| Instruction::CONST_4 | 5 << 12 | 1 << 8, |
| Instruction::RETURN | 1 << 8); |
| |
| ASSERT_TRUE(Check(data)); |
| } |
| |
| TEST(RegisterAllocatorTest, Loop2) { |
| /* |
| * Test the following snippet: |
| * int a = 0; |
| * while (a == 8) { |
| * a = 4 + 5; |
| * } |
| * return 6 + 7; |
| * |
| * Which becomes the following graph: |
| * constant0 |
| * constant4 |
| * constant5 |
| * constant6 |
| * constant7 |
| * constant8 |
| * goto |
| * | |
| * goto |
| * | |
| * phi |
| * equal |
| * if +++++ |
| * | \ + |
| * | 4 + 5 |
| * | goto |
| * | |
| * 6 + 7 |
| * return |
| * | |
| * exit |
| */ |
| |
| const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( |
| Instruction::CONST_4 | 0 | 0, |
| Instruction::CONST_4 | 8 << 12 | 1 << 8, |
| Instruction::IF_EQ | 1 << 8, 7, |
| Instruction::CONST_4 | 4 << 12 | 0 << 8, |
| Instruction::CONST_4 | 5 << 12 | 1 << 8, |
| Instruction::ADD_INT, 1 << 8 | 0, |
| Instruction::GOTO | 0xFA00, |
| Instruction::CONST_4 | 6 << 12 | 1 << 8, |
| Instruction::CONST_4 | 7 << 12 | 1 << 8, |
| Instruction::ADD_INT, 1 << 8 | 0, |
| Instruction::RETURN | 1 << 8); |
| |
| ASSERT_TRUE(Check(data)); |
| } |
| |
| static HGraph* BuildSSAGraph(const uint16_t* data, ArenaAllocator* allocator) { |
| HGraphBuilder builder(allocator); |
| const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); |
| HGraph* graph = builder.BuildGraph(*item); |
| graph->BuildDominatorTree(); |
| graph->TransformToSSA(); |
| graph->FindNaturalLoops(); |
| return graph; |
| } |
| |
| TEST(RegisterAllocatorTest, Loop3) { |
| /* |
| * Test the following snippet: |
| * int a = 0 |
| * do { |
| * b = a; |
| * a++; |
| * } while (a != 5) |
| * return b; |
| * |
| * Which becomes the following graph: |
| * constant0 |
| * constant1 |
| * constant5 |
| * goto |
| * | |
| * goto |
| * |++++++++++++ |
| * phi + |
| * a++ + |
| * equals + |
| * if + |
| * |++++++++++++ |
| * return |
| * | |
| * exit |
| */ |
| |
| const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( |
| Instruction::CONST_4 | 0 | 0, |
| Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8, |
| Instruction::CONST_4 | 5 << 12 | 2 << 8, |
| Instruction::IF_NE | 1 << 8 | 2 << 12, 3, |
| Instruction::RETURN | 0 << 8, |
| Instruction::MOVE | 1 << 12 | 0 << 8, |
| Instruction::GOTO | 0xF900); |
| |
| ArenaPool pool; |
| ArenaAllocator allocator(&pool); |
| HGraph* graph = BuildSSAGraph(data, &allocator); |
| CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); |
| SsaLivenessAnalysis liveness(*graph, codegen); |
| liveness.Analyze(); |
| RegisterAllocator register_allocator(&allocator, codegen, liveness); |
| register_allocator.AllocateRegisters(); |
| ASSERT_TRUE(register_allocator.Validate(false)); |
| |
| HBasicBlock* loop_header = graph->GetBlocks().Get(2); |
| HPhi* phi = loop_header->GetFirstPhi()->AsPhi(); |
| |
| LiveInterval* phi_interval = phi->GetLiveInterval(); |
| LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval(); |
| ASSERT_TRUE(phi_interval->HasRegister()); |
| ASSERT_TRUE(loop_update->HasRegister()); |
| ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister()); |
| |
| HBasicBlock* return_block = graph->GetBlocks().Get(3); |
| HReturn* ret = return_block->GetLastInstruction()->AsReturn(); |
| ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister()); |
| } |
| |
| } // namespace art |