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