ART: Rediscover loops after deleting blocks in DCE

The way DCE currently updates loop information does not cover all
cases. This patch removes the logic, resets loop information of live
blocks to pre-SSA state and reanalyzes the affected loops.

Change-Id: I0b996a70235b95a8db0de9a23a03f71db57a21b8
(cherry picked from commit a4b8c21dae70ae34aee13628632c39a675c06022)

6 files changed, 70 insertions, 32 deletions

diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index cd427c5ed8..6fbe75e802 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -47,6 +47,12 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
   }
 }
 
+static void MarkLoopHeadersContaining(const HBasicBlock& block, ArenaBitVector* set) {
+  for (HLoopInformationOutwardIterator it(block); !it.Done(); it.Advance()) {
+    set->SetBit(it.Current()->GetHeader()->GetBlockId());
+  }
+}
+
 void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
   if (stats_ != nullptr) {
     stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
@@ -58,18 +64,24 @@ void HDeadCodeElimination::RemoveDeadBlocks() {
   // Classify blocks as reachable/unreachable.
   ArenaAllocator* allocator = graph_->GetArena();
   ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false);
+  ArenaBitVector affected_loops(allocator, graph_->GetBlocks().Size(), false);
+
   MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
 
-  // Remove all dead blocks. Process blocks in post-order, because removal needs
-  // the block's chain of dominators.
+  // Remove all dead blocks. Iterate in post order because removal needs the
+  // block's chain of dominators and nested loops need to be updated from the
+  // inside out.
   for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block  = it.Current();
-    if (live_blocks.IsBitSet(block->GetBlockId())) {
-      // If this block is part of a loop that is being dismantled, we need to
-      // update its loop information.
-      block->UpdateLoopInformation();
+    int id = block->GetBlockId();
+    if (live_blocks.IsBitSet(id)) {
+      if (affected_loops.IsBitSet(id)) {
+        DCHECK(block->IsLoopHeader());
+        block->GetLoopInformation()->Update();
+      }
     } else {
       MaybeRecordDeadBlock(block);
+      MarkLoopHeadersContaining(*block, &affected_loops);
       block->DisconnectAndDelete();
     }
   }
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index 0bea0fc1c2..59a57c4345 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -31,13 +31,13 @@ class HDeadCodeElimination : public HOptimization {
  public:
   HDeadCodeElimination(HGraph* graph,
                        OptimizingCompilerStats* stats = nullptr,
-                       const char* name = kDeadCodeEliminationPassName)
+                       const char* name = kInitialDeadCodeEliminationPassName)
       : HOptimization(graph, true, name, stats) {}
 
   void Run() OVERRIDE;
 
-  static constexpr const char* kDeadCodeEliminationPassName =
-    "dead_code_elimination";
+  static constexpr const char* kInitialDeadCodeEliminationPassName = "dead_code_elimination";
+  static constexpr const char* kFinalDeadCodeEliminationPassName = "dead_code_elimination_final";
 
  private:
   void MaybeRecordDeadBlock(HBasicBlock* block);
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 7130127136..f5c630bf97 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -17,6 +17,7 @@
 #include "graph_visualizer.h"
 
 #include "code_generator.h"
+#include "dead_code_elimination.h"
 #include "licm.h"
 #include "nodes.h"
 #include "optimization.h"
@@ -253,7 +254,8 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
         }
       }
       output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
