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

1 files changed, 72 insertions, 72 deletions

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 @@ TEST(LiveRangesTest, CFG1) {
    *
    * 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 @@ TEST(LiveRangesTest, CFG1) {
   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 @@ TEST(LiveRangesTest, CFG2) {
    *
    * 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 @@ TEST(LiveRangesTest, CFG2) {
   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 @@ TEST(LiveRangesTest, CFG3) {
    *
    * 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(LiveRangesTest, CFG3) {
 
   // 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 @@ TEST(LiveRangesTest, Loop) {
    *
    * 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(LiveRangesTest, Loop) {
 
   // 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