| /* |
| * Copyright (C) 2013 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_MIR_GRAPH_H_ |
| #define ART_COMPILER_DEX_MIR_GRAPH_H_ |
| |
| #include "dex_file.h" |
| #include "dex_instruction.h" |
| #include "compiler_ir.h" |
| #include "arena_bit_vector.h" |
| #include "utils/growable_array.h" |
| #include "invoke_type.h" |
| #include "mir_annotations.h" |
| |
| namespace art { |
| |
| enum InstructionAnalysisAttributePos { |
| kUninterestingOp = 0, |
| kArithmeticOp, |
| kFPOp, |
| kSingleOp, |
| kDoubleOp, |
| kIntOp, |
| kLongOp, |
| kBranchOp, |
| kInvokeOp, |
| kArrayOp, |
| kHeavyweightOp, |
| kSimpleConstOp, |
| kMoveOp, |
| kSwitch |
| }; |
| |
| #define AN_NONE (1 << kUninterestingOp) |
| #define AN_MATH (1 << kArithmeticOp) |
| #define AN_FP (1 << kFPOp) |
| #define AN_LONG (1 << kLongOp) |
| #define AN_INT (1 << kIntOp) |
| #define AN_SINGLE (1 << kSingleOp) |
| #define AN_DOUBLE (1 << kDoubleOp) |
| #define AN_FLOATMATH (1 << kFPOp) |
| #define AN_BRANCH (1 << kBranchOp) |
| #define AN_INVOKE (1 << kInvokeOp) |
| #define AN_ARRAYOP (1 << kArrayOp) |
| #define AN_HEAVYWEIGHT (1 << kHeavyweightOp) |
| #define AN_SIMPLECONST (1 << kSimpleConstOp) |
| #define AN_MOVE (1 << kMoveOp) |
| #define AN_SWITCH (1 << kSwitch) |
| #define AN_COMPUTATIONAL (AN_MATH | AN_ARRAYOP | AN_MOVE | AN_SIMPLECONST) |
| |
| enum DataFlowAttributePos { |
| kUA = 0, |
| kUB, |
| kUC, |
| kAWide, |
| kBWide, |
| kCWide, |
| kDA, |
| kIsMove, |
| kSetsConst, |
| kFormat35c, |
| kFormat3rc, |
| kNullCheckSrc0, // Null check of uses[0]. |
| kNullCheckSrc1, // Null check of uses[1]. |
| kNullCheckSrc2, // Null check of uses[2]. |
| kNullCheckOut0, // Null check out outgoing arg0. |
| kDstNonNull, // May assume dst is non-null. |
| kRetNonNull, // May assume retval is non-null. |
| kNullTransferSrc0, // Object copy src[0] -> dst. |
| kNullTransferSrcN, // Phi null check state transfer. |
| kRangeCheckSrc1, // Range check of uses[1]. |
| kRangeCheckSrc2, // Range check of uses[2]. |
| kRangeCheckSrc3, // Range check of uses[3]. |
| kFPA, |
| kFPB, |
| kFPC, |
| kCoreA, |
| kCoreB, |
| kCoreC, |
| kRefA, |
| kRefB, |
| kRefC, |
| kUsesMethodStar, // Implicit use of Method*. |
| kDoLVN, // Worth computing local value numbers. |
| }; |
| |
| #define DF_NOP 0ULL |
| #define DF_UA (1ULL << kUA) |
| #define DF_UB (1ULL << kUB) |
| #define DF_UC (1ULL << kUC) |
| #define DF_A_WIDE (1ULL << kAWide) |
| #define DF_B_WIDE (1ULL << kBWide) |
| #define DF_C_WIDE (1ULL << kCWide) |
| #define DF_DA (1ULL << kDA) |
| #define DF_IS_MOVE (1ULL << kIsMove) |
| #define DF_SETS_CONST (1ULL << kSetsConst) |
| #define DF_FORMAT_35C (1ULL << kFormat35c) |
| #define DF_FORMAT_3RC (1ULL << kFormat3rc) |
| #define DF_NULL_CHK_0 (1ULL << kNullCheckSrc0) |
| #define DF_NULL_CHK_1 (1ULL << kNullCheckSrc1) |
| #define DF_NULL_CHK_2 (1ULL << kNullCheckSrc2) |
| #define DF_NULL_CHK_OUT0 (1ULL << kNullCheckOut0) |
| #define DF_NON_NULL_DST (1ULL << kDstNonNull) |
| #define DF_NON_NULL_RET (1ULL << kRetNonNull) |
| #define DF_NULL_TRANSFER_0 (1ULL << kNullTransferSrc0) |
| #define DF_NULL_TRANSFER_N (1ULL << kNullTransferSrcN) |
| #define DF_RANGE_CHK_1 (1ULL << kRangeCheckSrc1) |
| #define DF_RANGE_CHK_2 (1ULL << kRangeCheckSrc2) |
| #define DF_RANGE_CHK_3 (1ULL << kRangeCheckSrc3) |
| #define DF_FP_A (1ULL << kFPA) |
| #define DF_FP_B (1ULL << kFPB) |
| #define DF_FP_C (1ULL << kFPC) |
| #define DF_CORE_A (1ULL << kCoreA) |
| #define DF_CORE_B (1ULL << kCoreB) |
| #define DF_CORE_C (1ULL << kCoreC) |
| #define DF_REF_A (1ULL << kRefA) |
| #define DF_REF_B (1ULL << kRefB) |
| #define DF_REF_C (1ULL << kRefC) |
| #define DF_UMS (1ULL << kUsesMethodStar) |
| #define DF_LVN (1ULL << kDoLVN) |
| |
| #define DF_HAS_USES (DF_UA | DF_UB | DF_UC) |
| |
| #define DF_HAS_DEFS (DF_DA) |
| |
| #define DF_HAS_NULL_CHKS (DF_NULL_CHK_0 | \ |
| DF_NULL_CHK_1 | \ |
| DF_NULL_CHK_2 | \ |
| DF_NULL_CHK_OUT0) |
| |
| #define DF_HAS_RANGE_CHKS (DF_RANGE_CHK_1 | \ |
| DF_RANGE_CHK_2 | \ |
| DF_RANGE_CHK_3) |
| |
| #define DF_HAS_NR_CHKS (DF_HAS_NULL_CHKS | \ |
| DF_HAS_RANGE_CHKS) |
| |
| #define DF_A_IS_REG (DF_UA | DF_DA) |
| #define DF_B_IS_REG (DF_UB) |
| #define DF_C_IS_REG (DF_UC) |
| #define DF_IS_GETTER_OR_SETTER (DF_IS_GETTER | DF_IS_SETTER) |
| #define DF_USES_FP (DF_FP_A | DF_FP_B | DF_FP_C) |
| #define DF_NULL_TRANSFER (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N) |
| enum OatMethodAttributes { |
| kIsLeaf, // Method is leaf. |
| kHasLoop, // Method contains simple loop. |
| }; |
| |
| #define METHOD_IS_LEAF (1 << kIsLeaf) |
| #define METHOD_HAS_LOOP (1 << kHasLoop) |
| |
| // Minimum field size to contain Dalvik v_reg number. |
| #define VREG_NUM_WIDTH 16 |
| |
| #define INVALID_SREG (-1) |
| #define INVALID_VREG (0xFFFFU) |
| #define INVALID_REG (0xFF) |
| #define INVALID_OFFSET (0xDEADF00FU) |
| |
| #define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) |
| #define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) |
| #define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) |
| #define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) |
| #define MIR_INLINED (1 << kMIRInlined) |
| #define MIR_INLINED_PRED (1 << kMIRInlinedPred) |
| #define MIR_CALLEE (1 << kMIRCallee) |
| #define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck) |
| #define MIR_DUP (1 << kMIRDup) |
| |
| #define BLOCK_NAME_LEN 80 |
| |
| typedef uint16_t BasicBlockId; |
| static const BasicBlockId NullBasicBlockId = 0; |
| |
| /* |
| * In general, vreg/sreg describe Dalvik registers that originated with dx. However, |
| * it is useful to have compiler-generated temporary registers and have them treated |
| * in the same manner as dx-generated virtual registers. This struct records the SSA |
| * name of compiler-introduced temporaries. |
| */ |
| struct CompilerTemp { |
| int32_t v_reg; // Virtual register number for temporary. |
| int32_t s_reg_low; // SSA name for low Dalvik word. |
| }; |
| |
| enum CompilerTempType { |
| kCompilerTempVR, // A virtual register temporary. |
| kCompilerTempSpecialMethodPtr, // Temporary that keeps track of current method pointer. |
| }; |
| |
| // When debug option enabled, records effectiveness of null and range check elimination. |
| struct Checkstats { |
| int32_t null_checks; |
| int32_t null_checks_eliminated; |
| int32_t range_checks; |
| int32_t range_checks_eliminated; |
| }; |
| |
| // Dataflow attributes of a basic block. |
| struct BasicBlockDataFlow { |
| ArenaBitVector* use_v; |
| ArenaBitVector* def_v; |
| ArenaBitVector* live_in_v; |
| ArenaBitVector* phi_v; |
| int32_t* vreg_to_ssa_map; |
| ArenaBitVector* ending_null_check_v; |
| }; |
| |
| /* |
| * Normalized use/def for a MIR operation using SSA names rather than vregs. Note that |
| * uses/defs retain the Dalvik convention that long operations operate on a pair of 32-bit |
| * vregs. For example, "ADD_LONG v0, v2, v3" would have 2 defs (v0/v1) and 4 uses (v2/v3, v4/v5). |
| * Following SSA renaming, this is the primary struct used by code generators to locate |
| * operand and result registers. This is a somewhat confusing and unhelpful convention that |
| * we may want to revisit in the future. |
| */ |
| struct SSARepresentation { |
| int16_t num_uses; |
| int16_t num_defs; |
| int32_t* uses; |
| bool* fp_use; |
| int32_t* defs; |
| bool* fp_def; |
| }; |
| |
| /* |
| * The Midlevel Intermediate Representation node, which may be largely considered a |
| * wrapper around a Dalvik byte code. |
| */ |
| struct MIR { |
| /* |
| * TODO: remove embedded DecodedInstruction to save space, keeping only opcode. Recover |
| * additional fields on as-needed basis. Question: how to support MIR Pseudo-ops; probably |
| * need to carry aux data pointer. |
| */ |
| DecodedInstruction dalvikInsn; |
| uint16_t width; // Note: width can include switch table or fill array data. |
| NarrowDexOffset offset; // Offset of the instruction in code units. |
| uint16_t optimization_flags; |
| int16_t m_unit_index; // From which method was this MIR included |
| MIR* next; |
| SSARepresentation* ssa_rep; |
| union { |
| // Incoming edges for phi node. |
| BasicBlockId* phi_incoming; |
| // Establish link from check instruction (kMirOpCheck) to the actual throwing instruction. |
| MIR* throw_insn; |
| // Fused cmp branch condition. |
| ConditionCode ccode; |
| // IGET/IPUT annotation index, points to MIRGraph::ifield_annotations_. Due to limit on the |
| // number of code points (64K) and size of IGET/IPUT insn (2), this will never exceed 32K. |
| uint32_t ifield_annotation; |
| // SGET/SPUT annotation index, points to MIRGraph::sfield_annotations_. Due to limit on the |
| // number of code points (64K) and size of SGET/SPUT insn (2), this will never exceed 32K. |
| uint32_t sfield_annotation; |
| } meta; |
| }; |
| |
| struct SuccessorBlockInfo; |
| |
| struct BasicBlock { |
| BasicBlockId id; |
| BasicBlockId dfs_id; |
| NarrowDexOffset start_offset; // Offset in code units. |
| BasicBlockId fall_through; |
| BasicBlockId taken; |
| BasicBlockId i_dom; // Immediate dominator. |
| uint16_t nesting_depth; |
| BBType block_type:4; |
| BlockListType successor_block_list_type:4; |
| bool visited:1; |
| bool hidden:1; |
| bool catch_entry:1; |
| bool explicit_throw:1; |
| bool conditional_branch:1; |
| bool terminated_by_return:1; // Block ends with a Dalvik return opcode. |
| bool dominates_return:1; // Is a member of return extended basic block. |
| bool use_lvn:1; // Run local value numbering on this block. |
| MIR* first_mir_insn; |
| MIR* last_mir_insn; |
| BasicBlockDataFlow* data_flow_info; |
| ArenaBitVector* dominators; |
| ArenaBitVector* i_dominated; // Set nodes being immediately dominated. |
| ArenaBitVector* dom_frontier; // Dominance frontier. |
| GrowableArray<BasicBlockId>* predecessors; |
| GrowableArray<SuccessorBlockInfo*>* successor_blocks; |
| }; |
| |
| /* |
| * The "blocks" field in "successor_block_list" points to an array of elements with the type |
| * "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For swtich |
| * blocks, key is the case value. |
| */ |
| struct SuccessorBlockInfo { |
| BasicBlockId block; |
| int key; |
| }; |
| |
| /* |
| * Whereas a SSA name describes a definition of a Dalvik vreg, the RegLocation describes |
| * the type of an SSA name (and, can also be used by code generators to record where the |
| * value is located (i.e. - physical register, frame, spill, etc.). For each SSA name (SReg) |
| * there is a RegLocation. |
| * A note on SSA names: |
| * o SSA names for Dalvik vRegs v0..vN will be assigned 0..N. These represent the "vN_0" |
| * names. Negative SSA names represent special values not present in the Dalvik byte code. |
| * For example, SSA name -1 represents an invalid SSA name, and SSA name -2 represents the |
| * the Method pointer. SSA names < -2 are reserved for future use. |
| * o The vN_0 names for non-argument Dalvik should in practice never be used (as they would |
| * represent the read of an undefined local variable). The first definition of the |
| * underlying Dalvik vReg will result in a vN_1 name. |
| * |
| * FIXME: The orig_sreg field was added as a workaround for llvm bitcode generation. With |
| * the latest restructuring, we should be able to remove it and rely on s_reg_low throughout. |
| */ |
| struct RegLocation { |
| RegLocationType location:3; |
| unsigned wide:1; |
| unsigned defined:1; // Do we know the type? |
| unsigned is_const:1; // Constant, value in mir_graph->constant_values[]. |
| unsigned fp:1; // Floating point? |
| unsigned core:1; // Non-floating point? |
| unsigned ref:1; // Something GC cares about. |
| unsigned high_word:1; // High word of pair? |
| unsigned home:1; // Does this represent the home location? |
| VectorLengthType vec_len:3; // Is this value in a vector register, and how big is it? |
| uint8_t low_reg; // First physical register. |
| uint8_t high_reg; // 2nd physical register (if wide). |
| int16_t s_reg_low; // SSA name for low Dalvik word. |
| int16_t orig_sreg; // TODO: remove after Bitcode gen complete |
| // and consolidate usage w/ s_reg_low. |
| |
| bool IsVectorScalar() const { return vec_len == kVectorLength4 || vec_len == kVectorLength8;} |
| }; |
| |
| /* |
| * Collection of information describing an invoke, and the destination of |
| * the subsequent MOVE_RESULT (if applicable). Collected as a unit to enable |
| * more efficient invoke code generation. |
| */ |
| struct CallInfo { |
| int num_arg_words; // Note: word count, not arg count. |
| RegLocation* args; // One for each word of arguments. |
| RegLocation result; // Eventual target of MOVE_RESULT. |
| int opt_flags; |
| InvokeType type; |
| uint32_t dex_idx; |
| uint32_t index; // Method idx for invokes, type idx for FilledNewArray. |
| uintptr_t direct_code; |
| uintptr_t direct_method; |
| RegLocation target; // Target of following move_result. |
| bool skip_this; |
| bool is_range; |
| DexOffset offset; // Offset in code units. |
| }; |
| |
| |
| const RegLocation bad_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0, kVectorNotUsed, |
| INVALID_REG, INVALID_REG, INVALID_SREG, INVALID_SREG}; |
| |
| class MIRGraph { |
| public: |
| MIRGraph(CompilationUnit* cu, ArenaAllocator* arena); |
| ~MIRGraph(); |
| |
| /* |
| * Examine the graph to determine whether it's worthwile to spend the time compiling |
| * this method. |
| */ |
| bool SkipCompilation(Runtime::CompilerFilter compiler_filter); |
| |
| /* |
| * Parse dex method and add MIR at current insert point. Returns id (which is |
| * actually the index of the method in the m_units_ array). |
| */ |
| void InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, |
| InvokeType invoke_type, uint16_t class_def_idx, |
| uint32_t method_idx, jobject class_loader, const DexFile& dex_file); |
| |
| /* Find existing block */ |
| BasicBlock* FindBlock(DexOffset code_offset) { |
| return FindBlock(code_offset, false, false, NULL); |
| } |
| |
| const uint16_t* GetCurrentInsns() const { |
| return current_code_item_->insns_; |
| } |
| |
| const uint16_t* GetInsns(int m_unit_index) const { |
| return m_units_[m_unit_index]->GetCodeItem()->insns_; |
| } |
| |
| int GetNumBlocks() const { |
| return num_blocks_; |
| } |
| |
| size_t GetNumDalvikInsns() const { |
| return cu_->code_item->insns_size_in_code_units_; |
| } |
| |
| ArenaBitVector* GetTryBlockAddr() const { |
| return try_block_addr_; |
| } |
| |
| BasicBlock* GetEntryBlock() const { |
| return entry_block_; |
| } |
| |
| BasicBlock* GetExitBlock() const { |
| return exit_block_; |
| } |
| |
| BasicBlock* GetBasicBlock(int block_id) const { |
| return (block_id == NullBasicBlockId) ? NULL : block_list_.Get(block_id); |
| } |
| |
| size_t GetBasicBlockListCount() const { |
| return block_list_.Size(); |
| } |
| |
| GrowableArray<BasicBlock*>* GetBlockList() { |
| return &block_list_; |
| } |
| |
| GrowableArray<BasicBlockId>* GetDfsOrder() { |
| return dfs_order_; |
| } |
| |
| GrowableArray<BasicBlockId>* GetDfsPostOrder() { |
| return dfs_post_order_; |
| } |
| |
| GrowableArray<BasicBlockId>* GetDomPostOrder() { |
| return dom_post_order_traversal_; |
| } |
| |
| int GetDefCount() const { |
| return def_count_; |
| } |
| |
| ArenaAllocator* GetArena() { |
| return arena_; |
| } |
| |
| void EnableOpcodeCounting() { |
| opcode_count_ = static_cast<int*>(arena_->Alloc(kNumPackedOpcodes * sizeof(int), |
| ArenaAllocator::kAllocMisc)); |
| } |
| |
| void ShowOpcodeStats(); |
| |
| DexCompilationUnit* GetCurrentDexCompilationUnit() const { |
| return m_units_[current_method_]; |
| } |
| |
| /** |
| * @brief Dump a CFG into a dot file format. |
| * @param dir_prefix the directory the file will be created in. |
| * @param all_blocks does the dumper use all the basic blocks or use the reachable blocks. |
| * @param suffix does the filename require a suffix or not (default = nullptr). |
| */ |
| void DumpCFG(const char* dir_prefix, bool all_blocks, const char* suffix = nullptr); |
| |
| void DoAnnotateUsedFields(); |
| |
| const IFieldAnnotation& GetIFieldAnnotation(MIR* mir) { |
| DCHECK_LT(mir->meta.ifield_annotation, ifield_annotations_.Size()); |
| return ifield_annotations_.GetRawStorage()[mir->meta.ifield_annotation]; |
| } |
| |
| const SFieldAnnotation& GetSFieldAnnotation(MIR* mir) { |
| DCHECK_LT(mir->meta.sfield_annotation, sfield_annotations_.Size()); |
| return sfield_annotations_.GetRawStorage()[mir->meta.sfield_annotation]; |
| } |
| |
| void InitRegLocations(); |
| |
| void RemapRegLocations(); |
| |
| void DumpRegLocTable(RegLocation* table, int count); |
| |
| void BasicBlockOptimization(); |
| |
| bool IsConst(int32_t s_reg) const { |
| return is_constant_v_->IsBitSet(s_reg); |
| } |
| |
| bool IsConst(RegLocation loc) const { |
| return loc.orig_sreg < 0 ? false : IsConst(loc.orig_sreg); |
| } |
| |
| int32_t ConstantValue(RegLocation loc) const { |
| DCHECK(IsConst(loc)); |
| return constant_values_[loc.orig_sreg]; |
| } |
| |
| int32_t ConstantValue(int32_t s_reg) const { |
| DCHECK(IsConst(s_reg)); |
| return constant_values_[s_reg]; |
| } |
| |
| int64_t ConstantValueWide(RegLocation loc) const { |
| DCHECK(IsConst(loc)); |
| return (static_cast<int64_t>(constant_values_[loc.orig_sreg + 1]) << 32) | |
| Low32Bits(static_cast<int64_t>(constant_values_[loc.orig_sreg])); |
| } |
| |
| bool IsConstantNullRef(RegLocation loc) const { |
| return loc.ref && loc.is_const && (ConstantValue(loc) == 0); |
| } |
| |
| int GetNumSSARegs() const { |
| return num_ssa_regs_; |
| } |
| |
| void SetNumSSARegs(int new_num) { |
| /* |
| * TODO: It's theoretically possible to exceed 32767, though any cases which did |
| * would be filtered out with current settings. When orig_sreg field is removed |
| * from RegLocation, expand s_reg_low to handle all possible cases and remove DCHECK(). |
| */ |
| DCHECK_EQ(new_num, static_cast<int16_t>(new_num)); |
| num_ssa_regs_ = new_num; |
| } |
| |
| unsigned int GetNumReachableBlocks() const { |
| return num_reachable_blocks_; |
| } |
| |
| int GetUseCount(int vreg) const { |
| return use_counts_.Get(vreg); |
| } |
| |
| int GetRawUseCount(int vreg) const { |
| return raw_use_counts_.Get(vreg); |
| } |
| |
| int GetSSASubscript(int ssa_reg) const { |
| return ssa_subscripts_->Get(ssa_reg); |
| } |
| |
| RegLocation GetRawSrc(MIR* mir, int num) { |
| DCHECK(num < mir->ssa_rep->num_uses); |
| RegLocation res = reg_location_[mir->ssa_rep->uses[num]]; |
| return res; |
| } |
| |
| RegLocation GetRawDest(MIR* mir) { |
| DCHECK_GT(mir->ssa_rep->num_defs, 0); |
| RegLocation res = reg_location_[mir->ssa_rep->defs[0]]; |
| return res; |
| } |
| |
| RegLocation GetDest(MIR* mir) { |
| RegLocation res = GetRawDest(mir); |
| DCHECK(!res.wide); |
| return res; |
| } |
| |
| RegLocation GetSrc(MIR* mir, int num) { |
| RegLocation res = GetRawSrc(mir, num); |
| DCHECK(!res.wide); |
| return res; |
| } |
| |
| RegLocation GetDestWide(MIR* mir) { |
| RegLocation res = GetRawDest(mir); |
| DCHECK(res.wide); |
| return res; |
| } |
| |
| RegLocation GetSrcWide(MIR* mir, int low) { |
| RegLocation res = GetRawSrc(mir, low); |
| DCHECK(res.wide); |
| return res; |
| } |
| |
| RegLocation GetBadLoc() { |
| return bad_loc; |
| } |
| |
| int GetMethodSReg() const { |
| return method_sreg_; |
| } |
| |
| /** |
| * @brief Used to obtain the number of compiler temporaries being used. |
| * @return Returns the number of compiler temporaries. |
| */ |
| size_t GetNumUsedCompilerTemps() const { |
| size_t total_num_temps = compiler_temps_.Size(); |
| DCHECK_LE(num_non_special_compiler_temps_, total_num_temps); |
| return total_num_temps; |
| } |
| |
| /** |
| * @brief Used to obtain the number of non-special compiler temporaries being used. |
| * @return Returns the number of non-special compiler temporaries. |
| */ |
| size_t GetNumNonSpecialCompilerTemps() const { |
| return num_non_special_compiler_temps_; |
| } |
| |
| /** |
| * @brief Used to set the total number of available non-special compiler temporaries. |
| * @details Can fail setting the new max if there are more temps being used than the new_max. |
| * @param new_max The new maximum number of non-special compiler temporaries. |
| * @return Returns true if the max was set and false if failed to set. |
| */ |
| bool SetMaxAvailableNonSpecialCompilerTemps(size_t new_max) { |
| if (new_max < GetNumNonSpecialCompilerTemps()) { |
| return false; |
| } else { |
| max_available_non_special_compiler_temps_ = new_max; |
| return true; |
| } |
| } |
| |
| /** |
| * @brief Provides the number of non-special compiler temps available. |
| * @details Even if this returns zero, special compiler temps are guaranteed to be available. |
| * @return Returns the number of available temps. |
| */ |
| size_t GetNumAvailableNonSpecialCompilerTemps(); |
| |
| /** |
| * @brief Used to obtain an existing compiler temporary. |
| * @param index The index of the temporary which must be strictly less than the |
| * number of temporaries. |
| * @return Returns the temporary that was asked for. |
| */ |
| CompilerTemp* GetCompilerTemp(size_t index) const { |
| return compiler_temps_.Get(index); |
| } |
| |
| /** |
| * @brief Used to obtain the maximum number of compiler temporaries that can be requested. |
| * @return Returns the maximum number of compiler temporaries, whether used or not. |
| */ |
| size_t GetMaxPossibleCompilerTemps() const { |
| return max_available_special_compiler_temps_ + max_available_non_special_compiler_temps_; |
| } |
| |
| /** |
| * @brief Used to obtain a new unique compiler temporary. |
| * @param ct_type Type of compiler temporary requested. |
| * @param wide Whether we should allocate a wide temporary. |
| * @return Returns the newly created compiler temporary. |
| */ |
| CompilerTemp* GetNewCompilerTemp(CompilerTempType ct_type, bool wide); |
| |
| bool MethodIsLeaf() { |
| return attributes_ & METHOD_IS_LEAF; |
| } |
| |
| RegLocation GetRegLocation(int index) { |
| DCHECK((index >= 0) && (index < num_ssa_regs_)); |
| return reg_location_[index]; |
| } |
| |
| RegLocation GetMethodLoc() { |
| return reg_location_[method_sreg_]; |
| } |
| |
| bool IsBackedge(BasicBlock* branch_bb, BasicBlockId target_bb_id) { |
| return ((target_bb_id != NullBasicBlockId) && |
| (GetBasicBlock(target_bb_id)->start_offset <= branch_bb->start_offset)); |
| } |
| |
| bool IsBackwardsBranch(BasicBlock* branch_bb) { |
| return IsBackedge(branch_bb, branch_bb->taken) || IsBackedge(branch_bb, branch_bb->fall_through); |
| } |
| |
| void CountBranch(DexOffset target_offset) { |
| if (target_offset <= current_offset_) { |
| backward_branches_++; |
| } else { |
| forward_branches_++; |
| } |
| } |
| |
| int GetBranchCount() { |
| return backward_branches_ + forward_branches_; |
| } |
| |
| bool IsPseudoMirOp(Instruction::Code opcode) { |
| return static_cast<int>(opcode) >= static_cast<int>(kMirOpFirst); |
| } |
| |
| bool IsPseudoMirOp(int opcode) { |
| return opcode >= static_cast<int>(kMirOpFirst); |
| } |
| |
| void DumpCheckStats(); |
| MIR* FindMoveResult(BasicBlock* bb, MIR* mir); |
| int SRegToVReg(int ssa_reg) const; |
| void VerifyDataflow(); |
| void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb); |
| bool EliminateNullChecksAndInferTypes(BasicBlock *bb); |
| /* |
| * Type inference handling helpers. 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 by using an iterative walk over |
| * the graph, propagating types "defined" by typed opcodes to uses and defs in |
| * non-typed opcodes (such as MOVE). The Setxx(index) helpers are used to set defined |
| * types on typed opcodes (such as ADD_INT). The Setxx(index, is_xx) form is used to |
| * propagate types through non-typed opcodes such as PHI and MOVE. The is_xx flag |
| * tells whether our guess of the type is based on a previously typed definition. |
| * If so, the defined type takes precedence. Note that it's possible to have the same sreg |
| * show multiple defined types because dx treats constants as untyped bit patterns. |
| * The return value of the Setxx() helpers says whether or not the Setxx() action changed |
| * the current guess, and is used to know when to terminate the iterative walk. |
| */ |
| bool SetFp(int index, bool is_fp); |
| bool SetFp(int index); |
| bool SetCore(int index, bool is_core); |
| bool SetCore(int index); |
| bool SetRef(int index, bool is_ref); |
| bool SetRef(int index); |
| bool SetWide(int index, bool is_wide); |
| bool SetWide(int index); |
| bool SetHigh(int index, bool is_high); |
| bool SetHigh(int index); |
| |
| void AppendMIR(BasicBlock* bb, MIR* mir); |
| void PrependMIR(BasicBlock* bb, MIR* mir); |
| void InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir); |
| |
| /** |
| * @brief Used to obtain the next MIR that follows unconditionally. |
| * @details The implementation does not guarantee that a MIR does not |
| * follow even if this method returns nullptr. |
| * @param bb The basic block of "current" MIR. |
| * @param current The MIR for which to find an unconditional follower. |
| * @return Returns the following MIR if one can be found. |
| */ |
| MIR* GetNextUnconditionalMir(BasicBlock* bb, MIR* current); |
| |
| char* GetDalvikDisassembly(const MIR* mir); |
| void ReplaceSpecialChars(std::string& str); |
| std::string GetSSAName(int ssa_reg); |
| std::string GetSSANameWithConst(int ssa_reg, bool singles_only); |
| void GetBlockName(BasicBlock* bb, char* name); |
| const char* GetShortyFromTargetIdx(int); |
| void DumpMIRGraph(); |
| CallInfo* NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, bool is_range); |
| BasicBlock* NewMemBB(BBType block_type, int block_id); |
| MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir); |
| BasicBlock* NextDominatedBlock(BasicBlock* bb); |
| bool LayoutBlocks(BasicBlock* bb); |
| |
| /** |
| * @brief Perform the initial preparation for the Method Uses. |
| */ |
| void InitializeMethodUses(); |
| |
| /** |
| * @brief Perform the initial preparation for the Constant Propagation. |
| */ |
| void InitializeConstantPropagation(); |
| |
| /** |
| * @brief Perform the initial preparation for the SSA Transformation. |
| */ |
| void InitializeSSATransformation(); |
| |
| /** |
| * @brief Insert a the operands for the Phi nodes. |
| * @param bb the considered BasicBlock. |
| * @return true |
| */ |
| bool InsertPhiNodeOperands(BasicBlock* bb); |
| |
| /** |
| * @brief Perform constant propagation on a BasicBlock. |
| * @param bb the considered BasicBlock. |
| */ |
| void DoConstantPropagation(BasicBlock* bb); |
| |
| /** |
| * @brief Count the uses in the BasicBlock |
| * @param bb the BasicBlock |
| */ |
| void CountUses(struct BasicBlock* bb); |
| |
| /** |
| * @brief Initialize the data structures with Null Check data |
| * @param bb the considered BasicBlock |
| */ |
| void NullCheckEliminationInit(BasicBlock* bb); |
| |
| /** |
| * @brief Check if the temporary ssa register vector is allocated |
| */ |
| void CheckSSARegisterVector(); |
| |
| /** |
| * @brief Combine BasicBlocks |
| * @param the BasicBlock we are considering |
| */ |
| void CombineBlocks(BasicBlock* bb); |
| |
| void ClearAllVisitedFlags(); |
| /* |
| * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on |
| * we can verify that all catch entries have native PC entries. |
| */ |
| std::set<uint32_t> catches_; |
| |
| // TODO: make these private. |
| RegLocation* reg_location_; // Map SSA names to location. |
| SafeMap<unsigned int, unsigned int> block_id_map_; // Block collapse lookup cache. |
| |
| static const uint64_t oat_data_flow_attributes_[kMirOpLast]; |
| static const char* extended_mir_op_names_[kMirOpLast - kMirOpFirst]; |
| static const uint32_t analysis_attributes_[kMirOpLast]; |
| |
| private: |
| int FindCommonParent(int block1, int block2); |
| void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, |
| const ArenaBitVector* src2); |
| void HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, |
| ArenaBitVector* live_in_v, int dalvik_reg_id); |
| void HandleDef(ArenaBitVector* def_v, int dalvik_reg_id); |
| void CompilerInitializeSSAConversion(); |
| bool DoSSAConversion(BasicBlock* bb); |
| bool InvokeUsesMethodStar(MIR* mir); |
| int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction); |
| bool ContentIsInsn(const uint16_t* code_ptr); |
| BasicBlock* SplitBlock(DexOffset code_offset, BasicBlock* orig_block, |
| BasicBlock** immed_pred_block_p); |
| BasicBlock* FindBlock(DexOffset code_offset, bool split, bool create, |
| BasicBlock** immed_pred_block_p); |
| void ProcessTryCatchBlocks(); |
| BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
| int flags, const uint16_t* code_ptr, const uint16_t* code_end); |
| BasicBlock* ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
| int flags); |
| BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
| int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr, |
| const uint16_t* code_end); |
| int AddNewSReg(int v_reg); |
| void HandleSSAUse(int* uses, int dalvik_reg, int reg_index); |
| void HandleSSADef(int* defs, int dalvik_reg, int reg_index); |
| void DataFlowSSAFormat35C(MIR* mir); |
| void DataFlowSSAFormat3RC(MIR* mir); |
| bool FindLocalLiveIn(BasicBlock* bb); |
| bool InferTypeAndSize(BasicBlock* bb, MIR* mir, bool changed); |
| bool VerifyPredInfo(BasicBlock* bb); |
| BasicBlock* NeedsVisit(BasicBlock* bb); |
| BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb); |
| void MarkPreOrder(BasicBlock* bb); |
| void RecordDFSOrders(BasicBlock* bb); |
| void ComputeDFSOrders(); |
| void ComputeDefBlockMatrix(); |
| void ComputeDomPostOrderTraversal(BasicBlock* bb); |
| void ComputeDominators(); |
| void InsertPhiNodes(); |
| void DoDFSPreOrderSSARename(BasicBlock* block); |
| void SetConstant(int32_t ssa_reg, int value); |
| void SetConstantWide(int ssa_reg, int64_t value); |
| int GetSSAUseCount(int s_reg); |
| bool BasicBlockOpt(BasicBlock* bb); |
| bool BuildExtendedBBList(struct BasicBlock* bb); |
| bool FillDefBlockMatrix(BasicBlock* bb); |
| void InitializeDominationInfo(BasicBlock* bb); |
| bool ComputeblockIDom(BasicBlock* bb); |
| bool ComputeBlockDominators(BasicBlock* bb); |
| bool SetDominators(BasicBlock* bb); |
| bool ComputeBlockLiveIns(BasicBlock* bb); |
| bool ComputeDominanceFrontier(BasicBlock* bb); |
| |
| void CountChecks(BasicBlock* bb); |
| void AnalyzeBlock(BasicBlock* bb, struct MethodStats* stats); |
| bool ComputeSkipCompilation(struct MethodStats* stats, bool skip_default); |
| |
| CompilationUnit* const cu_; |
| GrowableArray<int>* ssa_base_vregs_; |
| GrowableArray<int>* ssa_subscripts_; |
| // Map original Dalvik virtual reg i to the current SSA name. |
| int* vreg_to_ssa_map_; // length == method->registers_size |
| int* ssa_last_defs_; // length == method->registers_size |
| ArenaBitVector* is_constant_v_; // length == num_ssa_reg |
| int* constant_values_; // length == num_ssa_reg |
| // Use counts of ssa names. |
| GrowableArray<uint32_t> use_counts_; // Weighted by nesting depth |
| GrowableArray<uint32_t> raw_use_counts_; // Not weighted |
| unsigned int num_reachable_blocks_; |
| GrowableArray<BasicBlockId>* dfs_order_; |
| GrowableArray<BasicBlockId>* dfs_post_order_; |
| GrowableArray<BasicBlockId>* dom_post_order_traversal_; |
| int* i_dom_list_; |
| ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks. |
| ArenaBitVector* temp_block_v_; |
| ArenaBitVector* temp_dalvik_register_v_; |
| ArenaBitVector* temp_ssa_register_v_; // num_ssa_regs. |
| static const int kInvalidEntry = -1; |
| GrowableArray<BasicBlock*> block_list_; |
| ArenaBitVector* try_block_addr_; |
| BasicBlock* entry_block_; |
| BasicBlock* exit_block_; |
| int num_blocks_; |
| const DexFile::CodeItem* current_code_item_; |
| GrowableArray<uint16_t> dex_pc_to_block_map_; // FindBlock lookup cache. |
| std::vector<DexCompilationUnit*> m_units_; // List of methods included in this graph |
| typedef std::pair<int, int> MIRLocation; // Insert point, (m_unit_ index, offset) |
| std::vector<MIRLocation> method_stack_; // Include stack |
| int current_method_; |
| DexOffset current_offset_; // Offset in code units |
| int def_count_; // Used to estimate size of ssa name storage. |
| int* opcode_count_; // Dex opcode coverage stats. |
| int num_ssa_regs_; // Number of names following SSA transformation. |
| std::vector<BasicBlockId> extended_basic_blocks_; // Heads of block "traces". |
| int method_sreg_; |
| unsigned int attributes_; |
| Checkstats* checkstats_; |
| ArenaAllocator* arena_; |
| int backward_branches_; |
| int forward_branches_; |
| GrowableArray<CompilerTemp*> compiler_temps_; |
| size_t num_non_special_compiler_temps_; |
| size_t max_available_non_special_compiler_temps_; |
| size_t max_available_special_compiler_temps_; |
| GrowableArray<IFieldAnnotation> ifield_annotations_; |
| GrowableArray<SFieldAnnotation> sfield_annotations_; |
| }; |
| |
| } // namespace art |
| |
| #endif // ART_COMPILER_DEX_MIR_GRAPH_H_ |