diff options
| -rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 33 | ||||
| -rw-r--r-- | test/594-checker-irreducible-linorder/smali/IrreducibleLoop.smali | 54 |
2 files changed, 66 insertions, 21 deletions
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 40dab74a23..1141fd1c76 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -1003,6 +1003,15 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { 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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { 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 366c7b9b68..ef53ee867a 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 |