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

1 files changed, 64 insertions, 6 deletions

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()) {