Fix another case of live_in at irreducible loop entry.

GVN was implicitly extending the liveness of an instruction across
an irreducible loop.

Fix this problem by clearing the value set at loop entries that contain
an irreducible loop.

bug:28252896
Change-Id: I68823cb88dceb4c2b4545286ba54fd0c958a48b0

12 files changed, 154 insertions, 45 deletions

diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 9efc13f61b..ccaf492f65 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -544,26 +544,19 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
       }
     }
 
-    if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
-        || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)
-        || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName)
-        || IsPass(BoundsCheckElimination::kBoundsCheckEliminationPassName)
-        || IsPass(RegisterAllocator::kRegisterAllocatorPassName)
-        || IsPass(HGraphBuilder::kBuilderPassName)) {
-      HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
-      if (info == nullptr) {
-        StartAttributeStream("loop") << "none";
+    HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
+    if (loop_info == nullptr) {
+      StartAttributeStream("loop") << "none";
+    } else {
+      StartAttributeStream("loop") << "B" << loop_info->GetHeader()->GetBlockId();
+      HLoopInformation* outer = loop_info->GetPreHeader()->GetLoopInformation();
+      if (outer != nullptr) {
+        StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
       } else {
-        StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
-        HLoopInformation* outer = info->GetPreHeader()->GetLoopInformation();
-        if (outer != nullptr) {
-          StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
-        } else {
-          StartAttributeStream("outer_loop") << "none";
-        }
-        StartAttributeStream("irreducible")
-            << std::boolalpha << info->IsIrreducible() << std::noboolalpha;
+        StartAttributeStream("outer_loop") << "none";
       }
+      StartAttributeStream("irreducible")
+          << std::boolalpha << loop_info->IsIrreducible() << std::noboolalpha;
     }
 
     if ((IsPass(HGraphBuilder::kBuilderPassName)
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index d0d52bf6cc..1e86b75075 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -454,11 +454,16 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
 
     if (!set->IsEmpty()) {
       if (block->IsLoopHeader()) {
-        if (block->GetLoopInformation()->IsIrreducible()) {
+        if (block->GetLoopInformation()->ContainsIrreducibleLoop()) {
           // To satisfy our linear scan algorithm, no instruction should flow in an irreducible
-          // loop header.
+          // loop header. We clear the set at entry of irreducible loops and any loop containing
+          // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction
+          // across the irreducible loop.
+          // Note that, if we're not compiling OSR, we could still do GVN and introduce
+          // phis at irreducible loop headers. We decided it was not worth the complexity.
           set->Clear();
         } else {
+          DCHECK(!block->GetLoopInformation()->IsIrreducible());
           DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
           set->Kill(side_effects_.GetLoopEffects(block));
         }
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 5a0b89c90a..7543cd6c54 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -101,16 +101,6 @@ void LICM::Run() {
     SideEffects loop_effects = side_effects_.GetLoopEffects(block);
     HBasicBlock* pre_header = loop_info->GetPreHeader();
 
-    bool contains_irreducible_loop = false;
-    if (graph_->HasIrreducibleLoops()) {
-      for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
-        if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
-          contains_irreducible_loop = true;
-          break;
-        }
-      }
-    }
-
     for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
       HBasicBlock* inner = it_loop.Current();
       DCHECK(inner->IsInLoop());
@@ -123,11 +113,12 @@ void LICM::Run() {
         visited->SetBit(inner->GetBlockId());
       }
 
-      if (contains_irreducible_loop) {
+      if (loop_info->ContainsIrreducibleLoop()) {
         // We cannot licm in an irreducible loop, or in a natural loop containing an
         // irreducible loop.
         continue;
       }
+      DCHECK(!loop_info->IsIrreducible());
 
       // We can move an instruction that can throw only if it is the first
       // throwing instruction in the loop. Note that the first potentially
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index eb9c381c4e..3910ca402a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -442,8 +442,10 @@ void HGraph::SimplifyCFG() {
 }
 
 GraphAnalysisResult HGraph::AnalyzeLoops() const {
-  // Order does not matter.
-  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+  // We iterate post order to ensure we visit inner loops before outer loops.
+  // `PopulateRecursive` needs this guarantee to know whether a natural loop
+  // contains an irreducible loop.
+  for (HPostOrderIterator it(*this); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     if (block->IsLoopHeader()) {
       if (block->IsCatchBlock()) {
@@ -576,6 +578,14 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
 
   blocks_.SetBit(block->GetBlockId());
   block->SetInLoop(this);
+  if (block->IsLoopHeader()) {
+    // We're visiting loops in post-order, so inner loops must have been
+    // populated already.
+    DCHECK(block->GetLoopInformation()->IsPopulated());
+    if (block->GetLoopInformation()->IsIrreducible()) {
+      contains_irreducible_loop_ = true;
+    }
+  }
   for (HBasicBlock* predecessor : block->GetPredecessors()) {
     PopulateRecursive(predecessor);
   }
@@ -679,6 +689,7 @@ void HLoopInformation::Populate() {
   }
   if (is_irreducible_loop) {
     irreducible_ = true;
+    contains_irreducible_loop_ = true;
     graph->SetHasIrreducibleLoops(true);
   }
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 71ad8e57a7..6960ceb965 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -650,6 +650,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
       : header_(header),
         suspend_check_(nullptr),
         irreducible_(false),
+        contains_irreducible_loop_(false),
         back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)),
         // Make bit vector growable, as the number of blocks may change.
         blocks_(graph->GetArena(), graph->GetBlocks().size(), true, kArenaAllocLoopInfoBackEdges) {
@@ -657,6 +658,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
   }
 
   bool IsIrreducible() const { return irreducible_; }
+  bool ContainsIrreducibleLoop() const { return contains_irreducible_loop_; }
 
   void Dump(std::ostream& os);
 
@@ -727,6 +729,10 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
 
   bool HasBackEdgeNotDominatedByHeader() const;
 
+  bool IsPopulated() const {
+    return blocks_.GetHighestBitSet() != -1;
+  }
+
  private:
   // Internal recursive implementation of `Populate`.
   void PopulateRecursive(HBasicBlock* block);
@@ -735,6 +741,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
   HBasicBlock* header_;
   HSuspendCheck* suspend_check_;
   bool irreducible_;
+  bool contains_irreducible_loop_;
   ArenaVector<HBasicBlock*> back_edges_;
   ArenaBitVector blocks_;
 
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index b1f9cbcdfa..4405b803e0 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1773,7 +1773,9 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
     // therefore will not have a location for that instruction for `to`.
     // Because the instruction is a constant or the ArtMethod, we don't need to
     // do anything: it will be materialized in the irreducible loop.
-    DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
+    DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
+        << defined_by->DebugName() << ":" << defined_by->GetId()
+        << " " << from->GetBlockId() << " -> " << to->GetBlockId();
     return;
   }
 
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 5534aeac29..36e0d993d1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -309,17 +309,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
     }
 
     if (block->IsLoopHeader()) {
-      if (kIsDebugBuild && block->GetLoopInformation()->IsIrreducible()) {
-        // To satisfy our liveness algorithm, we need to ensure loop headers of
-        // irreducible loops do not have any live-in instructions, except constants
-        // and the current method, which can be trivially re-materialized.
-        for (uint32_t idx : live_in->Indexes()) {
-          HInstruction* instruction = GetInstructionFromSsaIndex(idx);
-          DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
-          DCHECK(!instruction->IsParameterValue());
-          DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
-              << instruction->DebugName();
-        }
+      if (kIsDebugBuild) {
+        CheckNoLiveInIrreducibleLoop(*block);
       }
       size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
       // For all live_in instructions at the loop header, we need to create a range
@@ -344,6 +335,9 @@ void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
       // change in this loop), and the live_out set.  If the live_out
       // set does not change, there is no need to update the live_in set.
       if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+        if (kIsDebugBuild) {
+          CheckNoLiveInIrreducibleLoop(block);
+        }
         changed = true;
       }
     }
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 1141fd1c76..1fcba8bc77 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1260,6 +1260,23 @@ class SsaLivenessAnalysis : public ValueObject {
     return instruction->GetType() == Primitive::kPrimNot;
   }
 
+  void CheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
+    if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
+      return;
+    }
+    BitVector* live_in = GetLiveInSet(block);
+    // To satisfy our liveness algorithm, we need to ensure loop headers of
+    // irreducible loops do not have any live-in instructions, except constants
+    // and the current method, which can be trivially re-materialized.
+    for (uint32_t idx : live_in->Indexes()) {
+      HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+      DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+      DCHECK(!instruction->IsParameterValue());
+      DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+          << instruction->DebugName();
+    }
+  }
+
   HGraph* const graph_;
   CodeGenerator* const codegen_;
   ArenaVector<BlockInfo*> block_infos_;
diff --git a/test/599-checker-irreducible-loop/expected.txt b/test/599-checker-irreducible-loop/expected.txt
new file mode 100644
index 0000000000..573541ac97
--- /dev/null
+++ b/test/599-checker-irreducible-loop/expected.txt
@@ -0,0 +1 @@
+0
diff --git a/test/599-checker-irreducible-loop/info.txt b/test/599-checker-irreducible-loop/info.txt
new file mode 100644
index 0000000000..1e0dd02284
--- /dev/null
+++ b/test/599-checker-irreducible-loop/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing in the presence of
+an irreducible loop.
diff --git a/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000000..5331fd6a31
--- /dev/null
+++ b/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -0,0 +1,56 @@
+# Copyright (C) 2016 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LIrreducibleLoop;
+
+.super Ljava/lang/Object;
+
+## CHECK-START: int IrreducibleLoop.test(int) GVN (before)
+## CHECK-DAG:                     LoadClass loop:none
+## CHECK-DAG:                     LoadClass loop:{{B\d+}} outer_loop:none
+
+## CHECK-START: int IrreducibleLoop.test(int) GVN (after)
+## CHECK-DAG:                     LoadClass loop:none
+## CHECK-DAG:                     LoadClass loop:{{B\d+}} outer_loop:none
+.method public static test(I)I
+   .registers 2
+
+   sget v0, LIrreducibleLoop;->field1:I
+   sput v0, LIrreducibleLoop;->field2:I
+
+   if-eqz p0, :loop_entry
+   goto :exit
+
+   :loop_entry
+   if-eqz p0, :irreducible_loop_entry
+   sget v0, LIrreducibleLoop;->field2:I
+   sput v0, LIrreducibleLoop;->field1:I
+   if-eqz v0, :exit
+   goto :irreducible_other_loop_entry
+
+   :irreducible_loop_entry
+   if-eqz p0, :loop_back_edge
+   :irreducible_other_loop_entry
+   if-eqz v0, :loop_back_edge
+   goto :irreducible_loop_entry
+
+   :loop_back_edge
+   goto :loop_entry
+
+   :exit
+   return v0
+.end method
+
+.field public static field1:I
+.field public static field2:I
diff --git a/test/599-checker-irreducible-loop/src/Main.java b/test/599-checker-irreducible-loop/src/Main.java
new file mode 100644
index 0000000000..b47721f721
--- /dev/null
+++ b/test/599-checker-irreducible-loop/src/Main.java
@@ -0,0 +1,30 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("IrreducibleLoop");
+    Method m = c.getMethod("test", int.class);
+    Object[] arguments = { 42 };
+    // Invoke the code just for sanity checking.
+    System.out.println(m.invoke(null, arguments));
+  }
+}