blob: adc3b54bc95e251a79b43dc14b8f07ac0a64a24f [file] [log] [blame]
* 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
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* See the License for the specific language governing permissions and
* limitations under the License.
#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> {
TypeInference(MIRGraph* mir_graph, ScopedArenaAllocator* alloc);
bool Apply(BasicBlock* bb);
void Finish();
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() {
void SetNarrow() {
void SetFp() {
void SetCore() {
void SetRef() {
void SetLowWord() {
void SetHighWord() {
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);
enum FlagBits {
kBitNonNull = 0,
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> {
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);
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