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
diff --git a/compiler/optimizing/live_interval_test.cc b/compiler/optimizing/live_interval_test.cc
index 3e4b83b..ac8759c 100644
--- a/compiler/optimizing/live_interval_test.cc
+++ b/compiler/optimizing/live_interval_test.cc
@@ -278,4 +278,55 @@
}
}
+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 a123313..b0d3853 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -254,16 +254,28 @@
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 @@
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) {
