| /* |
| * 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. |
| */ |
| |
| #ifndef ART_COMPILER_DEX_TYPE_INFERENCE_H_ |
| #define ART_COMPILER_DEX_TYPE_INFERENCE_H_ |
| |
| #include "base/bit_utils.h" |
| #include "base/logging.h" |
| #include "base/arena_object.h" |
| #include "base/scoped_arena_containers.h" |
| |
| namespace art { |
| |
| class ArenaBitVector; |
| class BasicBlock; |
| struct CompilationUnit; |
| class DexFile; |
| class MirFieldInfo; |
| class MirMethodInfo; |
| class MIR; |
| class MIRGraph; |
| |
| /** |
| * @brief Determine the type of SSA registers. |
| * |
| * @details |
| * Because Dalvik's bytecode is not fully typed, we have to do some work to figure |
| * out the sreg type. For some operations it is clear based on the opcode (i.e. |
| * ADD_FLOAT v0, v1, v2), but for others (MOVE), we may never know the "real" type. |
| * |
| * We perform the type inference operation in two phases: |
| * 1. First, we make one pass over all insns in the topological sort order and |
| * extract known type information from all insns for their defs and uses. |
| * 2. Then we repeatedly go through the graph to process insns that can propagate |
| * types from inputs to outputs and vice versa. These insns are just the MOVEs, |
| * AGET/APUTs, IF_ccs and Phis (including pseudo-Phis, see below). |
| * |
| * Since the main purpose is to determine the basic FP/core/reference type, we don't |
| * need to record the precise reference type, we only record the array type to determine |
| * the result types of agets and source type of aputs. |
| * |
| * One complication is the check-cast instruction that effectively defines a new |
| * virtual register that has a different type than the original sreg. We need to |
| * track these virtual sregs and insert pseudo-phis where they merge. |
| * |
| * Another problems is with null references. The same zero constant can be used |
| * as differently typed null and moved around with move-object which would normally |
| * be an ill-formed assignment. So we need to keep track of values that can be null |
| * and values that cannot. |
| * |
| * Note that it's possible to have the same sreg show multiple defined types because dx |
| * treats constants as untyped bit patterns. We disable register promotion in that case. |
| */ |
| class TypeInference : public DeletableArenaObject<kArenaAllocMisc> { |
| public: |
| TypeInference(MIRGraph* mir_graph, ScopedArenaAllocator* alloc); |
| |
| bool Apply(BasicBlock* bb); |
| void Finish(); |
| |
| private: |
| struct Type { |
| static Type Unknown() { |
| return Type(0u); |
| } |
| |
| static Type NonArrayRefType() { |
| return Type(kFlagLowWord | kFlagNarrow | kFlagRef); |
| } |
| |
| static Type ArtMethodType(bool wide) { |
| return Type(kFlagLowWord | kFlagRef | (wide ? kFlagWide : kFlagNarrow)); |
| } |
| |
| static Type ObjectArrayType() { |
| return Type(kFlagNarrow | kFlagRef | kFlagLowWord | |
| (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayRef); |
| } |
| |
| static Type WideArrayType() { |
| // Core or FP unknown. |
| return Type(kFlagNarrow | kFlagRef | kFlagLowWord | |
| (1u << kBitArrayDepthStart) | kFlagArrayWide); |
| } |
| |
| static Type NarrowArrayType() { |
| // Core or FP unknown. |
| return Type(kFlagNarrow | kFlagRef | kFlagLowWord | |
| (1u << kBitArrayDepthStart) | kFlagArrayNarrow); |
| } |
| |
| static Type NarrowCoreArrayType() { |
| return Type(kFlagNarrow | kFlagRef | kFlagLowWord | |
| (1u << kBitArrayDepthStart) | kFlagArrayNarrow | kFlagArrayCore); |
| } |
| |
| static Type UnknownArrayType() { |
| return Type(kFlagNarrow | kFlagRef | kFlagLowWord | (1u << kBitArrayDepthStart)); |
| } |
| |
| static Type ArrayType(uint32_t array_depth, Type nested_type); |
| static Type ArrayTypeFromComponent(Type component_type); |
| static Type ShortyType(char shorty); |
| static Type DexType(const DexFile* dex_file, uint32_t type_idx); |
| |
| bool IsDefined() { |
| return raw_bits_ != 0u; |
| } |
| |
| bool SizeConflict() const { |
| // NOTE: Ignore array element conflicts that don't propagate to direct conflicts. |
| return (Wide() && Narrow()) || (HighWord() && LowWord()); |
| } |
| |
| bool TypeConflict() const { |
| // NOTE: Ignore array element conflicts that don't propagate to direct conflicts. |
| return (raw_bits_ & kMaskType) != 0u && !IsPowerOfTwo(raw_bits_ & kMaskType); // 2+ bits. |
| } |
| |
| void MarkSizeConflict() { |
| SetBits(kFlagLowWord | kFlagHighWord); |
| } |
| |
| void MarkTypeConflict() { |
| // Mark all three type bits so that merging any other type bits will not change this type. |
| SetBits(kFlagFp | kFlagCore | kFlagRef); |
| } |
| |
| void CheckPureRef() const { |
| DCHECK_EQ(raw_bits_ & (kMaskWideAndType | kMaskWord), kFlagNarrow | kFlagRef | kFlagLowWord); |
| } |
| |
| // If reference, don't treat as possible null and require precise type. |
| // |
| // References without this flag are allowed to have a type conflict and their |
| // type will not be propagated down. However, for simplicity we allow propagation |
| // of other flags up as it will affect only other null references; should those |
| // references be marked non-null later, we would have to do it anyway. |
| // NOTE: This is a negative "non-null" flag rather then a positive "is-null" |
| // to simplify merging together with other non-array flags. |
| bool NonNull() const { |
| return IsBitSet(kFlagNonNull); |
| } |
| |
| bool Wide() const { |
| return IsBitSet(kFlagWide); |
| } |
| |
| bool Narrow() const { |
| return IsBitSet(kFlagNarrow); |
| } |
| |
| bool Fp() const { |
| return IsBitSet(kFlagFp); |
| } |
| |
| bool Core() const { |
| return IsBitSet(kFlagCore); |
| } |
| |
| bool Ref() const { |
| return IsBitSet(kFlagRef); |
| } |
| |
| bool LowWord() const { |
| return IsBitSet(kFlagLowWord); |
| } |
| |
| bool HighWord() const { |
| return IsBitSet(kFlagHighWord); |
| } |
| |
| uint32_t ArrayDepth() const { |
| return raw_bits_ >> kBitArrayDepthStart; |
| } |
| |
| Type NestedType() const { |
| DCHECK_NE(ArrayDepth(), 0u); |
| return Type(kFlagLowWord | ((raw_bits_ & kMaskArrayWideAndType) >> kArrayTypeShift)); |
| } |
| |
| Type ComponentType() const { |
| DCHECK_NE(ArrayDepth(), 0u); |
| Type temp(raw_bits_ - (1u << kBitArrayDepthStart)); // array_depth - 1u; |
| return (temp.ArrayDepth() != 0u) ? temp.AsNull() : NestedType(); |
| } |
| |
| void SetWide() { |
| SetBits(kFlagWide); |
| } |
| |
| void SetNarrow() { |
| SetBits(kFlagNarrow); |
| } |
| |
| void SetFp() { |
| SetBits(kFlagFp); |
| } |
| |
| void SetCore() { |
| SetBits(kFlagCore); |
| } |
| |
| void SetRef() { |
| SetBits(kFlagRef); |
| } |
| |
| void SetLowWord() { |
| SetBits(kFlagLowWord); |
| } |
| |
| void SetHighWord() { |
| SetBits(kFlagHighWord); |
| } |
| |
| Type ToHighWord() const { |
| DCHECK_EQ(raw_bits_ & (kMaskWide | kMaskWord), kFlagWide | kFlagLowWord); |
| return Type(raw_bits_ ^ (kFlagLowWord | kFlagHighWord)); |
| } |
| |
| bool MergeHighWord(Type low_word_type) { |
| // NOTE: low_word_type may be also Narrow() or HighWord(). |
| DCHECK(low_word_type.Wide() && low_word_type.LowWord()); |
| return MergeBits(Type(low_word_type.raw_bits_ | kFlagHighWord), |
| kMaskWideAndType | kFlagHighWord); |
| } |
| |
| bool Copy(Type type) { |
| if (raw_bits_ != type.raw_bits_) { |
| raw_bits_ = type.raw_bits_; |
| return true; |
| } |
| return false; |
| } |
| |
| // Merge non-array flags. |
| bool MergeNonArrayFlags(Type src_type) { |
| return MergeBits(src_type, kMaskNonArray); |
| } |
| |
| // Merge array flags for conflict. |
| bool MergeArrayConflict(Type src_type); |
| |
| // Merge all flags. |
| bool MergeStrong(Type src_type); |
| |
| // Merge all flags. |
| bool MergeWeak(Type src_type); |
| |
| // Get the same type but mark that it should not be treated as null. |
| Type AsNonNull() const { |
| return Type(raw_bits_ | kFlagNonNull); |
| } |
| |
| // Get the same type but mark that it can be treated as null. |
| Type AsNull() const { |
| return Type(raw_bits_ & ~kFlagNonNull); |
| } |
| |
| private: |
| enum FlagBits { |
| kBitNonNull = 0, |
| kBitWide, |
| kBitNarrow, |
| kBitFp, |
| kBitCore, |
| kBitRef, |
| kBitLowWord, |
| kBitHighWord, |
| kBitArrayWide, |
| kBitArrayNarrow, |
| kBitArrayFp, |
| kBitArrayCore, |
| kBitArrayRef, |
| kBitArrayDepthStart, |
| }; |
| static constexpr size_t kArrayDepthBits = sizeof(uint32_t) * 8u - kBitArrayDepthStart; |
| |
| static constexpr uint32_t kFlagNonNull = 1u << kBitNonNull; |
| static constexpr uint32_t kFlagWide = 1u << kBitWide; |
| static constexpr uint32_t kFlagNarrow = 1u << kBitNarrow; |
| static constexpr uint32_t kFlagFp = 1u << kBitFp; |
| static constexpr uint32_t kFlagCore = 1u << kBitCore; |
| static constexpr uint32_t kFlagRef = 1u << kBitRef; |
| static constexpr uint32_t kFlagLowWord = 1u << kBitLowWord; |
| static constexpr uint32_t kFlagHighWord = 1u << kBitHighWord; |
| static constexpr uint32_t kFlagArrayWide = 1u << kBitArrayWide; |
| static constexpr uint32_t kFlagArrayNarrow = 1u << kBitArrayNarrow; |
| static constexpr uint32_t kFlagArrayFp = 1u << kBitArrayFp; |
| static constexpr uint32_t kFlagArrayCore = 1u << kBitArrayCore; |
| static constexpr uint32_t kFlagArrayRef = 1u << kBitArrayRef; |
| |
| static constexpr uint32_t kMaskWide = kFlagWide | kFlagNarrow; |
| static constexpr uint32_t kMaskType = kFlagFp | kFlagCore | kFlagRef; |
| static constexpr uint32_t kMaskWord = kFlagLowWord | kFlagHighWord; |
| static constexpr uint32_t kMaskArrayWide = kFlagArrayWide | kFlagArrayNarrow; |
| static constexpr uint32_t kMaskArrayType = kFlagArrayFp | kFlagArrayCore | kFlagArrayRef; |
| static constexpr uint32_t kMaskWideAndType = kMaskWide | kMaskType; |
| static constexpr uint32_t kMaskArrayWideAndType = kMaskArrayWide | kMaskArrayType; |
| |
| static constexpr size_t kArrayTypeShift = kBitArrayWide - kBitWide; |
| static_assert(kArrayTypeShift == kBitArrayNarrow - kBitNarrow, "shift mismatch"); |
| static_assert(kArrayTypeShift == kBitArrayFp - kBitFp, "shift mismatch"); |
| static_assert(kArrayTypeShift == kBitArrayCore - kBitCore, "shift mismatch"); |
| static_assert(kArrayTypeShift == kBitArrayRef - kBitRef, "shift mismatch"); |
| static_assert((kMaskWide << kArrayTypeShift) == kMaskArrayWide, "shift mismatch"); |
| static_assert((kMaskType << kArrayTypeShift) == kMaskArrayType, "shift mismatch"); |
| static_assert((kMaskWideAndType << kArrayTypeShift) == kMaskArrayWideAndType, "shift mismatch"); |
| |
| static constexpr uint32_t kMaskArrayDepth = static_cast<uint32_t>(-1) << kBitArrayDepthStart; |
| static constexpr uint32_t kMaskNonArray = ~(kMaskArrayWideAndType | kMaskArrayDepth); |
| |
| // The maximum representable array depth. If we exceed the maximum (which can happen |
| // only with an absurd nested array type in a dex file which would presumably cause |
| // OOM while being resolved), we can report false conflicts. |
| static constexpr uint32_t kMaxArrayDepth = static_cast<uint32_t>(-1) >> kBitArrayDepthStart; |
| |
| explicit Type(uint32_t raw_bits) : raw_bits_(raw_bits) { } |
| |
| bool IsBitSet(uint32_t flag) const { |
| return (raw_bits_ & flag) != 0u; |
| } |
| |
| void SetBits(uint32_t flags) { |
| raw_bits_ |= flags; |
| } |
| |
| bool MergeBits(Type src_type, uint32_t mask) { |
| uint32_t new_bits = raw_bits_ | (src_type.raw_bits_ & mask); |
| if (new_bits != raw_bits_) { |
| raw_bits_ = new_bits; |
| return true; |
| } |
| return false; |
| } |
| |
| uint32_t raw_bits_; |
| }; |
| |
| struct MethodSignature { |
| Type return_type; |
| size_t num_params; |
| Type* param_types; |
| }; |
| |
| struct SplitSRegData { |
| int32_t current_mod_s_reg; |
| int32_t* starting_mod_s_reg; // Indexed by BasicBlock::id. |
| int32_t* ending_mod_s_reg; // Indexed by BasicBlock::id. |
| |
| // NOTE: Before AddPseudoPhis(), def_phi_blocks_ marks the blocks |
| // with check-casts and the block with the original SSA reg. |
| // After AddPseudoPhis(), it marks blocks with pseudo-phis. |
| ArenaBitVector* def_phi_blocks_; // Indexed by BasicBlock::id. |
| }; |
| |
| class CheckCastData : public DeletableArenaObject<kArenaAllocMisc> { |
| public: |
| CheckCastData(MIRGraph* mir_graph, ScopedArenaAllocator* alloc); |
| |
| size_t NumSRegs() const { |
| return num_sregs_; |
| } |
| |
| void AddCheckCast(MIR* check_cast, Type type); |
| void AddPseudoPhis(); |
| void InitializeCheckCastSRegs(Type* sregs) const; |
| void MergeCheckCastConflicts(Type* sregs) const; |
| void MarkPseudoPhiBlocks(uint64_t* bb_df_attrs) const; |
| |
| void Start(BasicBlock* bb); |
| bool ProcessPseudoPhis(BasicBlock* bb, Type* sregs); |
| void ProcessCheckCast(MIR* mir); |
| |
| SplitSRegData* GetSplitSRegData(int32_t s_reg); |
| |
| private: |
| BasicBlock* FindDefBlock(MIR* check_cast); |
| BasicBlock* FindTopologicallyEarliestPredecessor(BasicBlock* bb); |
| bool IsSRegLiveAtStart(BasicBlock* bb, int v_reg, int32_t s_reg); |
| |
| MIRGraph* const mir_graph_; |
| ScopedArenaAllocator* const alloc_; |
| const size_t num_blocks_; |
| size_t num_sregs_; |
| |
| // Map check-cast mir to special sreg and type. |
| struct CheckCastMapValue { |
| int32_t modified_s_reg; |
| Type type; |
| }; |
| ScopedArenaSafeMap<MIR*, CheckCastMapValue> check_cast_map_; |
| ScopedArenaSafeMap<int32_t, SplitSRegData> split_sreg_data_; |
| }; |
| |
| static Type FieldType(const DexFile* dex_file, uint32_t field_idx); |
| static Type* PrepareIFieldTypes(const DexFile* dex_file, MIRGraph* mir_graph, |
| ScopedArenaAllocator* alloc); |
| static Type* PrepareSFieldTypes(const DexFile* dex_file, MIRGraph* mir_graph, |
| ScopedArenaAllocator* alloc); |
| static MethodSignature Signature(const DexFile* dex_file, uint32_t method_idx, bool is_static, |
| ScopedArenaAllocator* alloc); |
| static MethodSignature* PrepareSignatures(const DexFile* dex_file, MIRGraph* mir_graph, |
| ScopedArenaAllocator* alloc); |
| static CheckCastData* InitializeCheckCastData(MIRGraph* mir_graph, ScopedArenaAllocator* alloc); |
| |
| void InitializeSRegs(); |
| |
| int32_t ModifiedSReg(int32_t s_reg); |
| int32_t PhiInputModifiedSReg(int32_t s_reg, BasicBlock* bb, size_t pred_idx); |
| |
| bool UpdateSRegFromLowWordType(int32_t mod_s_reg, Type low_word_type); |
| |
| MIRGraph* const mir_graph_; |
| CompilationUnit* const cu_; |
| |
| // The type inference propagates types also backwards but this must not happen across |
| // check-cast. So we need to effectively split an SSA reg into two at check-cast and |
| // keep track of the types separately. |
| std::unique_ptr<CheckCastData> check_cast_data_; |
| |
| size_t num_sregs_; // Number of SSA regs or modified SSA regs, see check-cast. |
| const Type* const ifields_; // Indexed by MIR::meta::ifield_lowering_info. |
| const Type* const sfields_; // Indexed by MIR::meta::sfield_lowering_info. |
| const MethodSignature* const signatures_; // Indexed by MIR::meta::method_lowering_info. |
| const MethodSignature current_method_signature_; |
| Type* const sregs_; // Indexed by SSA reg or modified SSA reg, see check-cast. |
| uint64_t* const bb_df_attrs_; // Indexed by BasicBlock::id. |
| |
| friend class TypeInferenceTest; |
| }; |
| |
| } // namespace art |
| |
| #endif // ART_COMPILER_DEX_TYPE_INFERENCE_H_ |