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, 310 insertions, 0 deletions

diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
new file mode 100644
index 0000000..019d0f8
--- /dev/null
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -0,0 +1,310 @@
+/*
+ * 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();
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+  CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
+  RegisterAllocator register_allocator(&allocator, *codegen);
+  register_allocator.AllocateRegisters(liveness);
+  return register_allocator.Validate(liveness, 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, *codegen, &allocator, true, false));
+
+    intervals.Get(1)->SetRegister(0);
+    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *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, *codegen, &allocator, true, false));
+
+    intervals.Get(1)->SetRegister(0);
+    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *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, *codegen, &allocator, true, false));
+
+    intervals.Get(1)->SetRegister(0);
+    ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *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, *codegen, &allocator, true, false));
+
+    intervals.Get(1)->SetRegister(0);
+    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *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, *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, *codegen, &allocator, true, false));
+
+    intervals.Get(0)->GetNextSibling()->SetRegister(0);
+    ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *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);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+  CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
+  RegisterAllocator register_allocator(&allocator, *codegen);
+  register_allocator.AllocateRegisters(liveness);
+  ASSERT_TRUE(register_allocator.Validate(liveness, 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->GetFirstInstruction()->AsReturn();
+  ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
+}
+
+}  // namespace art