diff options
| -rw-r--r-- | compiler/optimizing/graph_visualizer.cc | 40 | ||||
| -rw-r--r-- | compiler/optimizing/inliner.cc | 41 | ||||
| -rw-r--r-- | compiler/optimizing/instruction_simplifier.cc | 13 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.cc | 41 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 128 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 3 | ||||
| -rw-r--r-- | compiler/optimizing/reference_type_propagation.cc | 448 | ||||
| -rw-r--r-- | compiler/optimizing/reference_type_propagation.h | 11 | ||||
| -rw-r--r-- | runtime/mirror/class-inl.h | 27 | ||||
| -rw-r--r-- | runtime/mirror/class.h | 26 | ||||
| -rw-r--r-- | test/441-checker-inliner/src/Main.java | 33 | ||||
| -rw-r--r-- | test/450-checker-types/src/Main.java | 108 |
12 files changed, 703 insertions, 216 deletions
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index afea40316c..069a7a460b 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -386,6 +386,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { StartAttributeStream("recursive") << std::boolalpha << invoke->IsRecursive() << std::noboolalpha; + StartAttributeStream("intrinsic") << invoke->GetIntrinsic(); } void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE { @@ -396,6 +397,11 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { return strcmp(pass_name_, name) == 0; } + bool IsReferenceTypePropagationPass() { + return strstr(pass_name_, ReferenceTypePropagation::kReferenceTypePropagationPassName) + != nullptr; + } + void PrintInstruction(HInstruction* instruction) { output_ << instruction->DebugName(); if (instruction->InputCount() > 0) { @@ -459,27 +465,19 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { } else { StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId(); } - } else if (IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName) - && is_after_pass_) { - if (instruction->GetType() == Primitive::kPrimNot) { - if (instruction->IsLoadClass()) { - ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI(); - ScopedObjectAccess soa(Thread::Current()); - if (info.GetTypeHandle().GetReference() != nullptr) { - StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get()); - } else { - StartAttributeStream("klass") << "unresolved"; - } - } else { - ReferenceTypeInfo info = instruction->GetReferenceTypeInfo(); - if (info.IsTop()) { - StartAttributeStream("klass") << "java.lang.Object"; - } else { - ScopedObjectAccess soa(Thread::Current()); - StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get()); - } - StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha; - } + } else if (IsReferenceTypePropagationPass() + && (instruction->GetType() == Primitive::kPrimNot)) { + ReferenceTypeInfo info = instruction->IsLoadClass() + ? instruction->AsLoadClass()->GetLoadedClassRTI() + : instruction->GetReferenceTypeInfo(); + ScopedObjectAccess soa(Thread::Current()); + if (info.IsValid()) { + StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get()); + StartAttributeStream("can_be_null") + << std::boolalpha << instruction->CanBeNull() << std::noboolalpha; + StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha; + } else { + DCHECK(!is_after_pass_) << "Type info should be valid after reference type propagation"; } } if (disasm_info_ != nullptr) { diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index c185b5887b..cfb1868bff 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -24,6 +24,7 @@ #include "driver/compiler_driver-inl.h" #include "driver/dex_compilation_unit.h" #include "instruction_simplifier.h" +#include "intrinsics.h" #include "mirror/class_loader.h" #include "mirror/dex_cache.h" #include "nodes.h" @@ -109,10 +110,8 @@ static ArtMethod* FindVirtualOrInterfaceTarget(HInvoke* invoke, ArtMethod* resol receiver = receiver->InputAt(0); } ReferenceTypeInfo info = receiver->GetReferenceTypeInfo(); - if (info.IsTop()) { - // We have no information on the receiver. - return nullptr; - } else if (!info.IsExact()) { + DCHECK(info.IsValid()) << "Invalid RTI for " << receiver->DebugName(); + if (!info.IsExact()) { // We currently only support inlining with known receivers. // TODO: Remove this check, we should be able to inline final methods // on unknown receivers. @@ -273,11 +272,11 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, const DexFile::CodeItem* code_item = resolved_method->GetCodeItem(); const DexFile& callee_dex_file = *resolved_method->GetDexFile(); uint32_t method_index = resolved_method->GetDexMethodIndex(); - + ClassLinker* class_linker = caller_compilation_unit_.GetClassLinker(); DexCompilationUnit dex_compilation_unit( nullptr, caller_compilation_unit_.GetClassLoader(), - caller_compilation_unit_.GetClassLinker(), + class_linker, *resolved_method->GetDexFile(), code_item, resolved_method->GetDeclaringClass()->GetDexClassDefIndex(), @@ -358,8 +357,10 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, HConstantFolding fold(callee_graph); ReferenceTypePropagation type_propagation(callee_graph, handles_); InstructionSimplifier simplify(callee_graph, stats_); + IntrinsicsRecognizer intrinsics(callee_graph, compiler_driver_); HOptimization* optimizations[] = { + &intrinsics, &dce, &fold, &type_propagation, @@ -450,7 +451,33 @@ bool HInliner::TryBuildAndInline(ArtMethod* resolved_method, } } - callee_graph->InlineInto(graph_, invoke_instruction); + HInstruction* return_replacement = callee_graph->InlineInto(graph_, invoke_instruction); + + // 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 */)); + } + + 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()); + ReferenceTypeInfo::TypeHandle return_handle = + handles_->NewHandle(resolved_method->GetReturnType()); + return_replacement->SetReferenceTypeInfo(ReferenceTypeInfo::Create( + return_handle, return_handle->IsFinal() /* is_exact */)); + } + } return true; } diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc index b30b6c7bae..d3911456fb 100644 --- a/compiler/optimizing/instruction_simplifier.cc +++ b/compiler/optimizing/instruction_simplifier.cc @@ -195,16 +195,17 @@ bool InstructionSimplifierVisitor::IsDominatedByInputNullCheck(HInstruction* ins // Returns whether doing a type test between the class of `object` against `klass` has // a statically known outcome. The result of the test is stored in `outcome`. static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) { - if (!klass->IsResolved()) { - // If the class couldn't be resolve it's not safe to compare against it. It's - // default type would be Top which might be wider that the actual class type - // and thus producing wrong results. + DCHECK(!object->IsNullConstant()) << "Null constants should be special cased"; + ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); + ScopedObjectAccess soa(Thread::Current()); + if (!obj_rti.IsValid()) { + // We run the simplifier before the reference type propagation so type info might not be + // available. return false; } - ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI(); - ScopedObjectAccess soa(Thread::Current()); + DCHECK(class_rti.IsValid() && class_rti.IsExact()); if (class_rti.IsSupertypeOf(obj_rti)) { *outcome = true; return true; diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 519fa005a6..188cb49f6a 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1485,7 +1485,7 @@ void HGraph::DeleteDeadBlock(HBasicBlock* block) { blocks_.Put(block->GetBlockId(), nullptr); } -void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { +HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { DCHECK(HasExitBlock()) << "Unimplemented scenario"; // Update the environments in this graph to have the invoke's environment // as parent. @@ -1510,6 +1510,7 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { outer_graph->SetHasBoundsChecks(true); } + HInstruction* return_value = nullptr; if (GetBlocks().Size() == 3) { // Simple case of an entry block, a body block, and an exit block. // Put the body block's instruction into `invoke`'s block. @@ -1524,7 +1525,8 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { // Replace the invoke with the return value of the inlined graph. if (last->IsReturn()) { - invoke->ReplaceWith(last->InputAt(0)); + return_value = last->InputAt(0); + invoke->ReplaceWith(return_value); } else { DCHECK(last->IsReturnVoid()); } @@ -1546,7 +1548,6 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { // Update all predecessors of the exit block (now the `to` block) // to not `HReturn` but `HGoto` instead. - HInstruction* return_value = nullptr; bool returns_void = to->GetPredecessors().Get(0)->GetLastInstruction()->IsReturnVoid(); if (to->GetPredecessors().Size() == 1) { HBasicBlock* predecessor = to->GetPredecessors().Get(0); @@ -1680,6 +1681,8 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { // Finally remove the invoke from the caller. invoke->GetBlock()->RemoveInstruction(invoke); + + return return_value; } /* @@ -1757,11 +1760,39 @@ void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { } } +void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) { + if (kIsDebugBuild) { + DCHECK_EQ(GetType(), Primitive::kPrimNot); + ScopedObjectAccess soa(Thread::Current()); + DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName(); + if (IsBoundType()) { + // Having the test here spares us from making the method virtual just for + // the sake of a DCHECK. + ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound(); + DCHECK(upper_bound_rti.IsSupertypeOf(rti)) + << " upper_bound_rti: " << upper_bound_rti + << " rti: " << rti; + DCHECK(!upper_bound_rti.GetTypeHandle()->IsFinal() || rti.IsExact()); + } + } + reference_type_info_ = rti; +} + +ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {} + +ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact) + : type_handle_(type_handle), is_exact_(is_exact) { + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(IsValidHandle(type_handle)); + } +} + std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { ScopedObjectAccess soa(Thread::Current()); os << "[" - << " is_top=" << rhs.IsTop() - << " type=" << (rhs.IsTop() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) + << " is_valid=" << rhs.IsValid() + << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) << " is_exact=" << rhs.IsExact() << " ]"; return os; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 7f446d4cf6..003900c8a6 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -210,7 +210,9 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { void ComputeTryBlockInformation(); // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. - void InlineInto(HGraph* outer_graph, HInvoke* invoke); + // Returns the instruction used to replace the invoke expression or null if the + // invoke is for a void method. + HInstruction* InlineInto(HGraph* outer_graph, HInvoke* invoke); // Need to add a couple of blocks to test if the loop body is entered and // put deoptimization instructions, etc. @@ -306,7 +308,12 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { // already, it is created and inserted into the graph. This method is only for // integral types. HConstant* GetConstant(Primitive::Type type, int64_t value); + + // TODO: This is problematic for the consistency of reference type propagation + // because it can be created anytime after the pass and thus it will be left + // with an invalid type. HNullConstant* GetNullConstant(); + HIntConstant* GetIntConstant(int32_t value) { return CreateConstant(value, &cached_int_constants_); } @@ -1460,79 +1467,64 @@ class ReferenceTypeInfo : ValueObject { public: typedef Handle<mirror::Class> TypeHandle; - static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) - SHARED_REQUIRES(Locks::mutator_lock_) { - if (type_handle->IsObjectClass()) { - // Override the type handle to be consistent with the case when we get to - // Top but don't have the Object class available. It avoids having to guess - // what value the type_handle has when it's Top. - return ReferenceTypeInfo(TypeHandle(), is_exact, true); - } else { - return ReferenceTypeInfo(type_handle, is_exact, false); - } + 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 CreateTop(bool is_exact) { - return ReferenceTypeInfo(TypeHandle(), is_exact, true); + 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 IsTop() const { return is_top_; } + + bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK(IsValid()); + return GetTypeHandle()->IsObjectClass(); + } bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) { - return !IsTop() && GetTypeHandle()->IsInterface(); + DCHECK(IsValid()); + return GetTypeHandle()->IsInterface(); } Handle<mirror::Class> GetTypeHandle() const { return type_handle_; } bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(Locks::mutator_lock_) { - if (IsTop()) { - // Top (equivalent for java.lang.Object) is supertype of anything. - return true; - } - if (rti.IsTop()) { - // If we get here `this` is not Top() so it can't be a supertype. - return false; - } + DCHECK(IsValid()); + DCHECK(rti.IsValid()); return 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 - // (e.g. tops are equal but they can be the result of a merge). + // (because the type can be the result of a merge). bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) { - if (IsExact() != rti.IsExact()) { - return false; - } - if (IsTop() && rti.IsTop()) { - // `Top` means java.lang.Object, so the types are equivalent. + if (!IsValid() && !rti.IsValid()) { + // Invalid types are equal. return true; } - if (IsTop() || rti.IsTop()) { - // If only one is top or object than they are not equivalent. - // NB: We need this extra check because the type_handle of `Top` is invalid - // and we cannot inspect its reference. + if (!IsValid() || !rti.IsValid()) { + // One is valid, the other not. return false; } - - // Finally check the types. - return GetTypeHandle().Get() == rti.GetTypeHandle().Get(); + return IsExact() == rti.IsExact() + && GetTypeHandle().Get() == rti.GetTypeHandle().Get(); } private: - ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {} - ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top) - : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {} + 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_; - // A true value here means that the object type should be java.lang.Object. - // We don't have access to the corresponding mirror object every time so this - // flag acts as a substitute. When true, the TypeHandle refers to a null - // pointer and should not be used. - bool is_top_; }; std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs); @@ -1550,7 +1542,7 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> { live_interval_(nullptr), lifetime_position_(kNoLifetime), side_effects_(side_effects), - reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {} + reference_type_info_(ReferenceTypeInfo::CreateInvalid()) {} virtual ~HInstruction() {} @@ -1596,6 +1588,7 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> { // Does not apply for all instructions, but having this at top level greatly // simplifies the null check elimination. + // TODO: Consider merging can_be_null into ReferenceTypeInfo. virtual bool CanBeNull() const { DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types"; return true; @@ -1606,10 +1599,7 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> { return false; } - void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) { - DCHECK_EQ(GetType(), Primitive::kPrimNot); - reference_type_info_ = reference_type_info; - } + void SetReferenceTypeInfo(ReferenceTypeInfo rti); ReferenceTypeInfo GetReferenceTypeInfo() const { DCHECK_EQ(GetType(), Primitive::kPrimNot); @@ -3904,7 +3894,7 @@ class HLoadClass : public HExpression<1> { is_referrers_class_(is_referrers_class), dex_pc_(dex_pc), generate_clinit_check_(false), - loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) { + loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) { SetRawInputAt(0, current_method); } @@ -3955,10 +3945,6 @@ class HLoadClass : public HExpression<1> { loaded_class_rti_ = rti; } - bool IsResolved() { - return loaded_class_rti_.IsExact(); - } - const DexFile& GetDexFile() { return dex_file_; } bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; } @@ -4201,27 +4187,43 @@ class HInstanceOf : public HExpression<2> { class HBoundType : public HExpression<1> { public: - HBoundType(HInstruction* input, ReferenceTypeInfo bound_type) + // Constructs an HBoundType with the given upper_bound. + // Ensures that the upper_bound is valid. + HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null) : HExpression(Primitive::kPrimNot, SideEffects::None()), - bound_type_(bound_type) { + upper_bound_(upper_bound), + upper_can_be_null_(upper_can_be_null), + can_be_null_(upper_can_be_null) { DCHECK_EQ(input->GetType(), Primitive::kPrimNot); SetRawInputAt(0, input); + SetReferenceTypeInfo(upper_bound_); } - const ReferenceTypeInfo& GetBoundType() const { return bound_type_; } + // GetUpper* should only be used in reference type propagation. + const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; } + bool GetUpperCanBeNull() const { return upper_can_be_null_; } - bool CanBeNull() const OVERRIDE { - // `null instanceof ClassX` always return false so we can't be null. - return false; + void SetCanBeNull(bool can_be_null) { + DCHECK(upper_can_be_null_ || !can_be_null); + can_be_null_ = can_be_null; } + bool CanBeNull() const OVERRIDE { return can_be_null_; } + DECLARE_INSTRUCTION(BoundType); private: // Encodes the most upper class that this instruction can have. In other words - // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()). - // It is used to bound the type in cases like `if (x instanceof ClassX) {}` - const ReferenceTypeInfo bound_type_; + // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()). + // It is used to bound the type in cases like: + // if (x instanceof ClassX) { + // // uper_bound_ will be ClassX + // } + const ReferenceTypeInfo upper_bound_; + // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this + // is false then can_be_null_ cannot be true). + const bool upper_can_be_null_; + bool can_be_null_; DISALLOW_COPY_AND_ASSIGN(HBoundType); }; diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 1c0123e188..3f5e8e054f 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -399,7 +399,8 @@ static void RunOptimizations(HGraph* graph, InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_after_bce"); ReferenceTypePropagation* type_propagation2 = - new (arena) ReferenceTypePropagation(graph, handles); + new (arena) ReferenceTypePropagation( + graph, handles, "reference_type_propagation_after_inlining"); InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier( graph, stats, "instruction_simplifier_before_codegen"); diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc index 68316c2618..f747fc516c 100644 --- a/compiler/optimizing/reference_type_propagation.cc +++ b/compiler/optimizing/reference_type_propagation.cc @@ -25,19 +25,35 @@ namespace art { class RTPVisitor : public HGraphDelegateVisitor { public: - RTPVisitor(HGraph* graph, StackHandleScopeCollection* handles) + RTPVisitor(HGraph* graph, + StackHandleScopeCollection* handles, + GrowableArray<HInstruction*>* worklist, + ReferenceTypeInfo::TypeHandle object_class_handle, + ReferenceTypeInfo::TypeHandle class_class_handle, + ReferenceTypeInfo::TypeHandle string_class_handle) : HGraphDelegateVisitor(graph), - handles_(handles) {} + handles_(handles), + object_class_handle_(object_class_handle), + class_class_handle_(class_class_handle), + string_class_handle_(string_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; + void VisitLoadString(HLoadString* instr) OVERRIDE; void VisitNewArray(HNewArray* instr) OVERRIDE; + void VisitParameterValue(HParameterValue* instr) OVERRIDE; void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info); void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass, bool is_exact); void VisitInstanceFieldGet(HInstanceFieldGet* instr) OVERRIDE; void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE; void VisitInvoke(HInvoke* instr) OVERRIDE; void VisitArrayGet(HArrayGet* instr) OVERRIDE; + void VisitCheckCast(HCheckCast* instr) OVERRIDE; + void VisitNullCheck(HNullCheck* instr) OVERRIDE; + void VisitFakeString(HFakeString* instr) OVERRIDE; void UpdateReferenceTypeInfo(HInstruction* instr, uint16_t type_idx, const DexFile& dex_file, @@ -45,8 +61,33 @@ class RTPVisitor : public HGraphDelegateVisitor { private: StackHandleScopeCollection* handles_; + ReferenceTypeInfo::TypeHandle object_class_handle_; + ReferenceTypeInfo::TypeHandle class_class_handle_; + ReferenceTypeInfo::TypeHandle string_class_handle_; + GrowableArray<HInstruction*>* worklist_; + + static constexpr size_t kDefaultWorklistSize = 8; }; +ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph, + StackHandleScopeCollection* handles, + const char* name) + : HOptimization(graph, name), + handles_(handles), + worklist_(graph->GetArena(), kDefaultWorklistSize) { + ClassLinker* linker = Runtime::Current()->GetClassLinker(); + object_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject)); + string_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangString)); + class_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangClass)); + + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + DCHECK(ReferenceTypeInfo::IsValidHandle(object_class_handle_)); + DCHECK(ReferenceTypeInfo::IsValidHandle(class_class_handle_)); + DCHECK(ReferenceTypeInfo::IsValidHandle(string_class_handle_)); + } +} + void ReferenceTypePropagation::Run() { // To properly propagate type info we need to visit in the dominator-based order. // Reverse post order guarantees a node's dominators are visited first. @@ -55,29 +96,122 @@ void ReferenceTypePropagation::Run() { VisitBasicBlock(it.Current()); } ProcessWorklist(); + + if (kIsDebugBuild) { + // TODO: move this to the graph checker. + ScopedObjectAccess soa(Thread::Current()); + for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + for (HInstructionIterator iti(block->GetInstructions()); !iti.Done(); iti.Advance()) { + HInstruction* instr = iti.Current(); + if (instr->GetType() == Primitive::kPrimNot) { + DCHECK(instr->GetReferenceTypeInfo().IsValid()) + << "Invalid RTI for instruction: " << instr->DebugName(); + if (instr->IsBoundType()) { + DCHECK(instr->AsBoundType()->GetUpperBound().IsValid()); + } else if (instr->IsLoadClass()) { + DCHECK(instr->AsLoadClass()->GetReferenceTypeInfo().IsExact()); + DCHECK(instr->AsLoadClass()->GetLoadedClassRTI().IsValid()); + } else if (instr->IsNullCheck()) { + DCHECK(instr->GetReferenceTypeInfo().IsEqual(instr->InputAt(0)->GetReferenceTypeInfo())) + << "NullCheck " << instr->GetReferenceTypeInfo() + << "Input(0) " << instr->InputAt(0)->GetReferenceTypeInfo(); + } + } + } + } + } } void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) { - // TODO: handle other instructions that give type info - // (array accesses) + RTPVisitor visitor(graph_, + handles_, + &worklist_, + object_class_handle_, + class_class_handle_, + string_class_handle_); + // Handle Phis first as there might be instructions in the same block who depend on them. + for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + VisitPhi(it.Current()->AsPhi()); + } - RTPVisitor visitor(graph_, handles_); - // Initialize exact types first for faster convergence. + // Handle instructions. for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { HInstruction* instr = it.Current(); instr->Accept(&visitor); } - // Handle Phis. - for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { - VisitPhi(it.Current()->AsPhi()); - } - // Add extra nodes to bound types. BoundTypeForIfNotNull(block); BoundTypeForIfInstanceOf(block); } +// Create a bound type for the given object narrowing the type as much as possible. +// The BoundType upper values for the super type and can_be_null will be taken from +// load_class.GetLoadedClassRTI() and upper_can_be_null. +static HBoundType* CreateBoundType(ArenaAllocator* arena, + HInstruction* obj, + HLoadClass* load_class, + bool upper_can_be_null) + SHARED_REQUIRES(Locks::mutator_lock_) { + ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); + ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); + HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null); + // Narrow the type as much as possible. + if (class_rti.GetTypeHandle()->IsFinal()) { + bound_type->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true)); + } else if (obj_rti.IsValid() && class_rti.IsSupertypeOf(obj_rti)) { + bound_type->SetReferenceTypeInfo(obj_rti); + } else { + bound_type->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); + } + return bound_type; +} + +// Check if we should create a bound type for the given object at the specified +// position. Because of inlining and the fact we run RTP more than once and we +// might have a HBoundType already. If we do, we should not create a new one. +// In this case we also assert that there are no other uses of the object (except +// the bound type) dominated by the specified dominator_instr or dominator_block. +static bool ShouldCreateBoundType(HInstruction* position, + HInstruction* obj, + ReferenceTypeInfo upper_bound, + HInstruction* dominator_instr, + HBasicBlock* dominator_block) + SHARED_REQUIRES(Locks::mutator_lock_) { + // If the position where we should insert the bound type is not already a + // a bound type then we need to create one. + if (position == nullptr || !position->IsBoundType()) { + return true; + } + + HBoundType* existing_bound_type = position->AsBoundType(); + if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) { + if (kIsDebugBuild) { + // Check that the existing HBoundType dominates all the uses. + for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { + HInstruction* user = it.Current()->GetUser(); + if (dominator_instr != nullptr) { + DCHECK(!dominator_instr->StrictlyDominates(user) + || user == existing_bound_type + || existing_bound_type->StrictlyDominates(user)); + } else if (dominator_block != nullptr) { + DCHECK(!dominator_block->Dominates(user->GetBlock()) + || user == existing_bound_type + || existing_bound_type->StrictlyDominates(user)); + } + } + } + } else { + // TODO: if the current bound type is a refinement we could update the + // existing_bound_type with the a new upper limit. However, we also need to + // update its users and have access to the work list. + } + return false; +} + void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { HIf* ifInstruction = block->GetLastInstruction()->AsIf(); if (ifInstruction == nullptr) { @@ -116,8 +250,23 @@ void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) { HInstruction* user = it.Current()->GetUser(); if (notNullBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { - bound_type = new (graph_->GetArena()) HBoundType(obj, ReferenceTypeInfo::CreateTop(false)); - notNullBlock->InsertInstructionBefore(bound_type, notNullBlock->GetFirstInstruction()); + ScopedObjectAccess soa(Thread::Current()); + HInstruction* insert_point = notNullBlock->GetFirstInstruction(); + ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create( + object_class_handle_, /* is_exact */ true); + if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) { + bound_type = new (graph_->GetArena()) HBoundType( + obj, object_rti, /* bound_can_be_null */ false); + if (obj->GetReferenceTypeInfo().IsValid()) { + bound_type->SetReferenceTypeInfo(obj->GetReferenceTypeInfo()); + } + notNullBlock->InsertInstructionBefore(bound_type, insert_point); + } else { + // We already have a bound type on the position we would need to insert + // the new one. The existing bound type should dominate all the users + // (dchecked) so there's no need to continue. + break; + } } user->ReplaceInput(bound_type, it.Current()->GetIndex()); } @@ -171,25 +320,23 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { HInstruction* user = it.Current()->GetUser(); if (instanceOfTrueBlock->Dominates(user->GetBlock())) { if (bound_type == nullptr) { + ScopedObjectAccess soa(Thread::Current()); HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass(); - - ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); - bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti); - - // Narrow the type as much as possible. - { - ScopedObjectAccess soa(Thread::Current()); - if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) { - bound_type->SetReferenceTypeInfo(obj_rti); - } else { - bound_type->SetReferenceTypeInfo( - ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); - } + HInstruction* insert_point = instanceOfTrueBlock->GetFirstInstruction(); + if (ShouldCreateBoundType(insert_point, obj, class_rti, nullptr, instanceOfTrueBlock)) { + bound_type = CreateBoundType( + graph_->GetArena(), + obj, + load_class, + false /* InstanceOf ensures the object is not null. */); + instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point); + } else { + // We already have a bound type on the position we would need to insert + // the new one. The existing bound type should dominate all the users + // (dchecked) so there's no need to continue. + break; } - - instanceOfTrueBlock->InsertInstructionBefore( - bound_type, instanceOfTrueBlock->GetFirstInstruction()); } user->ReplaceInput(bound_type, it.Current()->GetIndex()); } @@ -199,11 +346,32 @@ void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) { void RTPVisitor::SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass, bool is_exact) { - if (klass != nullptr) { + if (instr->IsInvokeStaticOrDirect() && instr->AsInvokeStaticOrDirect()->IsStringInit()) { + // Calls to String.<init> are replaced with a StringFactory. + if (kIsDebugBuild) { + ScopedObjectAccess soa(Thread::Current()); + ClassLinker* cl = Runtime::Current()->GetClassLinker(); + mirror::DexCache* dex_cache = cl->FindDexCache(instr->AsInvoke()->GetDexFile()); + ArtMethod* method = dex_cache->GetResolvedMethod( + instr->AsInvoke()->GetDexMethodIndex(), cl->GetImagePointerSize()); + DCHECK(method != nullptr); + mirror::Class* declaring_class = method->GetDeclaringClass(); + DCHECK(declaring_class != nullptr); + DCHECK(declaring_class->IsStringClass()) + << "Expected String class: " << PrettyDescriptor(declaring_class); + DCHECK(method->IsConstructor()) + << "Expected String.<init>: " << PrettyMethod(method); + } + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true)); + } else if (klass != nullptr) { ScopedObjectAccess soa(Thread::Current()); - MutableHandle<mirror::Class> handle = handles_->NewHandle(klass); + ReferenceTypeInfo::TypeHandle handle = handles_->NewHandle(klass); is_exact = is_exact || klass->IsFinal(); instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact)); + } else { + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false)); } } @@ -219,6 +387,13 @@ 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); } @@ -227,6 +402,13 @@ void RTPVisitor::VisitNewArray(HNewArray* instr) { UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true); } +void RTPVisitor::VisitParameterValue(HParameterValue* instr) { + if (instr->GetType() == Primitive::kPrimNot) { + // TODO: parse the signature and add precise types for the parameters. + SetClassAsTypeInfo(instr, nullptr, /* is_exact */ false); + } +} + void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info) { // The field index is unknown only during tests. @@ -238,10 +420,10 @@ void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr, ClassLinker* cl = Runtime::Current()->GetClassLinker(); mirror::DexCache* dex_cache = cl->FindDexCache(info.GetDexFile()); ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), dex_cache); - if (field != nullptr) { - mirror::Class* klass = field->GetType<false>(); - SetClassAsTypeInfo(instr, klass, /* is_exact */ false); - } + // 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<false>(); + SetClassAsTypeInfo(instr, klass, /* is_exact */ false); } void RTPVisitor::VisitInstanceFieldGet(HInstanceFieldGet* instr) { @@ -258,12 +440,58 @@ void RTPVisitor::VisitLoadClass(HLoadClass* instr) { Runtime::Current()->GetClassLinker()->FindDexCache(instr->GetDexFile()); // Get type from dex cache assuming it was populated by the verifier. mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex()); - if (resolved_class != nullptr) { - Handle<mirror::Class> handle = handles_->NewHandle(resolved_class); - instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true)); + DCHECK(resolved_class != nullptr); + ReferenceTypeInfo::TypeHandle handle = handles_->NewHandle(resolved_class); + instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true)); + instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_class_handle_, /* is_exact */ true)); +} + +void RTPVisitor::VisitClinitCheck(HClinitCheck* instr) { + instr->SetReferenceTypeInfo(instr->InputAt(0)->GetReferenceTypeInfo()); +} + +void RTPVisitor::VisitLoadString(HLoadString* instr) { + instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true)); +} + +void RTPVisitor::VisitNullCheck(HNullCheck* instr) { + ScopedObjectAccess soa(Thread::Current()); + ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); + DCHECK(parent_rti.IsValid()); + instr->SetReferenceTypeInfo(parent_rti); +} + +void RTPVisitor::VisitFakeString(HFakeString* instr) { + instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true)); +} + +void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { + HInstruction* obj = check_cast->InputAt(0); + HBoundType* bound_type = nullptr; + for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) { + HInstruction* user = it.Current()->GetUser(); + if (check_cast->StrictlyDominates(user)) { + if (bound_type == nullptr) { + ScopedObjectAccess soa(Thread::Current()); + HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); + ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); + if (ShouldCreateBoundType(check_cast->GetNext(), obj, class_rti, check_cast, nullptr)) { + bound_type = CreateBoundType( + GetGraph()->GetArena(), + obj, + load_class, + true /* CheckCast succeeds for nulls. */); + check_cast->GetBlock()->InsertInstructionAfter(bound_type, check_cast); + } else { + // We already have a bound type on the position we would need to insert + // the new one. The existing bound type should dominate all the users + // (dchecked) so there's no need to continue. + break; + } + } + user->ReplaceInput(bound_type, it.Current()->GetIndex()); + } } - Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass()); - instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true)); } void ReferenceTypePropagation::VisitPhi(HPhi* phi) { @@ -290,29 +518,54 @@ void ReferenceTypePropagation::VisitPhi(HPhi* phi) { ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a, const ReferenceTypeInfo& b) { + if (!b.IsValid()) { + return a; + } + if (!a.IsValid()) { + return b; + } + bool is_exact = a.IsExact() && b.IsExact(); - bool is_top = a.IsTop() || b.IsTop(); Handle<mirror::Class> type_handle; - if (!is_top) { - if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) { - type_handle = a.GetTypeHandle(); - } else if (a.IsSupertypeOf(b)) { - type_handle = a.GetTypeHandle(); - is_exact = false; - } else if (b.IsSupertypeOf(a)) { - type_handle = b.GetTypeHandle(); - is_exact = false; - } else { - // TODO: Find a common super class. - is_top = true; - is_exact = false; - } + if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) { + type_handle = a.GetTypeHandle(); + } else if (a.IsSupertypeOf(b)) { + type_handle = a.GetTypeHandle(); + is_exact = false; + } else if (b.IsSupertypeOf(a)) { + type_handle = b.GetTypeHandle(); + is_exact = false; + } else { + // TODO: Find the first common super class. + type_handle = object_class_handle_; + is_exact = false; } - return is_top - ? ReferenceTypeInfo::CreateTop(is_exact) - : ReferenceTypeInfo::Create(type_handle, is_exact); + return ReferenceTypeInfo::Create(type_handle, is_exact); +} + +static void UpdateArrayGet(HArrayGet* instr, + StackHandleScopeCollection* handles, + ReferenceTypeInfo::TypeHandle object_class_handle) + SHARED_REQUIRES(Locks::mutator_lock_) { + DCHECK_EQ(Primitive::kPrimNot, instr->GetType()); + + ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); + DCHECK(parent_rti.IsValid()); + + Handle<mirror::Class> handle = parent_rti.GetTypeHandle(); + if (handle->IsObjectArrayClass()) { + ReferenceTypeInfo::TypeHandle component_handle = handles->NewHandle(handle->GetComponentType()); + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(component_handle, /* is_exact */ false)); + } else { + // We don't know what the parent actually is, so we fallback to object. + instr->SetReferenceTypeInfo( + ReferenceTypeInfo::Create(object_class_handle, /* is_exact */ false)); + } + + return; } bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) { @@ -323,6 +576,15 @@ bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) { UpdateBoundType(instr->AsBoundType()); } else if (instr->IsPhi()) { UpdatePhi(instr->AsPhi()); + } else if (instr->IsNullCheck()) { + ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); + if (parent_rti.IsValid()) { + instr->SetReferenceTypeInfo(parent_rti); + } + } else if (instr->IsArrayGet()) { + // TODO: consider if it's worth "looking back" and bounding the input object + // to an array type. + UpdateArrayGet(instr->AsArrayGet(), handles_, object_class_handle_); } else { LOG(FATAL) << "Invalid instruction (should not get here)"; } @@ -340,45 +602,45 @@ void RTPVisitor::VisitInvoke(HInvoke* instr) { mirror::DexCache* dex_cache = cl->FindDexCache(instr->GetDexFile()); ArtMethod* method = dex_cache->GetResolvedMethod( instr->GetDexMethodIndex(), cl->GetImagePointerSize()); - if (method != nullptr) { - mirror::Class* klass = method->GetReturnType(false); - SetClassAsTypeInfo(instr, klass, /* is_exact */ false); - } + mirror::Class* klass = (method == nullptr) ? nullptr : method->GetReturnType(false); + SetClassAsTypeInfo(instr, klass, /* is_exact */ false); } void RTPVisitor::VisitArrayGet(HArrayGet* instr) { if (instr->GetType() != Primitive::kPrimNot) { return; } - - HInstruction* parent = instr->InputAt(0); ScopedObjectAccess soa(Thread::Current()); - Handle<mirror::Class> handle = parent->GetReferenceTypeInfo().GetTypeHandle(); - if (handle.GetReference() != nullptr && handle->IsObjectArrayClass()) { - SetClassAsTypeInfo(instr, handle->GetComponentType(), /* is_exact */ false); + UpdateArrayGet(instr, handles_, object_class_handle_); + if (!instr->GetReferenceTypeInfo().IsValid()) { + worklist_->Add(instr); } } void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) { ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo(); - // Be sure that we don't go over the bounded type. - ReferenceTypeInfo bound_rti = instr->GetBoundType(); - if (!bound_rti.IsSupertypeOf(new_rti)) { - new_rti = bound_rti; + if (!new_rti.IsValid()) { + return; // No new info yet. + } + + // Make sure that we don't go over the bounded type. + ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound(); + if (!upper_bound_rti.IsSupertypeOf(new_rti)) { + new_rti = upper_bound_rti; } instr->SetReferenceTypeInfo(new_rti); } void ReferenceTypePropagation::UpdatePhi(HPhi* instr) { ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo(); - if (new_rti.IsTop() && !new_rti.IsExact()) { - // Early return if we are Top and inexact. + if (new_rti.IsValid() && new_rti.IsObjectClass() && !new_rti.IsExact()) { + // Early return if we are Object and inexact. instr->SetReferenceTypeInfo(new_rti); return; } for (size_t i = 1; i < instr->InputCount(); i++) { new_rti = MergeTypes(new_rti, instr->InputAt(i)->GetReferenceTypeInfo()); - if (new_rti.IsTop()) { + if (new_rti.IsValid() && new_rti.IsObjectClass()) { if (!new_rti.IsExact()) { break; } else { @@ -392,21 +654,31 @@ 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() || instr->IsBoundType()); + DCHECK(instr->IsPhi() + || instr->IsBoundType() + || instr->IsNullCheck() + || instr->IsArrayGet()); - if (!instr->IsPhi()) { + if (!instr->IsPhi() && !instr->IsBoundType()) { return false; } - HPhi* phi = instr->AsPhi(); - bool existing_can_be_null = phi->CanBeNull(); - bool new_can_be_null = false; - for (size_t i = 0; i < phi->InputCount(); i++) { - new_can_be_null |= phi->InputAt(i)->CanBeNull(); + bool existing_can_be_null = instr->CanBeNull(); + if (instr->IsPhi()) { + HPhi* phi = instr->AsPhi(); + bool new_can_be_null = false; + for (size_t i = 0; i < phi->InputCount(); i++) { + if (phi->InputAt(i)->CanBeNull()) { + new_can_be_null = true; + break; + } + } + phi->SetCanBeNull(new_can_be_null); + } else if (instr->IsBoundType()) { + HBoundType* bound_type = instr->AsBoundType(); + bound_type->SetCanBeNull(instr->InputAt(0)->CanBeNull() && bound_type->GetUpperCanBeNull()); } - phi->SetCanBeNull(new_can_be_null); - - return existing_can_be_null != new_can_be_null; + return existing_can_be_null != instr->CanBeNull(); } void ReferenceTypePropagation::ProcessWorklist() { @@ -419,14 +691,18 @@ void ReferenceTypePropagation::ProcessWorklist() { } void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) { - DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) << instruction->GetType(); + DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) + << instruction->DebugName() << ":" << instruction->GetType(); worklist_.Add(instruction); } void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { HInstruction* user = it.Current()->GetUser(); - if (user->IsPhi() || user->IsBoundType()) { + if (user->IsPhi() + || user->IsBoundType() + || user->IsNullCheck() + || (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) { AddToWorklist(user); } } diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h index 11f5ac91ca..14d4a82e9b 100644 --- a/compiler/optimizing/reference_type_propagation.h +++ b/compiler/optimizing/reference_type_propagation.h @@ -30,10 +30,9 @@ namespace art { */ class ReferenceTypePropagation : public HOptimization { public: - ReferenceTypePropagation(HGraph* graph, StackHandleScopeCollection* handles) - : HOptimization(graph, kReferenceTypePropagationPassName), - handles_(handles), - worklist_(graph->GetArena(), kDefaultWorklistSize) {} + ReferenceTypePropagation(HGraph* graph, + StackHandleScopeCollection* handles, + const char* name = kReferenceTypePropagationPassName); void Run() OVERRIDE; @@ -60,6 +59,10 @@ class ReferenceTypePropagation : public HOptimization { GrowableArray<HInstruction*> worklist_; + ReferenceTypeInfo::TypeHandle object_class_handle_; + ReferenceTypeInfo::TypeHandle class_class_handle_; + ReferenceTypeInfo::TypeHandle string_class_handle_; + static constexpr size_t kDefaultWorklistSize = 8; DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation); diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h index 069e346a8d..6568487df9 100644 --- a/runtime/mirror/class-inl.h +++ b/runtime/mirror/class-inl.h @@ -913,6 +913,33 @@ inline void Class::CheckPointerSize(size_t pointer_size) { DCHECK_EQ(pointer_size, Runtime::Current()->GetClassLinker()->GetImagePointerSize()); } +template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption> +inline Class* Class::GetComponentType() { + return GetFieldObject<Class, kVerifyFlags, kReadBarrierOption>(ComponentTypeOffset()); +} + +template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption> +inline bool Class::IsArrayClass() { + return GetComponentType<kVerifyFlags, kReadBarrierOption>() != nullptr; +} + +inline bool Class::IsAssignableFrom(Class* src) { + DCHECK(src != nullptr); + if (this == src) { + // Can always assign to things of the same type. + return true; + } else if (IsObjectClass()) { + // Can assign any reference to java.lang.Object. + return !src->IsPrimitive(); + } else if (IsInterface()) { + return src->Implements(this); + } else if (src->IsArrayClass()) { + return IsAssignableFromArray(src); + } else { + return !src->IsInterface() && src->IsSubClass(this); + } +} + } // namespace mirror } // namespace art diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h index c01a5e8f1a..d95bcd80e5 100644 --- a/runtime/mirror/class.h +++ b/runtime/mirror/class.h @@ -404,9 +404,8 @@ class MANAGED Class FINAL : public Object { template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags, ReadBarrierOption kReadBarrierOption = kWithReadBarrier> - bool IsArrayClass() SHARED_REQUIRES(Locks::mutator_lock_) { - return GetComponentType<kVerifyFlags, kReadBarrierOption>() != nullptr; - } + + bool IsArrayClass() SHARED_REQUIRES(Locks::mutator_lock_); template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags, ReadBarrierOption kReadBarrierOption = kWithReadBarrier> @@ -423,9 +422,7 @@ class MANAGED Class FINAL : public Object { template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags, ReadBarrierOption kReadBarrierOption = kWithReadBarrier> - Class* GetComponentType() SHARED_REQUIRES(Locks::mutator_lock_) { - return GetFieldObject<Class, kVerifyFlags, kReadBarrierOption>(ComponentTypeOffset()); - } + Class* GetComponentType() SHARED_REQUIRES(Locks::mutator_lock_); void SetComponentType(Class* new_component_type) SHARED_REQUIRES(Locks::mutator_lock_) { DCHECK(GetComponentType() == nullptr); @@ -617,22 +614,7 @@ class MANAGED Class FINAL : public Object { // downcast would be necessary. Similarly for interfaces, a class that implements (or an interface // that extends) another can be assigned to its parent, but not vice-versa. All Classes may assign // to themselves. Classes for primitive types may not assign to each other. - ALWAYS_INLINE bool IsAssignableFrom(Class* src) SHARED_REQUIRES(Locks::mutator_lock_) { - DCHECK(src != nullptr); - if (this == src) { - // Can always assign to things of the same type. - return true; - } else if (IsObjectClass()) { - // Can assign any reference to java.lang.Object. - return !src->IsPrimitive(); - } else if (IsInterface()) { - return src->Implements(this); - } else if (src->IsArrayClass()) { - return IsAssignableFromArray(src); - } else { - return !src->IsInterface() && src->IsSubClass(this); - } - } + ALWAYS_INLINE bool IsAssignableFrom(Class* src) SHARED_REQUIRES(Locks::mutator_lock_); ALWAYS_INLINE Class* GetSuperClass() SHARED_REQUIRES(Locks::mutator_lock_); diff --git a/test/441-checker-inliner/src/Main.java b/test/441-checker-inliner/src/Main.java index 4db116a128..c108a900e2 100644 --- a/test/441-checker-inliner/src/Main.java +++ b/test/441-checker-inliner/src/Main.java @@ -157,6 +157,31 @@ public class Main { return x; } + /// CHECK-START: int Main.returnAbs(int) intrinsics_recognition (before) + /// CHECK-DAG: <<Result:i\d+>> InvokeStaticOrDirect + /// CHECK-DAG: Return [<<Result>>] + + /// CHECK-START: int Main.returnAbs(int) intrinsics_recognition (after) + /// CHECK-DAG: <<Result:i\d+>> InvokeStaticOrDirect intrinsic:MathAbsInt + /// CHECK-DAG: Return [<<Result>>] + + private static int returnAbs(int i) { + return Math.abs(i); + } + + /// CHECK-START: int Main.InlinedIntrinsicsAreStillIntrinsic() inliner (before) + /// CHECK-DAG: <<ConstMinus1:i\d+>> IntConstant -1 + /// CHECK-DAG: <<Result:i\d+>> InvokeStaticOrDirect + /// CHECK-DAG: Return [<<Result>>] + + /// CHECK-START: int Main.InlinedIntrinsicsAreStillIntrinsic() inliner (after) + /// CHECK-DAG: <<ConstMinus1:i\d+>> IntConstant -1 + /// CHECK-DAG: <<Result:i\d+>> InvokeStaticOrDirect intrinsic:MathAbsInt + /// CHECK-DAG: Return [<<Result>>] + + public static int InlinedIntrinsicsAreStillIntrinsic() { + return returnAbs(-1); + } private static void returnVoid() { return; @@ -238,5 +263,13 @@ public class Main { if (InlineWithControlFlow(false) != 2) { throw new Error(); } + + if (InlinedIntrinsicsAreStillIntrinsic() != 1) { + throw new Error(); + } + + if (returnAbs(-1) != 1) { + throw new Error(); + } } } diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java index 014f59a506..251a53e456 100644 --- a/test/450-checker-types/src/Main.java +++ b/test/450-checker-types/src/Main.java @@ -14,7 +14,6 @@ * limitations under the License. */ - interface Interface { void $noinline$f(); } @@ -52,6 +51,15 @@ class SubclassB extends Super { } } +class Generic<A> { + private A a = null; + public A get() { + return a; + } +} + +final class Final {} + public class Main { /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before) @@ -395,6 +403,104 @@ public class Main { ((SubclassA)a[0]).$noinline$g(); } + private Generic<SubclassC> genericC = new Generic<SubclassC>(); + private Generic<Final> genericFinal = new Generic<Final>(); + + private SubclassC get() { + return genericC.get(); + } + + private Final getFinal() { + return genericFinal.get(); + } + + /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after) + /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:SubclassC exact:false + /// CHECK-NEXT: Return [<<Invoke>>] + + /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation_after_inlining (after) + /// CHECK: <<BoundType:l\d+>> BoundType klass:SubclassC exact:false + /// CHECK: Return [<<BoundType>>] + private SubclassC inlineGenerics() { + SubclassC c = get(); + return c; + } + + /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after) + /// CHECK: <<Invoke:l\d+>> InvokeStaticOrDirect klass:Final exact:true + /// CHECK-NEXT: Return [<<Invoke>>] + + /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation_after_inlining (after) + /// CHECK: <<BoundType:l\d+>> BoundType klass:Final exact:true + /// CHECK: Return [<<BoundType>>] + private Final inlineGenericsFinal() { + Final f = getFinal(); + return f; + } + + /// CHECK-START: void Main.boundOnlyOnceIfNotNull(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private void boundOnlyOnceIfNotNull(Object o) { + if (o != null) { + o.toString(); + } + } + + /// CHECK-START: void Main.boundOnlyOnceIfInstanceOf(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private void boundOnlyOnceIfInstanceOf(Object o) { + if (o instanceof Main) { + o.toString(); + } + } + + /// CHECK-START: Final Main.boundOnlyOnceCheckCast(Generic) reference_type_propagation_after_inlining (after) + /// CHECK: BoundType + /// CHECK-NOT: BoundType + private Final boundOnlyOnceCheckCast(Generic<Final> o) { + Final f = o.get(); + return f; + } + + private Super getSuper() { + return new SubclassA(); + } + + /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation (after) + /// CHECK: <<Phi:l\d+>> Phi klass:Super + /// CHECK: NullCheck [<<Phi>>] klass:Super + + /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation_after_inlining (after) + /// CHECK: <<Phi:l\d+>> Phi klass:SubclassA + /// CHECK: NullCheck [<<Phi>>] klass:SubclassA + private void updateNodesInTheSameBlockAsPhi(boolean cond) { + Super s = getSuper(); + if (cond) { + s = new SubclassA(); + } + s.$noinline$f(); + } + + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) reference_type_propagation_after_inlining (after) + /// CHECK: <<This:l\d+>> ParameterValue + /// CHECK: <<Param:l\d+>> ParameterValue + /// CHECK: <<Clazz:l\d+>> LoadClass + /// CHECK: CheckCast [<<Param>>,<<Clazz>>] + /// CHECK: BoundType [<<Param>>] can_be_null:true + + /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) instruction_simplifier_after_types (after) + /// CHECK: <<This:l\d+>> ParameterValue + /// CHECK: <<Param:l\d+>> ParameterValue + /// CHECK: <<Clazz:l\d+>> LoadClass + /// CHECK: CheckCast [<<Param>>,<<Clazz>>] + /// CHECK: <<Bound:l\d+>> BoundType [<<Param>>] + /// CHECK: NullCheck [<<Bound>>] + public String checkcastPreserveNullCheck(Object a) { + return ((SubclassA)a).toString(); + } + public static void main(String[] args) { } } |