From 69a2804c3bb48cf4fd00a66080f613a4fd96c422 Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Wed, 29 Apr 2015 17:16:07 +0100 Subject: [PATCH] ART: Fix loop information after dead code elimination Compilation failed when only some blocks of a loop were removed during dead code elimination. Bug: 20680703 Change-Id: If31025169ca493f0d7f7f2788576e98d05f03394 --- compiler/optimizing/dead_code_elimination.cc | 9 +++-- compiler/optimizing/nodes.cc | 15 ++++++++- compiler/optimizing/nodes.h | 11 +++++-- test/480-checker-dead-blocks/src/Main.java | 49 +++++++++++++++++++++++++++- 4 files changed, 76 insertions(+), 8 deletions(-) diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index 91cd60acc..cd427c5ed 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -65,10 +65,13 @@ void HDeadCodeElimination::RemoveDeadBlocks() { for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); if (live_blocks.IsBitSet(block->GetBlockId())) { - continue; + // If this block is part of a loop that is being dismantled, we need to + // update its loop information. + block->UpdateLoopInformation(); + } else { + MaybeRecordDeadBlock(block); + block->DisconnectAndDelete(); } - MaybeRecordDeadBlock(block); - block->DisconnectAndDelete(); } // Connect successive blocks created by dead branches. Order does not matter. diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 699987c05..f07f4c759 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -376,7 +376,6 @@ bool HLoopInformation::Populate() { } HBasicBlock* HLoopInformation::GetPreHeader() const { - DCHECK_EQ(header_->GetPredecessors().Size(), 2u); return header_->GetDominator(); } @@ -1038,6 +1037,20 @@ void HBasicBlock::DisconnectAndDelete() { SetGraph(nullptr); } +void HBasicBlock::UpdateLoopInformation() { + // Check if loop information points to a dismantled loop. If so, replace with + // the loop information of a larger loop which contains this block, or nullptr + // otherwise. We iterate in case the larger loop has been destroyed too. + while (IsInLoop() && loop_information_->GetBackEdges().IsEmpty()) { + if (IsLoopHeader()) { + HSuspendCheck* suspend_check = loop_information_->GetSuspendCheck(); + DCHECK_EQ(suspend_check->GetBlock(), this); + RemoveInstruction(suspend_check); + } + loop_information_ = loop_information_->GetPreHeader()->GetLoopInformation(); + } +} + void HBasicBlock::MergeWith(HBasicBlock* other) { DCHECK_EQ(GetGraph(), other->GetGraph()); DCHECK(GetDominatedBlocks().Contains(other)); diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 3fe23e181..25ef78064 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -636,7 +636,7 @@ class HBasicBlock : public ArenaObject { void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); bool IsLoopHeader() const { - return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); + return IsInLoop() && (loop_information_->GetHeader() == this); } bool IsLoopPreHeaderFirstPredecessor() const { @@ -655,7 +655,7 @@ class HBasicBlock : public ArenaObject { void SetInLoop(HLoopInformation* info) { if (IsLoopHeader()) { // Nothing to do. This just means `info` is an outer loop. - } else if (loop_information_ == nullptr) { + } else if (!IsInLoop()) { loop_information_ = info; } else if (loop_information_->Contains(*info->GetHeader())) { // Block is currently part of an outer loop. Make it part of this inner loop. @@ -674,6 +674,11 @@ class HBasicBlock : public ArenaObject { loop_information_ = info; } + // Checks if the loop information points to a valid loop. If the loop has been + // dismantled (does not have a back edge any more), loop information is + // removed or replaced with the information of the first valid outer loop. + void UpdateLoopInformation(); + bool IsInLoop() const { return loop_information_ != nullptr; } // Returns wheter this block dominates the blocked passed as parameter. @@ -727,7 +732,7 @@ class HLoopInformationOutwardIterator : public ValueObject { void Advance() { DCHECK(!Done()); - current_ = current_->GetHeader()->GetDominator()->GetLoopInformation(); + current_ = current_->GetPreHeader()->GetLoopInformation(); } HLoopInformation* Current() const { diff --git a/test/480-checker-dead-blocks/src/Main.java b/test/480-checker-dead-blocks/src/Main.java index 560ce952a..83dbb2689 100644 --- a/test/480-checker-dead-blocks/src/Main.java +++ b/test/480-checker-dead-blocks/src/Main.java @@ -128,7 +128,7 @@ public class Main { // CHECK-DAG: [[Arg:i\d+]] ParameterValue // CHECK-DAG: Return [ [[Arg]] ] - // CHECK-START: int Main.testRemoveLoop(int) dead_code_elimination_final (after) + // CHECK-START: int Main.testDeadLoop(int) dead_code_elimination_final (after) // CHECK-NOT: If // CHECK-NOT: Add @@ -139,9 +139,56 @@ public class Main { return x; } + // CHECK-START: int Main.testUpdateLoopInformation(int) dead_code_elimination_final (before) + // CHECK-DAG: If + // CHECK-DAG: If + // CHECK-DAG: Add + + // CHECK-START: int Main.testUpdateLoopInformation(int) dead_code_elimination_final (after) + // CHECK-DAG: [[Arg:i\d+]] ParameterValue + // CHECK-DAG: Return [ [[Arg]] ] + + // CHECK-START: int Main.testUpdateLoopInformation(int) dead_code_elimination_final (after) + // CHECK-NOT: If + // CHECK-NOT: Add + + public static int testUpdateLoopInformation(int x) { + // Use of Or in the condition generates a dead loop where not all of its + // blocks are removed. This forces DCE to update their loop information. + while (inlineFalse() || !inlineTrue()) { + x++; + } + return x; + } + + // CHECK-START: int Main.testRemoveSuspendCheck(int, int) dead_code_elimination_final (before) + // CHECK: SuspendCheck + // CHECK: SuspendCheck + // CHECK: SuspendCheck + // CHECK-NOT: SuspendCheck + + // CHECK-START: int Main.testRemoveSuspendCheck(int, int) dead_code_elimination_final (after) + // CHECK: SuspendCheck + // CHECK: SuspendCheck + // CHECK-NOT: SuspendCheck + + public static int testRemoveSuspendCheck(int x, int y) { + // Inner loop will leave behind the header with its SuspendCheck. DCE must + // remove it, otherwise the outer loop would end up with two. + while (y > 0) { + while (inlineFalse() || !inlineTrue()) { + x++; + } + y--; + } + return x; + } + public static void main(String[] args) { assertIntEquals(7, testTrueBranch(4, 3)); assertIntEquals(1, testFalseBranch(4, 3)); assertIntEquals(42, testRemoveLoop(42)); + assertIntEquals(23, testUpdateLoopInformation(23)); + assertIntEquals(12, testRemoveSuspendCheck(12, 5)); } } -- 2.11.0