Detect phi cycles.

Having reference and non-reference phi equivalent, only happened
for the 0/null constant. To avoid such occurences, we must
detect phi cycles.

bug:25493693

Change-Id: Ie1a8460c3abacca96c299da107fa4407e17dd792
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index f3c1dbe..3b93b2b 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -763,6 +763,14 @@
                                 phi->GetId(),
                                 phi->GetRegNumber(),
                                 type_str.str().c_str()));
+        } else if (phi->GetType() == Primitive::kPrimNot) {
+          std::stringstream type_str;
+          type_str << other_phi->GetType();
+          AddError(StringPrintf(
+              "Equivalent non-reference phi (%d) found for VReg %d with type: %s.",
+              phi->GetId(),
+              phi->GetRegNumber(),
+              type_str.str().c_str()));
         } else {
           ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true);
           if (!IsConstantEquivalent(phi, other_phi, &visited)) {
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 94a297c..8113e65 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -124,91 +124,6 @@
   }
 }
 
-static void CheckHasNoTypedInputs(HInstruction* root_instr) {
-  ArenaAllocatorAdapter<void> adapter =
-      root_instr->GetBlock()->GetGraph()->GetArena()->Adapter(kArenaAllocReferenceTypePropagation);
-
-  ArenaVector<HPhi*> visited_phis(adapter);
-  ArenaVector<HInstruction*> worklist(adapter);
-  worklist.push_back(root_instr);
-
-  while (!worklist.empty()) {
-    HInstruction* instr = worklist.back();
-    worklist.pop_back();
-
-    if (instr->IsPhi() || instr->IsBoundType() || instr->IsNullCheck()) {
-      // Expect that both `root_instr` and its inputs have invalid RTI.
-      ScopedObjectAccess soa(Thread::Current());
-      DCHECK(!instr->GetReferenceTypeInfo().IsValid()) << "Instruction should not have valid RTI.";
-
-      // Insert all unvisited inputs to the worklist.
-      for (HInputIterator it(instr); !it.Done(); it.Advance()) {
-        HInstruction* input = it.Current();
-        if (input->IsPhi()) {
-          if (ContainsElement(visited_phis, input->AsPhi())) {
-            continue;
-          } else {
-            visited_phis.push_back(input->AsPhi());
-          }
-        }
-        worklist.push_back(input);
-      }
-    } else if (instr->IsNullConstant()) {
-      // The only input of `root_instr` allowed to have valid RTI because it is ignored.
-    } else {
-      LOG(FATAL) << "Unexpected input " << instr->DebugName() << instr->GetId() << " with RTI "
-          << instr->GetReferenceTypeInfo();
-      UNREACHABLE();
-    }
-  }
-}
-
-template<typename Functor>
-static void ForEachUntypedInstruction(HGraph* graph, Functor fn) {
-  ScopedObjectAccess soa(Thread::Current());
-  for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) {
-    for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) {
-      HPhi* phi = it.Current()->AsPhi();
-      // Note that the graph may contain dead phis when run from the SsaBuilder.
-      // Skip those as they might have a type conflict and will be removed anyway.
-      if (phi->IsLive() &&
-          phi->GetType() == Primitive::kPrimNot &&
-          !phi->GetReferenceTypeInfo().IsValid()) {
-        fn(phi);
-      }
-    }
-    for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) {
-      HInstruction* instr = it.Current();
-      if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
-        fn(instr);
-      }
-    }
-  }
-}
-
-void ReferenceTypePropagation::SetUntypedInstructionsToObject() {
-  // In some cases, the fix-point iteration will leave kPrimNot instructions with
-  // invalid RTI because bytecode does not provide enough typing information.
-  // Set the RTI of such instructions to Object.
-  // Example:
-  //   MyClass a = null, b = null;
-  //   while (a == null) {
-  //     if (cond) { a = b; } else { b = a; }
-  //   }
-
-  if (kIsDebugBuild) {
-    // Test that if we are going to set RTI from invalid to Object, that
-    // instruction did not have any typed instructions in its def-use chain
-    // and therefore its type could not be inferred.
-    ForEachUntypedInstruction(graph_, [](HInstruction* instr) { CheckHasNoTypedInputs(instr); });
-  }
-
-  ReferenceTypeInfo obj_rti = ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false);
-  ForEachUntypedInstruction(graph_, [obj_rti](HInstruction* instr) {
-    instr->SetReferenceTypeInfo(obj_rti);
-  });
-}
-
 void ReferenceTypePropagation::Run() {
   // To properly propagate type info we need to visit in the dominator-based order.
   // Reverse post order guarantees a node's dominators are visited first.
@@ -218,7 +133,6 @@
   }
 
   ProcessWorklist();
