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
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 @@
}
}
+ // 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 @@
}
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 @@
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 @@
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 @@
&& 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 @@
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 @@
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 @@
}
}
- // 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 @@
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 @@
// 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 @@
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);
diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java
index 656c791..501d79c 100644
--- a/test/444-checker-nce/src/Main.java
+++ b/test/444-checker-nce/src/Main.java
@@ -251,3 +251,27 @@
}
}
+
+// Regression for when we created and kept equivalent phis with the same type.
+// The phi used in comparison would be different then the one used for access
+// so we could not safely discard it.
+class ListElement {
+ private ListElement next;
+
+ // CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (before)
+ // CHECK: NullCheck
+ // CHECK: NullCheck
+
+ // CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (after)
+ // CHECK-NOT: NullCheck
+ static boolean isShorter(ListElement x, ListElement y) {
+ ListElement xTail = x;
+ ListElement yTail = y;
+ while (yTail != null) {
+ if (xTail == null) return true;
+ xTail = xTail.next;
+ yTail = yTail.next;
+ }
+ return false;
+ }
+}