ART: Disable back edge uses for irreducible loops
Algorithm adding back edge uses in liveness analysis makes assumptions
about the linear order which are not met in the presence of irreducible
loops. Disable back edges uses when the graph contains them.
This partially reverts CL I63632e8819ea3644d5c6fdfea00b66128bf22c24.
Bug: 28252747
Bug: 27615840
Bug: 27624868
Change-Id: I7ecdde0ed8a8831f7513b8e43cf7d84599b830a7
(cherry picked from commit 07b35109c64fc449a14723b259df17806fd0b16e)
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 40dab74..1141fd1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1003,6 +1003,15 @@
void AddBackEdgeUses(const HBasicBlock& block_at_use) {
DCHECK(block_at_use.IsInLoop());
+ if (block_at_use.GetGraph()->HasIrreducibleLoops()) {
+ // Linear order may not be well formed when irreducible loops are present,
+ // i.e. loop blocks may not be adjacent and a back edge may not be last,
+ // which violates assumptions made in this method.
+ return;
+ }
+
+ DCHECK(IsLinearOrderWellFormed(*block_at_use.GetGraph()));
+
// Add synthesized uses at the back edge of loops to help the register allocator.
// Note that this method is called in decreasing liveness order, to faciliate adding
// uses at the head of the `first_use_` linked list. Because below
@@ -1027,30 +1036,12 @@
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.
- 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()));
- }
- }
+ DCHECK(HasSynthesizeUseAt(back_edge_use_position));
break;
}
- 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;
- }
+ DCHECK(last_in_new_list == nullptr ||
+ back_edge_use_position > last_in_new_list->GetPosition());
UsePosition* new_use = new (allocator_) UsePosition(
/* user */ nullptr,
diff --git a/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali b/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
index 366c7b9..ef53ee8 100644
--- a/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
+++ b/test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali
@@ -67,3 +67,57 @@
return p3
.end method
+
+## CHECK-START: int IrreducibleLoop.liveness2(boolean, boolean, boolean, int) builder (after)
+## CHECK-DAG: Mul loop:<<Loop:B\d+>>
+## CHECK-DAG: Not loop:<<Loop>>
+
+## CHECK-START: int IrreducibleLoop.liveness2(boolean, boolean, boolean, int) liveness (after)
+## CHECK-DAG: Mul liveness:<<LPreEntry2:\d+>>
+## CHECK-DAG: Not liveness:<<LBackEdge1:\d+>>
+## CHECK-EVAL: <<LBackEdge1>> < <<LPreEntry2>>
+
+.method public liveness2(ZZZI)I
+ .registers 10
+
+ const v1, 1
+
+ :header1
+ if-eqz p0, :body1
+
+ :exit
+ return p3
+
+ :body1
+ # The test will generate an incorrect linear order when the following IF swaps
+ # its successors. To do that, load a boolean value and compare NotEqual to 1.
+ sget-boolean v2, LIrreducibleLoop;->f:Z
+ const v3, 1
+ if-ne v2, v3, :pre_header2
+
+ :pre_entry2
+ # This constant has a use in a phi in :back_edge2 and a back edge use in
+ # :back_edge1. Because the linear order is wrong, the back edge use has
+ # a lower liveness than the phi use.
+ const v0, 42
+ mul-int/2addr p3, p3
+ goto :back_edge2
+
+ :back_edge2
+ add-int/2addr p3, v0
+ add-int/2addr v0, v1
+ goto :header2
+
+ :header2
+ if-eqz p2, :back_edge2
+
+ :back_edge1
+ not-int p3, p3
+ goto :header1
+
+ :pre_header2
+ const v0, 42
+ goto :header2
+.end method
+
+.field public static f:Z
