Remove duplicates phis created during SSA transformation

When creating equivalent phis we copy the inputs of the original phi
which may be improperly typed. This will be fixed during the type
propagation but as a result we may have two equivalent phis with the
same type for the same dex register. This is correct but generates more
code and prevent some optimizations.

This CL adds another step in the SSA builder to remove the extra Phi
nodes created due to equality operators.

The graph checker verifies that for a given dex register not two phis
have the same type.

Also, replace zero int constant with null constant when we compare a
reference against null.

Change-Id: Id37cc11a016ea767c7e351575e003d822a9d2e60

5 files changed, 104 insertions, 30 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 7c3c2bf..e4dc534 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -18,6 +18,7 @@
 
 #include <map>
 #include <string>
+#include <sstream>
 
 #include "base/bit_vector-inl.h"
 #include "base/stringprintf.h"
@@ -194,6 +195,17 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
     }
   }
 
+  // Check Phi uniqueness (no two Phis with the same type refer to the same register).
+  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+    HPhi* phi = it.Current()->AsPhi();
+    if (phi->GetNextEquivalentPhiWithSameType() != nullptr) {
+      std::stringstream type_str;
+      type_str << phi->GetType();
+      AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s",
+          phi->GetId(), phi->GetRegNumber(), type_str.str().c_str()));
+    }
+  }
+
   if (block->IsLoopHeader()) {
     CheckLoop(block);
   }
@@ -399,37 +411,23 @@ void SSAChecker::VisitCondition(HCondition* op) {
   }
   HInstruction* lhs = op->InputAt(0);
   HInstruction* rhs = op->InputAt(1);
