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
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,