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
diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 9849388..c797497 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -43,11 +43,11 @@
*
* Which becomes the following graph (numbered by lifetime position):
* 2: constant0
- * 3: goto
+ * 4: goto
* |
- * 6: return
+ * 8: return
* |
- * 9: exit
+ * 12: exit
*/
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -60,14 +60,14 @@
liveness.Analyze();
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- LiveRange range = interval->GetRanges().Get(0);
- ASSERT_EQ(2u, range.GetStart());
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_EQ(2u, range->GetStart());
// Last use is the return instruction.
- ASSERT_EQ(6u, range.GetEnd());
+ ASSERT_EQ(8u, range->GetEnd());
HBasicBlock* block = graph->GetBlocks().Get(1);
ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
- ASSERT_EQ(6u, block->GetLastInstruction()->GetLifetimePosition());
+ ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
+ ASSERT_TRUE(range->GetNext() == nullptr);
}
TEST(LiveRangesTest, CFG2) {
@@ -81,16 +81,16 @@
*
* Which becomes the following graph (numbered by lifetime position):
* 2: constant0
- * 3: goto
+ * 4: goto
* |
- * 6: equal
- * 7: if
+ * 8: equal
+ * 10: if
* / \
- * 10: goto 13: goto
+ * 14: goto 18: goto
* \ /
- * 16: return
+ * 22: return
* |
- * 19: exit
+ * 26: exit
*/
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -105,14 +105,14 @@
liveness.Analyze();
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- LiveRange range = interval->GetRanges().Get(0);
- ASSERT_EQ(2u, range.GetStart());
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_EQ(2u, range->GetStart());
// Last use is the return instruction.
- ASSERT_EQ(16u, range.GetEnd());
+ ASSERT_EQ(22u, range->GetEnd());
HBasicBlock* block = graph->GetBlocks().Get(3);
ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
- ASSERT_EQ(16u, block->GetLastInstruction()->GetLifetimePosition());
+ ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
+ ASSERT_TRUE(range->GetNext() == nullptr);
}
TEST(LiveRangesTest, CFG3) {
@@ -127,18 +127,18 @@
*
* Which becomes the following graph (numbered by lifetime position):
* 2: constant0
- * 3: constant4
- * 4: goto
+ * 4: constant4
+ * 6: goto
* |
- * 7: equal
- * 8: if
+ * 10: equal
+ * 12: if
* / \
- * 11: goto 14: goto
+ * 16: goto 20: goto
* \ /
- * 16: phi
- * 17: return
+ * 22: phi
+ * 24: return
* |
- * 20: exit
+ * 38: exit
*/
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
@@ -154,34 +154,34 @@
// Test for the 0 constant.
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- LiveRange range = interval->GetRanges().Get(0);
- ASSERT_EQ(2u, range.GetStart());
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_EQ(2u, range->GetStart());
// Last use is the phi at the return block so instruction is live until
// the end of the then block.
- ASSERT_EQ(12u, range.GetEnd());
+ ASSERT_EQ(18u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the 4 constant.
interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
// The then branch is a hole for this constant, therefore its interval has 2 ranges.
- ASSERT_EQ(2u, interval->GetRanges().Size());
- // First range is the else block.
- range = interval->GetRanges().Get(0);
- ASSERT_EQ(13u, range.GetStart());
- // Last use is the phi at the return block.
- ASSERT_EQ(15u, range.GetEnd());
- // Second range starts from the definition and ends at the if block.
- range = interval->GetRanges().Get(1);
- ASSERT_EQ(3u, range.GetStart());
+ // First range starts from the definition and ends at the if block.
+ range = interval->GetFirstRange();
+ ASSERT_EQ(4u, range->GetStart());
// 9 is the end of the if block.
- ASSERT_EQ(9u, range.GetEnd());
+ ASSERT_EQ(14u, range->GetEnd());
+ // Second range is the else block.
+ range = range->GetNext();
+ ASSERT_EQ(18u, range->GetStart());
+ // Last use is the phi at the return block.
+ ASSERT_EQ(22u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the phi.
interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- range = interval->GetRanges().Get(0);
- ASSERT_EQ(16u, range.GetStart());
- ASSERT_EQ(17u, range.GetEnd());
+ range = interval->GetFirstRange();
+ ASSERT_EQ(22u, range->GetStart());
+ ASSERT_EQ(24u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
}
TEST(LiveRangesTest, Loop) {
@@ -195,21 +195,21 @@
*
* Which becomes the following graph (numbered by lifetime position):
* 2: constant0
- * 3: constant4
- * 4: constant5
- * 5: goto
- * |
+ * 4: constant4
+ * 6: constant5
* 8: goto
* |
- * 10: phi
- * 11: equal
- * 12: if +++++
+ * 12: goto
+ * |
+ * 14: phi
+ * 16: equal
+ * 18: if +++++
* | \ +
- * | 15: goto
+ * | 22: goto
* |
- * 18: return
+ * 26: return
* |
- * 21: exit
+ * 30: exit
*/
const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
@@ -228,36 +228,36 @@
// Test for the 0 constant.
LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- LiveRange range = interval->GetRanges().Get(0);
- ASSERT_EQ(2u, range.GetStart());
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_EQ(2u, range->GetStart());
// Last use is the loop phi so instruction is live until
// the end of the pre loop header.
- ASSERT_EQ(9u, range.GetEnd());
+ ASSERT_EQ(14u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the 4 constant.
interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+ range = interval->GetFirstRange();
// The instruction is live until the end of the loop.
- ASSERT_EQ(1u, interval->GetRanges().Size());
- range = interval->GetRanges().Get(0);
- ASSERT_EQ(3u, range.GetStart());
- ASSERT_EQ(16u, range.GetEnd());
+ ASSERT_EQ(4u, range->GetStart());
+ ASSERT_EQ(24u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the 5 constant.
interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
- // The instruction is live until the return instruction of the loop.
- ASSERT_EQ(1u, interval->GetRanges().Size());
- range = interval->GetRanges().Get(0);
- ASSERT_EQ(4u, range.GetStart());
- ASSERT_EQ(18u, range.GetEnd());
+ range = interval->GetFirstRange();
+ // The instruction is live until the return instruction after the loop.
+ ASSERT_EQ(6u, range->GetStart());
+ ASSERT_EQ(26u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
// Test for the phi.
interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
- ASSERT_EQ(1u, interval->GetRanges().Size());
- range = interval->GetRanges().Get(0);
+ range = interval->GetFirstRange();
// Instruction is consumed by the if.
- ASSERT_EQ(10u, range.GetStart());
- ASSERT_EQ(11u, range.GetEnd());
+ ASSERT_EQ(14u, range->GetStart());
+ ASSERT_EQ(16u, range->GetEnd());
+ ASSERT_TRUE(range->GetNext() == nullptr);
}
} // namespace art