ART: Fix dominance for irreducible loops
Computation of dominance was broken in the presence of irreducible
loops because the algorithm assumed that back edges are always
dominated by their respective headers and a fix-point iteration is
therefore unnecessary.
This is not true for irreducible loops, forcing us to revisit their
loop headers and all dependent blocks. This patch adds a fix-point
iteration if a back edge not dominated by its header is found.
Bug: 28611485
Change-Id: If84044e49d5b9c682949648033d2861628d7fe05
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 6703695..cf67e1a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -206,6 +206,22 @@
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 @@
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 @@
}
}
+ // 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 @@
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(),
@@ -667,6 +706,16 @@
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 afb995d..1c0ad6a 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -725,6 +725,8 @@
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 0000000..e69de29
--- /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 0000000..8ca4e63
--- /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 0000000..4d8b515
--- /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 0000000..38b2ab4
--- /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.
+ }
+}