ART: Update DCHECKs in SsaLivenessAnalysis::AddBackEdgeUses
Graph linearization in the presence of irreducible loops is not
guaranteed to generate a linear order where all blocks of a loop are
adjacent, first block is the header and last block is one of the back
edges.
These assumptions are made when inserting synthesized uses at the back
edges to aid the register allocator. Not meeting them will result in
the algorithm's early termination and back-edge uses not being added.
This patch updates the DCHECKs so the compiler does not fail in such
circumstances.
Bug: 27615840
Bug: 27624868
Change-Id: I63632e8819ea3644d5c6fdfea00b66128bf22c24
(cherry picked from commit adf84911030ca36835c48cbff8be6b078693fb00)
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 97f2aee..719feec 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -969,6 +969,38 @@
return false;
}
+ bool IsLinearOrderWellFormed(const HGraph& graph) {
+ for (HBasicBlock* header : graph.GetBlocks()) {
+ if (!header->IsLoopHeader()) {
+ continue;
+ }
+
+ HLoopInformation* loop = header->GetLoopInformation();
+ size_t num_blocks = loop->GetBlocks().NumSetBits();
+ size_t found_blocks = 0u;
+
+ for (HLinearOrderIterator it(graph); !it.Done(); it.Advance()) {
+ HBasicBlock* current = it.Current();
+ if (loop->Contains(*current)) {
+ found_blocks++;
+ if (found_blocks == 1u && current != header) {
+ // First block is not the header.
+ return false;
+ } else if (found_blocks == num_blocks && !loop->IsBackEdge(*current)) {
+ // Last block is not a back edge.
+ return false;
+ }
+ } else if (found_blocks != 0u && found_blocks != num_blocks) {
+ // Blocks are not adjacent.
+ return false;
+ }
+ }
+ DCHECK_EQ(found_blocks, num_blocks);
+ }
+
+ return true;
+ }
+
void AddBackEdgeUses(const HBasicBlock& block_at_use) {
DCHECK(block_at_use.IsInLoop());
// Add synthesized uses at the back edge of loops to help the register allocator.
@@ -995,12 +1027,30 @@
if ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
// There was a use already seen in this loop. Therefore the previous call to `AddUse`
// already inserted the backedge use. We can stop going outward.
- DCHECK(HasSynthesizeUseAt(back_edge_use_position));
+ if (kIsDebugBuild) {
+ if (!HasSynthesizeUseAt(back_edge_use_position)) {
+ // There exists a use prior to `back_edge_use_position` but there is
+ // no synthesized use at the back edge. This can happen in the presence
+ // of irreducible loops, when blocks of the loop are not adjacent in
+ // linear order, i.e. when there is an out-of-loop block between
+ // `block_at_use` and `back_edge_position` that uses this interval.
+ DCHECK(block_at_use.GetGraph()->HasIrreducibleLoops());
+ DCHECK(!IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+ }
+ }
break;
}
- DCHECK(last_in_new_list == nullptr
- || back_edge_use_position > last_in_new_list->GetPosition());
+ if (last_in_new_list != nullptr &&
+ back_edge_use_position <= last_in_new_list->GetPosition()) {
+ // Loops are not properly nested in the linear order, i.e. the back edge
+ // of an outer loop preceeds blocks of an inner loop. This can happen
+ // in the presence of irreducible loops.
+ DCHECK(block_at_use.GetGraph()->HasIrreducibleLoops());
+ DCHECK(!IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+ // We must bail out, otherwise we would generate an unsorted use list.
+ break;
+ }
UsePosition* new_use = new (allocator_) UsePosition(
/* user */ nullptr,
diff --git a/test/594-checker-regression-irreducible-linorder/expected.txt b/test/594-checker-regression-irreducible-linorder/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/expected.txt
diff --git a/test/594-checker-regression-irreducible-linorder/info.txt b/test/594-checker-regression-irreducible-linorder/info.txt
new file mode 100644
index 0000000..a1783f8
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/info.txt
@@ -0,0 +1,2 @@
+Regression test for a failing DCHECK in SSA liveness analysis in the presence
+of irreducible loops.
diff --git a/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali b/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..8e01084
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/smali/IrreducibleLoop.smali
@@ -0,0 +1,64 @@
+# 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 where liveness analysis produces linear order where loop blocks are
+# not adjacent.
+
+## CHECK-START: int IrreducibleLoop.liveness(boolean, boolean, boolean, int) builder (after)
+## CHECK-DAG: Add loop:none
+## CHECK-DAG: Mul loop:<<Loop:B\d+>>
+## CHECK-DAG: Not loop:<<Loop>>
+
+## CHECK-START: int IrreducibleLoop.liveness(boolean, boolean, boolean, int) liveness (after)
+## CHECK-DAG: Add liveness:<<LPreEntry:\d+>>
+## CHECK-DAG: Mul liveness:<<LHeader:\d+>>
+## CHECK-DAG: Not liveness:<<LBackEdge:\d+>>
+## CHECK-EVAL: (<<LHeader>> < <<LPreEntry>>) and (<<LPreEntry>> < <<LBackEdge>>)
+
+.method public static liveness(ZZZI)I
+ .registers 10
+ const/16 v0, 42
+
+ if-eqz p0, :header
+
+ :pre_entry
+ add-int/2addr p3, p3
+ invoke-static {v0}, Ljava/lang/System;->exit(I)V
+ goto :body1
+
+ :header
+ mul-int/2addr p3, p3
+ if-eqz p1, :body2
+
+ :body1
+ goto :body_merge
+
+ :body2
+ invoke-static {v0}, Ljava/lang/System;->exit(I)V
+ goto :body_merge
+
+ :body_merge
+ if-eqz p2, :exit
+
+ :back_edge
+ not-int p3, p3
+ goto :header
+
+ :exit
+ return p3
+
+.end method
diff --git a/test/594-checker-regression-irreducible-linorder/src/Main.java b/test/594-checker-regression-irreducible-linorder/src/Main.java
new file mode 100644
index 0000000..38b2ab4
--- /dev/null
+++ b/test/594-checker-regression-irreducible-linorder/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.
+ }
+}
