Improve detection of lifetime holes.

The check concluding that the next use was in a successor
was too conservative: two blocks following each other
in terms of liveness are not necessarily predecessor/sucessor.

Change-Id: Ideec98046c812aa5fb63781141b5fde24c706d6d

1 files changed, 166 insertions, 2 deletions

diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 6184897490..03f8625265 100644
--- a/compiler/optimizing/live_ranges_test.cc
+++ b/compiler/optimizing/live_ranges_test.cc
@@ -146,7 +146,7 @@ TEST(LiveRangesTest, CFG3) {
    *       22: phi
    *       24: return
    *         |
-   *       38: exit
+   *       28: exit
    */
   const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
     Instruction::CONST_4 | 0 | 0,
@@ -194,7 +194,7 @@ TEST(LiveRangesTest, CFG3) {
   ASSERT_TRUE(range->GetNext() == nullptr);
 }
 
-TEST(LiveRangesTest, Loop) {
+TEST(LiveRangesTest, Loop1) {
   /*
    * Test the following snippet:
    *  var a = 0;
@@ -272,4 +272,168 @@ TEST(LiveRangesTest, Loop) {
   ASSERT_TRUE(range->GetNext() == nullptr);
 }
 
+TEST(LiveRangesTest, Loop2) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  while (a == a) {
+   *    a = a + a;
+   *  }
+   *  return a;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       4: goto
+   *           |
+   *       8: goto
+   *           |
+   *       10: phi
+   *       12: equal
+   *       14: if +++++
+   *        |       \ +
+   *        |     18: suspend
+   *        |     20: add
+   *        |     22: goto
+   *        |
+   *       26: return
+   *         |
+   *       30: exit
+   *
+   * We want to make sure the phi at 10 has a lifetime hole after the add at 20.
+   */
+
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 6,
+    Instruction::ADD_INT, 0, 0,
+    Instruction::GOTO | 0xFB00,
+    Instruction::RETURN | 0 << 8);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  x86::CodeGeneratorX86 codegen(graph);
+  SsaLivenessAnalysis liveness(*graph, &codegen);
+  liveness.Analyze();
+
+  // Test for the 0 constant.
+  HIntConstant* constant = liveness.GetInstructionFromSsaIndex(0)->AsIntConstant();
+  LiveInterval* interval = constant->GetLiveInterval();
+  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(10u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+
+  // Test for the loop phi.
+  HPhi* phi = liveness.GetInstructionFromSsaIndex(1)->AsPhi();
+  interval = phi->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(10u, range->GetStart());
+  ASSERT_EQ(21u, range->GetEnd());
+  range = range->GetNext();
+  ASSERT_TRUE(range != nullptr);
+  ASSERT_EQ(24u, range->GetStart());
+  ASSERT_EQ(27u, range->GetEnd());
+
+  // Test for the add instruction.
+  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
+  interval = add->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(20u, range->GetStart());
+  ASSERT_EQ(24u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+}
+
+TEST(LiveRangesTest, CFG4) {
+  /*
+   * Test the following snippet:
+   *  var a = 0;
+   *  var b = 4;
+   *  if (a == a) {
+   *    a = b + a;
+   *  } else {
+   *    a = b + a
+   *  }
+   *  return b;
+   *
+   * Which becomes the following graph (numbered by lifetime position):
+   *       2: constant0
+   *       4: constant4
+   *       6: goto
+   *           |
+   *       10: equal
+   *       12: if
+   *       /       \
+   *   16: add    22: add
+   *   18: goto   24: goto
+   *       \       /
+   *       26: phi
+   *       28: return
+   *         |
+   *       32: exit
+   *
+   * We want to make sure the constant0 has a lifetime hole after the 16: add.
+   */
+  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::CONST_4 | 4 << 12 | 1 << 8,
+    Instruction::IF_EQ, 5,
+    Instruction::ADD_INT, 1 << 8,
+    Instruction::GOTO | 0x300,
+    Instruction::ADD_INT, 1 << 8,
+    Instruction::RETURN | 1 << 8);
+
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = BuildGraph(data, &allocator);
+  x86::CodeGeneratorX86 codegen(graph);
+  SsaLivenessAnalysis liveness(*graph, &codegen);
+  liveness.Analyze();
+
+  // Test for the 0 constant.
+  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
+  LiveRange* range = interval->GetFirstRange();
+  ASSERT_EQ(2u, range->GetStart());
+  ASSERT_EQ(16u, range->GetEnd());
+  range = range->GetNext();
+  ASSERT_TRUE(range != nullptr);
+  ASSERT_EQ(20u, range->GetStart());
+  ASSERT_EQ(22u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+
+  // Test for the 4 constant.
+  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(4u, range->GetStart());
+  ASSERT_EQ(29u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+
+  // Test for the first add.
+  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
+  interval = add->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(16u, range->GetStart());
+  ASSERT_EQ(20u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+
+  // Test for the second add.
+  add = liveness.GetInstructionFromSsaIndex(3)->AsAdd();
+  interval = add->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(22u, range->GetStart());
+  ASSERT_EQ(26u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+
+  // Test for the phi, which is unused.
+  HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
+  ASSERT_EQ(phi->NumberOfUses(), 0u);
+  interval = phi->GetLiveInterval();
+  range = interval->GetFirstRange();
+  ASSERT_EQ(26u, range->GetStart());
+  ASSERT_EQ(28u, range->GetEnd());
+  ASSERT_TRUE(range->GetNext() == nullptr);
+}
+
 }  // namespace art