Merge "Remove duplicates phis created during SSA transformation"
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 906c8e8..3a56c6c 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);
}
@@ -413,37 +425,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 4568a5e..24fee37 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 fe47939..649038b 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2752,6 +2752,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;
+ }
+}