-    } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)) {
+    } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
+               || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)) {
       output_ << " ( loop_header:";
       HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
       if (info == nullptr) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b9e58c7032..41adc7223e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -17,6 +17,7 @@
 #include "nodes.h"
 
 #include "ssa_builder.h"
+#include "base/bit_vector-inl.h"
 #include "utils/growable_array.h"
 #include "scoped_thread_state_change.h"
 
@@ -346,6 +347,7 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
 }
 
 bool HLoopInformation::Populate() {
+  DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
   for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) {
     HBasicBlock* back_edge = GetBackEdges().Get(i);
     DCHECK(back_edge->GetDominator() != nullptr);
@@ -365,6 +367,39 @@ bool HLoopInformation::Populate() {
   return true;
 }
 
+void HLoopInformation::Update() {
+  HGraph* graph = header_->GetGraph();
+  for (uint32_t id : blocks_.Indexes()) {
+    HBasicBlock* block = graph->GetBlocks().Get(id);
+    // Reset loop information of non-header blocks inside the loop, except
+    // members of inner nested loops because those should already have been
+    // updated by their own LoopInformation.
+    if (block->GetLoopInformation() == this && block != header_) {
+      block->SetLoopInformation(nullptr);
+    }
+  }
+  blocks_.ClearAllBits();
+
+  if (back_edges_.IsEmpty()) {
+    // The loop has been dismantled, delete its suspend check and remove info
+    // from the header.
+    DCHECK(HasSuspendCheck());
+    header_->RemoveInstruction(suspend_check_);
+    header_->SetLoopInformation(nullptr);
+    header_ = nullptr;
+    suspend_check_ = nullptr;
+  } else {
+    if (kIsDebugBuild) {
+      for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
+        DCHECK(header_->Dominates(back_edges_.Get(i)));
+      }
+    }
+    // This loop still has reachable back edges. Repopulate the list of blocks.
+    bool populate_successful = Populate();
+    DCHECK(populate_successful);
+  }
+}
+
 HBasicBlock* HLoopInformation::GetPreHeader() const {
   return header_->GetDominator();
 }
@@ -1049,20 +1084,6 @@ void HBasicBlock::DisconnectAndDelete() {
   SetGraph(nullptr);
 }
 
-void HBasicBlock::UpdateLoopInformation() {
-  // Check if loop information points to a dismantled loop. If so, replace with
-  // the loop information of a larger loop which contains this block, or nullptr
-  // otherwise. We iterate in case the larger loop has been destroyed too.
-  while (IsInLoop() && loop_information_->GetBackEdges().IsEmpty()) {
-    if (IsLoopHeader()) {
-      HSuspendCheck* suspend_check = loop_information_->GetSuspendCheck();
-      DCHECK_EQ(suspend_check->GetBlock(), this);
-      RemoveInstruction(suspend_check);
-    }
-    loop_information_ = loop_information_->GetPreHeader()->GetLoopInformation();
-  }
-}
-
 void HBasicBlock::MergeWith(HBasicBlock* other) {
   DCHECK_EQ(GetGraph(), other->GetGraph());
   DCHECK(GetDominatedBlocks().Contains(other));
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 031761e7f7..77b587e74f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -436,6 +436,12 @@ class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
   // that is the header dominates the back edge.
   bool Populate();
 
+  // Reanalyzes the loop by removing loop info from its blocks and re-running
+  // Populate(). If there are no back edges left, the loop info is completely
+  // removed as well as its SuspendCheck instruction. It must be run on nested
+  // inner loops first.
+  void Update();
+
   // Returns whether this loop information contains `block`.
   // Note that this loop information *must* be populated before entering this function.
   bool Contains(const HBasicBlock& block) const;
@@ -705,14 +711,9 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
     loop_information_ = info;
   }
 
-  // Checks if the loop information points to a valid loop. If the loop has been
-  // dismantled (does not have a back edge any more), loop information is
-  // removed or replaced with the information of the first valid outer loop.
-  void UpdateLoopInformation();
-
   bool IsInLoop() const { return loop_information_ != nullptr; }
 
-  // Returns wheter this block dominates the blocked passed as parameter.
+  // Returns whether this block dominates the blocked passed as parameter.
   bool Dominates(HBasicBlock* block) const;
 
   size_t GetLifetimeStart() const { return lifetime_start_; }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index e993d778d4..8bb5d8ebae 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -320,8 +320,10 @@ static void RunOptimizations(HGraph* graph,
                              const DexCompilationUnit& dex_compilation_unit,
                              PassInfoPrinter* pass_info_printer,
                              StackHandleScopeCollection* handles) {
-  HDeadCodeElimination dce1(graph, stats);
-  HDeadCodeElimination dce2(graph, stats, "dead_code_elimination_final");
+  HDeadCodeElimination dce1(graph, stats,
+                            HDeadCodeElimination::kInitialDeadCodeEliminationPassName);
+  HDeadCodeElimination dce2(graph, stats,
+                            HDeadCodeElimination::kFinalDeadCodeEliminationPassName);
   HConstantFolding fold1(graph);
   InstructionSimplifier simplify1(graph, stats);
   HBooleanSimplifier boolean_simplify(graph);