From e8ff50df01c89e1b5264a5a900cfebdde87a9b44 Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Thu, 7 May 2015 09:59:30 +0100 Subject: [PATCH] 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) --- compiler/optimizing/dead_code_elimination.cc | 24 +- compiler/optimizing/dead_code_elimination.h | 6 +- compiler/optimizing/graph_visualizer.cc | 4 +- compiler/optimizing/nodes.cc | 49 ++-- compiler/optimizing/nodes.h | 13 +- compiler/optimizing/optimizing_compiler.cc | 6 +- test/485-checker-dce-loop-update/expected.txt | 0 test/485-checker-dce-loop-update/info.txt | 2 + .../smali/TestCase.smali | 275 +++++++++++++++++++++ test/485-checker-dce-loop-update/src/Main.java | 27 ++ 10 files changed, 374 insertions(+), 32 deletions(-) create mode 100644 test/485-checker-dce-loop-update/expected.txt create mode 100644 test/485-checker-dce-loop-update/info.txt create mode 100644 test/485-checker-dce-loop-update/smali/TestCase.smali create mode 100644 test/485-checker-dce-loop-update/src/Main.java diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index cd427c5ed..6fbe75e80 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -47,6 +47,12 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) { } } +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 @@ void HDeadCodeElimination::RemoveDeadBlocks() { // 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 0bea0fc1c..59a57c434 100644 --- a/compiler/optimizing/dead_code_elimination.h +++ b/compiler/optimizing/dead_code_elimination.h @@ -31,13 +31,13 @@ class HDeadCodeElimination : public HOptimization { 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 713012713..f5c630bf9 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 @@ class HGraphVisualizerPrinter : public HGraphVisitor { } } 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 b9e58c703..41adc7223 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 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) { } 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 @@ bool HLoopInformation::Populate() { 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 @@ 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 031761e7f..77b587e74 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -436,6 +436,12 @@ class HLoopInformation : public ArenaObject { // 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 @@ 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. + // 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 e993d778d..8bb5d8eba 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -320,8 +320,10 @@ static void RunOptimizations(HGraph* graph, 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 000000000..e69de29bb 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 000000000..fccf10cc8 --- /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 000000000..3873ac50c --- /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 000000000..6bfe08b0d --- /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; + } +} -- 2.11.0