mir_graph.h revision 4e97c539408f47145526f0062c1c06df99146a73
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 17#ifndef ART_COMPILER_DEX_MIR_GRAPH_H_ 18#define ART_COMPILER_DEX_MIR_GRAPH_H_ 19 20#include "dex_file.h" 21#include "dex_instruction.h" 22#include "compiler_ir.h" 23#include "arena_bit_vector.h" 24#include "growable_array.h" 25 26namespace art { 27 28enum 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, 41 kMoveOp, 42 kSwitch 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) 59#define AN_SWITCH (1 << kSwitch) 60#define AN_COMPUTATIONAL (AN_MATH | AN_ARRAYOP | AN_MOVE | AN_SIMPLECONST) 61 62enum 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*. 95 kDoLVN, // Worth computing local value numbers. 96}; 97 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) 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) 154#define DF_NULL_TRANSFER (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N) 155enum 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 171/* SSA encodings for special registers */ 172#define SSA_METHOD_BASEREG (-2) 173/* First compiler temp basereg, grows smaller */ 174#define SSA_CTEMP_BASEREG (SSA_METHOD_BASEREG - 1) 175 176#define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) 177#define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) 178#define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) 179#define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) 180#define MIR_INLINED (1 << kMIRInlined) 181#define MIR_INLINED_PRED (1 << kMIRInlinedPred) 182#define MIR_CALLEE (1 << kMIRCallee) 183#define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck) 184#define MIR_DUP (1 << kMIRDup) 185 186#define BLOCK_NAME_LEN 80 187 188typedef uint16_t BasicBlockId; 189static const BasicBlockId NullBasicBlockId = 0; 190 191/* 192 * In general, vreg/sreg describe Dalvik registers that originated with dx. However, 193 * it is useful to have compiler-generated temporary registers and have them treated 194 * in the same manner as dx-generated virtual registers. This struct records the SSA 195 * name of compiler-introduced temporaries. 196 */ 197struct CompilerTemp { 198 int32_t s_reg; 199}; 200 201// When debug option enabled, records effectiveness of null and range check elimination. 202struct Checkstats { 203 int32_t null_checks; 204 int32_t null_checks_eliminated; 205 int32_t range_checks; 206 int32_t range_checks_eliminated; 207}; 208 209// Dataflow attributes of a basic block. 210struct BasicBlockDataFlow { 211 ArenaBitVector* use_v; 212 ArenaBitVector* def_v; 213 ArenaBitVector* live_in_v; 214 ArenaBitVector* phi_v; 215 int32_t* vreg_to_ssa_map; 216 ArenaBitVector* ending_null_check_v; 217}; 218 219/* 220 * Normalized use/def for a MIR operation using SSA names rather than vregs. Note that 221 * uses/defs retain the Dalvik convention that long operations operate on a pair of 32-bit 222 * vregs. For example, "ADD_LONG v0, v2, v3" would have 2 defs (v0/v1) and 4 uses (v2/v3, v4/v5). 223 * Following SSA renaming, this is the primary struct used by code generators to locate 224 * operand and result registers. This is a somewhat confusing and unhelpful convention that 225 * we may want to revisit in the future. 226 */ 227struct SSARepresentation { 228 int16_t num_uses; 229 int16_t num_defs; 230 int32_t* uses; 231 bool* fp_use; 232 int32_t* defs; 233 bool* fp_def; 234}; 235 236/* 237 * The Midlevel Intermediate Representation node, which may be largely considered a 238 * wrapper around a Dalvik byte code. 239 */ 240struct MIR { 241 /* 242 * TODO: remove embedded DecodedInstruction to save space, keeping only opcode. Recover 243 * additional fields on as-needed basis. Question: how to support MIR Pseudo-ops; probably 244 * need to carry aux data pointer. 245 */ 246 DecodedInstruction dalvikInsn; 247 uint16_t width; // Note: width can include switch table or fill array data. 248 NarrowDexOffset offset; // Offset of the instruction in code units. 249 uint16_t optimization_flags; 250 int16_t m_unit_index; // From which method was this MIR included 251 MIR* next; 252 SSARepresentation* ssa_rep; 253 union { 254 // Incoming edges for phi node. 255 BasicBlockId* phi_incoming; 256 // Establish link between two halves of throwing instructions. 257 MIR* throw_insn; 258 } meta; 259}; 260 261struct SuccessorBlockInfo; 262 263struct BasicBlock { 264 BasicBlockId id; 265 BasicBlockId dfs_id; 266 NarrowDexOffset start_offset; // Offset in code units. 267 BasicBlockId fall_through; 268 BasicBlockId taken; 269 BasicBlockId i_dom; // Immediate dominator. 270 uint16_t nesting_depth; 271 BBType block_type:4; 272 BlockListType successor_block_list_type:4; 273 bool visited:1; 274 bool hidden:1; 275 bool catch_entry:1; 276 bool explicit_throw:1; 277 bool conditional_branch:1; 278 bool terminated_by_return:1; // Block ends with a Dalvik return opcode. 279 bool dominates_return:1; // Is a member of return extended basic block. 280 bool use_lvn:1; // Run local value numbering on this block. 281 MIR* first_mir_insn; 282 MIR* last_mir_insn; 283 BasicBlockDataFlow* data_flow_info; 284 ArenaBitVector* dominators; 285 ArenaBitVector* i_dominated; // Set nodes being immediately dominated. 286 ArenaBitVector* dom_frontier; // Dominance frontier. 287 GrowableArray<BasicBlockId>* predecessors; 288 GrowableArray<SuccessorBlockInfo*>* successor_blocks; 289}; 290 291/* 292 * The "blocks" field in "successor_block_list" points to an array of elements with the type 293 * "SuccessorBlockInfo". For catch blocks, key is type index for the exception. For swtich 294 * blocks, key is the case value. 295 */ 296struct SuccessorBlockInfo { 297 BasicBlockId block; 298 int key; 299}; 300 301/* 302 * Whereas a SSA name describes a definition of a Dalvik vreg, the RegLocation describes 303 * the type of an SSA name (and, can also be used by code generators to record where the 304 * value is located (i.e. - physical register, frame, spill, etc.). For each SSA name (SReg) 305 * there is a RegLocation. 306 * A note on SSA names: 307 * o SSA names for Dalvik vRegs v0..vN will be assigned 0..N. These represent the "vN_0" 308 * names. Negative SSA names represent special values not present in the Dalvik byte code. 309 * For example, SSA name -1 represents an invalid SSA name, and SSA name -2 represents the 310 * the Method pointer. SSA names < -2 are reserved for future use. 311 * o The vN_0 names for non-argument Dalvik should in practice never be used (as they would 312 * represent the read of an undefined local variable). The first definition of the 313 * underlying Dalvik vReg will result in a vN_1 name. 314 * 315 * FIXME: The orig_sreg field was added as a workaround for llvm bitcode generation. With 316 * the latest restructuring, we should be able to remove it and rely on s_reg_low throughout. 317 */ 318struct RegLocation { 319 RegLocationType location:3; 320 unsigned wide:1; 321 unsigned defined:1; // Do we know the type? 322 unsigned is_const:1; // Constant, value in mir_graph->constant_values[]. 323 unsigned fp:1; // Floating point? 324 unsigned core:1; // Non-floating point? 325 unsigned ref:1; // Something GC cares about. 326 unsigned high_word:1; // High word of pair? 327 unsigned home:1; // Does this represent the home location? 328 VectorLengthType vec_len:3; // Is this value in a vector register, and how big is it? 329 uint8_t low_reg; // First physical register. 330 uint8_t high_reg; // 2nd physical register (if wide). 331 int16_t s_reg_low; // SSA name for low Dalvik word. 332 int16_t orig_sreg; // TODO: remove after Bitcode gen complete 333 // and consolidate usage w/ s_reg_low. 334 335 bool IsVectorScalar() const { return vec_len == kVectorLength4 || vec_len == kVectorLength8;} 336}; 337 338/* 339 * Collection of information describing an invoke, and the destination of 340 * the subsequent MOVE_RESULT (if applicable). Collected as a unit to enable 341 * more efficient invoke code generation. 342 */ 343struct CallInfo { 344 int num_arg_words; // Note: word count, not arg count. 345 RegLocation* args; // One for each word of arguments. 346 RegLocation result; // Eventual target of MOVE_RESULT. 347 int opt_flags; 348 InvokeType type; 349 uint32_t dex_idx; 350 uint32_t index; // Method idx for invokes, type idx for FilledNewArray. 351 uintptr_t direct_code; 352 uintptr_t direct_method; 353 RegLocation target; // Target of following move_result. 354 bool skip_this; 355 bool is_range; 356 DexOffset offset; // Offset in code units. 357}; 358 359 360const RegLocation bad_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0, kVectorNotUsed, 361 INVALID_REG, INVALID_REG, INVALID_SREG, INVALID_SREG}; 362 363class MIRGraph { 364 public: 365 MIRGraph(CompilationUnit* cu, ArenaAllocator* arena); 366 ~MIRGraph(); 367 368 /* 369 * Examine the graph to determine whether it's worthwile to spend the time compiling 370 * this method. 371 */ 372 bool SkipCompilation(Runtime::CompilerFilter compiler_filter); 373 374 /* 375 * Parse dex method and add MIR at current insert point. Returns id (which is 376 * actually the index of the method in the m_units_ array). 377 */ 378 void InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 379 InvokeType invoke_type, uint16_t class_def_idx, 380 uint32_t method_idx, jobject class_loader, const DexFile& dex_file); 381 382 /* Find existing block */ 383 BasicBlock* FindBlock(DexOffset code_offset) { 384 return FindBlock(code_offset, false, false, NULL); 385 } 386 387 const uint16_t* GetCurrentInsns() const { 388 return current_code_item_->insns_; 389 } 390 391 const uint16_t* GetInsns(int m_unit_index) const { 392 return m_units_[m_unit_index]->GetCodeItem()->insns_; 393 } 394 395 int GetNumBlocks() const { 396 return num_blocks_; 397 } 398 399 size_t GetNumDalvikInsns() const { 400 return cu_->code_item->insns_size_in_code_units_; 401 } 402 403 ArenaBitVector* GetTryBlockAddr() const { 404 return try_block_addr_; 405 } 406 407 BasicBlock* GetEntryBlock() const { 408 return entry_block_; 409 } 410 411 BasicBlock* GetExitBlock() const { 412 return exit_block_; 413 } 414 415 BasicBlock* GetBasicBlock(int block_id) const { 416 return (block_id == NullBasicBlockId) ? NULL : block_list_.Get(block_id); 417 } 418 419 size_t GetBasicBlockListCount() const { 420 return block_list_.Size(); 421 } 422 423 GrowableArray<BasicBlock*>* GetBlockList() { 424 return &block_list_; 425 } 426 427 GrowableArray<BasicBlockId>* GetDfsOrder() { 428 return dfs_order_; 429 } 430 431 GrowableArray<BasicBlockId>* GetDfsPostOrder() { 432 return dfs_post_order_; 433 } 434 435 GrowableArray<BasicBlockId>* GetDomPostOrder() { 436 return dom_post_order_traversal_; 437 } 438 439 int GetDefCount() const { 440 return def_count_; 441 } 442 443 ArenaAllocator* GetArena() { 444 return arena_; 445 } 446 447 void EnableOpcodeCounting() { 448 opcode_count_ = static_cast<int*>(arena_->Alloc(kNumPackedOpcodes * sizeof(int), 449 ArenaAllocator::kAllocMisc)); 450 } 451 452 void ShowOpcodeStats(); 453 454 DexCompilationUnit* GetCurrentDexCompilationUnit() const { 455 return m_units_[current_method_]; 456 } 457 458 /** 459 * @brief Dump a CFG into a dot file format. 460 * @param dir_prefix the directory the file will be created in. 461 * @param all_blocks does the dumper use all the basic blocks or use the reachable blocks. 462 * @param suffix does the filename require a suffix or not (default = nullptr). 463 */ 464 void DumpCFG(const char* dir_prefix, bool all_blocks, const char* suffix = nullptr); 465 466 void InitRegLocations(); 467 468 void RemapRegLocations(); 469 470 void DumpRegLocTable(RegLocation* table, int count); 471 472 void BasicBlockOptimization(); 473 474 bool IsConst(int32_t s_reg) const { 475 return is_constant_v_->IsBitSet(s_reg); 476 } 477 478 bool IsConst(RegLocation loc) const { 479 return loc.orig_sreg < 0 ? false : IsConst(loc.orig_sreg); 480 } 481 482 int32_t ConstantValue(RegLocation loc) const { 483 DCHECK(IsConst(loc)); 484 return constant_values_[loc.orig_sreg]; 485 } 486 487 int32_t ConstantValue(int32_t s_reg) const { 488 DCHECK(IsConst(s_reg)); 489 return constant_values_[s_reg]; 490 } 491 492 int64_t ConstantValueWide(RegLocation loc) const { 493 DCHECK(IsConst(loc)); 494 return (static_cast<int64_t>(constant_values_[loc.orig_sreg + 1]) << 32) | 495 Low32Bits(static_cast<int64_t>(constant_values_[loc.orig_sreg])); 496 } 497 498 bool IsConstantNullRef(RegLocation loc) const { 499 return loc.ref && loc.is_const && (ConstantValue(loc) == 0); 500 } 501 502 int GetNumSSARegs() const { 503 return num_ssa_regs_; 504 } 505 506 void SetNumSSARegs(int new_num) { 507 /* 508 * TODO: It's theoretically possible to exceed 32767, though any cases which did 509 * would be filtered out with current settings. When orig_sreg field is removed 510 * from RegLocation, expand s_reg_low to handle all possible cases and remove DCHECK(). 511 */ 512 DCHECK_EQ(new_num, static_cast<int16_t>(new_num)); 513 num_ssa_regs_ = new_num; 514 } 515 516 unsigned int GetNumReachableBlocks() const { 517 return num_reachable_blocks_; 518 } 519 520 int GetUseCount(int vreg) const { 521 return use_counts_.Get(vreg); 522 } 523 524 int GetRawUseCount(int vreg) const { 525 return raw_use_counts_.Get(vreg); 526 } 527 528 int GetSSASubscript(int ssa_reg) const { 529 return ssa_subscripts_->Get(ssa_reg); 530 } 531 532 RegLocation GetRawSrc(MIR* mir, int num) { 533 DCHECK(num < mir->ssa_rep->num_uses); 534 RegLocation res = reg_location_[mir->ssa_rep->uses[num]]; 535 return res; 536 } 537 538 RegLocation GetRawDest(MIR* mir) { 539 DCHECK_GT(mir->ssa_rep->num_defs, 0); 540 RegLocation res = reg_location_[mir->ssa_rep->defs[0]]; 541 return res; 542 } 543 544 RegLocation GetDest(MIR* mir) { 545 RegLocation res = GetRawDest(mir); 546 DCHECK(!res.wide); 547 return res; 548 } 549 550 RegLocation GetSrc(MIR* mir, int num) { 551 RegLocation res = GetRawSrc(mir, num); 552 DCHECK(!res.wide); 553 return res; 554 } 555 556 RegLocation GetDestWide(MIR* mir) { 557 RegLocation res = GetRawDest(mir); 558 DCHECK(res.wide); 559 return res; 560 } 561 562 RegLocation GetSrcWide(MIR* mir, int low) { 563 RegLocation res = GetRawSrc(mir, low); 564 DCHECK(res.wide); 565 return res; 566 } 567 568 RegLocation GetBadLoc() { 569 return bad_loc; 570 } 571 572 int GetMethodSReg() { 573 return method_sreg_; 574 } 575 576 bool MethodIsLeaf() { 577 return attributes_ & METHOD_IS_LEAF; 578 } 579 580 RegLocation GetRegLocation(int index) { 581 DCHECK((index >= 0) && (index > num_ssa_regs_)); 582 return reg_location_[index]; 583 } 584 585 RegLocation GetMethodLoc() { 586 return reg_location_[method_sreg_]; 587 } 588 589 bool IsBackedge(BasicBlock* branch_bb, BasicBlockId target_bb_id) { 590 return ((target_bb_id != NullBasicBlockId) && 591 (GetBasicBlock(target_bb_id)->start_offset <= branch_bb->start_offset)); 592 } 593 594 bool IsBackwardsBranch(BasicBlock* branch_bb) { 595 return IsBackedge(branch_bb, branch_bb->taken) || IsBackedge(branch_bb, branch_bb->fall_through); 596 } 597 598 void CountBranch(DexOffset target_offset) { 599 if (target_offset <= current_offset_) { 600 backward_branches_++; 601 } else { 602 forward_branches_++; 603 } 604 } 605 606 int GetBranchCount() { 607 return backward_branches_ + forward_branches_; 608 } 609 610 bool IsPseudoMirOp(Instruction::Code opcode) { 611 return static_cast<int>(opcode) >= static_cast<int>(kMirOpFirst); 612 } 613 614 bool IsPseudoMirOp(int opcode) { 615 return opcode >= static_cast<int>(kMirOpFirst); 616 } 617 618 void DumpCheckStats(); 619 MIR* FindMoveResult(BasicBlock* bb, MIR* mir); 620 int SRegToVReg(int ssa_reg) const; 621 void VerifyDataflow(); 622 void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb); 623 bool EliminateNullChecksAndInferTypes(BasicBlock *bb); 624 /* 625 * Type inference handling helpers. Because Dalvik's bytecode is not fully typed, 626 * we have to do some work to figure out the sreg type. For some operations it is 627 * clear based on the opcode (i.e. ADD_FLOAT v0, v1, v2), but for others (MOVE), we 628 * may never know the "real" type. 629 * 630 * We perform the type inference operation by using an iterative walk over 631 * the graph, propagating types "defined" by typed opcodes to uses and defs in 632 * non-typed opcodes (such as MOVE). The Setxx(index) helpers are used to set defined 633 * types on typed opcodes (such as ADD_INT). The Setxx(index, is_xx) form is used to 634 * propagate types through non-typed opcodes such as PHI and MOVE. The is_xx flag 635 * tells whether our guess of the type is based on a previously typed definition. 636 * If so, the defined type takes precedence. Note that it's possible to have the same sreg 637 * show multiple defined types because dx treats constants as untyped bit patterns. 638 * The return value of the Setxx() helpers says whether or not the Setxx() action changed 639 * the current guess, and is used to know when to terminate the iterative walk. 640 */ 641 bool SetFp(int index, bool is_fp); 642 bool SetFp(int index); 643 bool SetCore(int index, bool is_core); 644 bool SetCore(int index); 645 bool SetRef(int index, bool is_ref); 646 bool SetRef(int index); 647 bool SetWide(int index, bool is_wide); 648 bool SetWide(int index); 649 bool SetHigh(int index, bool is_high); 650 bool SetHigh(int index); 651 652 void AppendMIR(BasicBlock* bb, MIR* mir); 653 void PrependMIR(BasicBlock* bb, MIR* mir); 654 void InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir); 655 char* GetDalvikDisassembly(const MIR* mir); 656 void ReplaceSpecialChars(std::string& str); 657 std::string GetSSAName(int ssa_reg); 658 std::string GetSSANameWithConst(int ssa_reg, bool singles_only); 659 void GetBlockName(BasicBlock* bb, char* name); 660 const char* GetShortyFromTargetIdx(int); 661 void DumpMIRGraph(); 662 CallInfo* NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, bool is_range); 663 BasicBlock* NewMemBB(BBType block_type, int block_id); 664 MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir); 665 BasicBlock* NextDominatedBlock(BasicBlock* bb); 666 bool LayoutBlocks(BasicBlock* bb); 667 668 /** 669 * @brief Perform the initial preparation for the Method Uses. 670 */ 671 void InitializeMethodUses(); 672 673 /** 674 * @brief Perform the initial preparation for the Constant Propagation. 675 */ 676 void InitializeConstantPropagation(); 677 678 /** 679 * @brief Perform the initial preparation for the SSA Transformation. 680 */ 681 void InitializeSSATransformation(); 682 683 /** 684 * @brief Insert a the operands for the Phi nodes. 685 * @param bb the considered BasicBlock. 686 * @return true 687 */ 688 bool InsertPhiNodeOperands(BasicBlock* bb); 689 690 /** 691 * @brief Perform constant propagation on a BasicBlock. 692 * @param bb the considered BasicBlock. 693 */ 694 void DoConstantPropagation(BasicBlock* bb); 695 696 /** 697 * @brief Count the uses in the BasicBlock 698 * @param bb the BasicBlock 699 */ 700 void CountUses(struct BasicBlock* bb); 701 702 /** 703 * @brief Initialize the data structures with Null Check data 704 * @param bb the considered BasicBlock 705 */ 706 void NullCheckEliminationInit(BasicBlock* bb); 707 708 /** 709 * @brief Check if the temporary ssa register vector is allocated 710 */ 711 void CheckSSARegisterVector(); 712 713 /** 714 * @brief Combine BasicBlocks 715 * @param the BasicBlock we are considering 716 */ 717 void CombineBlocks(BasicBlock* bb); 718 719 void ClearAllVisitedFlags(); 720 /* 721 * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on 722 * we can verify that all catch entries have native PC entries. 723 */ 724 std::set<uint32_t> catches_; 725 726 // TODO: make these private. 727 RegLocation* reg_location_; // Map SSA names to location. 728 GrowableArray<CompilerTemp*> compiler_temps_; 729 SafeMap<unsigned int, unsigned int> block_id_map_; // Block collapse lookup cache. 730 731 static const uint64_t oat_data_flow_attributes_[kMirOpLast]; 732 static const char* extended_mir_op_names_[kMirOpLast - kMirOpFirst]; 733 static const uint32_t analysis_attributes_[kMirOpLast]; 734 735 private: 736 int FindCommonParent(int block1, int block2); 737 void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, 738 const ArenaBitVector* src2); 739 void HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, 740 ArenaBitVector* live_in_v, int dalvik_reg_id); 741 void HandleDef(ArenaBitVector* def_v, int dalvik_reg_id); 742 void CompilerInitializeSSAConversion(); 743 bool DoSSAConversion(BasicBlock* bb); 744 bool InvokeUsesMethodStar(MIR* mir); 745 int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction); 746 bool ContentIsInsn(const uint16_t* code_ptr); 747 BasicBlock* SplitBlock(DexOffset code_offset, BasicBlock* orig_block, 748 BasicBlock** immed_pred_block_p); 749 BasicBlock* FindBlock(DexOffset code_offset, bool split, bool create, 750 BasicBlock** immed_pred_block_p); 751 void ProcessTryCatchBlocks(); 752 BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 753 int flags, const uint16_t* code_ptr, const uint16_t* code_end); 754 BasicBlock* ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 755 int flags); 756 BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 757 int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr, 758 const uint16_t* code_end); 759 int AddNewSReg(int v_reg); 760 void HandleSSAUse(int* uses, int dalvik_reg, int reg_index); 761 void HandleSSADef(int* defs, int dalvik_reg, int reg_index); 762 void DataFlowSSAFormat35C(MIR* mir); 763 void DataFlowSSAFormat3RC(MIR* mir); 764 bool FindLocalLiveIn(BasicBlock* bb); 765 bool InferTypeAndSize(BasicBlock* bb, MIR* mir, bool changed); 766 bool VerifyPredInfo(BasicBlock* bb); 767 BasicBlock* NeedsVisit(BasicBlock* bb); 768 BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb); 769 void MarkPreOrder(BasicBlock* bb); 770 void RecordDFSOrders(BasicBlock* bb); 771 void ComputeDFSOrders(); 772 void ComputeDefBlockMatrix(); 773 void ComputeDomPostOrderTraversal(BasicBlock* bb); 774 void ComputeDominators(); 775 void InsertPhiNodes(); 776 void DoDFSPreOrderSSARename(BasicBlock* block); 777 void SetConstant(int32_t ssa_reg, int value); 778 void SetConstantWide(int ssa_reg, int64_t value); 779 int GetSSAUseCount(int s_reg); 780 bool BasicBlockOpt(BasicBlock* bb); 781 bool BuildExtendedBBList(struct BasicBlock* bb); 782 bool FillDefBlockMatrix(BasicBlock* bb); 783 void InitializeDominationInfo(BasicBlock* bb); 784 bool ComputeblockIDom(BasicBlock* bb); 785 bool ComputeBlockDominators(BasicBlock* bb); 786 bool SetDominators(BasicBlock* bb); 787 bool ComputeBlockLiveIns(BasicBlock* bb); 788 bool ComputeDominanceFrontier(BasicBlock* bb); 789 790 void CountChecks(BasicBlock* bb); 791 void AnalyzeBlock(BasicBlock* bb, struct MethodStats* stats); 792 bool ComputeSkipCompilation(struct MethodStats* stats, bool skip_default); 793 794 CompilationUnit* const cu_; 795 GrowableArray<int>* ssa_base_vregs_; 796 GrowableArray<int>* ssa_subscripts_; 797 // Map original Dalvik virtual reg i to the current SSA name. 798 int* vreg_to_ssa_map_; // length == method->registers_size 799 int* ssa_last_defs_; // length == method->registers_size 800 ArenaBitVector* is_constant_v_; // length == num_ssa_reg 801 int* constant_values_; // length == num_ssa_reg 802 // Use counts of ssa names. 803 GrowableArray<uint32_t> use_counts_; // Weighted by nesting depth 804 GrowableArray<uint32_t> raw_use_counts_; // Not weighted 805 unsigned int num_reachable_blocks_; 806 GrowableArray<BasicBlockId>* dfs_order_; 807 GrowableArray<BasicBlockId>* dfs_post_order_; 808 GrowableArray<BasicBlockId>* dom_post_order_traversal_; 809 int* i_dom_list_; 810 ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks. 811 ArenaBitVector* temp_block_v_; 812 ArenaBitVector* temp_dalvik_register_v_; 813 ArenaBitVector* temp_ssa_register_v_; // num_ssa_regs. 814 static const int kInvalidEntry = -1; 815 GrowableArray<BasicBlock*> block_list_; 816 ArenaBitVector* try_block_addr_; 817 BasicBlock* entry_block_; 818 BasicBlock* exit_block_; 819 int num_blocks_; 820 const DexFile::CodeItem* current_code_item_; 821 GrowableArray<uint16_t> dex_pc_to_block_map_; // FindBlock lookup cache. 822 std::vector<DexCompilationUnit*> m_units_; // List of methods included in this graph 823 typedef std::pair<int, int> MIRLocation; // Insert point, (m_unit_ index, offset) 824 std::vector<MIRLocation> method_stack_; // Include stack 825 int current_method_; 826 DexOffset current_offset_; // Offset in code units 827 int def_count_; // Used to estimate size of ssa name storage. 828 int* opcode_count_; // Dex opcode coverage stats. 829 int num_ssa_regs_; // Number of names following SSA transformation. 830 std::vector<BasicBlockId> extended_basic_blocks_; // Heads of block "traces". 831 int method_sreg_; 832 unsigned int attributes_; 833 Checkstats* checkstats_; 834 ArenaAllocator* arena_; 835 int backward_branches_; 836 int forward_branches_; 837}; 838 839} // namespace art 840 841#endif // ART_COMPILER_DEX_MIR_GRAPH_H_ 842