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
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 @@
* 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 @@
ASSERT_TRUE(range->GetNext() == nullptr);
}
-TEST(LiveRangesTest, Loop) {
+TEST(LiveRangesTest, Loop1) {
/*
* Test the following snippet:
* var a = 0;
@@ -272,4 +272,168 @@
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 @@
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 @@
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 @@
}
// 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 @@
// 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 @@
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(
