buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2013 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Brian Carlstrom | fc0e321 | 2013-07-17 14:40:12 -0700 | [diff] [blame] | 17 | #ifndef ART_COMPILER_DEX_MIR_GRAPH_H_ |
| 18 | #define ART_COMPILER_DEX_MIR_GRAPH_H_ |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 19 | |
| 20 | #include "dex_file.h" |
| 21 | #include "dex_instruction.h" |
| 22 | #include "compiler_ir.h" |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 23 | #include "arena_bit_vector.h" |
| 24 | #include "growable_array.h" |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 25 | |
| 26 | namespace art { |
| 27 | |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 28 | enum InstructionAnalysisAttributePos { |
| 29 | kUninterestingOp = 0, |
| 30 | kArithmeticOp, |
| 31 | kFPOp, |
| 32 | kSingleOp, |
| 33 | kDoubleOp, |
| 34 | kIntOp, |
| 35 | kLongOp, |
| 36 | kBranchOp, |
| 37 | kInvokeOp, |
| 38 | kArrayOp, |
| 39 | kHeavyweightOp, |
| 40 | kSimpleConstOp, |
buzbee | fe9ca40 | 2013-08-21 09:48:11 -0700 | [diff] [blame] | 41 | kMoveOp, |
| 42 | kSwitch |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 43 | }; |
| 44 | |
| 45 | #define AN_NONE (1 << kUninterestingOp) |
| 46 | #define AN_MATH (1 << kArithmeticOp) |
| 47 | #define AN_FP (1 << kFPOp) |
| 48 | #define AN_LONG (1 << kLongOp) |
| 49 | #define AN_INT (1 << kIntOp) |
| 50 | #define AN_SINGLE (1 << kSingleOp) |
| 51 | #define AN_DOUBLE (1 << kDoubleOp) |
| 52 | #define AN_FLOATMATH (1 << kFPOp) |
| 53 | #define AN_BRANCH (1 << kBranchOp) |
| 54 | #define AN_INVOKE (1 << kInvokeOp) |
| 55 | #define AN_ARRAYOP (1 << kArrayOp) |
| 56 | #define AN_HEAVYWEIGHT (1 << kHeavyweightOp) |
| 57 | #define AN_SIMPLECONST (1 << kSimpleConstOp) |
| 58 | #define AN_MOVE (1 << kMoveOp) |
buzbee | fe9ca40 | 2013-08-21 09:48:11 -0700 | [diff] [blame] | 59 | #define AN_SWITCH (1 << kSwitch) |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 60 | #define AN_COMPUTATIONAL (AN_MATH | AN_ARRAYOP | AN_MOVE | AN_SIMPLECONST) |
| 61 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 62 | enum DataFlowAttributePos { |
| 63 | kUA = 0, |
| 64 | kUB, |
| 65 | kUC, |
| 66 | kAWide, |
| 67 | kBWide, |
| 68 | kCWide, |
| 69 | kDA, |
| 70 | kIsMove, |
| 71 | kSetsConst, |
| 72 | kFormat35c, |
| 73 | kFormat3rc, |
| 74 | kNullCheckSrc0, // Null check of uses[0]. |
| 75 | kNullCheckSrc1, // Null check of uses[1]. |
| 76 | kNullCheckSrc2, // Null check of uses[2]. |
| 77 | kNullCheckOut0, // Null check out outgoing arg0. |
| 78 | kDstNonNull, // May assume dst is non-null. |
| 79 | kRetNonNull, // May assume retval is non-null. |
| 80 | kNullTransferSrc0, // Object copy src[0] -> dst. |
| 81 | kNullTransferSrcN, // Phi null check state transfer. |
| 82 | kRangeCheckSrc1, // Range check of uses[1]. |
| 83 | kRangeCheckSrc2, // Range check of uses[2]. |
| 84 | kRangeCheckSrc3, // Range check of uses[3]. |
| 85 | kFPA, |
| 86 | kFPB, |
| 87 | kFPC, |
| 88 | kCoreA, |
| 89 | kCoreB, |
| 90 | kCoreC, |
| 91 | kRefA, |
| 92 | kRefB, |
| 93 | kRefC, |
| 94 | kUsesMethodStar, // Implicit use of Method*. |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 95 | kDoLVN, // Worth computing local value numbers. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 96 | }; |
| 97 | |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 98 | #define DF_NOP 0ULL |
| 99 | #define DF_UA (1ULL << kUA) |
| 100 | #define DF_UB (1ULL << kUB) |
| 101 | #define DF_UC (1ULL << kUC) |
| 102 | #define DF_A_WIDE (1ULL << kAWide) |
| 103 | #define DF_B_WIDE (1ULL << kBWide) |
| 104 | #define DF_C_WIDE (1ULL << kCWide) |
| 105 | #define DF_DA (1ULL << kDA) |
| 106 | #define DF_IS_MOVE (1ULL << kIsMove) |
| 107 | #define DF_SETS_CONST (1ULL << kSetsConst) |
| 108 | #define DF_FORMAT_35C (1ULL << kFormat35c) |
| 109 | #define DF_FORMAT_3RC (1ULL << kFormat3rc) |
| 110 | #define DF_NULL_CHK_0 (1ULL << kNullCheckSrc0) |
| 111 | #define DF_NULL_CHK_1 (1ULL << kNullCheckSrc1) |
| 112 | #define DF_NULL_CHK_2 (1ULL << kNullCheckSrc2) |
| 113 | #define DF_NULL_CHK_OUT0 (1ULL << kNullCheckOut0) |
| 114 | #define DF_NON_NULL_DST (1ULL << kDstNonNull) |
| 115 | #define DF_NON_NULL_RET (1ULL << kRetNonNull) |
| 116 | #define DF_NULL_TRANSFER_0 (1ULL << kNullTransferSrc0) |
| 117 | #define DF_NULL_TRANSFER_N (1ULL << kNullTransferSrcN) |
| 118 | #define DF_RANGE_CHK_1 (1ULL << kRangeCheckSrc1) |
| 119 | #define DF_RANGE_CHK_2 (1ULL << kRangeCheckSrc2) |
| 120 | #define DF_RANGE_CHK_3 (1ULL << kRangeCheckSrc3) |
| 121 | #define DF_FP_A (1ULL << kFPA) |
| 122 | #define DF_FP_B (1ULL << kFPB) |
| 123 | #define DF_FP_C (1ULL << kFPC) |
| 124 | #define DF_CORE_A (1ULL << kCoreA) |
| 125 | #define DF_CORE_B (1ULL << kCoreB) |
| 126 | #define DF_CORE_C (1ULL << kCoreC) |
| 127 | #define DF_REF_A (1ULL << kRefA) |
| 128 | #define DF_REF_B (1ULL << kRefB) |
| 129 | #define DF_REF_C (1ULL << kRefC) |
| 130 | #define DF_UMS (1ULL << kUsesMethodStar) |
| 131 | #define DF_LVN (1ULL << kDoLVN) |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 132 | |
| 133 | #define DF_HAS_USES (DF_UA | DF_UB | DF_UC) |
| 134 | |
| 135 | #define DF_HAS_DEFS (DF_DA) |
| 136 | |
| 137 | #define DF_HAS_NULL_CHKS (DF_NULL_CHK_0 | \ |
| 138 | DF_NULL_CHK_1 | \ |
| 139 | DF_NULL_CHK_2 | \ |
| 140 | DF_NULL_CHK_OUT0) |
| 141 | |
| 142 | #define DF_HAS_RANGE_CHKS (DF_RANGE_CHK_1 | \ |
| 143 | DF_RANGE_CHK_2 | \ |
| 144 | DF_RANGE_CHK_3) |
| 145 | |
| 146 | #define DF_HAS_NR_CHKS (DF_HAS_NULL_CHKS | \ |
| 147 | DF_HAS_RANGE_CHKS) |
| 148 | |
| 149 | #define DF_A_IS_REG (DF_UA | DF_DA) |
| 150 | #define DF_B_IS_REG (DF_UB) |
| 151 | #define DF_C_IS_REG (DF_UC) |
| 152 | #define DF_IS_GETTER_OR_SETTER (DF_IS_GETTER | DF_IS_SETTER) |
| 153 | #define DF_USES_FP (DF_FP_A | DF_FP_B | DF_FP_C) |
Bill Buzbee | 0b1191c | 2013-10-28 22:11:59 +0000 | [diff] [blame] | 154 | #define DF_NULL_TRANSFER (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N) |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 155 | enum OatMethodAttributes { |
| 156 | kIsLeaf, // Method is leaf. |
| 157 | kHasLoop, // Method contains simple loop. |
| 158 | }; |
| 159 | |
| 160 | #define METHOD_IS_LEAF (1 << kIsLeaf) |
| 161 | #define METHOD_HAS_LOOP (1 << kHasLoop) |
| 162 | |
| 163 | // Minimum field size to contain Dalvik v_reg number. |
| 164 | #define VREG_NUM_WIDTH 16 |
| 165 | |
| 166 | #define INVALID_SREG (-1) |
| 167 | #define INVALID_VREG (0xFFFFU) |
| 168 | #define INVALID_REG (0xFF) |
| 169 | #define INVALID_OFFSET (0xDEADF00FU) |
| 170 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 171 | #define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) |
| 172 | #define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) |
| 173 | #define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) |
| 174 | #define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) |
| 175 | #define MIR_INLINED (1 << kMIRInlined) |
| 176 | #define MIR_INLINED_PRED (1 << kMIRInlinedPred) |
| 177 | #define MIR_CALLEE (1 << kMIRCallee) |
| 178 | #define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck) |
| 179 | #define MIR_DUP (1 << kMIRDup) |
| 180 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 181 | #define BLOCK_NAME_LEN 80 |
| 182 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 183 | typedef uint16_t BasicBlockId; |
| 184 | static const BasicBlockId NullBasicBlockId = 0; |
| 185 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 186 | /* |
| 187 | * In general, vreg/sreg describe Dalvik registers that originated with dx. However, |
| 188 | * it is useful to have compiler-generated temporary registers and have them treated |
| 189 | * in the same manner as dx-generated virtual registers. This struct records the SSA |
| 190 | * name of compiler-introduced temporaries. |
| 191 | */ |
| 192 | struct CompilerTemp { |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame^] | 193 | int32_t v_reg; // Virtual register number for temporary. |
| 194 | int32_t s_reg_low; // SSA name for low Dalvik word. |
| 195 | }; |
| 196 | |
| 197 | enum CompilerTempType { |
| 198 | kCompilerTempVR, // A virtual register temporary. |
| 199 | kCompilerTempSpecialMethodPtr, // Temporary that keeps track of current method pointer. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 200 | }; |
| 201 | |
| 202 | // When debug option enabled, records effectiveness of null and range check elimination. |
| 203 | struct Checkstats { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 204 | int32_t null_checks; |
| 205 | int32_t null_checks_eliminated; |
| 206 | int32_t range_checks; |
| 207 | int32_t range_checks_eliminated; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 208 | }; |
| 209 | |
| 210 | // Dataflow attributes of a basic block. |
| 211 | struct BasicBlockDataFlow { |
| 212 | ArenaBitVector* use_v; |
| 213 | ArenaBitVector* def_v; |
| 214 | ArenaBitVector* live_in_v; |
| 215 | ArenaBitVector* phi_v; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 216 | int32_t* vreg_to_ssa_map; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 217 | ArenaBitVector* ending_null_check_v; |
| 218 | }; |
| 219 | |
| 220 | /* |
| 221 | * Normalized use/def for a MIR operation using SSA names rather than vregs. Note that |
| 222 | * uses/defs retain the Dalvik convention that long operations operate on a pair of 32-bit |
| 223 | * vregs. For example, "ADD_LONG v0, v2, v3" would have 2 defs (v0/v1) and 4 uses (v2/v3, v4/v5). |
| 224 | * Following SSA renaming, this is the primary struct used by code generators to locate |
| 225 | * operand and result registers. This is a somewhat confusing and unhelpful convention that |
| 226 | * we may want to revisit in the future. |
| 227 | */ |
| 228 | struct SSARepresentation { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 229 | int16_t num_uses; |
| 230 | int16_t num_defs; |
| 231 | int32_t* uses; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 232 | bool* fp_use; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 233 | int32_t* defs; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 234 | bool* fp_def; |
| 235 | }; |
| 236 | |
| 237 | /* |
| 238 | * The Midlevel Intermediate Representation node, which may be largely considered a |
| 239 | * wrapper around a Dalvik byte code. |
| 240 | */ |
| 241 | struct MIR { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 242 | /* |
| 243 | * TODO: remove embedded DecodedInstruction to save space, keeping only opcode. Recover |
| 244 | * additional fields on as-needed basis. Question: how to support MIR Pseudo-ops; probably |
| 245 | * need to carry aux data pointer. |
| 246 | */ |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 247 | DecodedInstruction dalvikInsn; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 248 | uint16_t width; // Note: width can include switch table or fill array data. |
| 249 | NarrowDexOffset offset; // Offset of the instruction in code units. |
| 250 | uint16_t optimization_flags; |
| 251 | int16_t m_unit_index; // From which method was this MIR included |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 252 | MIR* next; |
| 253 | SSARepresentation* ssa_rep; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 254 | union { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 255 | // Incoming edges for phi node. |
| 256 | BasicBlockId* phi_incoming; |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 257 | // Establish link from check instruction (kMirOpCheck) to the actual throwing instruction. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 258 | MIR* throw_insn; |
Vladimir Marko | a894607 | 2014-01-22 10:30:44 +0000 | [diff] [blame] | 259 | // Fused cmp branch condition. |
| 260 | ConditionCode ccode; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 261 | } meta; |
| 262 | }; |
| 263 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 264 | struct SuccessorBlockInfo; |
| 265 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 266 | struct BasicBlock { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 267 | BasicBlockId id; |
| 268 | BasicBlockId dfs_id; |
| 269 | NarrowDexOffset start_offset; // Offset in code units. |
| 270 | BasicBlockId fall_through; |
| 271 | BasicBlockId taken; |
| 272 | BasicBlockId i_dom; // Immediate dominator. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 273 | uint16_t nesting_depth; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 274 | BBType block_type:4; |
| 275 | BlockListType successor_block_list_type:4; |
| 276 | bool visited:1; |
| 277 | bool hidden:1; |
| 278 | bool catch_entry:1; |
| 279 | bool explicit_throw:1; |
| 280 | bool conditional_branch:1; |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 281 | bool terminated_by_return:1; // Block ends with a Dalvik return opcode. |
| 282 | bool dominates_return:1; // Is a member of return extended basic block. |
| 283 | bool use_lvn:1; // Run local value numbering on this block. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 284 | MIR* first_mir_insn; |
| 285 | MIR* last_mir_insn; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 286 | BasicBlockDataFlow* data_flow_info; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 287 | ArenaBitVector* dominators; |
| 288 | ArenaBitVector* i_dominated; // Set nodes being immediately dominated. |
| 289 | ArenaBitVector* dom_frontier; // Dominance frontier. |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 290 | GrowableArray<BasicBlockId>* predecessors; |
| 291 | GrowableArray<SuccessorBlockInfo*>* successor_blocks; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 292 | }; |
| 293 | |
| 294 | /* |
| 295 | * The "blocks" field in "successor_block_list" points to an array of elements with the type |
| 296 | * "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For swtich |
| 297 | * blocks, key is the case value. |
| 298 | */ |
| 299 | struct SuccessorBlockInfo { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 300 | BasicBlockId block; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 301 | int key; |
| 302 | }; |
| 303 | |
| 304 | /* |
| 305 | * Whereas a SSA name describes a definition of a Dalvik vreg, the RegLocation describes |
| 306 | * the type of an SSA name (and, can also be used by code generators to record where the |
| 307 | * value is located (i.e. - physical register, frame, spill, etc.). For each SSA name (SReg) |
| 308 | * there is a RegLocation. |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 309 | * A note on SSA names: |
| 310 | * o SSA names for Dalvik vRegs v0..vN will be assigned 0..N. These represent the "vN_0" |
| 311 | * names. Negative SSA names represent special values not present in the Dalvik byte code. |
| 312 | * For example, SSA name -1 represents an invalid SSA name, and SSA name -2 represents the |
| 313 | * the Method pointer. SSA names < -2 are reserved for future use. |
| 314 | * o The vN_0 names for non-argument Dalvik should in practice never be used (as they would |
| 315 | * represent the read of an undefined local variable). The first definition of the |
| 316 | * underlying Dalvik vReg will result in a vN_1 name. |
| 317 | * |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 318 | * FIXME: The orig_sreg field was added as a workaround for llvm bitcode generation. With |
| 319 | * the latest restructuring, we should be able to remove it and rely on s_reg_low throughout. |
| 320 | */ |
| 321 | struct RegLocation { |
| 322 | RegLocationType location:3; |
| 323 | unsigned wide:1; |
| 324 | unsigned defined:1; // Do we know the type? |
| 325 | unsigned is_const:1; // Constant, value in mir_graph->constant_values[]. |
| 326 | unsigned fp:1; // Floating point? |
| 327 | unsigned core:1; // Non-floating point? |
| 328 | unsigned ref:1; // Something GC cares about. |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 329 | unsigned high_word:1; // High word of pair? |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 330 | unsigned home:1; // Does this represent the home location? |
Bill Buzbee | d61ba4b | 2014-01-13 21:44:01 +0000 | [diff] [blame] | 331 | VectorLengthType vec_len:3; // Is this value in a vector register, and how big is it? |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 332 | uint8_t low_reg; // First physical register. |
| 333 | uint8_t high_reg; // 2nd physical register (if wide). |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 334 | int16_t s_reg_low; // SSA name for low Dalvik word. |
| 335 | int16_t orig_sreg; // TODO: remove after Bitcode gen complete |
| 336 | // and consolidate usage w/ s_reg_low. |
Bill Buzbee | d61ba4b | 2014-01-13 21:44:01 +0000 | [diff] [blame] | 337 | |
| 338 | bool IsVectorScalar() const { return vec_len == kVectorLength4 || vec_len == kVectorLength8;} |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 339 | }; |
| 340 | |
| 341 | /* |
| 342 | * Collection of information describing an invoke, and the destination of |
| 343 | * the subsequent MOVE_RESULT (if applicable). Collected as a unit to enable |
| 344 | * more efficient invoke code generation. |
| 345 | */ |
| 346 | struct CallInfo { |
| 347 | int num_arg_words; // Note: word count, not arg count. |
| 348 | RegLocation* args; // One for each word of arguments. |
| 349 | RegLocation result; // Eventual target of MOVE_RESULT. |
| 350 | int opt_flags; |
| 351 | InvokeType type; |
| 352 | uint32_t dex_idx; |
| 353 | uint32_t index; // Method idx for invokes, type idx for FilledNewArray. |
| 354 | uintptr_t direct_code; |
| 355 | uintptr_t direct_method; |
| 356 | RegLocation target; // Target of following move_result. |
| 357 | bool skip_this; |
| 358 | bool is_range; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 359 | DexOffset offset; // Offset in code units. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 360 | }; |
| 361 | |
| 362 | |
Bill Buzbee | d61ba4b | 2014-01-13 21:44:01 +0000 | [diff] [blame] | 363 | const RegLocation bad_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0, kVectorNotUsed, |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 364 | INVALID_REG, INVALID_REG, INVALID_SREG, INVALID_SREG}; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 365 | |
| 366 | class MIRGraph { |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 367 | public: |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 368 | MIRGraph(CompilationUnit* cu, ArenaAllocator* arena); |
Ian Rogers | 6282dc1 | 2013-04-18 15:54:02 -0700 | [diff] [blame] | 369 | ~MIRGraph(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 370 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 371 | /* |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 372 | * Examine the graph to determine whether it's worthwile to spend the time compiling |
| 373 | * this method. |
| 374 | */ |
| 375 | bool SkipCompilation(Runtime::CompilerFilter compiler_filter); |
| 376 | |
| 377 | /* |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 378 | * Parse dex method and add MIR at current insert point. Returns id (which is |
| 379 | * actually the index of the method in the m_units_ array). |
| 380 | */ |
| 381 | void InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, |
Ian Rogers | 8b2c0b9 | 2013-09-19 02:56:49 -0700 | [diff] [blame] | 382 | InvokeType invoke_type, uint16_t class_def_idx, |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 383 | uint32_t method_idx, jobject class_loader, const DexFile& dex_file); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 384 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 385 | /* Find existing block */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 386 | BasicBlock* FindBlock(DexOffset code_offset) { |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 387 | return FindBlock(code_offset, false, false, NULL); |
| 388 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 389 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 390 | const uint16_t* GetCurrentInsns() const { |
| 391 | return current_code_item_->insns_; |
| 392 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 393 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 394 | const uint16_t* GetInsns(int m_unit_index) const { |
| 395 | return m_units_[m_unit_index]->GetCodeItem()->insns_; |
| 396 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 397 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 398 | int GetNumBlocks() const { |
| 399 | return num_blocks_; |
| 400 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 401 | |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 402 | size_t GetNumDalvikInsns() const { |
| 403 | return cu_->code_item->insns_size_in_code_units_; |
| 404 | } |
| 405 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 406 | ArenaBitVector* GetTryBlockAddr() const { |
| 407 | return try_block_addr_; |
| 408 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 409 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 410 | BasicBlock* GetEntryBlock() const { |
| 411 | return entry_block_; |
| 412 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 413 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 414 | BasicBlock* GetExitBlock() const { |
| 415 | return exit_block_; |
| 416 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 417 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 418 | BasicBlock* GetBasicBlock(int block_id) const { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 419 | return (block_id == NullBasicBlockId) ? NULL : block_list_.Get(block_id); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 420 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 421 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 422 | size_t GetBasicBlockListCount() const { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 423 | return block_list_.Size(); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 424 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 425 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 426 | GrowableArray<BasicBlock*>* GetBlockList() { |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 427 | return &block_list_; |
| 428 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 429 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 430 | GrowableArray<BasicBlockId>* GetDfsOrder() { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 431 | return dfs_order_; |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 432 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 433 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 434 | GrowableArray<BasicBlockId>* GetDfsPostOrder() { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 435 | return dfs_post_order_; |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 436 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 437 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 438 | GrowableArray<BasicBlockId>* GetDomPostOrder() { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 439 | return dom_post_order_traversal_; |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 440 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 441 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 442 | int GetDefCount() const { |
| 443 | return def_count_; |
| 444 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 445 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 446 | ArenaAllocator* GetArena() { |
| 447 | return arena_; |
| 448 | } |
| 449 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 450 | void EnableOpcodeCounting() { |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 451 | opcode_count_ = static_cast<int*>(arena_->Alloc(kNumPackedOpcodes * sizeof(int), |
| 452 | ArenaAllocator::kAllocMisc)); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 453 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 454 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 455 | void ShowOpcodeStats(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 456 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 457 | DexCompilationUnit* GetCurrentDexCompilationUnit() const { |
| 458 | return m_units_[current_method_]; |
| 459 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 460 | |
Jean Christophe Beyler | d0a5155 | 2014-01-10 14:18:31 -0800 | [diff] [blame] | 461 | /** |
| 462 | * @brief Dump a CFG into a dot file format. |
| 463 | * @param dir_prefix the directory the file will be created in. |
| 464 | * @param all_blocks does the dumper use all the basic blocks or use the reachable blocks. |
| 465 | * @param suffix does the filename require a suffix or not (default = nullptr). |
| 466 | */ |
| 467 | void DumpCFG(const char* dir_prefix, bool all_blocks, const char* suffix = nullptr); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 468 | |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 469 | void InitRegLocations(); |
| 470 | |
| 471 | void RemapRegLocations(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 472 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 473 | void DumpRegLocTable(RegLocation* table, int count); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 474 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 475 | void BasicBlockOptimization(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 476 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 477 | bool IsConst(int32_t s_reg) const { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 478 | return is_constant_v_->IsBitSet(s_reg); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 479 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 480 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 481 | bool IsConst(RegLocation loc) const { |
Mark Mendell | 5bb149e | 2013-12-17 13:26:54 -0800 | [diff] [blame] | 482 | return loc.orig_sreg < 0 ? false : IsConst(loc.orig_sreg); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 483 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 484 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 485 | int32_t ConstantValue(RegLocation loc) const { |
| 486 | DCHECK(IsConst(loc)); |
| 487 | return constant_values_[loc.orig_sreg]; |
| 488 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 489 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 490 | int32_t ConstantValue(int32_t s_reg) const { |
| 491 | DCHECK(IsConst(s_reg)); |
| 492 | return constant_values_[s_reg]; |
| 493 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 494 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 495 | int64_t ConstantValueWide(RegLocation loc) const { |
| 496 | DCHECK(IsConst(loc)); |
| 497 | return (static_cast<int64_t>(constant_values_[loc.orig_sreg + 1]) << 32) | |
| 498 | Low32Bits(static_cast<int64_t>(constant_values_[loc.orig_sreg])); |
| 499 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 500 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 501 | bool IsConstantNullRef(RegLocation loc) const { |
| 502 | return loc.ref && loc.is_const && (ConstantValue(loc) == 0); |
| 503 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 504 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 505 | int GetNumSSARegs() const { |
| 506 | return num_ssa_regs_; |
| 507 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 508 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 509 | void SetNumSSARegs(int new_num) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 510 | /* |
| 511 | * TODO: It's theoretically possible to exceed 32767, though any cases which did |
| 512 | * would be filtered out with current settings. When orig_sreg field is removed |
| 513 | * from RegLocation, expand s_reg_low to handle all possible cases and remove DCHECK(). |
| 514 | */ |
| 515 | DCHECK_EQ(new_num, static_cast<int16_t>(new_num)); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 516 | num_ssa_regs_ = new_num; |
| 517 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 518 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 519 | unsigned int GetNumReachableBlocks() const { |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 520 | return num_reachable_blocks_; |
| 521 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 522 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 523 | int GetUseCount(int vreg) const { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 524 | return use_counts_.Get(vreg); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 525 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 526 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 527 | int GetRawUseCount(int vreg) const { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 528 | return raw_use_counts_.Get(vreg); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 529 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 530 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 531 | int GetSSASubscript(int ssa_reg) const { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 532 | return ssa_subscripts_->Get(ssa_reg); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 533 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 534 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 535 | RegLocation GetRawSrc(MIR* mir, int num) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 536 | DCHECK(num < mir->ssa_rep->num_uses); |
| 537 | RegLocation res = reg_location_[mir->ssa_rep->uses[num]]; |
| 538 | return res; |
| 539 | } |
| 540 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 541 | RegLocation GetRawDest(MIR* mir) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 542 | DCHECK_GT(mir->ssa_rep->num_defs, 0); |
| 543 | RegLocation res = reg_location_[mir->ssa_rep->defs[0]]; |
| 544 | return res; |
| 545 | } |
| 546 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 547 | RegLocation GetDest(MIR* mir) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 548 | RegLocation res = GetRawDest(mir); |
| 549 | DCHECK(!res.wide); |
| 550 | return res; |
| 551 | } |
| 552 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 553 | RegLocation GetSrc(MIR* mir, int num) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 554 | RegLocation res = GetRawSrc(mir, num); |
| 555 | DCHECK(!res.wide); |
| 556 | return res; |
| 557 | } |
| 558 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 559 | RegLocation GetDestWide(MIR* mir) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 560 | RegLocation res = GetRawDest(mir); |
| 561 | DCHECK(res.wide); |
| 562 | return res; |
| 563 | } |
| 564 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 565 | RegLocation GetSrcWide(MIR* mir, int low) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 566 | RegLocation res = GetRawSrc(mir, low); |
| 567 | DCHECK(res.wide); |
| 568 | return res; |
| 569 | } |
| 570 | |
| 571 | RegLocation GetBadLoc() { |
| 572 | return bad_loc; |
| 573 | } |
| 574 | |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame^] | 575 | int GetMethodSReg() const { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 576 | return method_sreg_; |
| 577 | } |
| 578 | |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame^] | 579 | /** |
| 580 | * @brief Used to obtain the number of compiler temporaries being used. |
| 581 | * @return Returns the number of compiler temporaries. |
| 582 | */ |
| 583 | size_t GetNumUsedCompilerTemps() const { |
| 584 | size_t total_num_temps = compiler_temps_.Size(); |
| 585 | DCHECK_LE(num_non_special_compiler_temps_, total_num_temps); |
| 586 | return total_num_temps; |
| 587 | } |
| 588 | |
| 589 | /** |
| 590 | * @brief Used to obtain the number of non-special compiler temporaries being used. |
| 591 | * @return Returns the number of non-special compiler temporaries. |
| 592 | */ |
| 593 | size_t GetNumNonSpecialCompilerTemps() const { |
| 594 | return num_non_special_compiler_temps_; |
| 595 | } |
| 596 | |
| 597 | /** |
| 598 | * @brief Used to set the total number of available non-special compiler temporaries. |
| 599 | * @details Can fail setting the new max if there are more temps being used than the new_max. |
| 600 | * @param new_max The new maximum number of non-special compiler temporaries. |
| 601 | * @return Returns true if the max was set and false if failed to set. |
| 602 | */ |
| 603 | bool SetMaxAvailableNonSpecialCompilerTemps(size_t new_max) { |
| 604 | if (new_max < GetNumNonSpecialCompilerTemps()) { |
| 605 | return false; |
| 606 | } else { |
| 607 | max_available_non_special_compiler_temps_ = new_max; |
| 608 | return true; |
| 609 | } |
| 610 | } |
| 611 | |
| 612 | /** |
| 613 | * @brief Provides the number of non-special compiler temps available. |
| 614 | * @details Even if this returns zero, special compiler temps are guaranteed to be available. |
| 615 | * @return Returns the number of available temps. |
| 616 | */ |
| 617 | size_t GetNumAvailableNonSpecialCompilerTemps(); |
| 618 | |
| 619 | /** |
| 620 | * @brief Used to obtain an existing compiler temporary. |
| 621 | * @param index The index of the temporary which must be strictly less than the |
| 622 | * number of temporaries. |
| 623 | * @return Returns the temporary that was asked for. |
| 624 | */ |
| 625 | CompilerTemp* GetCompilerTemp(size_t index) const { |
| 626 | return compiler_temps_.Get(index); |
| 627 | } |
| 628 | |
| 629 | /** |
| 630 | * @brief Used to obtain the maximum number of compiler temporaries that can be requested. |
| 631 | * @return Returns the maximum number of compiler temporaries, whether used or not. |
| 632 | */ |
| 633 | size_t GetMaxPossibleCompilerTemps() const { |
| 634 | return max_available_special_compiler_temps_ + max_available_non_special_compiler_temps_; |
| 635 | } |
| 636 | |
| 637 | /** |
| 638 | * @brief Used to obtain a new unique compiler temporary. |
| 639 | * @param ct_type Type of compiler temporary requested. |
| 640 | * @param wide Whether we should allocate a wide temporary. |
| 641 | * @return Returns the newly created compiler temporary. |
| 642 | */ |
| 643 | CompilerTemp* GetNewCompilerTemp(CompilerTempType ct_type, bool wide); |
| 644 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 645 | bool MethodIsLeaf() { |
| 646 | return attributes_ & METHOD_IS_LEAF; |
| 647 | } |
| 648 | |
| 649 | RegLocation GetRegLocation(int index) { |
| 650 | DCHECK((index >= 0) && (index > num_ssa_regs_)); |
| 651 | return reg_location_[index]; |
| 652 | } |
| 653 | |
| 654 | RegLocation GetMethodLoc() { |
| 655 | return reg_location_[method_sreg_]; |
| 656 | } |
| 657 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 658 | bool IsBackedge(BasicBlock* branch_bb, BasicBlockId target_bb_id) { |
| 659 | return ((target_bb_id != NullBasicBlockId) && |
| 660 | (GetBasicBlock(target_bb_id)->start_offset <= branch_bb->start_offset)); |
buzbee | 9329e6d | 2013-08-19 12:55:10 -0700 | [diff] [blame] | 661 | } |
| 662 | |
| 663 | bool IsBackwardsBranch(BasicBlock* branch_bb) { |
| 664 | return IsBackedge(branch_bb, branch_bb->taken) || IsBackedge(branch_bb, branch_bb->fall_through); |
| 665 | } |
| 666 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 667 | void CountBranch(DexOffset target_offset) { |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 668 | if (target_offset <= current_offset_) { |
| 669 | backward_branches_++; |
| 670 | } else { |
| 671 | forward_branches_++; |
| 672 | } |
| 673 | } |
| 674 | |
| 675 | int GetBranchCount() { |
| 676 | return backward_branches_ + forward_branches_; |
| 677 | } |
| 678 | |
| 679 | bool IsPseudoMirOp(Instruction::Code opcode) { |
| 680 | return static_cast<int>(opcode) >= static_cast<int>(kMirOpFirst); |
| 681 | } |
| 682 | |
| 683 | bool IsPseudoMirOp(int opcode) { |
| 684 | return opcode >= static_cast<int>(kMirOpFirst); |
| 685 | } |
| 686 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 687 | void DumpCheckStats(); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 688 | MIR* FindMoveResult(BasicBlock* bb, MIR* mir); |
| 689 | int SRegToVReg(int ssa_reg) const; |
| 690 | void VerifyDataflow(); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 691 | void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb); |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 692 | bool EliminateNullChecksAndInferTypes(BasicBlock *bb); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 693 | /* |
| 694 | * Type inference handling helpers. Because Dalvik's bytecode is not fully typed, |
| 695 | * we have to do some work to figure out the sreg type. For some operations it is |
| 696 | * clear based on the opcode (i.e. ADD_FLOAT v0, v1, v2), but for others (MOVE), we |
| 697 | * may never know the "real" type. |
| 698 | * |
| 699 | * We perform the type inference operation by using an iterative walk over |
| 700 | * the graph, propagating types "defined" by typed opcodes to uses and defs in |
| 701 | * non-typed opcodes (such as MOVE). The Setxx(index) helpers are used to set defined |
| 702 | * types on typed opcodes (such as ADD_INT). The Setxx(index, is_xx) form is used to |
| 703 | * propagate types through non-typed opcodes such as PHI and MOVE. The is_xx flag |
| 704 | * tells whether our guess of the type is based on a previously typed definition. |
| 705 | * If so, the defined type takes precedence. Note that it's possible to have the same sreg |
| 706 | * show multiple defined types because dx treats constants as untyped bit patterns. |
| 707 | * The return value of the Setxx() helpers says whether or not the Setxx() action changed |
| 708 | * the current guess, and is used to know when to terminate the iterative walk. |
| 709 | */ |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 710 | bool SetFp(int index, bool is_fp); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 711 | bool SetFp(int index); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 712 | bool SetCore(int index, bool is_core); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 713 | bool SetCore(int index); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 714 | bool SetRef(int index, bool is_ref); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 715 | bool SetRef(int index); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 716 | bool SetWide(int index, bool is_wide); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 717 | bool SetWide(int index); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 718 | bool SetHigh(int index, bool is_high); |
buzbee | 28c2300 | 2013-09-07 09:12:27 -0700 | [diff] [blame] | 719 | bool SetHigh(int index); |
| 720 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 721 | void AppendMIR(BasicBlock* bb, MIR* mir); |
| 722 | void PrependMIR(BasicBlock* bb, MIR* mir); |
| 723 | void InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir); |
| 724 | char* GetDalvikDisassembly(const MIR* mir); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 725 | void ReplaceSpecialChars(std::string& str); |
| 726 | std::string GetSSAName(int ssa_reg); |
| 727 | std::string GetSSANameWithConst(int ssa_reg, bool singles_only); |
| 728 | void GetBlockName(BasicBlock* bb, char* name); |
| 729 | const char* GetShortyFromTargetIdx(int); |
| 730 | void DumpMIRGraph(); |
| 731 | CallInfo* NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, bool is_range); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 732 | BasicBlock* NewMemBB(BBType block_type, int block_id); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 733 | MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir); |
| 734 | BasicBlock* NextDominatedBlock(BasicBlock* bb); |
| 735 | bool LayoutBlocks(BasicBlock* bb); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 736 | |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 737 | /** |
| 738 | * @brief Perform the initial preparation for the Method Uses. |
| 739 | */ |
| 740 | void InitializeMethodUses(); |
| 741 | |
| 742 | /** |
| 743 | * @brief Perform the initial preparation for the Constant Propagation. |
| 744 | */ |
| 745 | void InitializeConstantPropagation(); |
| 746 | |
| 747 | /** |
| 748 | * @brief Perform the initial preparation for the SSA Transformation. |
| 749 | */ |
| 750 | void InitializeSSATransformation(); |
| 751 | |
| 752 | /** |
| 753 | * @brief Insert a the operands for the Phi nodes. |
| 754 | * @param bb the considered BasicBlock. |
| 755 | * @return true |
| 756 | */ |
| 757 | bool InsertPhiNodeOperands(BasicBlock* bb); |
| 758 | |
| 759 | /** |
| 760 | * @brief Perform constant propagation on a BasicBlock. |
| 761 | * @param bb the considered BasicBlock. |
| 762 | */ |
| 763 | void DoConstantPropagation(BasicBlock* bb); |
| 764 | |
| 765 | /** |
| 766 | * @brief Count the uses in the BasicBlock |
| 767 | * @param bb the BasicBlock |
| 768 | */ |
| 769 | void CountUses(struct BasicBlock* bb); |
| 770 | |
| 771 | /** |
| 772 | * @brief Initialize the data structures with Null Check data |
| 773 | * @param bb the considered BasicBlock |
| 774 | */ |
| 775 | void NullCheckEliminationInit(BasicBlock* bb); |
| 776 | |
| 777 | /** |
| 778 | * @brief Check if the temporary ssa register vector is allocated |
| 779 | */ |
| 780 | void CheckSSARegisterVector(); |
| 781 | |
| 782 | /** |
| 783 | * @brief Combine BasicBlocks |
| 784 | * @param the BasicBlock we are considering |
| 785 | */ |
| 786 | void CombineBlocks(BasicBlock* bb); |
| 787 | |
| 788 | void ClearAllVisitedFlags(); |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 789 | /* |
| 790 | * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on |
| 791 | * we can verify that all catch entries have native PC entries. |
| 792 | */ |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 793 | std::set<uint32_t> catches_; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 794 | |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 795 | // TODO: make these private. |
| 796 | RegLocation* reg_location_; // Map SSA names to location. |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 797 | SafeMap<unsigned int, unsigned int> block_id_map_; // Block collapse lookup cache. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 798 | |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 799 | static const uint64_t oat_data_flow_attributes_[kMirOpLast]; |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 800 | static const char* extended_mir_op_names_[kMirOpLast - kMirOpFirst]; |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 801 | static const uint32_t analysis_attributes_[kMirOpLast]; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 802 | |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 803 | private: |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 804 | int FindCommonParent(int block1, int block2); |
| 805 | void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, |
| 806 | const ArenaBitVector* src2); |
| 807 | void HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, |
| 808 | ArenaBitVector* live_in_v, int dalvik_reg_id); |
| 809 | void HandleDef(ArenaBitVector* def_v, int dalvik_reg_id); |
| 810 | void CompilerInitializeSSAConversion(); |
| 811 | bool DoSSAConversion(BasicBlock* bb); |
| 812 | bool InvokeUsesMethodStar(MIR* mir); |
| 813 | int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction); |
| 814 | bool ContentIsInsn(const uint16_t* code_ptr); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 815 | BasicBlock* SplitBlock(DexOffset code_offset, BasicBlock* orig_block, |
Ian Rogers | 71fe267 | 2013-03-19 20:45:02 -0700 | [diff] [blame] | 816 | BasicBlock** immed_pred_block_p); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 817 | BasicBlock* FindBlock(DexOffset code_offset, bool split, bool create, |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 818 | BasicBlock** immed_pred_block_p); |
| 819 | void ProcessTryCatchBlocks(); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 820 | BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 821 | int flags, const uint16_t* code_ptr, const uint16_t* code_end); |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 822 | BasicBlock* ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
| 823 | int flags); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 824 | BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 825 | int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr, |
| 826 | const uint16_t* code_end); |
| 827 | int AddNewSReg(int v_reg); |
| 828 | void HandleSSAUse(int* uses, int dalvik_reg, int reg_index); |
| 829 | void HandleSSADef(int* defs, int dalvik_reg, int reg_index); |
| 830 | void DataFlowSSAFormat35C(MIR* mir); |
| 831 | void DataFlowSSAFormat3RC(MIR* mir); |
| 832 | bool FindLocalLiveIn(BasicBlock* bb); |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 833 | bool InferTypeAndSize(BasicBlock* bb, MIR* mir, bool changed); |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 834 | bool VerifyPredInfo(BasicBlock* bb); |
| 835 | BasicBlock* NeedsVisit(BasicBlock* bb); |
| 836 | BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb); |
| 837 | void MarkPreOrder(BasicBlock* bb); |
| 838 | void RecordDFSOrders(BasicBlock* bb); |
| 839 | void ComputeDFSOrders(); |
| 840 | void ComputeDefBlockMatrix(); |
| 841 | void ComputeDomPostOrderTraversal(BasicBlock* bb); |
| 842 | void ComputeDominators(); |
| 843 | void InsertPhiNodes(); |
| 844 | void DoDFSPreOrderSSARename(BasicBlock* block); |
| 845 | void SetConstant(int32_t ssa_reg, int value); |
| 846 | void SetConstantWide(int ssa_reg, int64_t value); |
| 847 | int GetSSAUseCount(int s_reg); |
| 848 | bool BasicBlockOpt(BasicBlock* bb); |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 849 | bool BuildExtendedBBList(struct BasicBlock* bb); |
| 850 | bool FillDefBlockMatrix(BasicBlock* bb); |
| 851 | void InitializeDominationInfo(BasicBlock* bb); |
| 852 | bool ComputeblockIDom(BasicBlock* bb); |
| 853 | bool ComputeBlockDominators(BasicBlock* bb); |
| 854 | bool SetDominators(BasicBlock* bb); |
| 855 | bool ComputeBlockLiveIns(BasicBlock* bb); |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 856 | bool ComputeDominanceFrontier(BasicBlock* bb); |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 857 | |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 858 | void CountChecks(BasicBlock* bb); |
buzbee | ee17e0a | 2013-07-31 10:47:37 -0700 | [diff] [blame] | 859 | void AnalyzeBlock(BasicBlock* bb, struct MethodStats* stats); |
| 860 | bool ComputeSkipCompilation(struct MethodStats* stats, bool skip_default); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 861 | |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 862 | CompilationUnit* const cu_; |
| 863 | GrowableArray<int>* ssa_base_vregs_; |
| 864 | GrowableArray<int>* ssa_subscripts_; |
| 865 | // Map original Dalvik virtual reg i to the current SSA name. |
| 866 | int* vreg_to_ssa_map_; // length == method->registers_size |
| 867 | int* ssa_last_defs_; // length == method->registers_size |
| 868 | ArenaBitVector* is_constant_v_; // length == num_ssa_reg |
| 869 | int* constant_values_; // length == num_ssa_reg |
| 870 | // Use counts of ssa names. |
| 871 | GrowableArray<uint32_t> use_counts_; // Weighted by nesting depth |
| 872 | GrowableArray<uint32_t> raw_use_counts_; // Not weighted |
| 873 | unsigned int num_reachable_blocks_; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 874 | GrowableArray<BasicBlockId>* dfs_order_; |
| 875 | GrowableArray<BasicBlockId>* dfs_post_order_; |
| 876 | GrowableArray<BasicBlockId>* dom_post_order_traversal_; |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 877 | int* i_dom_list_; |
| 878 | ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks. |
| 879 | ArenaBitVector* temp_block_v_; |
| 880 | ArenaBitVector* temp_dalvik_register_v_; |
| 881 | ArenaBitVector* temp_ssa_register_v_; // num_ssa_regs. |
| 882 | static const int kInvalidEntry = -1; |
| 883 | GrowableArray<BasicBlock*> block_list_; |
| 884 | ArenaBitVector* try_block_addr_; |
| 885 | BasicBlock* entry_block_; |
| 886 | BasicBlock* exit_block_; |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 887 | int num_blocks_; |
| 888 | const DexFile::CodeItem* current_code_item_; |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 889 | GrowableArray<uint16_t> dex_pc_to_block_map_; // FindBlock lookup cache. |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 890 | std::vector<DexCompilationUnit*> m_units_; // List of methods included in this graph |
| 891 | typedef std::pair<int, int> MIRLocation; // Insert point, (m_unit_ index, offset) |
| 892 | std::vector<MIRLocation> method_stack_; // Include stack |
| 893 | int current_method_; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 894 | DexOffset current_offset_; // Offset in code units |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 895 | int def_count_; // Used to estimate size of ssa name storage. |
| 896 | int* opcode_count_; // Dex opcode coverage stats. |
| 897 | int num_ssa_regs_; // Number of names following SSA transformation. |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 898 | std::vector<BasicBlockId> extended_basic_blocks_; // Heads of block "traces". |
Brian Carlstrom | 6f485c6 | 2013-07-18 15:35:35 -0700 | [diff] [blame] | 899 | int method_sreg_; |
| 900 | unsigned int attributes_; |
| 901 | Checkstats* checkstats_; |
| 902 | ArenaAllocator* arena_; |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 903 | int backward_branches_; |
| 904 | int forward_branches_; |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame^] | 905 | GrowableArray<CompilerTemp*> compiler_temps_; |
| 906 | size_t num_non_special_compiler_temps_; |
| 907 | size_t max_available_non_special_compiler_temps_; |
| 908 | size_t max_available_special_compiler_temps_; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 909 | }; |
| 910 | |
| 911 | } // namespace art |
| 912 | |
Brian Carlstrom | fc0e321 | 2013-07-17 14:40:12 -0700 | [diff] [blame] | 913 | #endif // ART_COMPILER_DEX_MIR_GRAPH_H_ |