Build live ranges in preparation for register allocation.

Change-Id: I7ae24afaa4e49276136bf34f4ba7d62db7f28c01

1 files changed, 263 insertions, 0 deletions

diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
new file mode 100644
index 0000000..9849388
--- /dev/null
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -0,0 +1,263 @@
+/*
+ * 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 "dex_file.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "ssa_liveness_analysis.h"
+#include "utils/arena_allocator.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+static HGraph* BuildGraph(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(LiveRangesTest, CFG1) {
+  /*
+   * Test the following snippet:
+   *  return 0;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: goto
+   *           |
+   *       6: return
+   *           |
+   *       9: exit
+   */
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::RETURN);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  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());
+  // Last use is the return instruction.
+  ASSERT_EQ(6u, range.GetEnd());
+  HBasicBlock* block = graph->GetBlocks().Get(1);
+  ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+  ASSERT_EQ(6u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG2) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  if (0 == 0) {
+   *  } else {
+   *  }
+   *  return a;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: goto
+   *           |
+   *       6: equal
+   *       7: if
+   *       /       \
+   *   10: goto   13: goto
+   *       \       /
+   *       16: return
+   *         |
+   *       19: exit
+   */
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::GOTO | 0x100,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  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());
+  // Last use is the return instruction.
+  ASSERT_EQ(16u, range.GetEnd());
+  HBasicBlock* block = graph->GetBlocks().Get(3);
+  ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
+  ASSERT_EQ(16u, block->GetLastInstruction()->GetLifetimePosition());
+}
+
+TEST(LiveRangesTest, CFG3) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  if (0 == 0) {
+   *  } else {
+   *    a = 4;
+   *  }
+   *  return a;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: constant4
+   *       4: goto
+   *           |
+   *       7: equal
+   *       8: if
+   *       /       \
+   *   11: goto   14: goto
+   *       \       /
+   *       16: phi
+   *       17: return
+   *         |
+   *       20: exit
+   */
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 3,
+    Instruction::CONST_4 | 4 << 12 | 0,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  // 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());
+  // 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());
+
+  // 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());
+  // 9 is the end of the if block.
+  ASSERT_EQ(9u, range.GetEnd());
+
+  // 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());
+}
+
+TEST(LiveRangesTest, Loop) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  while (a == a) {
+   *    a = 4;
+   *  }
+   *  return 5;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       3: constant4
+   *       4: constant5
+   *       5: goto
+   *           |
+   *       8: goto
+   *           |
+   *       10: phi
+   *       11: equal
+   *       12: if +++++
+   *        |       \ +
+   *        |     15: goto
+   *        |
+   *       18: return
+   *         |
+   *       21: 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);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  SsaLivenessAnalysis liveness(*graph);
+  liveness.Analyze();
+
+  // 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());
+  // Last use is the loop phi so instruction is live until
+  // the end of the pre loop header.
+  ASSERT_EQ(9u, range.GetEnd());
+
+  // Test for the 4 constant.
+  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+  // 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());
+
+  // 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());
+
+  // Test for the phi.
+  interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
+  ASSERT_EQ(1u, interval->GetRanges().Size());
+  range = interval->GetRanges().Get(0);
+  // Instruction is consumed by the if.
+  ASSERT_EQ(10u, range.GetStart());
+  ASSERT_EQ(11u, range.GetEnd());
+}
+
+}  // namespace art