From adf84911030ca36835c48cbff8be6b078693fb00 Mon Sep 17 00:00:00 2001
From: David Brazdil <dbrazdil@google.com>
Date: Thu, 14 Apr 2016 13:47:24 +0100
Subject: 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
---
 compiler/optimizing/ssa_liveness_analysis.h | 56 +++++++++++++++++++++++++++--
 1 file changed, 53 insertions(+), 3 deletions(-)

(limited to 'compiler/optimizing/ssa_liveness_analysis.h')

diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 97f2aeeb1e..719feec468 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -969,6 +969,38 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
     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 @@ 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.
-        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,
-- 
cgit v1.2.3-59-g8ed1b