From 8ddb00ca935733f5d3b07816e5bb33d6cabe6ec4 Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 29 Sep 2014 12:00:40 +0100 Subject: [PATCH] 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 --- compiler/optimizing/live_ranges_test.cc | 168 ++++++++++++++++++++++++++- compiler/optimizing/liveness_test.cc | 47 ++++++++ compiler/optimizing/register_allocator.cc | 2 + compiler/optimizing/ssa_liveness_analysis.cc | 1 + compiler/optimizing/ssa_liveness_analysis.h | 19 +-- 5 files changed, 228 insertions(+), 9 deletions(-) diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index 618489749..03f862526 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 84b2e33ee..2d861696b 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 f4fb33605..1d1d694ad 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 680cc0a03..cd13d81a3 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 3ef24137c..c62e61b2c 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( -- 2.11.0