-  if (lhs->GetType() == Primitive::kPrimNot) {
-    if (!op->IsEqual() && !op->IsNotEqual()) {
+  if (PrimitiveKind(lhs->GetType()) != PrimitiveKind(rhs->GetType())) {
+    AddError(StringPrintf(
+        "Condition %s %d has inputs of different types: %s, and %s.",
+        op->DebugName(), op->GetId(),
+        Primitive::PrettyDescriptor(lhs->GetType()),
+        Primitive::PrettyDescriptor(rhs->GetType())));
+  }
+  if (!op->IsEqual() && !op->IsNotEqual()) {
+    if ((lhs->GetType() == Primitive::kPrimNot)) {
       AddError(StringPrintf(
           "Condition %s %d uses an object as left-hand side input.",
           op->DebugName(), op->GetId()));
-    }
-    if (rhs->IsIntConstant() && rhs->AsIntConstant()->GetValue() != 0) {
-      AddError(StringPrintf(
-          "Condition %s %d compares an object with a non-zero integer: %d.",
-          op->DebugName(), op->GetId(),
-          rhs->AsIntConstant()->GetValue()));
-    }
-  } else if (rhs->GetType() == Primitive::kPrimNot) {
-    if (!op->IsEqual() && !op->IsNotEqual()) {
+    } else if (rhs->GetType() == Primitive::kPrimNot) {
       AddError(StringPrintf(
           "Condition %s %d uses an object as right-hand side input.",
           op->DebugName(), op->GetId()));
     }
-    if (lhs->IsIntConstant() && lhs->AsIntConstant()->GetValue() != 0) {
-      AddError(StringPrintf(
-          "Condition %s %d compares a non-zero integer with an object: %d.",
-          op->DebugName(), op->GetId(),
-          lhs->AsIntConstant()->GetValue()));
-    }
-  } else if (PrimitiveKind(lhs->GetType()) != PrimitiveKind(rhs->GetType())) {
-      AddError(StringPrintf(
-          "Condition %s %d has inputs of different types: "
-          "%s, and %s.",
-          op->DebugName(), op->GetId(),
-          Primitive::PrettyDescriptor(lhs->GetType()),
-          Primitive::PrettyDescriptor(rhs->GetType())));
   }
 }
 
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 89fea0a..c8c3c3b 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -85,6 +85,7 @@ class SSAChecker : public GraphChecker {
  public:
   typedef GraphChecker super_type;
 
+  // TODO: There's no need to pass a separate allocator as we could get it from the graph.
   SSAChecker(ArenaAllocator* allocator, HGraph* graph)
     : GraphChecker(allocator, graph, "art::SSAChecker: ") {}
 
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 5f50494..19787c3 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2715,6 +2715,20 @@ class HPhi : public HInstruction {
   bool IsDead() const { return !is_live_; }
   bool IsLive() const { return is_live_; }
 
+  // Returns the next equivalent phi (starting from the current one) or null if there is none.
+  // An equivalent phi is a phi having the same dex register and type.
+  // It assumes that phis with the same dex register are adjacent.
+  HPhi* GetNextEquivalentPhiWithSameType() {
+    HInstruction* next = GetNext();
+    while (next != nullptr && next->AsPhi()->GetRegNumber() == reg_number_) {
+      if (next->GetType() == GetType()) {
+        return next->AsPhi();
+      }
+      next = next->GetNext();
+    }
+    return nullptr;
+  }
+
   DECLARE_INSTRUCTION(Phi);
 
  protected:
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index e154ea4..5c3d9bf 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -174,6 +174,54 @@ static bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) {
       && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber();
 }
 
+void SsaBuilder::FixNullConstantType() {
+  // The order doesn't matter here.
+  for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
+    for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) {
+      HInstruction* equality_instr = it.Current();
+      if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) {
+        continue;
+      }
+      HInstruction* left = equality_instr->InputAt(0);
+      HInstruction* right = equality_instr->InputAt(1);
+      HInstruction* null_instr = nullptr;
+
+      if ((left->GetType() == Primitive::kPrimNot)
+          && (right->IsNullConstant() || right->IsIntConstant())) {
+        null_instr = right;
+      } else if ((right->GetType() == Primitive::kPrimNot)
+              && (left->IsNullConstant() || left->IsIntConstant())) {
+        null_instr = left;
+      } else {
+        continue;
+      }
+
+      // If we got here, we are comparing against a reference and the int constant
+      // should be replaced with a null constant.
+      if (null_instr->IsIntConstant()) {
+        DCHECK_EQ(0, null_instr->AsIntConstant()->GetValue());
+        equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), null_instr == right ? 1 : 0);
+      }
+    }
+  }
+}
+
+void SsaBuilder::EquivalentPhisCleanup() {
+  // The order doesn't matter here.
+  for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
+    for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) {
+      HPhi* phi = it.Current()->AsPhi();
+      HPhi* next = phi->GetNextEquivalentPhiWithSameType();
+      if (next != nullptr) {
+        phi->ReplaceWith(next);
+        DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr)
+            << "More then one phi equivalent with type " << phi->GetType()
+            << " found for phi" << phi->GetId();
+      }
+    }
+  }
+}
+
 void SsaBuilder::BuildSsa() {
   // 1) Visit in reverse post order. We need to have all predecessors of a block visited
   // (with the exception of loops) in order to create the right environment for that
@@ -209,11 +257,21 @@ void SsaBuilder::BuildSsa() {
   PrimitiveTypePropagation type_propagation(GetGraph());
   type_propagation.Run();
 
-  // 5) Mark dead phis again. Steph 4) may have introduced new phis.
+  // 5) Fix the type for null constants which are part of an equality comparison.
+  FixNullConstantType();
+
+  // 6) When creating equivalent phis we copy the inputs of the original phi which
+  // may be improperly typed. This will be fixed during the type propagation but
+  // as a result we may end up with two equivalent phis with the same type for
+  // the same dex register. This pass cleans them up.
+  EquivalentPhisCleanup();
+
+  // 7) Mark dead phis again. Step 4) may have introduced new phis.
+  // Step 6) might enable the death of new phis.
   SsaDeadPhiElimination dead_phis(GetGraph());
   dead_phis.MarkDeadPhis();
 
-  // 6) Now that the graph is correclty typed, we can get rid of redundant phis.
+  // 8) Now that the graph is correctly typed, we can get rid of redundant phis.
   // Note that we cannot do this phase before type propagation, otherwise
   // we could get rid of phi equivalents, whose presence is a requirement for the
   // type propagation phase. Note that this is to satisfy statement (a) of the
@@ -221,7 +279,7 @@ void SsaBuilder::BuildSsa() {
   SsaRedundantPhiElimination redundant_phi(GetGraph());
   redundant_phi.Run();
 
-  // 7) Make sure environments use the right phi "equivalent": a phi marked dead
+  // 9) Make sure environments use the right phi "equivalent": a phi marked dead
   // can have a phi equivalent that is not dead. We must therefore update
   // all environment uses of the dead phi to use its equivalent. Note that there
   // can be multiple phis for the same Dex register that are live (for example
@@ -248,7 +306,7 @@ void SsaBuilder::BuildSsa() {
     }
   }
 
-  // 8) Deal with phis to guarantee liveness of phis in case of a debuggable
+  // 10) Deal with phis to guarantee liveness of phis in case of a debuggable
   // application. This is for satisfying statement (c) of the SsaBuilder
   // (see ssa_builder.h).
   if (GetGraph()->IsDebuggable()) {
@@ -256,7 +314,7 @@ void SsaBuilder::BuildSsa() {
     dead_phi_handler.Run();
   }
 
-  // 9) Now that the right phis are used for the environments, and we
+  // 11) Now that the right phis are used for the environments, and we
   // have potentially revive dead phis in case of a debuggable application,
   // we can eliminate phis we do not need. Regardless of the debuggable status,
   // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h),
@@ -264,7 +322,7 @@ void SsaBuilder::BuildSsa() {
   // input types.
   dead_phis.EliminateDeadPhis();
 
-  // 10) Clear locals.
+  // 12) Clear locals.
   for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
        !it.Done();
        it.Advance()) {
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 569b3e2..265e95b 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -85,6 +85,9 @@ class SsaBuilder : public HGraphVisitor {
   static constexpr const char* kSsaBuilderPassName = "ssa_builder";
 
  private:
+  void FixNullConstantType();
+  void EquivalentPhisCleanup();
+
   static HFloatConstant* GetFloatEquivalent(HIntConstant* constant);
   static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant);
   static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type);