-  SetUntypedInstructionsToObject();
   ValidateTypes();
 }
 
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 21789e1..5c05592 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -57,7 +57,6 @@
       SHARED_REQUIRES(Locks::mutator_lock_);
 
   void ValidateTypes();
-  void SetUntypedInstructionsToObject();
 
   StackHandleScopeCollection* handles_;
 
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 63aba88..2eef307 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -17,6 +17,7 @@
 #include "ssa_phi_elimination.h"
 
 #include "base/arena_containers.h"
+#include "base/bit_vector-inl.h"
 
 namespace art {
 
@@ -129,6 +130,9 @@
     }
   }
 
+  ArenaSet<uint32_t> visited_phis_in_cycle(graph_->GetArena()->Adapter());
+  ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter());
+
   while (!worklist_.empty()) {
     HPhi* phi = worklist_.back();
     worklist_.pop_back();
@@ -143,46 +147,92 @@
       continue;
     }
 
-    // Find if the inputs of the phi are the same instruction.
-    HInstruction* candidate = phi->InputAt(0);
-    // A loop phi cannot have itself as the first phi. Note that this
-    // check relies on our simplification pass ensuring the pre-header
-    // block is first in the list of predecessors of the loop header.
-    DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor());
-    DCHECK_NE(phi, candidate);
+    HInstruction* candidate = nullptr;
+    visited_phis_in_cycle.clear();
+    cycle_worklist.clear();
 
-    for (size_t i = 1; i < phi->InputCount(); ++i) {
-      HInstruction* input = phi->InputAt(i);
-      // For a loop phi, if the input is the phi, the phi is still candidate for
-      // elimination.
-      if (input != candidate && input != phi) {
+    cycle_worklist.push_back(phi);
+    visited_phis_in_cycle.insert(phi->GetId());
+    bool catch_phi_in_cycle = phi->IsCatchPhi();
+
+    // First do a simple loop over inputs and check if they are all the same.
+    for (size_t j = 0; j < phi->InputCount(); ++j) {
+      HInstruction* input = phi->InputAt(j);
+      if (input == phi) {
+        continue;
+      } else if (candidate == nullptr) {
+        candidate = input;
+      } else if (candidate != input) {
         candidate = nullptr;
         break;
       }
     }
 
-    // If the inputs are not the same, continue.
+    // If we haven't found a candidate, check for a phi cycle. Note that we need to detect
+    // such cycles to avoid having reference and non-reference equivalents. We check this
+    // invariant in the graph checker.
+    if (candidate == nullptr) {
+      // We iterate over the array as long as it grows.
+      for (size_t i = 0; i < cycle_worklist.size(); ++i) {
+        HPhi* current = cycle_worklist[i];
+        DCHECK(!current->IsLoopHeaderPhi() ||
+               current->GetBlock()->IsLoopPreHeaderFirstPredecessor());
+
+        for (size_t j = 0; j < current->InputCount(); ++j) {
+          HInstruction* input = current->InputAt(j);
+          if (input == current) {
+            continue;
+          } else if (input->IsPhi()) {
+            if (!ContainsElement(visited_phis_in_cycle, input->GetId())) {
+              cycle_worklist.push_back(input->AsPhi());
+              visited_phis_in_cycle.insert(input->GetId());
+              catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi();
+            } else {
+              // Already visited, nothing to do.
+            }
+          } else if (candidate == nullptr) {
+            candidate = input;
+          } else if (candidate != input) {
+            candidate = nullptr;
+            // Clear the cycle worklist to break out of the outer loop.
+            cycle_worklist.clear();
+            break;
+          }
+        }
+      }
+    }
+
     if (candidate == nullptr) {
       continue;
     }
 
-    // The candidate may not dominate a phi in a catch block.
-    if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) {
-      continue;
-    }
-
-    // Because we're updating the users of this phi, we may have new candidates
-    // for elimination. Add phis that use this phi to the worklist.
-    for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) {
-      HUseListNode<HInstruction*>* current = it.Current();
-      HInstruction* user = current->GetUser();
-      if (user->IsPhi()) {
-        worklist_.push_back(user->AsPhi());
+    for (HPhi* current : cycle_worklist) {
+      // The candidate may not dominate a phi in a catch block: there may be non-throwing
+      // instructions at the beginning of a try range, that may be the first input of
+      // catch phis.
+      // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions
+      // before the try entry.
+      if (catch_phi_in_cycle) {
+        if (!candidate->StrictlyDominates(current)) {
+          continue;
+        }
+      } else {
+        DCHECK(candidate->StrictlyDominates(current));
       }
-    }
 
-    phi->ReplaceWith(candidate);
-    phi->GetBlock()->RemovePhi(phi);
+      // Because we're updating the users of this phi, we may have new candidates
+      // for elimination. Add phis that use this phi to the worklist.
+      for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) {
+        HUseListNode<HInstruction*>* use = it.Current();
+        HInstruction* user = use->GetUser();
+        if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) {
+          worklist_.push_back(user->AsPhi());
+        }
+      }
+      DCHECK(candidate->StrictlyDominates(current));
+      current->ReplaceWith(candidate);
+      current->GetBlock()->RemovePhi(current);
+    }
   }
 }
 
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index fd4dd5e..92cf807 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -722,22 +722,6 @@
     }
   }
 
