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

4 files changed, 85 insertions, 114 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index f3c1dbe3f5..3b93b2b571 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -763,6 +763,14 @@ void SSAChecker::VisitPhi(HPhi* phi) {
                                 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 94a297c9e6..8113e65121 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -124,91 +124,6 @@ void ReferenceTypePropagation::ValidateTypes() {
   }
 }
 
-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 @@ void ReferenceTypePropagation::Run() {
   }
 
   ProcessWorklist();
-  SetUntypedInstructionsToObject();
   ValidateTypes();
 }
 
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 21789e1331..5c05592726 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -57,7 +57,6 @@ class ReferenceTypePropagation : public HOptimization {
       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 63aba88c2b..2eef307295 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 @@ void SsaRedundantPhiElimination::Run() {
     }
   }
 
+  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 @@ void SsaRedundantPhiElimination::Run() {
       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);
-
-    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) {
+    HInstruction* candidate = nullptr;
+    visited_phis_in_cycle.clear();
+    cycle_worklist.clear();
+
+    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) {
-      continue;
+      // 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;
+          }
+        }
+      }
     }
 
-    // The candidate may not dominate a phi in a catch block.
-    if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) {
+    if (candidate == nullptr) {
       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));
+      }
+
+      // 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);
     }
-
-    phi->ReplaceWith(candidate);
-    phi->GetBlock()->RemovePhi(phi);
   }
 }