diff options
| -rw-r--r-- | compiler/optimizing/nodes.cc | 83 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 2 | ||||
| -rw-r--r-- | test/598-checker-irreducible-dominance/expected.txt | 0 | ||||
| -rw-r--r-- | test/598-checker-irreducible-dominance/info.txt | 2 | ||||
| -rw-r--r-- | test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali | 52 | ||||
| -rw-r--r-- | test/598-checker-irreducible-dominance/src/Main.java | 25 |
6 files changed, 147 insertions, 17 deletions
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 679c274e62..1db1ff4ab4 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -206,6 +206,22 @@ HInstruction* HBasicBlock::GetFirstInstructionDisregardMoves() const { return instruction; } +static bool UpdateDominatorOfSuccessor(HBasicBlock* block, HBasicBlock* successor) { + DCHECK(ContainsElement(block->GetSuccessors(), successor)); + + HBasicBlock* old_dominator = successor->GetDominator(); + HBasicBlock* new_dominator = + (old_dominator == nullptr) ? block + : CommonDominator::ForPair(old_dominator, block); + + if (old_dominator == new_dominator) { + return false; + } else { + successor->SetDominator(new_dominator); + return true; + } +} + void HGraph::ComputeDominanceInformation() { DCHECK(reverse_post_order_.empty()); reverse_post_order_.reserve(blocks_.size()); @@ -228,15 +244,7 @@ void HGraph::ComputeDominanceInformation() { worklist.pop_back(); } else { HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; - - if (successor->GetDominator() == nullptr) { - successor->SetDominator(current); - } else { - // The CommonDominator can work for multiple blocks as long as the - // domination information doesn't change. However, since we're changing - // that information here, we can use the finder only for pairs of blocks. - successor->SetDominator(CommonDominator::ForPair(successor->GetDominator(), current)); - } + UpdateDominatorOfSuccessor(current, successor); // Once all the forward edges have been visited, we know the immediate // dominator of the block. We can then start visiting its successors. @@ -248,6 +256,44 @@ void HGraph::ComputeDominanceInformation() { } } + // Check if the graph has back edges not dominated by their respective headers. + // If so, we need to update the dominators of those headers and recursively of + // their successors. We do that with a fix-point iteration over all blocks. + // The algorithm is guaranteed to terminate because it loops only if the sum + // of all dominator chains has decreased in the current iteration. + bool must_run_fix_point = false; + for (HBasicBlock* block : blocks_) { + if (block != nullptr && + block->IsLoopHeader() && + block->GetLoopInformation()->HasBackEdgeNotDominatedByHeader()) { + must_run_fix_point = true; + break; + } + } + if (must_run_fix_point) { + bool update_occurred = true; + while (update_occurred) { + update_occurred = false; + for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + for (HBasicBlock* successor : block->GetSuccessors()) { + update_occurred |= UpdateDominatorOfSuccessor(block, successor); + } + } + } + } + + // Make sure that there are no remaining blocks whose dominator information + // needs to be updated. + if (kIsDebugBuild) { + for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + for (HBasicBlock* successor : block->GetSuccessors()) { + DCHECK(!UpdateDominatorOfSuccessor(block, successor)); + } + } + } + // Populate `dominated_blocks_` information after computing all dominators. // The potential presence of irreducible loops requires to do it after. for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { @@ -595,14 +641,7 @@ void HLoopInformation::Populate() { blocks_.SetBit(header_->GetBlockId()); header_->SetInLoop(this); - bool is_irreducible_loop = false; - for (HBasicBlock* back_edge : GetBackEdges()) { - DCHECK(back_edge->GetDominator() != nullptr); - if (!header_->Dominates(back_edge)) { - is_irreducible_loop = true; - break; - } - } + bool is_irreducible_loop = HasBackEdgeNotDominatedByHeader(); if (is_irreducible_loop) { ArenaBitVector visited(graph->GetArena(), @@ -670,6 +709,16 @@ size_t HLoopInformation::GetLifetimeEnd() const { return last_position; } +bool HLoopInformation::HasBackEdgeNotDominatedByHeader() const { + for (HBasicBlock* back_edge : GetBackEdges()) { + DCHECK(back_edge->GetDominator() != nullptr); + if (!header_->Dominates(back_edge)) { + return true; + } + } + return false; +} + bool HBasicBlock::Dominates(HBasicBlock* other) const { // Walk up the dominator tree from `other`, to find out if `this` // is an ancestor. diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index afb995d438..1c0ad6a6cc 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -725,6 +725,8 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> { blocks_.ClearAllBits(); } + bool HasBackEdgeNotDominatedByHeader() const; + private: // Internal recursive implementation of `Populate`. void PopulateRecursive(HBasicBlock* block); diff --git a/test/598-checker-irreducible-dominance/expected.txt b/test/598-checker-irreducible-dominance/expected.txt new file mode 100644 index 0000000000..e69de29bb2 --- /dev/null +++ b/test/598-checker-irreducible-dominance/expected.txt diff --git a/test/598-checker-irreducible-dominance/info.txt b/test/598-checker-irreducible-dominance/info.txt new file mode 100644 index 0000000000..8ca4e63be9 --- /dev/null +++ b/test/598-checker-irreducible-dominance/info.txt @@ -0,0 +1,2 @@ +Regression test for HGraphBuilder which would compute wrong dominance information +in the presence of irreducible loops.
\ No newline at end of file diff --git a/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali b/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali new file mode 100644 index 0000000000..4d8b5152fd --- /dev/null +++ b/test/598-checker-irreducible-dominance/smali/IrreducibleLoop.smali @@ -0,0 +1,52 @@ +# Copyright (C) 2016 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 LIrreducibleLoop; +.super Ljava/lang/Object; + +# Test case in which `inner_back_edge` is not dominated by `inner_header` and +# causes `outer_back_edge` to not be dominated by `outer_header`. HGraphBuilder +# not do a fix-point iteration and would miss the path to `outer_back_edge` +# through `inner_back_edge` and incorrectly label the outer loop non-irreducible. + +## CHECK-START: int IrreducibleLoop.dominance(int) builder (after) +## CHECK: Add irreducible:true + +.method public static dominance(I)I + .registers 2 + + if-eqz p0, :outer_header + goto :inner_back_edge + + :outer_header + if-eqz p0, :inner_header + + :outer_branch_exit + if-eqz p0, :outer_merge + return p0 + + :inner_header + goto :outer_merge + + :inner_back_edge + goto :inner_header + + :outer_merge + if-eqz p0, :inner_back_edge + + :outer_back_edge + add-int/2addr p0, p0 + goto :outer_header + +.end method diff --git a/test/598-checker-irreducible-dominance/src/Main.java b/test/598-checker-irreducible-dominance/src/Main.java new file mode 100644 index 0000000000..38b2ab4384 --- /dev/null +++ b/test/598-checker-irreducible-dominance/src/Main.java @@ -0,0 +1,25 @@ +/* + * Copyright (C) 2016 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. + */ + +public class Main { + // Workaround for b/18051191. + class InnerClass {} + + public static void main(String[] args) { + // Nothing to run. This regression test merely makes sure the smali test + // case successfully compiles. + } +} |