-  /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after)
-  /// CHECK-DAG:  <<Null:l\d+>>      NullConstant
-  /// CHECK-DAG:  <<PhiA:l\d+>>      Phi [<<Null>>,<<PhiB:l\d+>>,<<PhiA>>] klass:java.lang.Object exact:false
-  /// CHECK-DAG:  <<PhiB>>           Phi [<<Null>>,<<PhiB>>,<<PhiA>>] klass:java.lang.Object exact:false
-  private void testLoopPhisWithNullAndCrossUses(boolean cond) {
-    Main a = null;
-    Main b = null;
-    while (a == null) {
-      if (cond) {
-        a = b;
-      } else {
-        b = a;
-      }
-    }
-  }
-
   /// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() ssa_builder (after)
   /// CHECK-DAG:  <<Null:l\d+>>      NullConstant
   /// CHECK-DAG:  <<LoopPhi:l\d+>>   Phi [<<Null>>,<<Phi:l\d+>>] klass:java.lang.Object[] exact:true
diff --git a/test/557-checker-ref-equivalent/expected.txt b/test/557-checker-ref-equivalent/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/557-checker-ref-equivalent/expected.txt
diff --git a/test/557-checker-ref-equivalent/info.txt b/test/557-checker-ref-equivalent/info.txt
new file mode 100644
index 0000000..30e763b
--- /dev/null
+++ b/test/557-checker-ref-equivalent/info.txt
@@ -0,0 +1 @@
+Checker tests to ensure we do not get reference and integer phi equivalents.
diff --git a/test/557-checker-ref-equivalent/smali/TestCase.smali b/test/557-checker-ref-equivalent/smali/TestCase.smali
new file mode 100644
index 0000000..2472957
--- /dev/null
+++ b/test/557-checker-ref-equivalent/smali/TestCase.smali
@@ -0,0 +1,51 @@
+# Copyright (C) 2015 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 LTestCase;
+
+.super Ljava/lang/Object;
+
+## CHECK-START: void TestCase.testIntRefEquivalent() ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static testIntRefEquivalent()V
+    .registers 4
+
+    const v0, 0
+
+    :try_start
+    invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+    if-eqz v0, :end_if
+    const v0, 0
+    :end_if
+    invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+    goto :no_catch
+    :try_end
+
+    .catch Ljava/lang/Exception; {:try_start .. :try_end} :exception
+    :exception
+    # We used to have a reference and an integer phi equivalents here, which
+    # broke the invariant of not sharing the same spill slot between those two
+    # types.
+    invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+
+    :no_catch
+    goto :try_start
+    return-void
+
+.end method
+
+.method public static foo(ILjava/lang/Object;)V
+    .registers 4
+    return-void
+.end method
diff --git a/test/557-checker-ref-equivalent/src/Main.java b/test/557-checker-ref-equivalent/src/Main.java
new file mode 100644
index 0000000..a970af5
--- /dev/null
+++ b/test/557-checker-ref-equivalent/src/Main.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+public class Main {
+
+  /// CHECK-START: void Main.testRedundantPhiCycle(boolean) ssa_builder (after)
+  /// CHECK-NOT:  Phi
+  private void testRedundantPhiCycle(boolean cond) {
+    Object o = null;
+    while (true) {
+      if (cond) {
+        o = null;
+      }
+      System.out.println(o);
+    }
+  }
+
+  /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after)
+  /// CHECK-NOT:  Phi
+  private void testLoopPhisWithNullAndCrossUses(boolean cond) {
+    Main a = null;
+    Main b = null;
+    while (a == null) {
+      if (cond) {
+        a = b;
+      } else {
+        b = a;
+      }
+    }
+  }
+
+  public static void main(String[] args) {
+  }
+}