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

5 files changed, 228 insertions, 9 deletions

diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc
index 6184897..03f8625 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
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 84b2e33..2d86169 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -546,4 +546,51 @@ TEST(LivenessTest, Loop7) {
   TestCode(data, expected);
 }
 
+TEST(LivenessTest, Loop8) {
+  // var a = 0;
+  // while (a == a) {
+  //   a = a + a;
+  // }
+  // return a;
+  //
+  // We want to test that the ins of the loop exit
+  // does contain the phi.
+  // Bitsets are made of:
+  // (constant0, phi, add)
+  const char* expected =
+    "Block 0\n"
+    "  live in: (000)\n"
+    "  live out: (100)\n"
+    "  kill: (100)\n"
+    "Block 1\n"  // pre loop header
+    "  live in: (100)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n"
+    "Block 2\n"  // loop header
+    "  live in: (000)\n"
+    "  live out: (010)\n"
+    "  kill: (010)\n"
+    "Block 3\n"  // back edge
+    "  live in: (010)\n"
+    "  live out: (000)\n"
+    "  kill: (001)\n"
+    "Block 4\n"  // return block
+    "  live in: (010)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n"
+    "Block 5\n"  // exit block
+    "  live in: (000)\n"
+    "  live out: (000)\n"
+    "  kill: (000)\n";
+
+  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);
+
+  TestCode(data, expected);
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index f4fb336..1d1d694 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1018,6 +1018,8 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
     return;
   }
 
+  DCHECK(destination != nullptr && source != nullptr);
+
   if (!destination->HasRegister()) {
     // Values are eagerly spilled. Spill slot already contains appropriate value.
     return;
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 680cc0a..cd13d81 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -189,6 +189,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
     }
 
     // Add a range that covers this block to all instructions live_in because of successors.
+    // Instructions defined in this block will have their start of the range adjusted.
     for (uint32_t idx : live_in->Indexes()) {
       HInstruction* current = instructions_from_ssa_index_.Get(idx);
       current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 3ef2413..c62e61b 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -183,8 +183,6 @@ class LiveInterval : public ArenaObject {
       // or its output to the same register.
       ++position;
     }
-    size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
-    size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
     if ((first_use_ != nullptr)
         && (first_use_->GetUser() == instruction)
         && (first_use_->GetPosition() < position)) {
@@ -200,18 +198,25 @@ class LiveInterval : public ArenaObject {
       return;
     }
 
+    size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
     if (first_range_ == nullptr) {
       // First time we see a use of that interval.
-      first_range_ = last_range_ = new (allocator_) LiveRange(start_block_position, position, nullptr);
+      first_range_ = last_range_ = new (allocator_) LiveRange(
+          start_block_position, position, nullptr);
     } else if (first_range_->GetStart() == start_block_position) {
-      // There is a use later in the same block.
+      // There is a use later in the same block or in a following block.
+      // Note that in such a case, `AddRange` for the whole blocks has been called
+      // before arriving in this method, and this is the reason the start of
+      // `first_range_` is before the given `position`.
       DCHECK_LE(position, first_range_->GetEnd());
-    } else if (first_range_->GetStart() == end_block_position) {
-      // Last use is in the following block.
-      first_range_->start_ = start_block_position;
     } else {
       DCHECK(first_range_->GetStart() > position);
       // There is a hole in the interval. Create a new range.
+      // Note that the start of `first_range_` can be equal to `end`: two blocks
+      // having adjacent lifetime positions are not necessarily
+      // predecessor/successor. When two blocks are predecessor/successor, the
+      // liveness algorithm has called `AddRange` before arriving in this method,
+      // and the check line 205 would succeed.
       first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_);
     }
     first_use_ = new (allocator_) UsePosition(