diff options
-rw-r--r-- | compiler/optimizing/graph_checker.cc | 46 | ||||
-rw-r--r-- | compiler/optimizing/graph_checker.h | 1 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 14 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.cc | 70 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.h | 3 | ||||
-rw-r--r-- | test/444-checker-nce/src/Main.java | 24 |
6 files changed, 128 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); 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 @@ public class Main { } } + +// 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; + } +} |