ART: Rediscover loops after deleting blocks in DCE
The way DCE currently updates loop information does not cover all
cases. This patch removes the logic, resets loop information of live
blocks to pre-SSA state and reanalyzes the affected loops.
Change-Id: I0b996a70235b95a8db0de9a23a03f71db57a21b8
(cherry picked from commit a4b8c21dae70ae34aee13628632c39a675c06022)
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index cd427c5..6fbe75e 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -47,6 +47,12 @@
}
}
+static void MarkLoopHeadersContaining(const HBasicBlock& block, ArenaBitVector* set) {
+ for (HLoopInformationOutwardIterator it(block); !it.Done(); it.Advance()) {
+ set->SetBit(it.Current()->GetHeader()->GetBlockId());
+ }
+}
+
void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
if (stats_ != nullptr) {
stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
@@ -58,18 +64,24 @@
// Classify blocks as reachable/unreachable.
ArenaAllocator* allocator = graph_->GetArena();
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false);
+ ArenaBitVector affected_loops(allocator, graph_->GetBlocks().Size(), false);
+
MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
- // Remove all dead blocks. Process blocks in post-order, because removal needs
- // the block's chain of dominators.
+ // Remove all dead blocks. Iterate in post order because removal needs the
+ // block's chain of dominators and nested loops need to be updated from the
+ // inside out.
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
- if (live_blocks.IsBitSet(block->GetBlockId())) {
- // If this block is part of a loop that is being dismantled, we need to
- // update its loop information.
- block->UpdateLoopInformation();
+ int id = block->GetBlockId();
+ if (live_blocks.IsBitSet(id)) {
+ if (affected_loops.IsBitSet(id)) {
+ DCHECK(block->IsLoopHeader());
+ block->GetLoopInformation()->Update();
+ }
} else {
MaybeRecordDeadBlock(block);
+ MarkLoopHeadersContaining(*block, &affected_loops);
block->DisconnectAndDelete();
}
}
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index 0bea0fc..59a57c4 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -31,13 +31,13 @@
public:
HDeadCodeElimination(HGraph* graph,
OptimizingCompilerStats* stats = nullptr,
- const char* name = kDeadCodeEliminationPassName)
+ const char* name = kInitialDeadCodeEliminationPassName)
: HOptimization(graph, true, name, stats) {}
void Run() OVERRIDE;
- static constexpr const char* kDeadCodeEliminationPassName =
- "dead_code_elimination";
+ static constexpr const char* kInitialDeadCodeEliminationPassName = "dead_code_elimination";
+ static constexpr const char* kFinalDeadCodeEliminationPassName = "dead_code_elimination_final";
private:
void MaybeRecordDeadBlock(HBasicBlock* block);
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 7130127..f5c630b 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -17,6 +17,7 @@
#include "graph_visualizer.h"
#include "code_generator.h"
+#include "dead_code_elimination.h"
#include "licm.h"
#include "nodes.h"
#include "optimization.h"
@@ -253,7 +254,8 @@
}
}
output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
- } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)) {
+ } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
+ || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)) {
output_ << " ( loop_header:";
HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
if (info == nullptr) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b9e58c7..41adc72 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -17,6 +17,7 @@
#include "nodes.h"
#include "ssa_builder.h"
+#include "base/bit_vector-inl.h"
#include "utils/growable_array.h"
#include "scoped_thread_state_change.h"
@@ -346,6 +347,7 @@
}
bool HLoopInformation::Populate() {
+ DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) {
HBasicBlock* back_edge = GetBackEdges().Get(i);
DCHECK(back_edge->GetDominator() != nullptr);
@@ -365,6 +367,39 @@
return true;
}
+void HLoopInformation::Update() {
+ HGraph* graph = header_->GetGraph();
+ for (uint32_t id : blocks_.Indexes()) {
+ HBasicBlock* block = graph->GetBlocks().Get(id);
+ // Reset loop information of non-header blocks inside the loop, except
+ // members of inner nested loops because those should already have been
+ // updated by their own LoopInformation.
+ if (block->GetLoopInformation() == this && block != header_) {
+ block->SetLoopInformation(nullptr);
+ }
+ }
+ blocks_.ClearAllBits();
+
+ if (back_edges_.IsEmpty()) {
+ // The loop has been dismantled, delete its suspend check and remove info
+ // from the header.
+ DCHECK(HasSuspendCheck());
+ header_->RemoveInstruction(suspend_check_);
+ header_->SetLoopInformation(nullptr);
+ header_ = nullptr;
+ suspend_check_ = nullptr;
+ } else {
+ if (kIsDebugBuild) {
+ for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
+ DCHECK(header_->Dominates(back_edges_.Get(i)));
+ }
+ }
+ // This loop still has reachable back edges. Repopulate the list of blocks.
+ bool populate_successful = Populate();
+ DCHECK(populate_successful);
+ }
+}
+
HBasicBlock* HLoopInformation::GetPreHeader() const {
return header_->GetDominator();
}
@@ -1049,20 +1084,6 @@
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 031761e..77b587e 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -436,6 +436,12 @@
// that is the header dominates the back edge.
bool Populate();
+ // Reanalyzes the loop by removing loop info from its blocks and re-running
+ // Populate(). If there are no back edges left, the loop info is completely
+ // removed as well as its SuspendCheck instruction. It must be run on nested
+ // inner loops first.
+ void Update();
+
// Returns whether this loop information contains `block`.
// Note that this loop information *must* be populated before entering this function.
bool Contains(const HBasicBlock& block) const;
@@ -705,14 +711,9 @@
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.
+ // Returns whether this block dominates the blocked passed as parameter.
bool Dominates(HBasicBlock* block) const;
size_t GetLifetimeStart() const { return lifetime_start_; }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index e993d77..8bb5d8e 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -320,8 +320,10 @@
const DexCompilationUnit& dex_compilation_unit,
PassInfoPrinter* pass_info_printer,
StackHandleScopeCollection* handles) {
- HDeadCodeElimination dce1(graph, stats);
- HDeadCodeElimination dce2(graph, stats, "dead_code_elimination_final");
+ HDeadCodeElimination dce1(graph, stats,
+ HDeadCodeElimination::kInitialDeadCodeEliminationPassName);
+ HDeadCodeElimination dce2(graph, stats,
+ HDeadCodeElimination::kFinalDeadCodeEliminationPassName);
HConstantFolding fold1(graph);
InstructionSimplifier simplify1(graph, stats);
HBooleanSimplifier boolean_simplify(graph);
diff --git a/test/485-checker-dce-loop-update/expected.txt b/test/485-checker-dce-loop-update/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/485-checker-dce-loop-update/expected.txt
diff --git a/test/485-checker-dce-loop-update/info.txt b/test/485-checker-dce-loop-update/info.txt
new file mode 100644
index 0000000..fccf10c
--- /dev/null
+++ b/test/485-checker-dce-loop-update/info.txt
@@ -0,0 +1,2 @@
+Tests loop information update after DCE because block removal can disconnect loops, leaving other
+live blocks outside the loop they had been a member of.
\ No newline at end of file
diff --git a/test/485-checker-dce-loop-update/smali/TestCase.smali b/test/485-checker-dce-loop-update/smali/TestCase.smali
new file mode 100644
index 0000000..3873ac5
--- /dev/null
+++ b/test/485-checker-dce-loop-update/smali/TestCase.smali
@@ -0,0 +1,275 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LTestCase;
+
+.super Ljava/lang/Object;
+
+.method public static $inline$True()Z
+ .registers 1
+ const/4 v0, 1
+ return v0
+.end method
+
+
+# CHECK-START: int TestCase.testSingleExit(int, boolean) dead_code_elimination_final (before)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst1:i\d+]] IntConstant 1
+# CHECK-DAG: [[Cst5:i\d+]] IntConstant 5
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[Add5:i\d+]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[Cst1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add5]] Add [ [[PhiX]] [[Cst5]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+# CHECK-START: int TestCase.testSingleExit(int, boolean) dead_code_elimination_final (after)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[AddX:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[AddX]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+.method public static testSingleExit(IZ)I
+ .registers 3
+
+ # p0 = int X
+ # p1 = boolean Y
+ # v0 = true
+
+ invoke-static {}, LTestCase;->$inline$True()Z
+ move-result v0
+
+ :loop_start
+ if-eqz p1, :loop_body # cannot be determined statically
+ if-nez v0, :loop_end # will always exit
+
+ # Dead block
+ add-int/lit8 p0, p0, 5
+ goto :loop_start
+
+ # Live block
+ :loop_body
+ add-int/lit8 p0, p0, 7
+ goto :loop_start
+
+ :loop_end
+ return p0
+.end method
+
+
+# CHECK-START: int TestCase.testMultipleExits(int, boolean, boolean) dead_code_elimination_final (before)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst1:i\d+]] IntConstant 1
+# CHECK-DAG: [[Cst5:i\d+]] IntConstant 5
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[Add5:i\d+]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgZ]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[Cst1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add5]] Add [ [[PhiX]] [[Cst5]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+# CHECK-START: int TestCase.testMultipleExits(int, boolean, boolean) dead_code_elimination_final (after)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgZ]] ] loop_header:null
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+.method public static testMultipleExits(IZZ)I
+ .registers 4
+
+ # p0 = int X
+ # p1 = boolean Y
+ # p2 = boolean Z
+ # v0 = true
+
+ invoke-static {}, LTestCase;->$inline$True()Z
+ move-result v0
+
+ :loop_start
+ if-eqz p1, :loop_body # cannot be determined statically
+ if-nez p2, :loop_end # may exit
+ if-nez v0, :loop_end # will always exit
+
+ # Dead block
+ add-int/lit8 p0, p0, 5
+ goto :loop_start
+
+ # Live block
+ :loop_body
+ add-int/lit8 p0, p0, 7
+ goto :loop_start
+
+ :loop_end
+ return p0
+.end method
+
+
+# CHECK-START: int TestCase.testExitPredecessors(int, boolean, boolean) dead_code_elimination_final (before)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst1:i\d+]] IntConstant 1
+# CHECK-DAG: [[Cst5:i\d+]] IntConstant 5
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[Cst9:i\d+]] IntConstant 9
+# CHECK-DAG: [[PhiX1:i\d+]] Phi [ [[ArgX]] [[Add5:i\d+]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgZ]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Mul9:i\d+]] Mul [ [[PhiX1]] [[Cst9]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[PhiX2:i\d+]] Phi [ [[Mul9]] [[PhiX1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[Cst1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add5]] Add [ [[PhiX2]] [[Cst5]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX1]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: Return [ [[PhiX2]] ] loop_header:null
+
+# CHECK-START: int TestCase.testExitPredecessors(int, boolean, boolean) dead_code_elimination_final (after)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+# CHECK-DAG: [[Cst9:i\d+]] IntConstant 9
+# CHECK-DAG: [[PhiX1:i\d+]] Phi [ [[ArgX]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX1]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgZ]] ] loop_header:null
+# CHECK-DAG: [[Mul9:i\d+]] Mul [ [[PhiX1]] [[Cst9]] ] loop_header:null
+# CHECK-DAG: [[PhiX2:i\d+]] Phi [ [[Mul9]] [[PhiX1]] ] loop_header:null
+# CHECK-DAG: Return [ [[PhiX2]] ] loop_header:null
+
+.method public static testExitPredecessors(IZZ)I
+ .registers 4
+
+ # p0 = int X
+ # p1 = boolean Y
+ # p2 = boolean Z
+ # v0 = true
+
+ invoke-static {}, LTestCase;->$inline$True()Z
+ move-result v0
+
+ :loop_start
+ if-eqz p1, :loop_body # cannot be determined statically
+
+ # Additional logic which will end up outside the loop
+ if-eqz p2, :skip_if
+ mul-int/lit8 p0, p0, 9
+ :skip_if
+
+ if-nez v0, :loop_end # will always take the branch
+
+ # Dead block
+ add-int/lit8 p0, p0, 5
+ goto :loop_start
+
+ # Live block
+ :loop_body
+ add-int/lit8 p0, p0, 7
+ goto :loop_start
+
+ :loop_end
+ return p0
+.end method
+
+
+# CHECK-START: int TestCase.testInnerLoop(int, boolean, boolean) dead_code_elimination_final (before)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst0:i\d+]] IntConstant 0
+# CHECK-DAG: [[Cst1:i\d+]] IntConstant 1
+# CHECK-DAG: [[Cst5:i\d+]] IntConstant 5
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+#
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[Add5:i\d+]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: [[PhiZ1:i\d+]] Phi [ [[ArgZ]] [[XorZ:i\d+]] [[PhiZ1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+#
+# ### Inner loop ###
+# CHECK-DAG: [[PhiZ2:i\d+]] Phi [ [[PhiZ1]] [[XorZ]] ] loop_header:[[HeaderZ:B\d+]]
+# CHECK-DAG: [[XorZ]] Xor [ [[PhiZ2]] [[Cst1]] ] loop_header:[[HeaderZ]]
+# CHECK-DAG: [[CondZ:z\d+]] Equal [ [[XorZ]] [[Cst0]] ] loop_header:[[HeaderZ]]
+# CHECK-DAG: If [ [[CondZ]] ] loop_header:[[HeaderZ]]
+#
+# CHECK-DAG: [[Add5]] Add [ [[PhiX]] [[Cst5]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+# CHECK-START: int TestCase.testInnerLoop(int, boolean, boolean) dead_code_elimination_final (after)
+# CHECK-DAG: [[ArgX:i\d+]] ParameterValue
+# CHECK-DAG: [[ArgY:z\d+]] ParameterValue
+# CHECK-DAG: [[ArgZ:z\d+]] ParameterValue
+# CHECK-DAG: [[Cst0:i\d+]] IntConstant 0
+# CHECK-DAG: [[Cst1:i\d+]] IntConstant 1
+# CHECK-DAG: [[Cst7:i\d+]] IntConstant 7
+#
+# CHECK-DAG: [[PhiX:i\d+]] Phi [ [[ArgX]] [[Add7:i\d+]] ] loop_header:[[HeaderY:B\d+]]
+# CHECK-DAG: [[PhiZ1:i\d+]] Phi [ [[ArgZ]] [[PhiZ1]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: If [ [[ArgY]] ] loop_header:[[HeaderY]]
+# CHECK-DAG: [[Add7]] Add [ [[PhiX]] [[Cst7]] ] loop_header:[[HeaderY]]
+#
+# ### Inner loop ###
+# CHECK-DAG: [[PhiZ2:i\d+]] Phi [ [[PhiZ1]] [[XorZ:i\d+]] ] loop_header:[[HeaderZ:B\d+]]
+# CHECK-DAG: [[XorZ]] Xor [ [[PhiZ2]] [[Cst1]] ] loop_header:[[HeaderZ]]
+# CHECK-DAG: [[CondZ:z\d+]] Equal [ [[XorZ]] [[Cst0]] ] loop_header:[[HeaderZ]]
+# CHECK-DAG: If [ [[CondZ]] ] loop_header:[[HeaderZ]]
+#
+# CHECK-DAG: Return [ [[PhiX]] ] loop_header:null
+
+.method public static testInnerLoop(IZZ)I
+ .registers 4
+
+ # p0 = int X
+ # p1 = boolean Y
+ # p2 = boolean Z
+ # v0 = true
+
+ invoke-static {}, LTestCase;->$inline$True()Z
+ move-result v0
+
+ :loop_start
+ if-eqz p1, :loop_body # cannot be determined statically
+
+ # Inner loop which will end up outside its parent
+ :inner_loop_start
+ xor-int/lit8 p2, p2, 1
+ if-eqz p2, :inner_loop_start
+
+ if-nez v0, :loop_end # will always take the branch
+
+ # Dead block
+ add-int/lit8 p0, p0, 5
+ goto :loop_start
+
+ # Live block
+ :loop_body
+ add-int/lit8 p0, p0, 7
+ goto :loop_start
+
+ :loop_end
+ return p0
+.end method
diff --git a/test/485-checker-dce-loop-update/src/Main.java b/test/485-checker-dce-loop-update/src/Main.java
new file mode 100644
index 0000000..6bfe08b
--- /dev/null
+++ b/test/485-checker-dce-loop-update/src/Main.java
@@ -0,0 +1,27 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+
+ // Workaround for b/18051191.
+ class InnerClass {}
+
+ public static void main(String[] args) throws Exception {
+ return;
+ }
+}
