From d9510dfc32349eeb4f2145c801f7ba1d5bccfb12 Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Wed, 4 Nov 2015 23:30:22 +0000 Subject: [PATCH] ART: Refactor SsaBuilder for more precise typing info This patch refactors the SsaBuilder to do the following: 1) All phis are constructed live and marked dead if not used or proved to be conflicting. 2) Primitive type propagation, now not a separate pass, identifies conflicting types and marks corresponding phis dead. 3) When compiling --debuggable, DeadPhiHandling used to revive phis which had only environmental uses but did not attempt to resolve conflicts. This pass was removed as obsolete and is now superseded by primitive type propagation (identifying conflicting phis) and SsaDeadPhiEliminiation (keeping phis live if debuggable + env use). 4) Resolving conflicts requires correct primitive type information on all instructions. This was not the case for ArrayGet instructions which can have ambiguous types in the bytecode. To this end, SsaBuilder now runs reference type propagation and types ArrayGets from the type of the input array. 5) With RTP being run inside the SsaBuilder, it is not necessary to run it as a separate optimization pass. Optimizations can now assume that all instructions of type kPrimNot have reference type info after SsaBuilder (with the exception of NullConstant). 6) Graph now contains a reference type to be assigned to NullConstant. All reference type instructions therefore have RTI, as now enforced by the SsaChecker. Bug: 24252151 Bug: 24252100 Bug: 22538329 Bug: 25786318 Change-Id: I7a3aee1ff66c82d64b4846611c547af17e91d260 --- compiler/Android.mk | 1 - compiler/optimizing/bounds_check_elimination.cc | 9 +- compiler/optimizing/constant_folding_test.cc | 4 +- compiler/optimizing/dead_code_elimination_test.cc | 9 +- compiler/optimizing/graph_checker.cc | 12 + compiler/optimizing/graph_checker_test.cc | 10 +- compiler/optimizing/graph_visualizer.cc | 19 +- compiler/optimizing/gvn_test.cc | 20 +- compiler/optimizing/induction_var_analysis_test.cc | 8 +- compiler/optimizing/induction_var_range_test.cc | 5 +- compiler/optimizing/inliner.cc | 67 +- compiler/optimizing/licm_test.cc | 17 +- compiler/optimizing/linearize_test.cc | 21 +- compiler/optimizing/live_ranges_test.cc | 18 +- compiler/optimizing/liveness_test.cc | 30 +- compiler/optimizing/nodes.cc | 49 +- compiler/optimizing/nodes.h | 304 ++++----- compiler/optimizing/optimizing_compiler.cc | 51 +- compiler/optimizing/optimizing_compiler_stats.h | 8 +- compiler/optimizing/optimizing_unit_test.h | 11 +- compiler/optimizing/primitive_type_propagation.cc | 133 ---- compiler/optimizing/primitive_type_propagation.h | 52 -- compiler/optimizing/reference_type_propagation.cc | 143 +++-- compiler/optimizing/register_allocator_test.cc | 34 +- compiler/optimizing/ssa_builder.cc | 695 ++++++++++++--------- compiler/optimizing/ssa_builder.h | 42 +- compiler/optimizing/ssa_phi_elimination.cc | 18 +- compiler/optimizing/ssa_test.cc | 31 +- test/444-checker-nce/src/Main.java | 52 +- test/450-checker-types/src/Main.java | 211 +++++-- test/477-checker-bound-type/src/Main.java | 8 +- test/530-checker-lse/src/Main.java | 12 +- test/540-checker-rtp-bug/src/Main.java | 8 +- test/549-checker-types-merge/src/Main.java | 22 +- test/552-checker-primitive-typeprop/expected.txt | 0 test/552-checker-primitive-typeprop/info.txt | 2 + .../smali/ArrayGet.smali | 245 ++++++++ .../smali/SsaBuilder.smali | 52 ++ .../smali/TypePropagation.smali | 136 ++++ test/552-checker-primitive-typeprop/src/Main.java | 43 ++ 40 files changed, 1621 insertions(+), 991 deletions(-) delete mode 100644 compiler/optimizing/primitive_type_propagation.cc delete mode 100644 compiler/optimizing/primitive_type_propagation.h create mode 100644 test/552-checker-primitive-typeprop/expected.txt create mode 100644 test/552-checker-primitive-typeprop/info.txt create mode 100644 test/552-checker-primitive-typeprop/smali/ArrayGet.smali create mode 100644 test/552-checker-primitive-typeprop/smali/SsaBuilder.smali create mode 100644 test/552-checker-primitive-typeprop/smali/TypePropagation.smali create mode 100644 test/552-checker-primitive-typeprop/src/Main.java diff --git a/compiler/Android.mk b/compiler/Android.mk index bdd9a8443..f0bf4997c 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -92,7 +92,6 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/parallel_move_resolver.cc \ optimizing/pc_relative_fixups_x86.cc \ optimizing/prepare_for_register_allocation.cc \ - optimizing/primitive_type_propagation.cc \ optimizing/reference_type_propagation.cc \ optimizing/register_allocator.cc \ optimizing/sharpening.cc \ diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 4c3f66aa4..dc75ff1ab 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -1590,15 +1590,18 @@ class BCEVisitor : public HGraphVisitor { HGraph* graph = GetGraph(); HInstruction* zero; switch (type) { - case Primitive::Type::kPrimNot: zero = graph->GetNullConstant(); break; - case Primitive::Type::kPrimFloat: zero = graph->GetFloatConstant(0); break; - case Primitive::Type::kPrimDouble: zero = graph->GetDoubleConstant(0); break; + case Primitive::kPrimNot: zero = graph->GetNullConstant(); break; + case Primitive::kPrimFloat: zero = graph->GetFloatConstant(0); break; + case Primitive::kPrimDouble: zero = graph->GetDoubleConstant(0); break; default: zero = graph->GetConstant(type, 0); break; } HPhi* phi = new (graph->GetArena()) HPhi(graph->GetArena(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type)); phi->SetRawInputAt(0, instruction); phi->SetRawInputAt(1, zero); + if (type == Primitive::kPrimNot) { + phi->SetReferenceTypeInfo(instruction->GetReferenceTypeInfo()); + } new_preheader->AddPhi(phi); return phi; } diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc index e469c8d6d..a8f65bf51 100644 --- a/compiler/optimizing/constant_folding_test.cc +++ b/compiler/optimizing/constant_folding_test.cc @@ -32,7 +32,7 @@ namespace art { /** * Fixture class for the constant folding and dce tests. */ -class ConstantFoldingTest : public testing::Test { +class ConstantFoldingTest : public CommonCompilerTest { public: ConstantFoldingTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -56,7 +56,7 @@ class ConstantFoldingTest : public testing::Test { const std::string& expected_after_dce, std::function check_after_cf) { ASSERT_NE(graph_, nullptr); - graph_->TryBuildingSsa(); + TransformToSsa(graph_); StringPrettyPrinter printer_before(graph_); printer_before.VisitInsertionOrder(); diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc index 2c6a1ef63..f0f98efad 100644 --- a/compiler/optimizing/dead_code_elimination_test.cc +++ b/compiler/optimizing/dead_code_elimination_test.cc @@ -26,6 +26,8 @@ namespace art { +class DeadCodeEliminationTest : public CommonCompilerTest {}; + static void TestCode(const uint16_t* data, const std::string& expected_before, const std::string& expected_after) { @@ -34,7 +36,7 @@ static void TestCode(const uint16_t* data, HGraph* graph = CreateCFG(&allocator, data); ASSERT_NE(graph, nullptr); - graph->TryBuildingSsa(); + TransformToSsa(graph); StringPrettyPrinter printer_before(graph); printer_before.VisitInsertionOrder(); @@ -55,7 +57,6 @@ static void TestCode(const uint16_t* data, ASSERT_EQ(actual_after, expected_after); } - /** * Small three-register program. * @@ -69,7 +70,7 @@ static void TestCode(const uint16_t* data, * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 * return-void 7. return */ -TEST(DeadCodeElimination, AdditionAndConditionalJump) { +TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 1 << 8 | 1 << 12, Instruction::CONST_4 | 0 << 8 | 0 << 12, @@ -131,7 +132,7 @@ TEST(DeadCodeElimination, AdditionAndConditionalJump) { * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4 * return 13. return-void */ -TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) { +TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 << 8 | 0 << 12, Instruction::CONST_4 | 1 << 8 | 1 << 12, diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index dfc363f9f..f3c1dbe3f 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -24,6 +24,7 @@ #include "base/arena_containers.h" #include "base/bit_vector-inl.h" #include "base/stringprintf.h" +#include "handle_scope-inl.h" namespace art { @@ -594,6 +595,17 @@ void SSAChecker::VisitInstruction(HInstruction* instruction) { } } } + + // Ensure that reference type instructions have reference type info. + if (instruction->GetType() == Primitive::kPrimNot) { + ScopedObjectAccess soa(Thread::Current()); + if (!instruction->GetReferenceTypeInfo().IsValid()) { + AddError(StringPrintf("Reference type instruction %s:%d does not have " + "valid reference type information.", + instruction->DebugName(), + instruction->GetId())); + } + } } static Primitive::Type PrimitiveKind(Primitive::Type type) { diff --git a/compiler/optimizing/graph_checker_test.cc b/compiler/optimizing/graph_checker_test.cc index fee56c7f9..d10df4ce3 100644 --- a/compiler/optimizing/graph_checker_test.cc +++ b/compiler/optimizing/graph_checker_test.cc @@ -17,8 +17,6 @@ #include "graph_checker.h" #include "optimizing_unit_test.h" -#include "gtest/gtest.h" - namespace art { /** @@ -43,7 +41,6 @@ HGraph* CreateSimpleCFG(ArenaAllocator* allocator) { return graph; } - static void TestCode(const uint16_t* data) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -61,8 +58,7 @@ static void TestCodeSSA(const uint16_t* data) { HGraph* graph = CreateCFG(&allocator, data); ASSERT_NE(graph, nullptr); - graph->BuildDominatorTree(); - graph->TransformToSsa(); + TransformToSsa(graph); SSAChecker ssa_checker(graph); ssa_checker.Run(); @@ -145,7 +141,9 @@ TEST(GraphChecker, BlockEndingWithNonBranchInstruction) { ASSERT_FALSE(graph_checker.IsValid()); } -TEST(SSAChecker, SSAPhi) { +class SSACheckerTest : public CommonCompilerTest {}; + +TEST_F(SSACheckerTest, SSAPhi) { // This code creates one Phi function during the conversion to SSA form. const uint16_t data[] = ONE_REGISTER_CODE_ITEM( Instruction::CONST_4 | 0 | 0, diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index e9fdb84d1..5f1328f54 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -30,6 +30,7 @@ #include "optimization.h" #include "reference_type_propagation.h" #include "register_allocator.h" +#include "ssa_builder.h" #include "ssa_liveness_analysis.h" #include "utils/assembler.h" @@ -505,7 +506,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { } else { StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId(); } - } else if ((IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName) + } else if ((IsPass(SsaBuilder::kSsaBuilderPassName) || IsPass(HInliner::kInlinerPassName)) && (instruction->GetType() == Primitive::kPrimNot)) { ReferenceTypeInfo info = instruction->IsLoadClass() @@ -519,21 +520,15 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha; } else if (instruction->IsLoadClass()) { StartAttributeStream("klass") << "unresolved"; - } else if (instruction->IsNullConstant()) { + } else { // The NullConstant may be added to the graph during other passes that happen between // ReferenceTypePropagation and Inliner (e.g. InstructionSimplifier). If the inliner // doesn't run or doesn't inline anything, the NullConstant remains untyped. // So we should check NullConstants for validity only after reference type propagation. - // - // Note: The infrastructure to properly type NullConstants everywhere is to complex to add - // for the benefits. - StartAttributeStream("klass") << "not_set"; - DCHECK(!is_after_pass_ - || !IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName)) - << " Expected a valid rti after reference type propagation"; - } else { - DCHECK(!is_after_pass_) - << "Expected a valid rti after reference type propagation"; + DCHECK(graph_in_bad_state_ || + (!is_after_pass_ && IsPass(SsaBuilder::kSsaBuilderPassName))) + << instruction->DebugName() << instruction->GetId() << " has invalid rti " + << (is_after_pass_ ? "after" : "before") << " pass " << pass_name_; } } if (disasm_info_ != nullptr) { diff --git a/compiler/optimizing/gvn_test.cc b/compiler/optimizing/gvn_test.cc index de60cf21a..9929696de 100644 --- a/compiler/optimizing/gvn_test.cc +++ b/compiler/optimizing/gvn_test.cc @@ -21,11 +21,11 @@ #include "optimizing_unit_test.h" #include "side_effects_analysis.h" -#include "gtest/gtest.h" - namespace art { -TEST(GVNTest, LocalFieldElimination) { +class GVNTest : public CommonCompilerTest {}; + +TEST_F(GVNTest, LocalFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle dex_cache; @@ -100,7 +100,7 @@ TEST(GVNTest, LocalFieldElimination) { ASSERT_EQ(different_offset->GetBlock(), block); ASSERT_EQ(use_after_kill->GetBlock(), block); - graph->TryBuildingSsa(); + TransformToSsa(graph); SideEffectsAnalysis side_effects(graph); side_effects.Run(); GVNOptimization(graph, side_effects).Run(); @@ -110,7 +110,7 @@ TEST(GVNTest, LocalFieldElimination) { ASSERT_EQ(use_after_kill->GetBlock(), block); } -TEST(GVNTest, GlobalFieldElimination) { +TEST_F(GVNTest, GlobalFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle dex_cache; @@ -182,7 +182,7 @@ TEST(GVNTest, GlobalFieldElimination) { 0)); join->AddInstruction(new (&allocator) HExit()); - graph->TryBuildingSsa(); + TransformToSsa(graph); SideEffectsAnalysis side_effects(graph); side_effects.Run(); GVNOptimization(graph, side_effects).Run(); @@ -193,7 +193,7 @@ TEST(GVNTest, GlobalFieldElimination) { ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); } -TEST(GVNTest, LoopFieldElimination) { +TEST_F(GVNTest, LoopFieldElimination) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle dex_cache; @@ -288,7 +288,7 @@ TEST(GVNTest, LoopFieldElimination) { ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); ASSERT_EQ(field_get_in_exit->GetBlock(), exit); - graph->TryBuildingSsa(); + TransformToSsa(graph); { SideEffectsAnalysis side_effects(graph); side_effects.Run(); @@ -316,7 +316,7 @@ TEST(GVNTest, LoopFieldElimination) { } // Test that inner loops affect the side effects of the outer loop. -TEST(GVNTest, LoopSideEffects) { +TEST_F(GVNTest, LoopSideEffects) { ArenaPool pool; ArenaAllocator allocator(&pool); NullHandle dex_cache; @@ -364,7 +364,7 @@ TEST(GVNTest, LoopSideEffects) { inner_loop_exit->AddInstruction(new (&allocator) HGoto()); outer_loop_exit->AddInstruction(new (&allocator) HExit()); - graph->TryBuildingSsa(); + TransformToSsa(graph); ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( *outer_loop_header->GetLoopInformation())); diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index 5de94f43c..776c115e9 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -18,7 +18,6 @@ #include "base/arena_allocator.h" #include "builder.h" -#include "gtest/gtest.h" #include "induction_var_analysis.h" #include "nodes.h" #include "optimizing_unit_test.h" @@ -28,7 +27,7 @@ namespace art { /** * Fixture class for the InductionVarAnalysis tests. */ -class InductionVarAnalysisTest : public testing::Test { +class InductionVarAnalysisTest : public CommonCompilerTest { public: InductionVarAnalysisTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -102,6 +101,7 @@ class InductionVarAnalysisTest : public testing::Test { basic_[d] = new (&allocator_) HLocal(d); entry_->AddInstruction(basic_[d]); loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_)); + loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto()); HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt); loop_header_[d]->AddInstruction(load); HInstruction* compare = new (&allocator_) HLessThan(load, constant100_); @@ -168,7 +168,7 @@ class InductionVarAnalysisTest : public testing::Test { // Performs InductionVarAnalysis (after proper set up). void PerformInductionVarAnalysis() { - ASSERT_TRUE(graph_->TryBuildingSsa()); + TransformToSsa(graph_); iva_ = new (&allocator_) HInductionVarAnalysis(graph_); iva_->Run(); } @@ -212,7 +212,7 @@ TEST_F(InductionVarAnalysisTest, ProperLoopSetup) { // .. // } BuildLoopNest(10); - ASSERT_TRUE(graph_->TryBuildingSsa()); + TransformToSsa(graph_); ASSERT_EQ(entry_->GetLoopInformation(), nullptr); for (int d = 0; d < 1; d++) { ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(), diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index 128b5bb81..a1c797a80 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -16,7 +16,6 @@ #include "base/arena_allocator.h" #include "builder.h" -#include "gtest/gtest.h" #include "induction_var_analysis.h" #include "induction_var_range.h" #include "nodes.h" @@ -29,7 +28,7 @@ using Value = InductionVarRange::Value; /** * Fixture class for the InductionVarRange tests. */ -class InductionVarRangeTest : public testing::Test { +class InductionVarRangeTest : public CommonCompilerTest { public: InductionVarRangeTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -105,7 +104,7 @@ class InductionVarRangeTest : public testing::Test { /** Performs induction variable analysis. */ void PerformInductionVarAnalysis() { - ASSERT_TRUE(graph_->TryBuildingSsa()); + TransformToSsa(graph_); iva_->Run(); } diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index a4dcb3aeb..db1170909 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -33,6 +33,7 @@ #include "reference_type_propagation.h" #include "register_allocator.h" #include "sharpening.h" +#include "ssa_builder.h" #include "ssa_phi_elimination.h" #include "scoped_thread_state_change.h" #include "thread.h" @@ -514,7 +515,7 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, return false; } - if (!callee_graph->TryBuildingSsa()) { + if (callee_graph->TryBuildingSsa(handles_) != kBuildSsaSuccess) { VLOG(compiler) << "Method " << PrettyMethod(method_index, callee_dex_file) << " could not be transformed to SSA"; return false; @@ -549,14 +550,12 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, // Run simple optimizations on the graph. HDeadCodeElimination dce(callee_graph, stats_); HConstantFolding fold(callee_graph); - ReferenceTypePropagation type_propagation(callee_graph, handles_); HSharpening sharpening(callee_graph, codegen_, dex_compilation_unit, compiler_driver_); InstructionSimplifier simplify(callee_graph, stats_); IntrinsicsRecognizer intrinsics(callee_graph, compiler_driver_); HOptimization* optimizations[] = { &intrinsics, - &type_propagation, &sharpening, &simplify, &fold, @@ -677,42 +676,36 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, DCHECK_EQ(graph_, return_replacement->GetBlock()->GetGraph()); } - // When merging the graph we might create a new NullConstant in the caller graph which does - // not have the chance to be typed. We assign the correct type here so that we can keep the - // assertion that every reference has a valid type. This also simplifies checks along the way. - HNullConstant* null_constant = graph_->GetNullConstant(); - if (!null_constant->GetReferenceTypeInfo().IsValid()) { - ReferenceTypeInfo::TypeHandle obj_handle = - handles_->NewHandle(class_linker->GetClassRoot(ClassLinker::kJavaLangObject)); - null_constant->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(obj_handle, false /* is_exact */)); - } - // Check the integrity of reference types and run another type propagation if needed. - if ((return_replacement != nullptr) - && (return_replacement->GetType() == Primitive::kPrimNot)) { - if (!return_replacement->GetReferenceTypeInfo().IsValid()) { - // Make sure that we have a valid type for the return. We may get an invalid one when - // we inline invokes with multiple branches and create a Phi for the result. - // TODO: we could be more precise by merging the phi inputs but that requires - // some functionality from the reference type propagation. - DCHECK(return_replacement->IsPhi()); - size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize(); - ReferenceTypeInfo::TypeHandle return_handle = - handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size)); - return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create( - return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */)); - } + if (return_replacement != nullptr) { + if (return_replacement->GetType() == Primitive::kPrimNot) { + if (!return_replacement->GetReferenceTypeInfo().IsValid()) { + // Make sure that we have a valid type for the return. We may get an invalid one when + // we inline invokes with multiple branches and create a Phi for the result. + // TODO: we could be more precise by merging the phi inputs but that requires + // some functionality from the reference type propagation. + DCHECK(return_replacement->IsPhi()); + size_t pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize(); + ReferenceTypeInfo::TypeHandle return_handle = + handles_->NewHandle(resolved_method->GetReturnType(true /* resolve */, pointer_size)); + return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create( + return_handle, return_handle->CannotBeAssignedFromOtherTypes() /* is_exact */)); + } - if (do_rtp) { - // If the return type is a refinement of the declared type run the type propagation again. - ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo(); - ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo(); - if (invoke_rti.IsStrictSupertypeOf(return_rti) - || (return_rti.IsExact() && !invoke_rti.IsExact()) - || !return_replacement->CanBeNull()) { - ReferenceTypePropagation rtp_fixup(graph_, handles_); - rtp_fixup.Run(); + if (do_rtp) { + // If the return type is a refinement of the declared type run the type propagation again. + ReferenceTypeInfo return_rti = return_replacement->GetReferenceTypeInfo(); + ReferenceTypeInfo invoke_rti = invoke_instruction->GetReferenceTypeInfo(); + if (invoke_rti.IsStrictSupertypeOf(return_rti) + || (return_rti.IsExact() && !invoke_rti.IsExact()) + || !return_replacement->CanBeNull()) { + ReferenceTypePropagation(graph_, handles_).Run(); + } + } + } else if (return_replacement->IsInstanceOf()) { + if (do_rtp) { + // Inlining InstanceOf into an If may put a tighter bound on reference types. + ReferenceTypePropagation(graph_, handles_).Run(); } } } diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc index 2bb769a43..956de2cb8 100644 --- a/compiler/optimizing/licm_test.cc +++ b/compiler/optimizing/licm_test.cc @@ -16,7 +16,6 @@ #include "base/arena_allocator.h" #include "builder.h" -#include "gtest/gtest.h" #include "licm.h" #include "nodes.h" #include "optimizing_unit_test.h" @@ -27,7 +26,7 @@ namespace art { /** * Fixture class for the LICM tests. */ -class LICMTest : public testing::Test { +class LICMTest : public CommonCompilerTest { public: LICMTest() : pool_(), allocator_(&pool_) { graph_ = CreateGraph(&allocator_); @@ -70,16 +69,16 @@ class LICMTest : public testing::Test { loop_preheader_->AddInstruction(new (&allocator_) HGoto()); loop_header_->AddInstruction(new (&allocator_) HIf(parameter_)); loop_body_->AddInstruction(new (&allocator_) HGoto()); + return_->AddInstruction(new (&allocator_) HReturnVoid()); exit_->AddInstruction(new (&allocator_) HExit()); } // Performs LICM optimizations (after proper set up). void PerformLICM() { - ASSERT_TRUE(graph_->TryBuildingSsa()); + TransformToSsa(graph_); SideEffectsAnalysis side_effects(graph_); side_effects.Run(); - LICM licm(graph_, side_effects); - licm.Run(); + LICM(graph_, side_effects).Run(); } // General building fields. @@ -169,10 +168,10 @@ TEST_F(LICMTest, ArrayHoisting) { // Populate the loop with instructions: set/get array with different types. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimLong, 0); + parameter_, constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, constant_, constant_, Primitive::kPrimInt, 0); + parameter_, constant_, constant_, Primitive::kPrimShort, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); @@ -187,10 +186,10 @@ TEST_F(LICMTest, NoArrayHoisting) { // Populate the loop with instructions: set/get array with same types. HInstruction* get_array = new (&allocator_) HArrayGet( - parameter_, constant_, Primitive::kPrimLong, 0); + parameter_, constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); HInstruction* set_array = new (&allocator_) HArraySet( - parameter_, get_array, constant_, Primitive::kPrimLong, 0); + parameter_, get_array, constant_, Primitive::kPrimByte, 0); loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); EXPECT_EQ(get_array->GetBlock(), loop_body_); diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc index a059766e0..ed275b154 100644 --- a/compiler/optimizing/linearize_test.cc +++ b/compiler/optimizing/linearize_test.cc @@ -29,13 +29,12 @@ #include "nodes.h" #include "optimizing_unit_test.h" #include "pretty_printer.h" -#include "ssa_builder.h" #include "ssa_liveness_analysis.h" -#include "gtest/gtest.h" - namespace art { +class LinearizeTest : public CommonCompilerTest {}; + template static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[number_of_blocks]) { ArenaPool pool; @@ -46,7 +45,7 @@ static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[numb bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - graph->TryBuildingSsa(); + TransformToSsa(graph); std::unique_ptr features_x86( X86InstructionSetFeatures::FromCppDefines()); @@ -60,7 +59,7 @@ static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[numb } } -TEST(LinearizeTest, CFG1) { +TEST_F(LinearizeTest, CFG1) { // Structure of this graph (+ are back edges) // Block0 // | @@ -85,7 +84,7 @@ TEST(LinearizeTest, CFG1) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG2) { +TEST_F(LinearizeTest, CFG2) { // Structure of this graph (+ are back edges) // Block0 // | @@ -110,7 +109,7 @@ TEST(LinearizeTest, CFG2) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG3) { +TEST_F(LinearizeTest, CFG3) { // Structure of this graph (+ are back edges) // Block0 // | @@ -137,7 +136,7 @@ TEST(LinearizeTest, CFG3) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG4) { +TEST_F(LinearizeTest, CFG4) { /* Structure of this graph (+ are back edges) // Block0 // | @@ -167,7 +166,7 @@ TEST(LinearizeTest, CFG4) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG5) { +TEST_F(LinearizeTest, CFG5) { /* Structure of this graph (+ are back edges) // Block0 // | @@ -197,7 +196,7 @@ TEST(LinearizeTest, CFG5) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG6) { +TEST_F(LinearizeTest, CFG6) { // Block0 // | // Block1 @@ -223,7 +222,7 @@ TEST(LinearizeTest, CFG6) { TestCode(data, blocks); } -TEST(LinearizeTest, CFG7) { +TEST_F(LinearizeTest, CFG7) { // Structure of this graph (+ are back edges) // Block0 // | diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index 7f6756069..926f9399a 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -27,10 +27,10 @@ #include "prepare_for_register_allocation.h" #include "ssa_liveness_analysis.h" -#include "gtest/gtest.h" - namespace art { +class LiveRangesTest : public CommonCompilerTest {}; + static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) { HGraph* graph = CreateGraph(allocator); HGraphBuilder builder(graph); @@ -39,13 +39,13 @@ static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) { // Suspend checks implementation may change in the future, and this test relies // on how instructions are ordered. RemoveSuspendChecks(graph); - graph->TryBuildingSsa(); + TransformToSsa(graph); // `Inline` conditions into ifs. PrepareForRegisterAllocation(graph).Run(); return graph; } -TEST(LiveRangesTest, CFG1) { +TEST_F(LiveRangesTest, CFG1) { /* * Test the following snippet: * return 0; @@ -83,7 +83,7 @@ TEST(LiveRangesTest, CFG1) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST(LiveRangesTest, CFG2) { +TEST_F(LiveRangesTest, CFG2) { /* * Test the following snippet: * var a = 0; @@ -131,7 +131,7 @@ TEST(LiveRangesTest, CFG2) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST(LiveRangesTest, CFG3) { +TEST_F(LiveRangesTest, CFG3) { /* * Test the following snippet: * var a = 0; @@ -204,7 +204,7 @@ TEST(LiveRangesTest, CFG3) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST(LiveRangesTest, Loop1) { +TEST_F(LiveRangesTest, Loop1) { /* * Test the following snippet: * var a = 0; @@ -284,7 +284,7 @@ TEST(LiveRangesTest, Loop1) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST(LiveRangesTest, Loop2) { +TEST_F(LiveRangesTest, Loop2) { /* * Test the following snippet: * var a = 0; @@ -360,7 +360,7 @@ TEST(LiveRangesTest, Loop2) { ASSERT_TRUE(range->GetNext() == nullptr); } -TEST(LiveRangesTest, CFG4) { +TEST_F(LiveRangesTest, CFG4) { /* * Test the following snippet: * var a = 0; diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc index 9d7d0b6c6..7736eedae 100644 --- a/compiler/optimizing/liveness_test.cc +++ b/compiler/optimizing/liveness_test.cc @@ -27,10 +27,10 @@ #include "prepare_for_register_allocation.h" #include "ssa_liveness_analysis.h" -#include "gtest/gtest.h" - namespace art { +class LivenessTest : public CommonCompilerTest {}; + static void DumpBitVector(BitVector* vector, std::ostream& buffer, size_t count, @@ -51,7 +51,7 @@ static void TestCode(const uint16_t* data, const char* expected) { const DexFile::CodeItem* item = reinterpret_cast(data); bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - graph->TryBuildingSsa(); + TransformToSsa(graph); // `Inline` conditions into ifs. PrepareForRegisterAllocation(graph).Run(); std::unique_ptr features_x86( @@ -75,7 +75,7 @@ static void TestCode(const uint16_t* data, const char* expected) { ASSERT_STREQ(expected, buffer.str().c_str()); } -TEST(LivenessTest, CFG1) { +TEST_F(LivenessTest, CFG1) { const char* expected = "Block 0\n" " live in: (0)\n" @@ -98,7 +98,7 @@ TEST(LivenessTest, CFG1) { TestCode(data, expected); } -TEST(LivenessTest, CFG2) { +TEST_F(LivenessTest, CFG2) { const char* expected = "Block 0\n" " live in: (0)\n" @@ -120,7 +120,7 @@ TEST(LivenessTest, CFG2) { TestCode(data, expected); } -TEST(LivenessTest, CFG3) { +TEST_F(LivenessTest, CFG3) { const char* expected = "Block 0\n" // entry block " live in: (000)\n" @@ -149,7 +149,7 @@ TEST(LivenessTest, CFG3) { TestCode(data, expected); } -TEST(LivenessTest, CFG4) { +TEST_F(LivenessTest, CFG4) { // var a; // if (0 == 0) { // a = 5; @@ -197,7 +197,7 @@ TEST(LivenessTest, CFG4) { TestCode(data, expected); } -TEST(LivenessTest, CFG5) { +TEST_F(LivenessTest, CFG5) { // var a = 0; // if (0 == 0) { // } else { @@ -242,7 +242,7 @@ TEST(LivenessTest, CFG5) { TestCode(data, expected); } -TEST(LivenessTest, Loop1) { +TEST_F(LivenessTest, Loop1) { // Simple loop with one preheader and one back edge. // var a = 0; // while (a == a) { @@ -288,7 +288,7 @@ TEST(LivenessTest, Loop1) { TestCode(data, expected); } -TEST(LivenessTest, Loop3) { +TEST_F(LivenessTest, Loop3) { // Test that the returned value stays live in a preceding loop. // var a = 0; // while (a == a) { @@ -335,7 +335,7 @@ TEST(LivenessTest, Loop3) { } -TEST(LivenessTest, Loop4) { +TEST_F(LivenessTest, Loop4) { // Make sure we support a preheader of a loop not being the first predecessor // in the predecessor list of the header. // var a = 0; @@ -387,7 +387,7 @@ TEST(LivenessTest, Loop4) { TestCode(data, expected); } -TEST(LivenessTest, Loop5) { +TEST_F(LivenessTest, Loop5) { // Make sure we create a preheader of a loop when a header originally has two // incoming blocks and one back edge. // Bitsets are made of: @@ -443,7 +443,7 @@ TEST(LivenessTest, Loop5) { TestCode(data, expected); } -TEST(LivenessTest, Loop6) { +TEST_F(LivenessTest, Loop6) { // Bitsets are made of: // (constant0, constant4, constant5, phi in block 2) const char* expected = @@ -494,7 +494,7 @@ TEST(LivenessTest, Loop6) { } -TEST(LivenessTest, Loop7) { +TEST_F(LivenessTest, Loop7) { // Bitsets are made of: // (constant0, constant4, constant5, phi in block 2, phi in block 6) const char* expected = @@ -548,7 +548,7 @@ TEST(LivenessTest, Loop7) { TestCode(data, expected); } -TEST(LivenessTest, Loop8) { +TEST_F(LivenessTest, Loop8) { // var a = 0; // while (a == a) { // a = a + a; diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 926bc156c..bb0b545c1 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -198,10 +198,38 @@ void HGraph::ComputeDominanceInformation() { } } -void HGraph::TransformToSsa() { - DCHECK(!reverse_post_order_.empty()); - SsaBuilder ssa_builder(this); - ssa_builder.BuildSsa(); +BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) { + BuildDominatorTree(); + + // The SSA builder requires loops to all be natural. Specifically, the dead phi + // elimination phase checks the consistency of the graph when doing a post-order + // visit for eliminating dead phis: a dead phi can only have loop header phi + // users remaining when being visited. + BuildSsaResult result = AnalyzeNaturalLoops(); + if (result != kBuildSsaSuccess) { + return result; + } + + // Precompute per-block try membership before entering the SSA builder, + // which needs the information to build catch block phis from values of + // locals at throwing instructions inside try blocks. + ComputeTryBlockInformation(); + + // Create the inexact Object reference type and store it in the HGraph. + ScopedObjectAccess soa(Thread::Current()); + ClassLinker* linker = Runtime::Current()->GetClassLinker(); + inexact_object_rti_ = ReferenceTypeInfo::Create( + handles->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)), + /* is_exact */ false); + + // Tranforms graph to SSA form. + result = SsaBuilder(this, handles).BuildSsa(); + if (result != kBuildSsaSuccess) { + return result; + } + + in_ssa_form_ = true; + return kBuildSsaSuccess; } HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) { @@ -410,7 +438,7 @@ void HGraph::SimplifyCFG() { } } -bool HGraph::AnalyzeNaturalLoops() const { +BuildSsaResult HGraph::AnalyzeNaturalLoops() const { // Order does not matter. for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); @@ -418,16 +446,16 @@ bool HGraph::AnalyzeNaturalLoops() const { if (block->IsCatchBlock()) { // TODO: Dealing with exceptional back edges could be tricky because // they only approximate the real control flow. Bail out for now. - return false; + return kBuildSsaFailThrowCatchLoop; } HLoopInformation* info = block->GetLoopInformation(); if (!info->Populate()) { // Abort if the loop is non natural. We currently bailout in such cases. - return false; + return kBuildSsaFailNonNaturalLoop; } } } - return true; + return kBuildSsaSuccess; } void HGraph::InsertConstant(HConstant* constant) { @@ -446,8 +474,13 @@ HNullConstant* HGraph::GetNullConstant(uint32_t dex_pc) { // id and/or any invariants the graph is assuming when adding new instructions. if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { cached_null_constant_ = new (arena_) HNullConstant(dex_pc); + cached_null_constant_->SetReferenceTypeInfo(inexact_object_rti_); InsertConstant(cached_null_constant_); } + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(cached_null_constant_->GetReferenceTypeInfo().IsValid()); + } return cached_null_constant_; } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 1f8ef4717..55e436f0b 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -98,6 +98,13 @@ enum IfCondition { kCondAE, // >= }; +enum BuildSsaResult { + kBuildSsaFailNonNaturalLoop, + kBuildSsaFailThrowCatchLoop, + kBuildSsaFailAmbiguousArrayGet, + kBuildSsaSuccess, +}; + class HInstructionList : public ValueObject { public: HInstructionList() : first_instruction_(nullptr), last_instruction_(nullptr) {} @@ -143,6 +150,122 @@ class HInstructionList : public ValueObject { DISALLOW_COPY_AND_ASSIGN(HInstructionList); }; +class ReferenceTypeInfo : ValueObject { + public: + typedef Handle TypeHandle; + + static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { + // The constructor will check that the type_handle is valid. + return ReferenceTypeInfo(type_handle, is_exact); + } + + static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } + + static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { + return handle.GetReference() != nullptr; + } + + bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { + return IsValidHandle(type_handle_); + } + + bool IsExact() const { return is_exact_; } + + bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsObjectClass(); + } + + bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsStringClass(); + } + + bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); + } + + bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsInterface(); + } + + bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsArrayClass(); + } + + bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsPrimitiveArray(); + } + + bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); + } + + bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + if (!IsExact()) return false; + if (!IsArrayClass()) return false; + return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + if (!IsExact()) return false; + if (!IsArrayClass()) return false; + if (!rti.IsArrayClass()) return false; + return GetTypeHandle()->GetComponentType()->IsAssignableFrom( + rti.GetTypeHandle()->GetComponentType()); + } + + Handle GetTypeHandle() const { return type_handle_; } + + bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + DCHECK(rti.IsValid()); + return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + DCHECK(rti.IsValid()); + return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && + GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); + } + + // Returns true if the type information provide the same amount of details. + // Note that it does not mean that the instructions have the same actual type + // (because the type can be the result of a merge). + bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { + if (!IsValid() && !rti.IsValid()) { + // Invalid types are equal. + return true; + } + if (!IsValid() || !rti.IsValid()) { + // One is valid, the other not. + return false; + } + return IsExact() == rti.IsExact() + && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); + } + + private: + ReferenceTypeInfo(); + ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); + + // The class of the object. + TypeHandle type_handle_; + // Whether or not the type is exact or a superclass of the actual type. + // Whether or not we have any information about this type. + bool is_exact_; +}; + +std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); + // Control-flow graph of a method. Contains a list of basic blocks. class HGraph : public ArenaObject { public: @@ -179,7 +302,8 @@ class HGraph : public ArenaObject { cached_float_constants_(std::less(), arena->Adapter(kArenaAllocConstantsMap)), cached_long_constants_(std::less(), arena->Adapter(kArenaAllocConstantsMap)), cached_double_constants_(std::less(), arena->Adapter(kArenaAllocConstantsMap)), - cached_current_method_(nullptr) { + cached_current_method_(nullptr), + inexact_object_rti_(ReferenceTypeInfo::CreateInvalid()) { blocks_.reserve(kDefaultNumberOfBlocks); } @@ -197,36 +321,23 @@ class HGraph : public ArenaObject { void AddBlock(HBasicBlock* block); - // Try building the SSA form of this graph, with dominance computation and loop - // recognition. Returns whether it was successful in doing all these steps. - bool TryBuildingSsa() { - BuildDominatorTree(); - // The SSA builder requires loops to all be natural. Specifically, the dead phi - // elimination phase checks the consistency of the graph when doing a post-order - // visit for eliminating dead phis: a dead phi can only have loop header phi - // users remaining when being visited. - if (!AnalyzeNaturalLoops()) return false; - // Precompute per-block try membership before entering the SSA builder, - // which needs the information to build catch block phis from values of - // locals at throwing instructions inside try blocks. - ComputeTryBlockInformation(); - TransformToSsa(); - in_ssa_form_ = true; - return true; - } + // Try building the SSA form of this graph, with dominance computation and + // loop recognition. Returns a code specifying that it was successful or the + // reason for failure. + BuildSsaResult TryBuildingSsa(StackHandleScopeCollection* handles); void ComputeDominanceInformation(); void ClearDominanceInformation(); void BuildDominatorTree(); - void TransformToSsa(); void SimplifyCFG(); void SimplifyCatchBlocks(); - // Analyze all natural loops in this graph. Returns false if one - // loop is not natural, that is the header does not dominate the - // back edge. - bool AnalyzeNaturalLoops() const; + // Analyze all natural loops in this graph. Returns a code specifying that it + // was successful or the reason for failure. The method will fail if a loop + // is not natural, that is the header does not dominate a back edge, or if it + // is a throw-catch loop, i.e. the header is a catch block. + BuildSsaResult AnalyzeNaturalLoops() const; // Iterate over blocks to compute try block membership. Needs reverse post // order and loop information. @@ -487,6 +598,10 @@ class HGraph : public ArenaObject { // (such as when the superclass could not be found). ArtMethod* art_method_; + // Keep the RTI of inexact Object to avoid having to pass stack handle + // collection pointer to passes which may create NullConstant. + ReferenceTypeInfo inexact_object_rti_; + friend class SsaBuilder; // For caching constants. friend class SsaLivenessAnalysis; // For the linear order. ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); @@ -1674,122 +1789,6 @@ class HEnvironment : public ArenaObject { DISALLOW_COPY_AND_ASSIGN(HEnvironment); }; -class ReferenceTypeInfo : ValueObject { - public: - typedef Handle TypeHandle; - - static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) { - // The constructor will check that the type_handle is valid. - return ReferenceTypeInfo(type_handle, is_exact); - } - - static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); } - - static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) { - return handle.GetReference() != nullptr; - } - - bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) { - return IsValidHandle(type_handle_); - } - - bool IsExact() const { return is_exact_; } - - bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsObjectClass(); - } - - bool IsStringClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsStringClass(); - } - - bool IsObjectArray() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return IsArrayClass() && GetTypeHandle()->GetComponentType()->IsObjectClass(); - } - - bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsInterface(); - } - - bool IsArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsArrayClass(); - } - - bool IsPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsPrimitiveArray(); - } - - bool IsNonPrimitiveArrayClass() const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - return GetTypeHandle()->IsArrayClass() && !GetTypeHandle()->IsPrimitiveArray(); - } - - bool CanArrayHold(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - if (!IsExact()) return false; - if (!IsArrayClass()) return false; - return GetTypeHandle()->GetComponentType()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - bool CanArrayHoldValuesOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - if (!IsExact()) return false; - if (!IsArrayClass()) return false; - if (!rti.IsArrayClass()) return false; - return GetTypeHandle()->GetComponentType()->IsAssignableFrom( - rti.GetTypeHandle()->GetComponentType()); - } - - Handle GetTypeHandle() const { return type_handle_; } - - bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - DCHECK(rti.IsValid()); - return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - bool IsStrictSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(IsValid()); - DCHECK(rti.IsValid()); - return GetTypeHandle().Get() != rti.GetTypeHandle().Get() && - GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get()); - } - - // Returns true if the type information provide the same amount of details. - // Note that it does not mean that the instructions have the same actual type - // (because the type can be the result of a merge). - bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { - if (!IsValid() && !rti.IsValid()) { - // Invalid types are equal. - return true; - } - if (!IsValid() || !rti.IsValid()) { - // One is valid, the other not. - return false; - } - return IsExact() == rti.IsExact() - && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); - } - - private: - ReferenceTypeInfo(); - ReferenceTypeInfo(TypeHandle type_handle, bool is_exact); - - // The class of the object. - TypeHandle type_handle_; - // Whether or not the type is exact or a superclass of the actual type. - // Whether or not we have any information about this type. - bool is_exact_; -}; - -std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); - class HInstruction : public ArenaObject { public: HInstruction(SideEffects side_effects, uint32_t dex_pc) @@ -4417,7 +4416,16 @@ class HPhi : public HInstruction { void RemoveInputAt(size_t index); Primitive::Type GetType() const OVERRIDE { return type_; } - void SetType(Primitive::Type type) { type_ = type; } + void SetType(Primitive::Type new_type) { + // Make sure that only valid type changes occur. The following are allowed: + // (1) int -> float/ref (primitive type propagation), + // (2) long -> double (primitive type propagation). + DCHECK(type_ == new_type || + (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimFloat) || + (type_ == Primitive::kPrimInt && new_type == Primitive::kPrimNot) || + (type_ == Primitive::kPrimLong && new_type == Primitive::kPrimDouble)); + type_ = new_type; + } bool CanBeNull() const OVERRIDE { return can_be_null_; } void SetCanBeNull(bool can_be_null) { can_be_null_ = can_be_null; } @@ -4657,7 +4665,21 @@ class HArrayGet : public HExpression<2> { return false; } - void SetType(Primitive::Type type) { type_ = type; } + bool IsEquivalentOf(HArrayGet* other) const { + bool result = (GetDexPc() == other->GetDexPc()); + if (kIsDebugBuild && result) { + DCHECK_EQ(GetBlock(), other->GetBlock()); + DCHECK_EQ(GetArray(), other->GetArray()); + DCHECK_EQ(GetIndex(), other->GetIndex()); + if (Primitive::IsIntOrLongType(GetType())) { + DCHECK(Primitive::IsFloatingPointType(other->GetType())); + } else { + DCHECK(Primitive::IsFloatingPointType(GetType())); + DCHECK(Primitive::IsIntOrLongType(other->GetType())); + } + } + return result; + } HInstruction* GetArray() const { return InputAt(0); } HInstruction* GetIndex() const { return InputAt(1); } diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 831b626c4..ba435180e 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -501,11 +501,8 @@ static void RunOptimizations(HGraph* graph, CompilerDriver* driver, OptimizingCompilerStats* stats, const DexCompilationUnit& dex_compilation_unit, - PassObserver* pass_observer) { - ScopedObjectAccess soa(Thread::Current()); - StackHandleScopeCollection handles(soa.Self()); - ScopedThreadSuspension sts(soa.Self(), kNative); - + PassObserver* pass_observer, + StackHandleScopeCollection* handles) { ArenaAllocator* arena = graph->GetArena(); HDeadCodeElimination* dce1 = new (arena) HDeadCodeElimination( graph, stats, HDeadCodeElimination::kInitialDeadCodeEliminationPassName); @@ -522,29 +519,23 @@ static void RunOptimizations(HGraph* graph, LoadStoreElimination* lse = new (arena) LoadStoreElimination(graph, *side_effects); HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph); BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction); - ReferenceTypePropagation* type_propagation = - new (arena) ReferenceTypePropagation(graph, &handles); HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver); InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier( - graph, stats, "instruction_simplifier_after_types"); - InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_after_bce"); - InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier( + InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_before_codegen"); IntrinsicsRecognizer* intrinsics = new (arena) IntrinsicsRecognizer(graph, driver); HOptimization* optimizations1[] = { intrinsics, + sharpening, fold1, simplify1, - type_propagation, - sharpening, dce1, - simplify2 }; RunOptimizations(optimizations1, arraysize(optimizations1), pass_observer); - MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, &handles); + MaybeRunInliner(graph, codegen, driver, stats, dex_compilation_unit, pass_observer, handles); HOptimization* optimizations2[] = { // BooleanSimplifier depends on the InstructionSimplifier removing @@ -557,13 +548,13 @@ static void RunOptimizations(HGraph* graph, induction, bce, fold3, // evaluates code generated by dynamic bce - simplify3, + simplify2, lse, dce2, // The codegen has a few assumptions that only the instruction simplifier // can satisfy. For example, the code generator does not expect to see a // HTypeConversion from a type to the same type. - simplify4, + simplify3, }; RunOptimizations(optimizations2, arraysize(optimizations2), pass_observer); @@ -768,14 +759,29 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, } VLOG(compiler) << "Optimizing " << pass_observer.GetMethodName(); + if (run_optimizations_) { + ScopedObjectAccess soa(Thread::Current()); + StackHandleScopeCollection handles(soa.Self()); + ScopedThreadSuspension sts(soa.Self(), kNative); + { PassScope scope(SsaBuilder::kSsaBuilderPassName, &pass_observer); - if (!graph->TryBuildingSsa()) { - // We could not transform the graph to SSA, bailout. - LOG(INFO) << "Skipping compilation of " << pass_observer.GetMethodName() - << ": it contains a non natural loop"; - MaybeRecordStat(MethodCompilationStat::kNotCompiledCannotBuildSSA); + BuildSsaResult result = graph->TryBuildingSsa(&handles); + if (result != kBuildSsaSuccess) { + switch (result) { + case kBuildSsaFailNonNaturalLoop: + MaybeRecordStat(MethodCompilationStat::kNotCompiledNonNaturalLoop); + break; + case kBuildSsaFailThrowCatchLoop: + MaybeRecordStat(MethodCompilationStat::kNotCompiledThrowCatchLoop); + break; + case kBuildSsaFailAmbiguousArrayGet: + MaybeRecordStat(MethodCompilationStat::kNotCompiledAmbiguousArrayGet); + break; + case kBuildSsaSuccess: + UNREACHABLE(); + } pass_observer.SetGraphInBadState(); return nullptr; } @@ -786,7 +792,8 @@ CodeGenerator* OptimizingCompiler::TryCompile(ArenaAllocator* arena, compiler_driver, compilation_stats_.get(), dex_compilation_unit, - &pass_observer); + &pass_observer, + &handles); codegen->CompileOptimized(code_allocator); } else { codegen->CompileBaseline(code_allocator); diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 6296eedfb..4713514bb 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -38,7 +38,9 @@ enum MethodCompilationStat { kRemovedDeadInstruction, kRemovedNullCheck, kNotCompiledBranchOutsideMethodCode, - kNotCompiledCannotBuildSSA, + kNotCompiledNonNaturalLoop, + kNotCompiledThrowCatchLoop, + kNotCompiledAmbiguousArrayGet, kNotCompiledHugeMethod, kNotCompiledLargeMethodNoBranches, kNotCompiledMalformedOpcode, @@ -104,7 +106,9 @@ class OptimizingCompilerStats { case kRemovedDeadInstruction: name = "RemovedDeadInstruction"; break; case kRemovedNullCheck: name = "RemovedNullCheck"; break; case kNotCompiledBranchOutsideMethodCode: name = "NotCompiledBranchOutsideMethodCode"; break; - case kNotCompiledCannotBuildSSA : name = "NotCompiledCannotBuildSSA"; break; + case kNotCompiledNonNaturalLoop : name = "NotCompiledNonNaturalLoop"; break; + case kNotCompiledThrowCatchLoop : name = "NotCompiledThrowCatchLoop"; break; + case kNotCompiledAmbiguousArrayGet : name = "NotCompiledAmbiguousArrayGet"; break; case kNotCompiledHugeMethod : name = "NotCompiledHugeMethod"; break; case kNotCompiledLargeMethodNoBranches : name = "NotCompiledLargeMethodNoBranches"; break; case kNotCompiledMalformedOpcode : name = "NotCompiledMalformedOpcode"; break; diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h index 350f0b14a..af3a00530 100644 --- a/compiler/optimizing/optimizing_unit_test.h +++ b/compiler/optimizing/optimizing_unit_test.h @@ -19,9 +19,13 @@ #include "nodes.h" #include "builder.h" +#include "common_compiler_test.h" #include "compiler/dex/pass_manager.h" #include "dex_file.h" #include "dex_instruction.h" +#include "handle_scope-inl.h" +#include "scoped_thread_state_change.h" +#include "ssa_builder.h" #include "ssa_liveness_analysis.h" #include "gtest/gtest.h" @@ -42,7 +46,6 @@ namespace art { #define FIVE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(5, __VA_ARGS__) #define SIX_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(6, __VA_ARGS__) - LiveInterval* BuildInterval(const size_t ranges[][2], size_t number_of_ranges, ArenaAllocator* allocator, @@ -111,6 +114,12 @@ inline bool IsRemoved(HInstruction* instruction) { return instruction->GetBlock() == nullptr; } +inline void TransformToSsa(HGraph* graph) { + ScopedObjectAccess soa(Thread::Current()); + StackHandleScopeCollection handles(soa.Self()); + EXPECT_EQ(graph->TryBuildingSsa(&handles), kBuildSsaSuccess); +} + } // namespace art #endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc deleted file mode 100644 index bde54ee97..000000000 --- a/compiler/optimizing/primitive_type_propagation.cc +++ /dev/null @@ -1,133 +0,0 @@ -/* - * Copyright (C) 2014 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "primitive_type_propagation.h" - -#include "nodes.h" -#include "ssa_builder.h" - -namespace art { - -static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { - // We trust the verifier has already done the necessary checking. - switch (existing) { - case Primitive::kPrimFloat: - case Primitive::kPrimDouble: - case Primitive::kPrimNot: - return existing; - default: - // Phis are initialized with a void type, so if we are asked - // to merge with a void type, we should use the existing one. - return new_type == Primitive::kPrimVoid - ? existing - : HPhi::ToPhiType(new_type); - } -} - -// Re-compute and update the type of the instruction. Returns -// whether or not the type was changed. -bool PrimitiveTypePropagation::UpdateType(HPhi* phi) { - DCHECK(phi->IsLive()); - Primitive::Type existing = phi->GetType(); - - Primitive::Type new_type = existing; - for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - Primitive::Type input_type = phi->InputAt(i)->GetType(); - new_type = MergeTypes(new_type, input_type); - } - phi->SetType(new_type); - - if (new_type == Primitive::kPrimDouble - || new_type == Primitive::kPrimFloat - || new_type == Primitive::kPrimNot) { - // If the phi is of floating point type, we need to update its inputs to that - // type. For inputs that are phis, we need to recompute their types. - for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - HInstruction* input = phi->InputAt(i); - if (input->GetType() != new_type) { - HInstruction* equivalent = (new_type == Primitive::kPrimNot) - ? SsaBuilder::GetReferenceTypeEquivalent(input) - : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type); - phi->ReplaceInput(equivalent, i); - if (equivalent->IsPhi()) { - AddToWorklist(equivalent->AsPhi()); - } else if (equivalent == input) { - // The input has changed its type. It can be an input of other phis, - // so we need to put phi users in the work list. - AddDependentInstructionsToWorklist(equivalent); - } - } - } - } - - return existing != new_type; -} - -void PrimitiveTypePropagation::Run() { - for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - VisitBasicBlock(it.Current()); - } - ProcessWorklist(); -} - -void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { - if (block->IsLoopHeader()) { - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - HPhi* phi = it.Current()->AsPhi(); - if (phi->IsLive()) { - AddToWorklist(phi); - } - } - } else { - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - // Eagerly compute the type of the phi, for quicker convergence. Note - // that we don't need to add users to the worklist because we are - // doing a reverse post-order visit, therefore either the phi users are - // non-loop phi and will be visited later in the visit, or are loop-phis, - // and they are already in the work list. - HPhi* phi = it.Current()->AsPhi(); - if (phi->IsLive()) { - UpdateType(phi); - } - } - } -} - -void PrimitiveTypePropagation::ProcessWorklist() { - while (!worklist_.empty()) { - HPhi* instruction = worklist_.back(); - worklist_.pop_back(); - if (UpdateType(instruction)) { - AddDependentInstructionsToWorklist(instruction); - } - } -} - -void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { - DCHECK(instruction->IsLive()); - worklist_.push_back(instruction); -} - -void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { - for (HUseIterator it(instruction->GetUses()); !it.Done(); it.Advance()) { - HPhi* phi = it.Current()->GetUser()->AsPhi(); - if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) { - AddToWorklist(phi); - } - } -} - -} // namespace art diff --git a/compiler/optimizing/primitive_type_propagation.h b/compiler/optimizing/primitive_type_propagation.h deleted file mode 100644 index 212fcfc69..000000000 --- a/compiler/optimizing/primitive_type_propagation.h +++ /dev/null @@ -1,52 +0,0 @@ -/* - * Copyright (C) 2014 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ -#define ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ - -#include "base/arena_containers.h" -#include "nodes.h" - -namespace art { - -// Compute and propagate primitive types of phis in the graph. -class PrimitiveTypePropagation : public ValueObject { - public: - explicit PrimitiveTypePropagation(HGraph* graph) - : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocPrimitiveTypePropagation)) { - worklist_.reserve(kDefaultWorklistSize); - } - - void Run(); - - private: - void VisitBasicBlock(HBasicBlock* block); - void ProcessWorklist(); - void AddToWorklist(HPhi* phi); - void AddDependentInstructionsToWorklist(HInstruction* instruction); - bool UpdateType(HPhi* phi); - - HGraph* const graph_; - ArenaVector worklist_; - - static constexpr size_t kDefaultWorklistSize = 8; - - DISALLOW_COPY_AND_ASSIGN(PrimitiveTypePropagation); -}; - -} // namespace art - -#endif // ART_COMPILER_OPTIMIZING_PRIMITIVE_TYPE_PROPAGATION_H_ diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index fea903d9c..94a297c9e 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -40,7 +40,6 @@ class RTPVisitor : public HGraphDelegateVisitor { throwable_class_handle_(throwable_class_handle), worklist_(worklist) {} - void VisitNullConstant(HNullConstant* null_constant) OVERRIDE; void VisitNewInstance(HNewInstance* new_instance) OVERRIDE; void VisitLoadClass(HLoadClass* load_class) OVERRIDE; void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE; @@ -71,8 +70,6 @@ class RTPVisitor : public HGraphDelegateVisitor { ReferenceTypeInfo::TypeHandle string_class_handle_; ReferenceTypeInfo::TypeHandle throwable_class_handle_; ArenaVector* worklist_; - - static constexpr size_t kDefaultWorklistSize = 8; }; ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph, @@ -171,9 +168,13 @@ static void ForEachUntypedInstruction(HGraph* graph, Functor fn) { ScopedObjectAccess soa(Thread::Current()); for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) { for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) { - HInstruction* instr = it.Current(); - if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) { - fn(instr); + HPhi* phi = it.Current()->AsPhi(); + // Note that the graph may contain dead phis when run from the SsaBuilder. + // Skip those as they might have a type conflict and will be removed anyway. + if (phi->IsLive() && + phi->GetType() == Primitive::kPrimNot && + !phi->GetReferenceTypeInfo().IsValid()) { + fn(phi); } } for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) { @@ -376,6 +377,75 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { } } +// Returns true if one of the patterns below has been recognized. If so, the +// InstanceOf instruction together with the true branch of `ifInstruction` will +// be returned using the out parameters. +// Recognized patterns: +// (1) patterns equivalent to `if (obj instanceof X)` +// (a) InstanceOf -> Equal to 1 -> If +// (b) InstanceOf -> NotEqual to 0 -> If +// (c) InstanceOf -> If +// (2) patterns equivalent to `if (!(obj instanceof X))` +// (a) InstanceOf -> Equal to 0 -> If +// (b) InstanceOf -> NotEqual to 1 -> If +// (c) InstanceOf -> BooleanNot -> If +static bool MatchIfInstanceOf(HIf* ifInstruction, + /* out */ HInstanceOf** instanceOf, + /* out */ HBasicBlock** trueBranch) { + HInstruction* input = ifInstruction->InputAt(0); + + if (input->IsEqual()) { + HInstruction* rhs = input->AsEqual()->GetConstantRight(); + if (rhs != nullptr) { + HInstruction* lhs = input->AsEqual()->GetLeastConstantLeft(); + if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { + if (rhs->AsIntConstant()->IsOne()) { + // Case (1a) + *trueBranch = ifInstruction->IfTrueSuccessor(); + } else { + // Case (2a) + DCHECK(rhs->AsIntConstant()->IsZero()); + *trueBranch = ifInstruction->IfFalseSuccessor(); + } + *instanceOf = lhs->AsInstanceOf(); + return true; + } + } + } else if (input->IsNotEqual()) { + HInstruction* rhs = input->AsNotEqual()->GetConstantRight(); + if (rhs != nullptr) { + HInstruction* lhs = input->AsNotEqual()->GetLeastConstantLeft(); + if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { + if (rhs->AsIntConstant()->IsZero()) { + // Case (1b) + *trueBranch = ifInstruction->IfTrueSuccessor(); + } else { + // Case (2b) + DCHECK(rhs->AsIntConstant()->IsOne()); + *trueBranch = ifInstruction->IfFalseSuccessor(); + } + *instanceOf = lhs->AsInstanceOf(); + return true; + } + } + } else if (input->IsInstanceOf()) { + // Case (1c) + *instanceOf = input->AsInstanceOf(); + *trueBranch = ifInstruction->IfTrueSuccessor(); + return true; + } else if (input->IsBooleanNot()) { + HInstruction* not_input = input->InputAt(0); + if (not_input->IsInstanceOf()) { + // Case (2c) + *instanceOf = not_input->AsInstanceOf(); + *trueBranch = ifInstruction->IfFalseSuccessor(); + return true; + } + } + + return false; +} + // Detects if `block` is the True block for the pattern // `if (x instanceof ClassX) { }` // If that's the case insert an HBoundType instruction to bound the type of `x` @@ -385,22 +455,11 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { if (ifInstruction == nullptr) { return; } - HInstruction* ifInput = ifInstruction->InputAt(0); - HInstruction* instanceOf = nullptr; - HBasicBlock* instanceOfTrueBlock = nullptr; - // The instruction simplifier has transformed: - // - `if (a instanceof A)` into an HIf with an HInstanceOf input - // - `if (!(a instanceof A)` into an HIf with an HBooleanNot input (which in turn - // has an HInstanceOf input) - // So we should not see the usual HEqual here. - if (ifInput->IsInstanceOf()) { - instanceOf = ifInput; - instanceOfTrueBlock = ifInstruction->IfTrueSuccessor(); - } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) { - instanceOf = ifInput->InputAt(0); - instanceOfTrueBlock = ifInstruction->IfFalseSuccessor(); - } else { + // Try to recognize common `if (instanceof)` and `if (!instanceof)` patterns. + HInstanceOf* instanceOf = nullptr; + HBasicBlock* instanceOfTrueBlock = nullptr; + if (!MatchIfInstanceOf(ifInstruction, &instanceOf, &instanceOfTrueBlock)) { return; } @@ -505,13 +564,6 @@ void RTPVisitor::UpdateReferenceTypeInfo(HInstruction* instr, SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact); } -void RTPVisitor::VisitNullConstant(HNullConstant* instr) { - // TODO: The null constant could be bound contextually (e.g. based on return statements) - // to a more precise type. - instr->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false)); -} - void RTPVisitor::VisitNewInstance(HNewInstance* instr) { UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true); } @@ -523,7 +575,11 @@ void RTPVisitor::VisitNewArray(HNewArray* instr) { static mirror::Class* GetClassFromDexCache(Thread* self, const DexFile& dex_file, uint16_t type_idx) SHARED_REQUIRES(Locks::mutator_lock_) { mirror::DexCache* dex_cache = - Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, false); + Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file, /* allow_failure */ true); + if (dex_cache == nullptr) { + // Dex cache could not be found. This should only happen during gtests. + return nullptr; + } // Get type from dex cache assuming it was populated by the verifier. return dex_cache->GetResolvedType(type_idx); } @@ -540,17 +596,24 @@ void RTPVisitor::VisitParameterValue(HParameterValue* instr) { void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info) { - // The field index is unknown only during tests. - if (instr->GetType() != Primitive::kPrimNot || info.GetFieldIndex() == kUnknownFieldIndex) { + if (instr->GetType() != Primitive::kPrimNot) { return; } ScopedObjectAccess soa(Thread::Current()); - ClassLinker* cl = Runtime::Current()->GetClassLinker(); - ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get()); - // TODO: There are certain cases where we can't resolve the field. - // b/21914925 is open to keep track of a repro case for this issue. - mirror::Class* klass = (field == nullptr) ? nullptr : field->GetType(); + mirror::Class* klass = nullptr; + + // The field index is unknown only during tests. + if (info.GetFieldIndex() != kUnknownFieldIndex) { + ClassLinker* cl = Runtime::Current()->GetClassLinker(); + ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), info.GetDexCache().Get()); + // TODO: There are certain cases where we can't resolve the field. + // b/21914925 is open to keep track of a repro case for this issue. + if (field != nullptr) { + klass = field->GetType(); + } + } + SetClassAsTypeInfo(instr, klass, /* is_exact */ false); } @@ -666,7 +729,7 @@ void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { } void ReferenceTypePropagation::VisitPhi(HPhi* phi) { - if (phi->GetType() != Primitive::kPrimNot) { + if (phi->IsDead() || phi->GetType() != Primitive::kPrimNot) { return; } @@ -824,6 +887,8 @@ void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) { // NullConstant inputs are ignored during merging as they do not provide any useful information. // If all the inputs are NullConstants then the type of the phi will be set to Object. void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { + DCHECK(instr->IsLive()); + size_t input_count = instr->InputCount(); size_t first_input_index_not_null = 0; while (first_input_index_not_null < input_count && @@ -868,7 +933,7 @@ void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { // Re-computes and updates the nullability of the instruction. Returns whether or // not the nullability was changed. bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) { - DCHECK(instr->IsPhi() + DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive()) || instr->IsBoundType() || instr->IsNullCheck() || instr->IsArrayGet()); @@ -916,7 +981,7 @@ void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) { void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { for (HUseIterator it(instruction->GetUses()); !it.Done(); it.Advance()) { HInstruction* user = it.Current()->GetUser(); - if (user->IsPhi() + if ((user->IsPhi() && user->AsPhi()->IsLive()) || user->IsBoundType() || user->IsNullCheck() || (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) { diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index 080f97075..b900ed096 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -28,13 +28,13 @@ #include "ssa_liveness_analysis.h" #include "ssa_phi_elimination.h" -#include "gtest/gtest.h" - namespace art { // Note: the register allocator tests rely on the fact that constants have live // intervals and registers get allocated to them. +class RegisterAllocatorTest : public CommonCompilerTest {}; + static bool Check(const uint16_t* data) { ArenaPool pool; ArenaAllocator allocator(&pool); @@ -42,7 +42,7 @@ static bool Check(const uint16_t* data) { HGraphBuilder builder(graph); const DexFile::CodeItem* item = reinterpret_cast(data); builder.BuildGraph(*item); - graph->TryBuildingSsa(); + TransformToSsa(graph); std::unique_ptr features_x86( X86InstructionSetFeatures::FromCppDefines()); x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); @@ -57,7 +57,7 @@ static bool Check(const uint16_t* data) { * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator * tests are based on this validation method. */ -TEST(RegisterAllocatorTest, ValidateIntervals) { +TEST_F(RegisterAllocatorTest, ValidateIntervals) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = CreateGraph(&allocator); @@ -146,7 +146,7 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { } } -TEST(RegisterAllocatorTest, CFG1) { +TEST_F(RegisterAllocatorTest, CFG1) { /* * Test the following snippet: * return 0; @@ -166,7 +166,7 @@ TEST(RegisterAllocatorTest, CFG1) { ASSERT_TRUE(Check(data)); } -TEST(RegisterAllocatorTest, Loop1) { +TEST_F(RegisterAllocatorTest, Loop1) { /* * Test the following snippet: * int a = 0; @@ -205,7 +205,7 @@ TEST(RegisterAllocatorTest, Loop1) { ASSERT_TRUE(Check(data)); } -TEST(RegisterAllocatorTest, Loop2) { +TEST_F(RegisterAllocatorTest, Loop2) { /* * Test the following snippet: * int a = 0; @@ -259,11 +259,11 @@ static HGraph* BuildSSAGraph(const uint16_t* data, ArenaAllocator* allocator) { HGraphBuilder builder(graph); const DexFile::CodeItem* item = reinterpret_cast(data); builder.BuildGraph(*item); - graph->TryBuildingSsa(); + TransformToSsa(graph); return graph; } -TEST(RegisterAllocatorTest, Loop3) { +TEST_F(RegisterAllocatorTest, Loop3) { /* * Test the following snippet: * int a = 0 @@ -326,7 +326,7 @@ TEST(RegisterAllocatorTest, Loop3) { ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister()); } -TEST(RegisterAllocatorTest, FirstRegisterUse) { +TEST_F(RegisterAllocatorTest, FirstRegisterUse) { const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8, @@ -366,7 +366,7 @@ TEST(RegisterAllocatorTest, FirstRegisterUse) { ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition()); } -TEST(RegisterAllocatorTest, DeadPhi) { +TEST_F(RegisterAllocatorTest, DeadPhi) { /* Test for a dead loop phi taking as back-edge input a phi that also has * this loop phi as input. Walking backwards in SsaDeadPhiElimination * does not solve the problem because the loop phi will be visited last. @@ -407,7 +407,7 @@ TEST(RegisterAllocatorTest, DeadPhi) { * that share the same register. It should split the interval it is currently * allocating for at the minimum lifetime position between the two inactive intervals. */ -TEST(RegisterAllocatorTest, FreeUntil) { +TEST_F(RegisterAllocatorTest, FreeUntil) { const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( Instruction::CONST_4 | 0 | 0, Instruction::RETURN); @@ -539,7 +539,7 @@ static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator, return graph; } -TEST(RegisterAllocatorTest, PhiHint) { +TEST_F(RegisterAllocatorTest, PhiHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HPhi *phi; @@ -658,7 +658,7 @@ static HGraph* BuildFieldReturn(ArenaAllocator* allocator, return graph; } -TEST(RegisterAllocatorTest, ExpectedInRegisterHint) { +TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *field, *ret; @@ -726,7 +726,7 @@ static HGraph* BuildTwoSubs(ArenaAllocator* allocator, return graph; } -TEST(RegisterAllocatorTest, SameAsFirstInputHint) { +TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *first_sub, *second_sub; @@ -795,7 +795,7 @@ static HGraph* BuildDiv(ArenaAllocator* allocator, return graph; } -TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { +TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { ArenaPool pool; ArenaAllocator allocator(&pool); HInstruction *div; @@ -819,7 +819,7 @@ TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { // Test a bug in the register allocator, where allocating a blocked // register would lead to spilling an inactive interval at the wrong // position. -TEST(RegisterAllocatorTest, SpillInactive) { +TEST_F(RegisterAllocatorTest, SpillInactive) { ArenaPool pool; // Create a synthesized graph to please the register_allocator and diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 9e6cfbe65..9e869e18e 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -17,214 +17,11 @@ #include "ssa_builder.h" #include "nodes.h" -#include "primitive_type_propagation.h" +#include "reference_type_propagation.h" #include "ssa_phi_elimination.h" namespace art { -// Returns whether this is a loop header phi which was eagerly created but later -// found inconsistent due to the vreg being undefined in one of its predecessors. -// Such phi is marked dead and should be ignored until its removal in SsaPhiElimination. -static bool IsUndefinedLoopHeaderPhi(HPhi* phi) { - return phi->IsLoopHeaderPhi() && phi->InputCount() != phi->GetBlock()->GetPredecessors().size(); -} - -/** - * A debuggable application may require to reviving phis, to ensure their - * associated DEX register is available to a debugger. This class implements - * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It - * also makes sure that phis with incompatible input types are not revived - * (statement (b) of the SsaBuilder). - * - * This phase must be run after detecting dead phis through the - * DeadPhiElimination phase, and before deleting the dead phis. - */ -class DeadPhiHandling : public ValueObject { - public: - explicit DeadPhiHandling(HGraph* graph) - : graph_(graph), worklist_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { - worklist_.reserve(kDefaultWorklistSize); - } - - void Run(); - - private: - void VisitBasicBlock(HBasicBlock* block); - void ProcessWorklist(); - void AddToWorklist(HPhi* phi); - void AddDependentInstructionsToWorklist(HPhi* phi); - bool UpdateType(HPhi* phi); - - HGraph* const graph_; - ArenaVector worklist_; - - static constexpr size_t kDefaultWorklistSize = 8; - - DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); -}; - -static bool HasConflictingEquivalent(HPhi* phi) { - if (phi->GetNext() == nullptr) { - return false; - } - HPhi* next = phi->GetNext()->AsPhi(); - if (next->GetRegNumber() == phi->GetRegNumber()) { - if (next->GetType() == Primitive::kPrimVoid) { - // We only get a void type for an equivalent phi we processed and found out - // it was conflicting. - return true; - } else { - // Go to the next phi, in case it is also an equivalent. - return HasConflictingEquivalent(next); - } - } - return false; -} - -bool DeadPhiHandling::UpdateType(HPhi* phi) { - if (phi->IsDead()) { - // Phi was rendered dead while waiting in the worklist because it was replaced - // with an equivalent. - return false; - } - - Primitive::Type existing = phi->GetType(); - - bool conflict = false; - Primitive::Type new_type = existing; - for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - HInstruction* input = phi->InputAt(i); - if (input->IsPhi() && input->AsPhi()->IsDead()) { - // We are doing a reverse post order visit of the graph, reviving - // phis that have environment uses and updating their types. If an - // input is a phi, and it is dead (because its input types are - // conflicting), this phi must be marked dead as well. - conflict = true; - break; - } - Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); - - // The only acceptable transitions are: - // - From void to typed: first time we update the type of this phi. - // - From int to reference (or reference to int): the phi has to change - // to reference type. If the integer input cannot be converted to a - // reference input, the phi will remain dead. - if (new_type == Primitive::kPrimVoid) { - new_type = input_type; - } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { - if (input->IsPhi() && HasConflictingEquivalent(input->AsPhi())) { - // If we already asked for an equivalent of the input phi, but that equivalent - // ended up conflicting, make this phi conflicting too. - conflict = true; - break; - } - HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); - if (equivalent == nullptr) { - conflict = true; - break; - } - phi->ReplaceInput(equivalent, i); - if (equivalent->IsPhi()) { - DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); - // We created a new phi, but that phi has the same inputs as the old phi. We - // add it to the worklist to ensure its inputs can also be converted to reference. - // If not, it will remain dead, and the algorithm will make the current phi dead - // as well. - equivalent->AsPhi()->SetLive(); - AddToWorklist(equivalent->AsPhi()); - } - } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { - new_type = Primitive::kPrimNot; - // Start over, we may request reference equivalents for the inputs of the phi. - i = -1; - } else if (new_type != input_type) { - conflict = true; - break; - } - } - - if (conflict) { - phi->SetType(Primitive::kPrimVoid); - phi->SetDead(); - return true; - } else if (existing == new_type) { - return false; - } - - DCHECK(phi->IsLive()); - phi->SetType(new_type); - - // There might exist a `new_type` equivalent of `phi` already. In that case, - // we replace the equivalent with the, now live, `phi`. - HPhi* equivalent = phi->GetNextEquivalentPhiWithSameType(); - if (equivalent != nullptr) { - // There cannot be more than two equivalents with the same type. - DCHECK(equivalent->GetNextEquivalentPhiWithSameType() == nullptr); - // If doing fix-point iteration, the equivalent might be in `worklist_`. - // Setting it dead will make UpdateType skip it. - equivalent->SetDead(); - equivalent->ReplaceWith(phi); - } - - return true; -} - -void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - HPhi* phi = it.Current()->AsPhi(); - if (IsUndefinedLoopHeaderPhi(phi)) { - DCHECK(phi->IsDead()); - continue; - } - if (phi->IsDead() && phi->HasEnvironmentUses()) { - phi->SetLive(); - if (block->IsLoopHeader()) { - // Loop phis must have a type to guarantee convergence of the algorithm. - DCHECK_NE(phi->GetType(), Primitive::kPrimVoid); - AddToWorklist(phi); - } else { - // Because we are doing a reverse post order visit, all inputs of - // this phi have been visited and therefore had their (initial) type set. - UpdateType(phi); - } - } - } -} - -void DeadPhiHandling::ProcessWorklist() { - while (!worklist_.empty()) { - HPhi* instruction = worklist_.back(); - worklist_.pop_back(); - // Note that the same equivalent phi can be added multiple times in the work list, if - // used by multiple phis. The first call to `UpdateType` will know whether the phi is - // dead or live. - if (instruction->IsLive() && UpdateType(instruction)) { - AddDependentInstructionsToWorklist(instruction); - } - } -} - -void DeadPhiHandling::AddToWorklist(HPhi* instruction) { - DCHECK(instruction->IsLive()); - worklist_.push_back(instruction); -} - -void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { - for (HUseIterator it(instruction->GetUses()); !it.Done(); it.Advance()) { - HPhi* phi = it.Current()->GetUser()->AsPhi(); - if (phi != nullptr && !phi->IsDead()) { - AddToWorklist(phi); - } - } -} - -void DeadPhiHandling::Run() { - for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { - VisitBasicBlock(it.Current()); - } - ProcessWorklist(); -} - void SsaBuilder::SetLoopHeaderPhiInputs() { for (size_t i = loop_headers_.size(); i > 0; --i) { HBasicBlock* block = loop_headers_[i - 1]; @@ -285,10 +82,11 @@ void SsaBuilder::EquivalentPhisCleanup() { HPhi* phi = it.Current()->AsPhi(); HPhi* next = phi->GetNextEquivalentPhiWithSameType(); if (next != nullptr) { - // Make sure we do not replace a live phi with a dead phi. A live phi has been - // handled by the type propagation phase, unlike a dead phi. + // Make sure we do not replace a live phi with a dead phi. A live phi + // has been handled by the type propagation phase, unlike a dead phi. if (next->IsLive()) { phi->ReplaceWith(next); + phi->SetDead(); } else { next->ReplaceWith(phi); } @@ -300,64 +98,7 @@ void SsaBuilder::EquivalentPhisCleanup() { } } -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 - // block. For loops, we create phis whose inputs will be set in 2). - for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { - VisitBasicBlock(it.Current()); - } - - // 2) Set inputs of loop phis. - SetLoopHeaderPhiInputs(); - - // 3) Mark dead phis. This will mark phis that are only used by environments: - // at the DEX level, the type of these phis does not need to be consistent, but - // our code generator will complain if the inputs of a phi do not have the same - // type. The marking allows the type propagation to know which phis it needs - // to handle. We mark but do not eliminate: the elimination will be done in - // step 9). - SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); - dead_phis_for_type_propagation.MarkDeadPhis(); - - // 4) Propagate types of phis. At this point, phis are typed void in the general - // case, or float/double/reference when we created an equivalent phi. So we - // need to propagate the types across phis to give them a correct type. - PrimitiveTypePropagation type_propagation(GetGraph()); - type_propagation.Run(); - - // 5) When creating equivalent phis we copy the inputs of the original phi which - // may be improperly typed. This was fixed during the type propagation in 4) 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(); - - // 6) Mark dead phis again. Step 4) may have introduced new phis. - // Step 5) might enable the death of new phis. - SsaDeadPhiElimination dead_phis(GetGraph()); - dead_phis.MarkDeadPhis(); - - // 7) 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 - // SsaBuilder (see ssa_builder.h). - SsaRedundantPhiElimination redundant_phi(GetGraph()); - redundant_phi.Run(); - - // 8) Fix the type for null constants which are part of an equality comparison. - // We need to do this after redundant phi elimination, to ensure the only cases - // that we can see are reference comparison against 0. The redundant phi - // elimination ensures we do not see a phi taking two 0 constants in a HEqual - // or HNotEqual. - FixNullConstantType(); - - // 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 - // when merging constants), in which case it is OK for the environments - // to just reference one. +void SsaBuilder::FixEnvironmentPhis() { for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { @@ -378,24 +119,345 @@ void SsaBuilder::BuildSsa() { phi->ReplaceWith(next); } } +} - // 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()) { - DeadPhiHandling dead_phi_handler(GetGraph()); - dead_phi_handler.Run(); +static void AddDependentInstructionsToWorklist(HInstruction* instruction, + ArenaVector* worklist) { + // If `instruction` is a dead phi, type conflict was just identified. All its + // live phi users, and transitively users of those users, therefore need to be + // marked dead/conflicting too, so we add them to the worklist. Otherwise we + // add users whose type does not match and needs to be updated. + bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); + for (HUseIterator it(instruction->GetUses()); !it.Done(); it.Advance()) { + HInstruction* user = it.Current()->GetUser(); + if (user->IsPhi() && user->AsPhi()->IsLive()) { + if (add_all_live_phis || user->GetType() != instruction->GetType()) { + worklist->push_back(user->AsPhi()); + } + } } +} + +// Find a candidate primitive type for `phi` by merging the type of its inputs. +// Return false if conflict is identified. +static bool TypePhiFromInputs(HPhi* phi) { + Primitive::Type common_type = phi->GetType(); - // 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), - // as well as for the code generation, which does not deal with phis of conflicting + for (HInputIterator it(phi); !it.Done(); it.Advance()) { + HInstruction* input = it.Current(); + if (input->IsPhi() && input->AsPhi()->IsDead()) { + // Phis are constructed live so if an input is a dead phi, it must have + // been made dead due to type conflict. Mark this phi conflicting too. + return false; + } + + Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); + if (common_type == input_type) { + // No change in type. + } else if (Primitive::ComponentSize(common_type) != Primitive::ComponentSize(input_type)) { + // Types are of different sizes, e.g. int vs. long. Must be a conflict. + return false; + } else if (Primitive::IsIntegralType(common_type)) { + // Previous inputs were integral, this one is not but is of the same size. + // This does not imply conflict since some bytecode instruction types are + // ambiguous. TypeInputsOfPhi will either type them or detect a conflict. + DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot); + common_type = input_type; + } else if (Primitive::IsIntegralType(input_type)) { + // Input is integral, common type is not. Same as in the previous case, if + // there is a conflict, it will be detected during TypeInputsOfPhi. + DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot); + } else { + // Combining float and reference types. Clearly a conflict. + DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) || + (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat)); + return false; + } + } + + // We have found a candidate type for the phi. Set it and return true. We may + // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi. + phi->SetType(common_type); + return true; +} + +// Replace inputs of `phi` to match its type. Return false if conflict is identified. +bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector* worklist) { + Primitive::Type common_type = phi->GetType(); + if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) { + // Phi either contains only other untyped phis (common_type == kPrimVoid), + // or `common_type` is integral and we do not need to retype ambiguous inputs + // because they are always constructed with the integral type candidate. + if (kIsDebugBuild) { + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + HInstruction* input = phi->InputAt(i); + if (common_type == Primitive::kPrimVoid) { + DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid); + } else { + DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) || + HPhi::ToPhiType(input->GetType()) == common_type); + } + } + } + // Inputs did not need to be replaced, hence no conflict. Report success. + return true; + } else { + DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); + for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { + HInstruction* input = phi->InputAt(i); + if (input->GetType() != common_type) { + // Input type does not match phi's type. Try to retype the input or + // generate a suitably typed equivalent. + HInstruction* equivalent = (common_type == Primitive::kPrimNot) + ? GetReferenceTypeEquivalent(input) + : GetFloatOrDoubleEquivalent(input, common_type); + if (equivalent == nullptr) { + // Input could not be typed. Report conflict. + return false; + } + // Make sure the input did not change its type and we do not need to + // update its users. + DCHECK_NE(input, equivalent); + + phi->ReplaceInput(equivalent, i); + if (equivalent->IsPhi()) { + worklist->push_back(equivalent->AsPhi()); + } + } + } + // All inputs either matched the type of the phi or we successfully replaced + // them with a suitable equivalent. Report success. + return true; + } +} + +// Attempt to set the primitive type of `phi` to match its inputs. Return whether +// it was changed by the algorithm or not. +bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector* worklist) { + DCHECK(phi->IsLive()); + Primitive::Type original_type = phi->GetType(); + + // Try to type the phi in two stages: + // (1) find a candidate type for the phi by merging types of all its inputs, + // (2) try to type the phi's inputs to that candidate type. + // Either of these stages may detect a type conflict and fail, in which case + // we immediately abort. + if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { + // Conflict detected. Mark the phi dead and return true because it changed. + phi->SetDead(); + return true; + } + + // Return true if the type of the phi has changed. + return phi->GetType() != original_type; +} + +void SsaBuilder::RunPrimitiveTypePropagation() { + ArenaVector worklist(GetGraph()->GetArena()->Adapter()); + + for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + if (block->IsLoopHeader()) { + for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { + HPhi* phi = phi_it.Current()->AsPhi(); + if (phi->IsLive()) { + worklist.push_back(phi); + } + } + } else { + for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { + // Eagerly compute the type of the phi, for quicker convergence. Note + // that we don't need to add users to the worklist because we are + // doing a reverse post-order visit, therefore either the phi users are + // non-loop phi and will be visited later in the visit, or are loop-phis, + // and they are already in the work list. + HPhi* phi = phi_it.Current()->AsPhi(); + if (phi->IsLive()) { + UpdatePrimitiveType(phi, &worklist); + } + } + } + } + + ProcessPrimitiveTypePropagationWorklist(&worklist); + EquivalentPhisCleanup(); +} + +void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector* worklist) { + // Process worklist + while (!worklist->empty()) { + HPhi* phi = worklist->back(); + worklist->pop_back(); + // The phi could have been made dead as a result of conflicts while in the + // worklist. If it is now dead, there is no point in updating its type. + if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { + AddDependentInstructionsToWorklist(phi, worklist); + } + } +} + +static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { + Primitive::Type type = aget->GetType(); + DCHECK(Primitive::IsIntOrLongType(type)); + HArrayGet* next = aget->GetNext()->AsArrayGet(); + return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr; +} + +static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { + Primitive::Type type = aget->GetType(); + DCHECK(Primitive::IsIntOrLongType(type)); + DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); + + HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( + aget->GetArray(), + aget->GetIndex(), + type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, + aget->GetDexPc()); + aget->GetBlock()->InsertInstructionAfter(equivalent, aget); + return equivalent; +} + +// Returns true if the array input of `aget` is either of type int[] or long[]. +// Should only be called on ArrayGets with ambiguous type (int/float, long/double) +// on arrays which were typed to an array class by RTP. +static bool IsArrayGetOnIntegralArray(HArrayGet* aget) SHARED_REQUIRES(Locks::mutator_lock_) { + ReferenceTypeInfo array_type = aget->GetArray()->GetReferenceTypeInfo(); + DCHECK(array_type.IsPrimitiveArrayClass()); + ReferenceTypeInfo::TypeHandle array_type_handle = array_type.GetTypeHandle(); + + bool is_integral_type; + if (Primitive::Is64BitType(aget->GetType())) { + is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveLong(); + DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveDouble()); + } else { + is_integral_type = array_type_handle->GetComponentType()->IsPrimitiveInt(); + DCHECK(is_integral_type || array_type_handle->GetComponentType()->IsPrimitiveFloat()); + } + return is_integral_type; +} + +bool SsaBuilder::FixAmbiguousArrayGets() { + if (ambiguous_agets_.empty()) { + return true; + } + + // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet + // uses (because they are untyped) and environment uses (if --debuggable). + // After resolving all ambiguous ArrayGets, we will re-run primitive type + // propagation on the Phis which need to be updated. + ArenaVector worklist(GetGraph()->GetArena()->Adapter()); + + { + ScopedObjectAccess soa(Thread::Current()); + + for (HArrayGet* aget_int : ambiguous_agets_) { + if (!aget_int->GetArray()->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { + // RTP did not type the input array. Bail. + return false; + } + + HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); + if (IsArrayGetOnIntegralArray(aget_int)) { + if (aget_float != nullptr) { + // There is a float/double equivalent. We must replace it and re-run + // primitive type propagation on all dependent instructions. + aget_float->ReplaceWith(aget_int); + aget_float->GetBlock()->RemoveInstruction(aget_float); + AddDependentInstructionsToWorklist(aget_int, &worklist); + } + } else { + if (aget_float == nullptr) { + // This is a float/double ArrayGet but there were no typed uses which + // would create the typed equivalent. Create it now. + aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); + } + // Replace the original int/long instruction. Note that it may have phi + // uses, environment uses, as well as real uses (from untyped ArraySets). + // We need to re-run primitive type propagation on its dependent instructions. + aget_int->ReplaceWith(aget_float); + aget_int->GetBlock()->RemoveInstruction(aget_int); + AddDependentInstructionsToWorklist(aget_float, &worklist); + } + } + } + + // Set a flag stating that types of ArrayGets have been resolved. This is used + // by GetFloatOrDoubleEquivalentOfArrayGet to report conflict. + agets_fixed_ = true; + + if (!worklist.empty()) { + ProcessPrimitiveTypePropagationWorklist(&worklist); + EquivalentPhisCleanup(); + } + + return true; +} + +BuildSsaResult 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 block. For loops, we create phis whose inputs will be set in 2). + for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); + } + + // 2) Set inputs of loop header phis. + SetLoopHeaderPhiInputs(); + + // 3) Propagate types of phis. At this point, phis are typed void in the general + // case, or float/double/reference if we created an equivalent phi. So we need + // to propagate the types across phis to give them a correct type. If a type + // conflict is detected in this stage, the phi is marked dead. + RunPrimitiveTypePropagation(); + + // 4) Now that the correct primitive types have been assigned, 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 SsaBuilder (see ssa_builder.h). + SsaRedundantPhiElimination(GetGraph()).Run(); + + // 5) Fix the type for null constants which are part of an equality comparison. + // We need to do this after redundant phi elimination, to ensure the only cases + // that we can see are reference comparison against 0. The redundant phi + // elimination ensures we do not see a phi taking two 0 constants in a HEqual + // or HNotEqual. + FixNullConstantType(); + + // 6) Compute type of reference type instructions. The pass assumes that + // NullConstant has been fixed up. + ReferenceTypePropagation(GetGraph(), handles_).Run(); + + // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float + // or long/double). Now that RTP computed the type of the array input, the + // ambiguity can be resolved and the correct equivalent kept. + if (!FixAmbiguousArrayGets()) { + return kBuildSsaFailAmbiguousArrayGet; + } + + // 8) Mark dead phis. This will mark phis which are not used by instructions + // or other live phis. If compiling as debuggable code, phis will also be kept + // live if they have an environment use. + SsaDeadPhiElimination dead_phi_elimimation(GetGraph()); + dead_phi_elimimation.MarkDeadPhis(); + + // 9) Make sure environments use the right phi equivalent: a phi marked dead + // can have a phi equivalent that is not dead. In that case we have to replace + // it with the live equivalent because deoptimization and try/catch rely on + // environments containing values of all live vregs at that point. Note that + // there can be multiple phis for the same Dex register that are live + // (for example when merging constants), in which case it is okay for the + // environments to just reference one. + FixEnvironmentPhis(); + + // 10) Now that the right phis are used for the environments, 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), as well + // as for the code generation, which does not deal with phis of conflicting // input types. - dead_phis.EliminateDeadPhis(); + dead_phi_elimimation.EliminateDeadPhis(); - // 12) Clear locals. + // 11) Clear locals. for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); !it.Done(); it.Advance()) { @@ -404,6 +466,8 @@ void SsaBuilder::BuildSsa() { current->GetBlock()->RemoveInstruction(current); } } + + return kBuildSsaSuccess; } ArenaVector* SsaBuilder::GetLocalsFor(HBasicBlock* block) { @@ -591,6 +655,8 @@ HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { * phi with a floating point / reference type. */ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { + DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one."; + // We place the floating point /reference phi next to this phi. HInstruction* next = phi->GetNext(); if (next != nullptr @@ -606,35 +672,50 @@ HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive: ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { - // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, - // but the type propagation phase will fix it. + // Copy the inputs. Note that the graph may not be correctly typed + // by doing this copy, but the type propagation phase will fix it. new_phi->SetRawInputAt(i, phi->InputAt(i)); } phi->GetBlock()->InsertPhiAfter(new_phi, phi); + DCHECK(new_phi->IsLive()); return new_phi; } else { + // An existing equivalent was found. If it is dead, conflict was previously + // identified and we return nullptr instead. HPhi* next_phi = next->AsPhi(); DCHECK_EQ(next_phi->GetType(), type); - if (next_phi->IsDead()) { - // TODO(dbrazdil): Remove this SetLive (we should not need to revive phis) - // once we stop running MarkDeadPhis before PrimitiveTypePropagation. This - // cannot revive undefined loop header phis because they cannot have uses. - DCHECK(!IsUndefinedLoopHeaderPhi(next_phi)); - next_phi->SetLive(); + return next_phi->IsLive() ? next_phi : nullptr; + } +} + +HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { + DCHECK(Primitive::IsIntegralType(aget->GetType())); + + if (!Primitive::IsIntOrLongType(aget->GetType())) { + // Cannot type boolean, char, byte, short to float/double. + return nullptr; + } + + DCHECK(ContainsElement(ambiguous_agets_, aget)); + if (agets_fixed_) { + // This used to be an ambiguous ArrayGet but its type has been resolved to + // int/long. Requesting a float/double equivalent should lead to a conflict. + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(IsArrayGetOnIntegralArray(aget)); } - return next_phi; + return nullptr; + } else { + // This is an ambiguous ArrayGet which has not been resolved yet. Return an + // equivalent float/double instruction to use until it is resolved. + HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); + return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; } } -HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, - HInstruction* value, - Primitive::Type type) { +HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { if (value->IsArrayGet()) { - // The verifier has checked that values in arrays cannot be used for both - // floating point and non-floating point operations. It is therefore safe to just - // change the type of the operation. - value->AsArrayGet()->SetType(type); - return value; + return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); } else if (value->IsLongConstant()) { return GetDoubleEquivalent(value->AsLongConstant()); } else if (value->IsIntConstant()) { @@ -642,12 +723,7 @@ HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, } else if (value->IsPhi()) { return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); } else { - // For other instructions, we assume the verifier has checked that the dex format is correctly - // typed and the value in a dex register will not be used for both floating point and - // non-floating point operations. So the only reason an instruction would want a floating - // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. - DCHECK(user->IsPhi()) << "is actually " << user->DebugName() << " (" << user->GetId() << ")"; - return value; + return nullptr; } } @@ -662,15 +738,17 @@ HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { } void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { + Primitive::Type load_type = load->GetType(); HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()]; // If the operation requests a specific type, we make sure its input is of that type. - if (load->GetType() != value->GetType()) { - if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { - value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); - } else if (load->GetType() == Primitive::kPrimNot) { + if (load_type != value->GetType()) { + if (load_type == Primitive::kPrimFloat || load_type == Primitive::kPrimDouble) { + value = GetFloatOrDoubleEquivalent(value, load_type); + } else if (load_type == Primitive::kPrimNot) { value = GetReferenceTypeEquivalent(value); } } + load->ReplaceWith(value); load->GetBlock()->RemoveInstruction(load); } @@ -760,4 +838,13 @@ void SsaBuilder::VisitTemporary(HTemporary* temp) { temp->GetBlock()->RemoveInstruction(temp); } +void SsaBuilder::VisitArrayGet(HArrayGet* aget) { + Primitive::Type type = aget->GetType(); + DCHECK(!Primitive::IsFloatingPointType(type)); + if (Primitive::IsIntOrLongType(type)) { + ambiguous_agets_.push_back(aget); + } + VisitInstruction(aget); +} + } // namespace art diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index dcce5e4c2..ed6f5cab5 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -49,17 +49,20 @@ static constexpr int kDefaultNumberOfLoops = 2; */ class SsaBuilder : public HGraphVisitor { public: - explicit SsaBuilder(HGraph* graph) + explicit SsaBuilder(HGraph* graph, StackHandleScopeCollection* handles) : HGraphVisitor(graph), + handles_(handles), + agets_fixed_(false), current_locals_(nullptr), loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), + ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), locals_for_(graph->GetBlocks().size(), ArenaVector(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { loop_headers_.reserve(kDefaultNumberOfLoops); } - void BuildSsa(); + BuildSsaResult BuildSsa(); // Returns locals vector for `block`. If it is a catch block, the vector will be // prepopulated with catch phis for vregs which are defined in `current_locals_`. @@ -71,23 +74,38 @@ class SsaBuilder : public HGraphVisitor { void VisitStoreLocal(HStoreLocal* store); void VisitInstruction(HInstruction* instruction); void VisitTemporary(HTemporary* instruction); - - static HInstruction* GetFloatOrDoubleEquivalent(HInstruction* user, - HInstruction* instruction, - Primitive::Type type); - - static HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); + void VisitArrayGet(HArrayGet* aget); static constexpr const char* kSsaBuilderPassName = "ssa_builder"; private: void SetLoopHeaderPhiInputs(); + void FixEnvironmentPhis(); void FixNullConstantType(); void EquivalentPhisCleanup(); + void RunPrimitiveTypePropagation(); + + // Attempts to resolve types of aget and aget-wide instructions from reference + // type information on the input array. Returns false if the type of the array + // is unknown. + bool FixAmbiguousArrayGets(); + + bool TypeInputsOfPhi(HPhi* phi, ArenaVector* worklist); + bool UpdatePrimitiveType(HPhi* phi, ArenaVector* worklist); + void ProcessPrimitiveTypePropagationWorklist(ArenaVector* worklist); - static HFloatConstant* GetFloatEquivalent(HIntConstant* constant); - static HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); - static HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); + HInstruction* GetFloatOrDoubleEquivalent(HInstruction* instruction, Primitive::Type type); + HInstruction* GetReferenceTypeEquivalent(HInstruction* instruction); + + HFloatConstant* GetFloatEquivalent(HIntConstant* constant); + HDoubleConstant* GetDoubleEquivalent(HLongConstant* constant); + HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); + HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget); + + StackHandleScopeCollection* const handles_; + + // True if types of ambiguous ArrayGets have been resolved. + bool agets_fixed_; // Locals for the current block being visited. ArenaVector* current_locals_; @@ -96,6 +114,8 @@ class SsaBuilder : public HGraphVisitor { // over these blocks to set the inputs of their phis. ArenaVector loop_headers_; + ArenaVector ambiguous_agets_; + // HEnvironment for each block. ArenaVector> locals_for_; diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc index a3219dcc3..63aba88c2 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -40,15 +40,17 @@ void SsaDeadPhiElimination::MarkDeadPhis() { continue; } - bool has_non_phi_use = false; - for (HUseIterator use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { - if (!use_it.Current()->GetUser()->IsPhi()) { - has_non_phi_use = true; - break; + bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses()); + if (!keep_alive) { + for (HUseIterator use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { + if (!use_it.Current()->GetUser()->IsPhi()) { + keep_alive = true; + break; + } } } - if (has_non_phi_use) { + if (keep_alive) { worklist_.push_back(phi); } else { phi->SetDead(); @@ -94,8 +96,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() { for (HUseIterator use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { HInstruction* user = use_it.Current()->GetUser(); - DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); - DCHECK(user->AsPhi()->IsDead()) << user->GetId(); + DCHECK(user->IsLoopHeaderPhi()); + DCHECK(user->AsPhi()->IsDead()); } } // Remove the phi from use lists of its inputs. diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc index 024278f4b..d2885a8fd 100644 --- a/compiler/optimizing/ssa_test.cc +++ b/compiler/optimizing/ssa_test.cc @@ -28,6 +28,8 @@ namespace art { +class SsaTest : public CommonCompilerTest {}; + class SsaPrettyPrinter : public HPrettyPrinter { public: explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {} @@ -83,11 +85,10 @@ static void TestCode(const uint16_t* data, const char* expected) { bool graph_built = builder.BuildGraph(*item); ASSERT_TRUE(graph_built); - graph->BuildDominatorTree(); + TransformToSsa(graph); // Suspend checks implementation may change in the future, and this test relies // on how instructions are ordered. RemoveSuspendChecks(graph); - graph->TransformToSsa(); ReNumberInstructions(graph); // Test that phis had their type set. @@ -103,7 +104,7 @@ static void TestCode(const uint16_t* data, const char* expected) { ASSERT_STREQ(expected, printer.str().c_str()); } -TEST(SsaTest, CFG1) { +TEST_F(SsaTest, CFG1) { // Test that we get rid of loads and stores. const char* expected = "BasicBlock 0, succ: 1\n" @@ -131,7 +132,7 @@ TEST(SsaTest, CFG1) { TestCode(data, expected); } -TEST(SsaTest, CFG2) { +TEST_F(SsaTest, CFG2) { // Test that we create a phi for the join block of an if control flow instruction // when there is only code in the else branch. const char* expected = @@ -162,7 +163,7 @@ TEST(SsaTest, CFG2) { TestCode(data, expected); } -TEST(SsaTest, CFG3) { +TEST_F(SsaTest, CFG3) { // Test that we create a phi for the join block of an if control flow instruction // when both branches update a local. const char* expected = @@ -195,7 +196,7 @@ TEST(SsaTest, CFG3) { TestCode(data, expected); } -TEST(SsaTest, Loop1) { +TEST_F(SsaTest, Loop1) { // Test that we create a phi for an initialized local at entry of a loop. const char* expected = "BasicBlock 0, succ: 1\n" @@ -228,7 +229,7 @@ TEST(SsaTest, Loop1) { TestCode(data, expected); } -TEST(SsaTest, Loop2) { +TEST_F(SsaTest, Loop2) { // Simple loop with one preheader and one back edge. const char* expected = "BasicBlock 0, succ: 1\n" @@ -258,7 +259,7 @@ TEST(SsaTest, Loop2) { TestCode(data, expected); } -TEST(SsaTest, Loop3) { +TEST_F(SsaTest, Loop3) { // Test that a local not yet defined at the entry of a loop is handled properly. const char* expected = "BasicBlock 0, succ: 1\n" @@ -290,7 +291,7 @@ TEST(SsaTest, Loop3) { TestCode(data, expected); } -TEST(SsaTest, Loop4) { +TEST_F(SsaTest, Loop4) { // Make sure we support a preheader of a loop not being the first predecessor // in the predecessor list of the header. const char* expected = @@ -325,7 +326,7 @@ TEST(SsaTest, Loop4) { TestCode(data, expected); } -TEST(SsaTest, Loop5) { +TEST_F(SsaTest, Loop5) { // Make sure we create a preheader of a loop when a header originally has two // incoming blocks and one back edge. const char* expected = @@ -367,7 +368,7 @@ TEST(SsaTest, Loop5) { TestCode(data, expected); } -TEST(SsaTest, Loop6) { +TEST_F(SsaTest, Loop6) { // Test a loop with one preheader and two back edges (e.g. continue). const char* expected = "BasicBlock 0, succ: 1\n" @@ -406,7 +407,7 @@ TEST(SsaTest, Loop6) { TestCode(data, expected); } -TEST(SsaTest, Loop7) { +TEST_F(SsaTest, Loop7) { // Test a loop with one preheader, one back edge, and two exit edges (e.g. break). const char* expected = "BasicBlock 0, succ: 1\n" @@ -448,7 +449,7 @@ TEST(SsaTest, Loop7) { TestCode(data, expected); } -TEST(SsaTest, DeadLocal) { +TEST_F(SsaTest, DeadLocal) { // Test that we correctly handle a local not being used. const char* expected = "BasicBlock 0, succ: 1\n" @@ -466,7 +467,7 @@ TEST(SsaTest, DeadLocal) { TestCode(data, expected); } -TEST(SsaTest, LocalInIf) { +TEST_F(SsaTest, LocalInIf) { // Test that we do not create a phi in the join block when one predecessor // does not update the local. const char* expected = @@ -496,7 +497,7 @@ TEST(SsaTest, LocalInIf) { TestCode(data, expected); } -TEST(SsaTest, MultiplePredecessors) { +TEST_F(SsaTest, MultiplePredecessors) { // Test that we do not create a phi when one predecessor // does not update the local. const char* expected = diff --git a/test/444-checker-nce/src/Main.java b/test/444-checker-nce/src/Main.java index 32122e4dc..865355ce9 100644 --- a/test/444-checker-nce/src/Main.java +++ b/test/444-checker-nce/src/Main.java @@ -16,11 +16,11 @@ public class Main { - /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier (before) /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.keepTest(Main) instruction_simplifier (after) /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect public Main keepTest(Main m) { @@ -31,7 +31,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.thisTest() instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.thisTest() instruction_simplifier (after) /// CHECK-NOT: NullCheck /// CHECK: InvokeStaticOrDirect public Main thisTest() { @@ -45,7 +45,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: InvokeStaticOrDirect - /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.newInstanceRemoveTest() instruction_simplifier (after) /// CHECK-NOT: NullCheck public Main newInstanceRemoveTest() { Main m = new Main(); @@ -57,7 +57,7 @@ public class Main { /// CHECK: NullCheck /// CHECK: ArrayGet - /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.newArrayRemoveTest() instruction_simplifier (after) /// CHECK: NewArray /// CHECK-NOT: NullCheck /// CHECK: ArrayGet @@ -66,11 +66,11 @@ public class Main { return ms[0]; } - /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier (before) /// CHECK: NewInstance /// CHECK: NullCheck - /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.ifRemoveTest(boolean) instruction_simplifier (after) /// CHECK: NewInstance /// CHECK-NOT: NullCheck public Main ifRemoveTest(boolean flag) { @@ -83,11 +83,11 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier (before) /// CHECK: NewInstance /// CHECK: NullCheck - /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.ifKeepTest(boolean) instruction_simplifier (after) /// CHECK: NewInstance /// CHECK: NullCheck public Main ifKeepTest(boolean flag) { @@ -98,10 +98,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.forRemoveTest(int) instruction_simplifier (after) /// CHECK-NOT: NullCheck public Main forRemoveTest(int count) { Main a = new Main(); @@ -114,10 +114,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.forKeepTest(int) instruction_simplifier (after) /// CHECK: NullCheck public Main forKeepTest(int count) { Main a = new Main(); @@ -132,10 +132,10 @@ public class Main { return m.g(); } - /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.phiFlowRemoveTest(int) instruction_simplifier (after) /// CHECK-NOT: NullCheck public Main phiFlowRemoveTest(int count) { Main a = new Main(); @@ -154,10 +154,10 @@ public class Main { return n.g(); } - /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.phiFlowKeepTest(int) instruction_simplifier (after) /// CHECK: NullCheck public Main phiFlowKeepTest(int count) { Main a = new Main(); @@ -181,7 +181,7 @@ public class Main { /// CHECK-START: Main Main.scopeRemoveTest(int, Main) ssa_builder (after) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.scopeRemoveTest(int, Main) instruction_simplifier (after) /// CHECK-NOT: NullCheck public Main scopeRemoveTest(int count, Main a) { Main m = null; @@ -196,10 +196,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.scopeKeepTest(int, Main) instruction_simplifier (after) /// CHECK: NullCheck public Main scopeKeepTest(int count, Main a) { Main m = new Main(); @@ -214,10 +214,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.scopeIfNotNullRemove(Main) instruction_simplifier (after) /// CHECK-NOT: NullCheck public Main scopeIfNotNullRemove(Main m) { if (m != null) { @@ -226,10 +226,10 @@ public class Main { return m; } - /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier_after_types (before) + /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier (before) /// CHECK: NullCheck - /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier_after_types (after) + /// CHECK-START: Main Main.scopeIfKeep(Main) instruction_simplifier (after) /// CHECK: NullCheck public Main scopeIfKeep(Main m) { if (m == null) { @@ -258,11 +258,11 @@ public class Main { class ListElement { private ListElement next; - /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (before) + /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier (before) /// CHECK: NullCheck /// CHECK: NullCheck - /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier_after_types (after) + /// CHECK-START: boolean ListElement.isShorter(ListElement, ListElement) instruction_simplifier (after) /// CHECK-NOT: NullCheck static boolean isShorter(ListElement x, ListElement y) { ListElement xTail = x; diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java index f1f80caff..fd4dd5ecb 100644 --- a/test/450-checker-types/src/Main.java +++ b/test/450-checker-types/src/Main.java @@ -72,49 +72,49 @@ final class FinalException extends Exception {} public class Main { - /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testSimpleRemove() { Super s = new SubclassA(); ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier (after) /// CHECK: CheckCast public void testSimpleKeep(Super s) { ((SubclassA)s).$noinline$f(); } - /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (before) + /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (after) + /// CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public String testClassRemove() { Object s = SubclassA.class; return ((Class)s).getName(); } - /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (before) + /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (after) + /// CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier (after) /// CHECK: CheckCast public String testClassKeep() { Object s = SubclassA.class; return ((SubclassA)s).$noinline$h(); } - /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testIfRemove(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testIfRemove(int x) { Super s; @@ -126,10 +126,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testIfKeep(int) instruction_simplifier (after) /// CHECK: CheckCast public void testIfKeep(int x) { Super s; @@ -141,10 +141,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testForRemove(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testForRemove(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testForRemove(int x) { Super s = new SubclassA(); @@ -156,10 +156,10 @@ public class Main { ((SubclassA)s).$noinline$g(); } - /// CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testForKeep(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testForKeep(int) instruction_simplifier (after) /// CHECK: CheckCast public void testForKeep(int x) { Super s = new SubclassA(); @@ -171,10 +171,10 @@ public class Main { ((SubclassC)s).$noinline$g(); } - /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier (after) /// CHECK: CheckCast public void testPhiFromCall(int i) { Object x; @@ -186,11 +186,12 @@ public class Main { ((SubclassC)x).$noinline$g(); } - /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier (before) /// CHECK: CheckCast /// CHECK: CheckCast + /// CHECK-NOT: CheckCast - /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOf(Object o) { if (o instanceof SubclassC) { @@ -201,11 +202,101 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (before) + public static boolean $inline$InstanceofSubclassB(Object o) { return o instanceof SubclassB; } + public static boolean $inline$InstanceofSubclassC(Object o) { return o instanceof SubclassC; } + + /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) ssa_builder (after) + /// CHECK-DAG: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: NotEqual [<>,<>] + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: Equal [<>,<>] + + /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (before) + /// CHECK: CheckCast + /// CHECK: CheckCast + /// CHECK-NOT: CheckCast + + /// CHECK-START: void Main.testInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (after) + /// CHECK-NOT: CheckCast + public void testInstanceOf_NotInlined(Object o) { + if ((o instanceof SubclassC) == true) { + ((SubclassC)o).$noinline$g(); + } + if ((o instanceof SubclassB) != false) { + ((SubclassB)o).$noinline$g(); + } + } + + /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) ssa_builder (after) + /// CHECK-DAG: <> IntConstant 0 + /// CHECK-DAG: <> IntConstant 1 + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: Equal [<>,<>] + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: NotEqual [<>,<>] + + /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (before) + /// CHECK: CheckCast + /// CHECK: CheckCast + /// CHECK-NOT: CheckCast + + /// CHECK-START: void Main.testNotInstanceOf_NotInlined(java.lang.Object) instruction_simplifier (after) + /// CHECK-NOT: CheckCast + public void testNotInstanceOf_NotInlined(Object o) { + if ((o instanceof SubclassC) != true) { + // Empty branch to flip the condition. + } else { + ((SubclassC)o).$noinline$g(); + } + if ((o instanceof SubclassB) == false) { + // Empty branch to flip the condition. + } else { + ((SubclassB)o).$noinline$g(); + } + } + + /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) inliner (after) + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: If [<>] + + /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (before) + /// CHECK: CheckCast + /// CHECK-NOT: CheckCast + + /// CHECK-START: void Main.testInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (after) + /// CHECK-NOT: CheckCast + public void testInstanceOf_Inlined(Object o) { + if (!$inline$InstanceofSubclassC(o)) { + // Empty branch to flip the condition. + } else { + ((SubclassC)o).$noinline$g(); + } + } + + /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) inliner (after) + /// CHECK-DAG: <> InstanceOf + /// CHECK-DAG: <> BooleanNot [<>] + /// CHECK-DAG: If [<>] + + /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (before) + /// CHECK: CheckCast + /// CHECK-NOT: CheckCast + + /// CHECK-START: void Main.testNotInstanceOf_Inlined(java.lang.Object) instruction_simplifier_after_bce (after) + /// CHECK-NOT: CheckCast + public void testNotInstanceOf_Inlined(Object o) { + if ($inline$InstanceofSubclassC(o)) { + ((SubclassC)o).$noinline$g(); + } + } + + /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier (before) /// CHECK: CheckCast /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier (after) /// CHECK: CheckCast /// CHECK: CheckCast public void testInstanceOfKeep(Object o) { @@ -217,11 +308,11 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier (before) /// CHECK: CheckCast /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfNested(Object o) { if (o instanceof SubclassC) { @@ -233,10 +324,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhi(int i) { Object o; @@ -251,10 +342,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfInFor(int n) { Object o = new SubclassA(); @@ -268,10 +359,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfSubclass() { Object o = new SubclassA(); @@ -280,10 +371,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhiSubclass(int i) { Object o; @@ -298,10 +389,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfWithPhiTop(int i) { Object o; @@ -316,10 +407,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfSubclassInFor(int n) { Object o = new SubclassA(); @@ -333,10 +424,10 @@ public class Main { } } - /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceOfTopInFor(int n) { Object o = new SubclassA(); @@ -361,10 +452,10 @@ public class Main { public SubclassA a = new SubclassA(); public static SubclassA b = new SubclassA(); - /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInstanceFieldGetSimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInstanceFieldGetSimpleRemove() { Main m = new Main(); @@ -372,10 +463,10 @@ public class Main { ((SubclassA)a).$noinline$g(); } - /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testStaticFieldGetSimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testStaticFieldGetSimpleRemove() { Super b = Main.b; @@ -384,36 +475,36 @@ public class Main { public SubclassA $noinline$getSubclass() { throw new RuntimeException(); } - /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testArraySimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testArraySimpleRemove() { Super[] b = new SubclassA[10]; SubclassA[] c = (SubclassA[])b; } - /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testInvokeSimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testInvokeSimpleRemove() { Super b = $noinline$getSubclass(); ((SubclassA)b).$noinline$g(); } - /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier_after_types (before) + /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier (before) /// CHECK: CheckCast - /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier_after_types (after) + /// CHECK-START: void Main.testArrayGetSimpleRemove() instruction_simplifier (after) /// CHECK-NOT: CheckCast public void testArrayGetSimpleRemove() { Super[] a = new SubclassA[10]; ((SubclassA)a[0]).$noinline$g(); } - /// CHECK-START: int Main.testLoadExceptionInCatchNonExact(int, int) reference_type_propagation (after) + /// CHECK-START: int Main.testLoadExceptionInCatchNonExact(int, int) ssa_builder (after) /// CHECK: LoadException klass:java.lang.ArithmeticException can_be_null:false exact:false public int testLoadExceptionInCatchNonExact(int x, int y) { try { @@ -423,7 +514,7 @@ public class Main { } } - /// CHECK-START: int Main.testLoadExceptionInCatchExact(int) reference_type_propagation (after) + /// CHECK-START: int Main.testLoadExceptionInCatchExact(int) ssa_builder (after) /// CHECK: LoadException klass:FinalException can_be_null:false exact:true public int testLoadExceptionInCatchExact(int x) { try { @@ -437,7 +528,7 @@ public class Main { } } - /// CHECK-START: int Main.testLoadExceptionInCatchAll(int, int) reference_type_propagation (after) + /// CHECK-START: int Main.testLoadExceptionInCatchAll(int, int) ssa_builder (after) /// CHECK: LoadException klass:java.lang.Throwable can_be_null:false exact:false public int testLoadExceptionInCatchAll(int x, int y) { try { @@ -458,7 +549,7 @@ public class Main { return genericFinal.get(); } - /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after) + /// CHECK-START: SubclassC Main.inlineGenerics() ssa_builder (after) /// CHECK: <> InvokeStaticOrDirect klass:SubclassC exact:false /// CHECK-NEXT: Return [<>] @@ -470,7 +561,7 @@ public class Main { return c; } - /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after) + /// CHECK-START: Final Main.inlineGenericsFinal() ssa_builder (after) /// CHECK: <> InvokeStaticOrDirect klass:Final exact:true /// CHECK-NEXT: Return [<>] @@ -512,7 +603,7 @@ public class Main { return new SubclassA(); } - /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation (after) + /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) ssa_builder (after) /// CHECK: <> Phi klass:Super /// CHECK: NullCheck [<>] klass:Super @@ -534,7 +625,7 @@ public class Main { /// CHECK: CheckCast [<>,<>] /// CHECK: BoundType [<>] can_be_null:true - /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier (after) /// CHECK: <> ParameterValue /// CHECK: <> ParameterValue /// CHECK: <> LoadClass @@ -546,7 +637,7 @@ public class Main { } - /// CHECK-START: void Main.argumentCheck(Super, double, SubclassA, Final) reference_type_propagation (after) + /// CHECK-START: void Main.argumentCheck(Super, double, SubclassA, Final) ssa_builder (after) /// CHECK: ParameterValue klass:Main can_be_null:false exact:false /// CHECK: ParameterValue klass:Super can_be_null:true exact:false /// CHECK: ParameterValue @@ -562,7 +653,7 @@ public class Main { private int mainField = 0; - /// CHECK-START: SuperInterface Main.getWiderType(boolean, Interface, OtherInterface) reference_type_propagation (after) + /// CHECK-START: SuperInterface Main.getWiderType(boolean, Interface, OtherInterface) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: Return [<>] private SuperInterface getWiderType(boolean cond, Interface a, OtherInterface b) { @@ -618,7 +709,7 @@ public class Main { getSuper(); } - /// CHECK-START: void Main.testLoopPhiWithNullFirstInput(boolean) reference_type_propagation (after) + /// CHECK-START: void Main.testLoopPhiWithNullFirstInput(boolean) ssa_builder (after) /// CHECK-DAG: <> NullConstant /// CHECK-DAG: <> NewInstance klass:Main exact:true /// CHECK-DAG: <> Phi [<>,<>,<
>] klass:Main exact:true @@ -631,7 +722,7 @@ public class Main { } } - /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) reference_type_propagation (after) + /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after) /// CHECK-DAG: <> NullConstant /// CHECK-DAG: <> Phi [<>,<>,<>] klass:java.lang.Object exact:false /// CHECK-DAG: <> Phi [<>,<>,<>] klass:java.lang.Object exact:false @@ -647,7 +738,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() reference_type_propagation (after) + /// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() ssa_builder (after) /// CHECK-DAG: <> NullConstant /// CHECK-DAG: <> Phi [<>,<>] klass:java.lang.Object[] exact:true /// CHECK-DAG: <> NewArray klass:java.lang.Object[] exact:true diff --git a/test/477-checker-bound-type/src/Main.java b/test/477-checker-bound-type/src/Main.java index c87370240..0f65e4467 100644 --- a/test/477-checker-bound-type/src/Main.java +++ b/test/477-checker-bound-type/src/Main.java @@ -17,7 +17,7 @@ public class Main { - /// CHECK-START: java.lang.Object Main.boundTypeForIf(java.lang.Object) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.boundTypeForIf(java.lang.Object) ssa_builder (after) /// CHECK: BoundType public static Object boundTypeForIf(Object a) { if (a != null) { @@ -27,7 +27,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.boundTypeForInstanceOf(java.lang.Object) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.boundTypeForInstanceOf(java.lang.Object) ssa_builder (after) /// CHECK: BoundType public static Object boundTypeForInstanceOf(Object a) { if (a instanceof Main) { @@ -37,7 +37,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.noBoundTypeForIf(java.lang.Object) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.noBoundTypeForIf(java.lang.Object) ssa_builder (after) /// CHECK-NOT: BoundType public static Object noBoundTypeForIf(Object a) { if (a == null) { @@ -47,7 +47,7 @@ public class Main { } } - /// CHECK-START: java.lang.Object Main.noBoundTypeForInstanceOf(java.lang.Object) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.noBoundTypeForInstanceOf(java.lang.Object) ssa_builder (after) /// CHECK-NOT: BoundType public static Object noBoundTypeForInstanceOf(Object a) { if (a instanceof Main) { diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java index 98251e4af..ced3e50d4 100644 --- a/test/530-checker-lse/src/Main.java +++ b/test/530-checker-lse/src/Main.java @@ -453,16 +453,14 @@ public class Main { } /// CHECK-START: float Main.test19(float[], float[]) load_store_elimination (before) - /// CHECK: <> ArrayGet - /// CHECK: ArraySet - /// CHECK: <> ArrayGet + /// CHECK: {{f\d+}} ArrayGet + /// CHECK: {{f\d+}} ArrayGet /// CHECK-START: float Main.test19(float[], float[]) load_store_elimination (after) - /// CHECK: <> ArrayGet - /// CHECK: ArraySet - /// CHECK: <> ArrayGet + /// CHECK: {{f\d+}} ArrayGet + /// CHECK-NOT: {{f\d+}} ArrayGet - // I/F, J/D aliasing should keep the load/store. + // I/F, J/D aliasing should not happen any more and LSE should eliminate the load. static float test19(float[] fa1, float[] fa2) { fa1[0] = fa2[0]; return fa1[0]; diff --git a/test/540-checker-rtp-bug/src/Main.java b/test/540-checker-rtp-bug/src/Main.java index e9f16c04d..9a9f0b604 100644 --- a/test/540-checker-rtp-bug/src/Main.java +++ b/test/540-checker-rtp-bug/src/Main.java @@ -21,14 +21,14 @@ final class Final { } public class Main { - /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) reference_type_propagation (after) + /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: <> LoadClass /// CHECK: CheckCast [<>,<>] /// CHECK: <> BoundType [<>] klass:Final /// CHECK: Return [<>] - /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) instruction_simplifier_after_types (after) + /// CHECK-START: Final Main.testKeepCheckCast(java.lang.Object, boolean) instruction_simplifier (after) /// CHECK: <> Phi /// CHECK: <> LoadClass /// CHECK: CheckCast [<>,<>] @@ -43,7 +43,7 @@ public class Main { return (Final) x; } - /// CHECK-START: void Main.testKeepInstanceOf(java.lang.Object, boolean) reference_type_propagation (after) + /// CHECK-START: void Main.testKeepInstanceOf(java.lang.Object, boolean) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: <> LoadClass /// CHECK: InstanceOf [<>,<>] @@ -65,7 +65,7 @@ public class Main { } } - /// CHECK-START: java.lang.String Main.testNoInline(java.lang.Object, boolean) reference_type_propagation (after) + /// CHECK-START: java.lang.String Main.testNoInline(java.lang.Object, boolean) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: <> NullCheck [<>] /// CHECK: <> InvokeVirtual [<>] method_name:java.lang.Object.toString diff --git a/test/549-checker-types-merge/src/Main.java b/test/549-checker-types-merge/src/Main.java index dc27f1042..917073b1c 100644 --- a/test/549-checker-types-merge/src/Main.java +++ b/test/549-checker-types-merge/src/Main.java @@ -38,14 +38,14 @@ class ClassImplementsInterfaceA extends ClassSuper implements InterfaceA {} public class Main { - /// CHECK-START: java.lang.Object Main.testMergeNullContant(boolean) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeNullContant(boolean) ssa_builder (after) /// CHECK: <> Phi klass:Main /// CHECK: Return [<>] private Object testMergeNullContant(boolean cond) { return cond ? null : new Main(); } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassExtendsB) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassExtendsB) ssa_builder (after) /// CHECK: <> Phi klass:ClassSuper /// CHECK: Return [<>] private Object testMergeClasses(boolean cond, ClassExtendsA a, ClassExtendsB b) { @@ -53,7 +53,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassExtendsA, ClassSuper) ssa_builder (after) /// CHECK: <> Phi klass:ClassSuper /// CHECK: Return [<>] private Object testMergeClasses(boolean cond, ClassExtendsA a, ClassSuper b) { @@ -61,7 +61,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassSuper, ClassSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassSuper, ClassSuper) ssa_builder (after) /// CHECK: <> Phi klass:ClassSuper /// CHECK: Return [<>] private Object testMergeClasses(boolean cond, ClassSuper a, ClassSuper b) { @@ -69,7 +69,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassOtherSuper, ClassSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClasses(boolean, ClassOtherSuper, ClassSuper) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: Return [<>] private Object testMergeClasses(boolean cond, ClassOtherSuper a, ClassSuper b) { @@ -77,7 +77,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassImplementsInterfaceA, InterfaceSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassImplementsInterfaceA, InterfaceSuper) ssa_builder (after) /// CHECK: <> Phi klass:InterfaceSuper /// CHECK: Return [<>] private Object testMergeClassWithInterface(boolean cond, ClassImplementsInterfaceA a, InterfaceSuper b) { @@ -85,7 +85,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassSuper, InterfaceSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeClassWithInterface(boolean, ClassSuper, InterfaceSuper) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: Return [<>] private Object testMergeClassWithInterface(boolean cond, ClassSuper a, InterfaceSuper b) { @@ -93,7 +93,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceSuper) ssa_builder (after) /// CHECK: <> Phi klass:InterfaceSuper /// CHECK: Return [<>] private Object testMergeInterfaces(boolean cond, InterfaceExtendsA a, InterfaceSuper b) { @@ -101,7 +101,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceSuper) ssa_builder (after) /// CHECK: <> Phi klass:InterfaceSuper /// CHECK: Return [<>] private Object testMergeInterfaces(boolean cond, InterfaceSuper a, InterfaceSuper b) { @@ -109,7 +109,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceExtendsB) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceExtendsA, InterfaceExtendsB) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: Return [<>] private Object testMergeInterfaces(boolean cond, InterfaceExtendsA a, InterfaceExtendsB b) { @@ -117,7 +117,7 @@ public class Main { return cond ? a : b; } - /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceOtherSuper) reference_type_propagation (after) + /// CHECK-START: java.lang.Object Main.testMergeInterfaces(boolean, InterfaceSuper, InterfaceOtherSuper) ssa_builder (after) /// CHECK: <> Phi klass:java.lang.Object /// CHECK: Return [<>] private Object testMergeInterfaces(boolean cond, InterfaceSuper a, InterfaceOtherSuper b) { diff --git a/test/552-checker-primitive-typeprop/expected.txt b/test/552-checker-primitive-typeprop/expected.txt new file mode 100644 index 000000000..e69de29bb diff --git a/test/552-checker-primitive-typeprop/info.txt b/test/552-checker-primitive-typeprop/info.txt new file mode 100644 index 000000000..9d6905691 --- /dev/null +++ b/test/552-checker-primitive-typeprop/info.txt @@ -0,0 +1,2 @@ +Test that phis with environment uses which can be properly typed are kept +in --debuggable mode. \ No newline at end of file diff --git a/test/552-checker-primitive-typeprop/smali/ArrayGet.smali b/test/552-checker-primitive-typeprop/smali/ArrayGet.smali new file mode 100644 index 000000000..042fa0c80 --- /dev/null +++ b/test/552-checker-primitive-typeprop/smali/ArrayGet.smali @@ -0,0 +1,245 @@ +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +.class public LArrayGet; +.super Ljava/lang/Object; + + +# Test phi with fixed-type ArrayGet as an input and a matching second input. +# The phi should be typed accordingly. + +## CHECK-START: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFixedType(float[], float) ssa_builder (after) +## CHECK-DAG: <> ParameterValue +## CHECK-DAG: <> ArrayGet +## CHECK-DAG: {{f\d+}} Phi [<>,<>] reg:0 +.method public static matchingFixedType([FF)V + .registers 8 + + const v0, 0x0 + const v1, 0x1 + + aget v0, p0, v0 # read value + add-float v2, v0, v1 # float use fixes type + + float-to-int v2, p1 + if-eqz v2, :after + move v0, p1 + :after + # v0 = Phi [ArrayGet, Arg1] => float + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + + +# Test phi with fixed-type ArrayGet as an input and a conflicting second input. +# The phi should be eliminated due to the conflict. + +## CHECK-START: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType(float[], int) ssa_builder (after) +## CHECK-NOT: Phi +.method public static conflictingFixedType([FI)V + .registers 8 + + const v0, 0x0 + const v1, 0x1 + + aget v0, p0, v0 # read value + add-float v2, v0, v1 # float use fixes type + + if-eqz p1, :after + move v0, p1 + :after + # v0 = Phi [ArrayGet, Arg1] => conflict + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + + +# Same test as the one above, only this time tests that type of ArrayGet is not +# changed. + +## CHECK-START: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFixedType2(int[], float) ssa_builder (after) +## CHECK: {{i\d+}} ArrayGet +.method public static conflictingFixedType2([IF)V + .registers 8 + + const v0, 0x0 + const v1, 0x1 + + aget v0, p0, v0 # read value + add-int v2, v0, v1 # int use fixes type + + float-to-int v2, p1 + if-eqz v2, :after + move v0, p1 + :after + # v0 = Phi [ArrayGet, Arg1] => conflict + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + + +# Test phi with free-type ArrayGet as an input and a matching second input. +# The phi should be typed accordingly. + +## CHECK-START: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.matchingFreeType(float[], float) ssa_builder (after) +## CHECK-DAG: <> ParameterValue +## CHECK-DAG: <> ArrayGet +## CHECK-DAG: ArraySet [{{l\d+}},{{i\d+}},<>] +## CHECK-DAG: {{f\d+}} Phi [<>,<>] reg:0 +.method public static matchingFreeType([FF)V + .registers 8 + + const v0, 0x0 + const v1, 0x1 + + aget v0, p0, v0 # read value, should be float but has no typed use + aput v0, p0, v1 # aput does not disambiguate the type + + float-to-int v2, p1 + if-eqz v2, :after + move v0, p1 + :after + # v0 = Phi [ArrayGet, Arg1] => float + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + + +# Test phi with free-type ArrayGet as an input and a conflicting second input. +# The phi will be kept and typed according to the second input despite the +# conflict. + +## CHECK-START: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after) +## CHECK-NOT: Phi + +## CHECK-START-DEBUGGABLE: void ArrayGet.conflictingFreeType(int[], float) ssa_builder (after) +## CHECK-NOT: Phi + +.method public static conflictingFreeType([IF)V + .registers 8 + + const v0, 0x0 + const v1, 0x1 + + aget v0, p0, v0 # read value, should be int but has no typed use + aput v0, p0, v1 + + float-to-int v2, p1 + if-eqz v2, :after + move v0, p1 + :after + # v0 = Phi [ArrayGet, Arg1] => float + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + + +# Test that real use of ArrayGet is propagated through phis. The following test +# case uses ArrayGet indirectly through two phis. It also creates an unused +# conflicting phi which should not be preserved. + +## CHECK-START: void ArrayGet.conflictingPhiUses(int[], float, boolean, boolean, boolean) ssa_builder (after) +## CHECK: InvokeStaticOrDirect env:[[{{i\d+}},{{i\d+}},_,{{i\d+}},{{.*}} + +.method public static conflictingPhiUses([IFZZZ)V + .registers 10 + + const v0, 0x0 + + # Create v1 = Phi [0x0, int ArrayGet] + move v1, v0 + if-eqz p2, :else1 + aget v1, p0, v0 + :else1 + + # Create v2 = Phi [v1, float] + move v2, v1 + if-eqz p3, :else2 + move v2, p1 + :else2 + + # Create v3 = Phi [v1, int] + move v3, v1 + if-eqz p4, :else3 + move v3, v0 + :else3 + + # Use v3 as int. + add-int/lit8 v4, v3, 0x2a + + # Create env uses. + invoke-static {}, Ljava/lang/System;->nanoTime()J + + return-void +.end method + +# Test that the right ArrayGet equivalent is always selected. The following test +# case uses ArrayGet as float through one phi and as an indeterminate type through +# another. The situation needs to be resolved so that only one instruction +# remains. + +## CHECK-START: void ArrayGet.typedVsUntypedPhiUse(float[], float, boolean, boolean) ssa_builder (after) +## CHECK: {{f\d+}} ArrayGet + +## CHECK-START: void ArrayGet.typedVsUntypedPhiUse(float[], float, boolean, boolean) ssa_builder (after) +## CHECK-NOT: {{i\d+}} ArrayGet + +.method public static typedVsUntypedPhiUse([FFZZ)V + .registers 10 + + const v0, 0x0 + + # v1 = float ArrayGet + aget v1, p0, v0 + + # Create v2 = Phi [v1, 0.0f] + move v2, v1 + if-eqz p2, :else1 + move v2, v0 + :else1 + + # Use v2 as float + cmpl-float v2, v2, p1 + + # Create v3 = Phi [v1, 0.0f] + move v3, v1 + if-eqz p3, :else2 + move v3, v0 + :else2 + + # Use v3 without a determinate type. + aput v3, p0, v0 + + return-void +.end method diff --git a/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali b/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali new file mode 100644 index 000000000..395feaaf6 --- /dev/null +++ b/test/552-checker-primitive-typeprop/smali/SsaBuilder.smali @@ -0,0 +1,52 @@ +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +.class public LSsaBuilder; +.super Ljava/lang/Object; + +# Check that a dead phi with a live equivalent is replaced in an environment. The +# following test case throws an exception and uses v0 afterwards. However, v0 +# contains a phi that is interpreted as int for the environment, and as float for +# instruction use. SsaBuilder must substitute the int variant before removing it, +# otherwise running the code with an array short enough to throw will crash at +# runtime because v0 is undefined. + +## CHECK-START: int SsaBuilder.environmentPhi(boolean, int[]) ssa_builder (after) +## CHECK-DAG: <> FloatConstant 0 +## CHECK-DAG: <> FloatConstant 2 +## CHECK-DAG: <> Phi [<>,<>] +## CHECK-DAG: BoundsCheck env:[[<>,{{i\d+}},{{z\d+}},{{l\d+}}]] + +.method public static environmentPhi(Z[I)I + .registers 4 + + const v0, 0x0 + if-eqz p0, :else + const v0, 0x40000000 + :else + # v0 = phi that can be both int and float + + :try_start + const v1, 0x3 + aput v1, p1, v1 + const v0, 0x1 # generate catch phi for v0 + const v1, 0x4 + aput v1, p1, v1 + :try_end + .catchall {:try_start .. :try_end} :use_as_float + + :use_as_float + float-to-int v0, v0 + return v0 +.end method \ No newline at end of file diff --git a/test/552-checker-primitive-typeprop/smali/TypePropagation.smali b/test/552-checker-primitive-typeprop/smali/TypePropagation.smali new file mode 100644 index 000000000..58682a192 --- /dev/null +++ b/test/552-checker-primitive-typeprop/smali/TypePropagation.smali @@ -0,0 +1,136 @@ +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +.class public LTypePropagation; +.super Ljava/lang/Object; + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDeadPhi(boolean, boolean, int, float, float) ssa_builder (after) +## CHECK-NOT: Phi +.method public static mergeDeadPhi(ZZIFF)V + .registers 8 + + if-eqz p0, :after1 + move p2, p3 + :after1 + # p2 = merge(int,float) = conflict + + if-eqz p1, :after2 + move p2, p4 + :after2 + # p2 = merge(conflict,float) = conflict + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeSameType(boolean, int, int) ssa_builder (after) +## CHECK: {{i\d+}} Phi +## CHECK-NOT: Phi +.method public static mergeSameType(ZII)V + .registers 8 + if-eqz p0, :after + move p1, p2 + :after + # p1 = merge(int,int) = int + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeVoidInput(boolean, boolean, int, int) ssa_builder (after) +## CHECK: {{i\d+}} Phi +## CHECK: {{i\d+}} Phi +## CHECK-NOT: Phi +.method public static mergeVoidInput(ZZII)V + .registers 8 + :loop + # p2 = void (loop phi) => p2 = merge(int,int) = int + if-eqz p0, :after + move p2, p3 + :after + # p2 = merge(void,int) = int + if-eqz p1, :loop + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeDifferentSize(boolean, int, long) ssa_builder (after) +## CHECK-NOT: Phi +.method public static mergeDifferentSize(ZIJ)V + .registers 8 + if-eqz p0, :after + move-wide p1, p2 + :after + # p1 = merge(int,long) = conflict + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeRefFloat(boolean, float, java.lang.Object) ssa_builder (after) +## CHECK-NOT: Phi +.method public static mergeRefFloat(ZFLjava/lang/Object;)V + .registers 8 + if-eqz p0, :after + move-object p1, p2 + :after + # p1 = merge(float,reference) = conflict + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Success(boolean, float) ssa_builder (after) +## CHECK: {{f\d+}} Phi +## CHECK-NOT: Phi +.method public static mergeIntFloat_Success(ZF)V + .registers 8 + if-eqz p0, :after + const/4 p1, 0x0 + :after + # p1 = merge(float,0x0) = float + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.mergeIntFloat_Fail(boolean, int, float) ssa_builder (after) +## CHECK-NOT: Phi +.method public static mergeIntFloat_Fail(ZIF)V + .registers 8 + if-eqz p0, :after + move p1, p2 + :after + # p1 = merge(int,float) = conflict + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method + +## CHECK-START-DEBUGGABLE: void TypePropagation.updateAllUsersOnConflict(boolean, boolean, int, float, int) ssa_builder (after) +## CHECK-NOT: Phi +.method public static updateAllUsersOnConflict(ZZIFI)V + .registers 8 + + :loop1 + # loop phis for all args + # p2 = merge(int,float) = float? => conflict + move p2, p3 + if-eqz p0, :loop1 + + :loop2 + # loop phis for all args + # requests float equivalent of p4 phi in loop1 => conflict + # propagates conflict to loop2's phis + move p2, p4 + if-eqz p1, :loop2 + + invoke-static {}, Ljava/lang/System;->nanoTime()J # create an env use + return-void +.end method diff --git a/test/552-checker-primitive-typeprop/src/Main.java b/test/552-checker-primitive-typeprop/src/Main.java new file mode 100644 index 000000000..fe2343e48 --- /dev/null +++ b/test/552-checker-primitive-typeprop/src/Main.java @@ -0,0 +1,43 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +import java.lang.reflect.Method; + +public class Main { + + // Workaround for b/18051191. + class InnerClass {} + + private static void assertEquals(int expected, int actual) { + if (expected != actual) { + throw new Error("Wrong result, expected=" + expected + ", actual=" + actual); + } + } + + public static void main(String[] args) throws Exception { + Class c = Class.forName("SsaBuilder"); + Method m = c.getMethod("environmentPhi", new Class[] { boolean.class, int[].class }); + + int[] array = new int[3]; + int result; + + result = (Integer) m.invoke(null, new Object[] { true, array } ); + assertEquals(2, result); + + result = (Integer) m.invoke(null, new Object[] { false, array } ); + assertEquals(0, result); + } +} -- 2.11.0