Fix a bug in the liveness analysis.

A range after a loop might also be after a lifetime hole.
In this situation we must preserve the hole, and not merge
it with the loop start.

Change-Id: I82eddef059592102a25362cdaa4273200574c2ae

2 files changed, 71 insertions, 7 deletions

diff --git a/compiler/optimizing/live_interval_test.cc b/compiler/optimizing/live_interval_test.cc
index 3e4b83b0b1..ac8759c805 100644
--- a/compiler/optimizing/live_interval_test.cc
+++ b/compiler/optimizing/live_interval_test.cc
@@ -278,4 +278,55 @@ TEST(LiveInterval, SplitAt) {
   }
 }
 
+TEST(LiveInterval, AddLoopRange) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+
+  {
+    // Test when only used in a loop.
+    static constexpr size_t ranges[][2] = {{0, 4}};
+    LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+    interval->AddLoopRange(0, 8);
+    LiveRange* range = interval->GetFirstRange();
+    ASSERT_TRUE(range->GetNext() == nullptr);
+    ASSERT_EQ(range->GetStart(), 0u);
+    ASSERT_EQ(range->GetEnd(), 8u);
+  }
+
+  {
+    // Test when only used in a loop.
+    static constexpr size_t ranges[][2] = {{2, 4}};
+    LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+    interval->AddLoopRange(0, 8);
+    LiveRange* range = interval->GetFirstRange();
+    ASSERT_TRUE(range->GetNext() == nullptr);
+    ASSERT_EQ(range->GetStart(), 0u);
+    ASSERT_EQ(range->GetEnd(), 8u);
+  }
+
+  {
+    // Test when used just after the loop.
+    static constexpr size_t ranges[][2] = {{2, 4}, {8, 10}};
+    LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+    interval->AddLoopRange(0, 8);
+    LiveRange* range = interval->GetFirstRange();
+    ASSERT_TRUE(range->GetNext() == nullptr);
+    ASSERT_EQ(range->GetStart(), 0u);
+    ASSERT_EQ(range->GetEnd(), 10u);
+  }
+
+  {
+    // Test when use after the loop is after a lifetime hole.
+    static constexpr size_t ranges[][2] = {{2, 4}, {10, 12}};
+    LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+    interval->AddLoopRange(0, 8);
+    LiveRange* range = interval->GetFirstRange();
+    ASSERT_EQ(range->GetStart(), 0u);
+    ASSERT_EQ(range->GetEnd(), 8u);
+    range = range->GetNext();
+    ASSERT_EQ(range->GetStart(), 10u);
+    ASSERT_EQ(range->GetEnd(), 12u);
+  }
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index a123313426..b0d38531e9 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -254,16 +254,28 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
 
   void AddLoopRange(size_t start, size_t end) {
     DCHECK(first_range_ != nullptr);
-    while (first_range_ != nullptr && first_range_->GetEnd() < end) {
-      DCHECK_LE(start, first_range_->GetStart());
-      first_range_ = first_range_->GetNext();
+    DCHECK_LE(start, first_range_->GetStart());
+    // Find the range that covers the positions after the loop.
+    LiveRange* after_loop = first_range_;
+    LiveRange* last_in_loop = nullptr;
+    while (after_loop != nullptr && after_loop->GetEnd() < end) {
+      DCHECK_LE(start, after_loop->GetStart());
+      last_in_loop = after_loop;
+      after_loop = after_loop->GetNext();
     }
-    if (first_range_ == nullptr) {
+    if (after_loop == nullptr) {
       // Uses are only in the loop.
       first_range_ = last_range_ = new (allocator_) LiveRange(start, end, nullptr);
-    } else {
+    } else if (after_loop->GetStart() <= end) {
+      first_range_ = after_loop;
       // There are uses after the loop.
       first_range_->start_ = start;
+    } else {
+      // The use after the loop is after a lifetime hole.
+      DCHECK(last_in_loop != nullptr);
+      first_range_ = last_in_loop;
+      first_range_->start_ = start;
+      first_range_->end_ = end;
     }
   }
 
@@ -479,10 +491,11 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   void Dump(std::ostream& stream) const {
     stream << "ranges: { ";
     LiveRange* current = first_range_;
-    do {
+    while (current != nullptr) {
       current->Dump(stream);
       stream << " ";
-    } while ((current = current->GetNext()) != nullptr);
+      current = current->GetNext();
+    }
     stream << "}, uses: { ";
     UsePosition* use = first_use_;
     if (use != nullptr) {