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