mir_graph.h revision 86ec520fc8b696ed6f164d7b756009ecd6e4aace
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 "utils/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#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 181#define BLOCK_NAME_LEN 80 182 183typedef uint16_t BasicBlockId; 184static const BasicBlockId NullBasicBlockId = 0; 185 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 */ 192struct CompilerTemp { 193 int32_t v_reg; // Virtual register number for temporary. 194 int32_t s_reg_low; // SSA name for low Dalvik word. 195}; 196 197enum CompilerTempType { 198 kCompilerTempVR, // A virtual register temporary. 199 kCompilerTempSpecialMethodPtr, // Temporary that keeps track of current method pointer. 200}; 201 202// When debug option enabled, records effectiveness of null and range check elimination. 203struct Checkstats { 204 int32_t null_checks; 205 int32_t null_checks_eliminated; 206 int32_t range_checks; 207 int32_t range_checks_eliminated; 208}; 209 210// Dataflow attributes of a basic block. 211struct BasicBlockDataFlow { 212 ArenaBitVector* use_v; 213 ArenaBitVector* def_v; 214 ArenaBitVector* live_in_v; 215 ArenaBitVector* phi_v; 216 int32_t* vreg_to_ssa_map; 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 */ 228struct SSARepresentation { 229 int16_t num_uses; 230 int16_t num_defs; 231 int32_t* uses; 232 bool* fp_use; 233 int32_t* defs; 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 */ 241struct MIR { 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 */ 247 DecodedInstruction dalvikInsn; 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 252 MIR* next; 253 SSARepresentation* ssa_rep; 254 union { 255 // Incoming edges for phi node. 256 BasicBlockId* phi_incoming; 257 // Establish link from check instruction (kMirOpCheck) to the actual throwing instruction. 258 MIR* throw_insn; 259 // Fused cmp branch condition. 260 ConditionCode ccode; 261 } meta; 262}; 263 264struct SuccessorBlockInfo; 265 266struct BasicBlock { 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. 273 uint16_t nesting_depth; 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; 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. 284 MIR* first_mir_insn; 285 MIR* last_mir_insn; 286 BasicBlockDataFlow* data_flow_info; 287 ArenaBitVector* dominators; 288 ArenaBitVector* i_dominated; // Set nodes being immediately dominated. 289 ArenaBitVector* dom_frontier; // Dominance frontier. 290 GrowableArray<BasicBlockId>* predecessors; 291 GrowableArray<SuccessorBlockInfo*>* successor_blocks; 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 */ 299struct SuccessorBlockInfo { 300 BasicBlockId block; 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. 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 * 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 */ 321struct 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. 329 unsigned high_word:1; // High word of pair? 330 unsigned home:1; // Does this represent the home location? 331 VectorLengthType vec_len:3; // Is this value in a vector register, and how big is it? 332 uint8_t low_reg; // First physical register. 333 uint8_t high_reg; // 2nd physical register (if wide). 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. 337 338 bool IsVectorScalar() const { return vec_len == kVectorLength4 || vec_len == kVectorLength8;} 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 */ 346struct 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; 359 DexOffset offset; // Offset in code units. 360}; 361 362 363const RegLocation bad_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0, kVectorNotUsed, 364 INVALID_REG, INVALID_REG, INVALID_SREG, INVALID_SREG}; 365 366class MIRGraph { 367 public: 368 MIRGraph(CompilationUnit* cu, ArenaAllocator* arena); 369 ~MIRGraph(); 370 371 /* 372 * Examine the graph to determine whether it's worthwile to spend the time compiling 373 * this method. 374 */ 375 bool SkipCompilation(); 376 377 /* 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, 382 InvokeType invoke_type, uint16_t class_def_idx, 383 uint32_t method_idx, jobject class_loader, const DexFile& dex_file); 384 385 /* Find existing block */ 386 BasicBlock* FindBlock(DexOffset code_offset) { 387 return FindBlock(code_offset, false, false, NULL); 388 } 389 390 const uint16_t* GetCurrentInsns() const { 391 return current_code_item_->insns_; 392 } 393 394 const uint16_t* GetInsns(int m_unit_index) const { 395 return m_units_[m_unit_index]->GetCodeItem()->insns_; 396 } 397 398 int GetNumBlocks() const { 399 return num_blocks_; 400 } 401 402 size_t GetNumDalvikInsns() const { 403 return cu_->code_item->insns_size_in_code_units_; 404 } 405 406 ArenaBitVector* GetTryBlockAddr() const { 407 return try_block_addr_; 408 } 409 410 BasicBlock* GetEntryBlock() const { 411 return entry_block_; 412 } 413 414 BasicBlock* GetExitBlock() const { 415 return exit_block_; 416 } 417 418 BasicBlock* GetBasicBlock(int block_id) const { 419 return (block_id == NullBasicBlockId) ? NULL : block_list_.Get(block_id); 420 } 421 422 size_t GetBasicBlockListCount() const { 423 return block_list_.Size(); 424 } 425 426 GrowableArray<BasicBlock*>* GetBlockList() { 427 return &block_list_; 428 } 429 430 GrowableArray<BasicBlockId>* GetDfsOrder() { 431 return dfs_order_; 432 } 433 434 GrowableArray<BasicBlockId>* GetDfsPostOrder() { 435 return dfs_post_order_; 436 } 437 438 GrowableArray<BasicBlockId>* GetDomPostOrder() { 439 return dom_post_order_traversal_; 440 } 441 442 int GetDefCount() const { 443 return def_count_; 444 } 445 446 ArenaAllocator* GetArena() { 447 return arena_; 448 } 449 450 void EnableOpcodeCounting() { 451 opcode_count_ = static_cast<int*>(arena_->Alloc(kNumPackedOpcodes * sizeof(int), 452 ArenaAllocator::kAllocMisc)); 453 } 454 455 void ShowOpcodeStats(); 456 457 DexCompilationUnit* GetCurrentDexCompilationUnit() const { 458 return m_units_[current_method_]; 459 } 460 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); 468 469 void InitRegLocations(); 470 471 void RemapRegLocations(); 472 473 void DumpRegLocTable(RegLocation* table, int count); 474 475 void BasicBlockOptimization(); 476 477 bool IsConst(int32_t s_reg) const { 478 return is_constant_v_->IsBitSet(s_reg); 479 } 480 481 bool IsConst(RegLocation loc) const { 482 return loc.orig_sreg < 0 ? false : IsConst(loc.orig_sreg); 483 } 484 485 int32_t ConstantValue(RegLocation loc) const { 486 DCHECK(IsConst(loc)); 487 return constant_values_[loc.orig_sreg]; 488 } 489 490 int32_t ConstantValue(int32_t s_reg) const { 491 DCHECK(IsConst(s_reg)); 492 return constant_values_[s_reg]; 493 } 494 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 } 500 501 bool IsConstantNullRef(RegLocation loc) const { 502 return loc.ref && loc.is_const && (ConstantValue(loc) == 0); 503 } 504 505 int GetNumSSARegs() const { 506 return num_ssa_regs_; 507 } 508 509 void SetNumSSARegs(int new_num) { 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)); 516 num_ssa_regs_ = new_num; 517 } 518 519 unsigned int GetNumReachableBlocks() const { 520 return num_reachable_blocks_; 521 } 522 523 int GetUseCount(int vreg) const { 524 return use_counts_.Get(vreg); 525 } 526 527 int GetRawUseCount(int vreg) const { 528 return raw_use_counts_.Get(vreg); 529 } 530 531 int GetSSASubscript(int ssa_reg) const { 532 return ssa_subscripts_->Get(ssa_reg); 533 } 534 535 RegLocation GetRawSrc(MIR* mir, int num) { 536 DCHECK(num < mir->ssa_rep->num_uses); 537 RegLocation res = reg_location_[mir->ssa_rep->uses[num]]; 538 return res; 539 } 540 541 RegLocation GetRawDest(MIR* mir) { 542 DCHECK_GT(mir->ssa_rep->num_defs, 0); 543 RegLocation res = reg_location_[mir->ssa_rep->defs[0]]; 544 return res; 545 } 546 547 RegLocation GetDest(MIR* mir) { 548 RegLocation res = GetRawDest(mir); 549 DCHECK(!res.wide); 550 return res; 551 } 552 553 RegLocation GetSrc(MIR* mir, int num) { 554 RegLocation res = GetRawSrc(mir, num); 555 DCHECK(!res.wide); 556 return res; 557 } 558 559 RegLocation GetDestWide(MIR* mir) { 560 RegLocation res = GetRawDest(mir); 561 DCHECK(res.wide); 562 return res; 563 } 564 565 RegLocation GetSrcWide(MIR* mir, int low) { 566 RegLocation res = GetRawSrc(mir, low); 567 DCHECK(res.wide); 568 return res; 569 } 570 571 RegLocation GetBadLoc() { 572 return bad_loc; 573 } 574 575 int GetMethodSReg() const { 576 return method_sreg_; 577 } 578 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 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 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)); 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 667 void CountBranch(DexOffset target_offset) { 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 687 void DumpCheckStats(); 688 MIR* FindMoveResult(BasicBlock* bb, MIR* mir); 689 int SRegToVReg(int ssa_reg) const; 690 void VerifyDataflow(); 691 void CheckForDominanceFrontier(BasicBlock* dom_bb, const BasicBlock* succ_bb); 692 bool EliminateNullChecksAndInferTypes(BasicBlock *bb); 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 */ 710 bool SetFp(int index, bool is_fp); 711 bool SetFp(int index); 712 bool SetCore(int index, bool is_core); 713 bool SetCore(int index); 714 bool SetRef(int index, bool is_ref); 715 bool SetRef(int index); 716 bool SetWide(int index, bool is_wide); 717 bool SetWide(int index); 718 bool SetHigh(int index, bool is_high); 719 bool SetHigh(int index); 720 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 725 /** 726 * @brief Used to obtain the next MIR that follows unconditionally. 727 * @details The implementation does not guarantee that a MIR does not 728 * follow even if this method returns nullptr. 729 * @param bb The basic block of "current" MIR. 730 * @param current The MIR for which to find an unconditional follower. 731 * @return Returns the following MIR if one can be found. 732 */ 733 MIR* GetNextUnconditionalMir(BasicBlock* bb, MIR* current); 734 735 char* GetDalvikDisassembly(const MIR* mir); 736 void ReplaceSpecialChars(std::string& str); 737 std::string GetSSAName(int ssa_reg); 738 std::string GetSSANameWithConst(int ssa_reg, bool singles_only); 739 void GetBlockName(BasicBlock* bb, char* name); 740 const char* GetShortyFromTargetIdx(int); 741 void DumpMIRGraph(); 742 CallInfo* NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, bool is_range); 743 BasicBlock* NewMemBB(BBType block_type, int block_id); 744 MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir); 745 BasicBlock* NextDominatedBlock(BasicBlock* bb); 746 bool LayoutBlocks(BasicBlock* bb); 747 748 /** 749 * @brief Perform the initial preparation for the Method Uses. 750 */ 751 void InitializeMethodUses(); 752 753 /** 754 * @brief Perform the initial preparation for the Constant Propagation. 755 */ 756 void InitializeConstantPropagation(); 757 758 /** 759 * @brief Perform the initial preparation for the SSA Transformation. 760 */ 761 void InitializeSSATransformation(); 762 763 /** 764 * @brief Insert a the operands for the Phi nodes. 765 * @param bb the considered BasicBlock. 766 * @return true 767 */ 768 bool InsertPhiNodeOperands(BasicBlock* bb); 769 770 /** 771 * @brief Perform constant propagation on a BasicBlock. 772 * @param bb the considered BasicBlock. 773 */ 774 void DoConstantPropagation(BasicBlock* bb); 775 776 /** 777 * @brief Count the uses in the BasicBlock 778 * @param bb the BasicBlock 779 */ 780 void CountUses(struct BasicBlock* bb); 781 782 /** 783 * @brief Initialize the data structures with Null Check data 784 * @param bb the considered BasicBlock 785 */ 786 void NullCheckEliminationInit(BasicBlock* bb); 787 788 /** 789 * @brief Check if the temporary ssa register vector is allocated 790 */ 791 void CheckSSARegisterVector(); 792 793 /** 794 * @brief Combine BasicBlocks 795 * @param the BasicBlock we are considering 796 */ 797 void CombineBlocks(BasicBlock* bb); 798 799 void ClearAllVisitedFlags(); 800 /* 801 * IsDebugBuild sanity check: keep track of the Dex PCs for catch entries so that later on 802 * we can verify that all catch entries have native PC entries. 803 */ 804 std::set<uint32_t> catches_; 805 806 // TODO: make these private. 807 RegLocation* reg_location_; // Map SSA names to location. 808 SafeMap<unsigned int, unsigned int> block_id_map_; // Block collapse lookup cache. 809 810 static const uint64_t oat_data_flow_attributes_[kMirOpLast]; 811 static const char* extended_mir_op_names_[kMirOpLast - kMirOpFirst]; 812 static const uint32_t analysis_attributes_[kMirOpLast]; 813 814 private: 815 int FindCommonParent(int block1, int block2); 816 void ComputeSuccLineIn(ArenaBitVector* dest, const ArenaBitVector* src1, 817 const ArenaBitVector* src2); 818 void HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, 819 ArenaBitVector* live_in_v, int dalvik_reg_id); 820 void HandleDef(ArenaBitVector* def_v, int dalvik_reg_id); 821 void CompilerInitializeSSAConversion(); 822 bool DoSSAConversion(BasicBlock* bb); 823 bool InvokeUsesMethodStar(MIR* mir); 824 int ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction); 825 bool ContentIsInsn(const uint16_t* code_ptr); 826 BasicBlock* SplitBlock(DexOffset code_offset, BasicBlock* orig_block, 827 BasicBlock** immed_pred_block_p); 828 BasicBlock* FindBlock(DexOffset code_offset, bool split, bool create, 829 BasicBlock** immed_pred_block_p); 830 void ProcessTryCatchBlocks(); 831 BasicBlock* ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 832 int flags, const uint16_t* code_ptr, const uint16_t* code_end); 833 BasicBlock* ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 834 int flags); 835 BasicBlock* ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, int width, 836 int flags, ArenaBitVector* try_block_addr, const uint16_t* code_ptr, 837 const uint16_t* code_end); 838 int AddNewSReg(int v_reg); 839 void HandleSSAUse(int* uses, int dalvik_reg, int reg_index); 840 void HandleSSADef(int* defs, int dalvik_reg, int reg_index); 841 void DataFlowSSAFormat35C(MIR* mir); 842 void DataFlowSSAFormat3RC(MIR* mir); 843 bool FindLocalLiveIn(BasicBlock* bb); 844 bool InferTypeAndSize(BasicBlock* bb, MIR* mir, bool changed); 845 bool VerifyPredInfo(BasicBlock* bb); 846 BasicBlock* NeedsVisit(BasicBlock* bb); 847 BasicBlock* NextUnvisitedSuccessor(BasicBlock* bb); 848 void MarkPreOrder(BasicBlock* bb); 849 void RecordDFSOrders(BasicBlock* bb); 850 void ComputeDFSOrders(); 851 void ComputeDefBlockMatrix(); 852 void ComputeDomPostOrderTraversal(BasicBlock* bb); 853 void ComputeDominators(); 854 void InsertPhiNodes(); 855 void DoDFSPreOrderSSARename(BasicBlock* block); 856 void SetConstant(int32_t ssa_reg, int value); 857 void SetConstantWide(int ssa_reg, int64_t value); 858 int GetSSAUseCount(int s_reg); 859 bool BasicBlockOpt(BasicBlock* bb); 860 bool BuildExtendedBBList(struct BasicBlock* bb); 861 bool FillDefBlockMatrix(BasicBlock* bb); 862 void InitializeDominationInfo(BasicBlock* bb); 863 bool ComputeblockIDom(BasicBlock* bb); 864 bool ComputeBlockDominators(BasicBlock* bb); 865 bool SetDominators(BasicBlock* bb); 866 bool ComputeBlockLiveIns(BasicBlock* bb); 867 bool ComputeDominanceFrontier(BasicBlock* bb); 868 869 void CountChecks(BasicBlock* bb); 870 void AnalyzeBlock(BasicBlock* bb, struct MethodStats* stats); 871 bool ComputeSkipCompilation(struct MethodStats* stats, bool skip_default); 872 873 CompilationUnit* const cu_; 874 GrowableArray<int>* ssa_base_vregs_; 875 GrowableArray<int>* ssa_subscripts_; 876 // Map original Dalvik virtual reg i to the current SSA name. 877 int* vreg_to_ssa_map_; // length == method->registers_size 878 int* ssa_last_defs_; // length == method->registers_size 879 ArenaBitVector* is_constant_v_; // length == num_ssa_reg 880 int* constant_values_; // length == num_ssa_reg 881 // Use counts of ssa names. 882 GrowableArray<uint32_t> use_counts_; // Weighted by nesting depth 883 GrowableArray<uint32_t> raw_use_counts_; // Not weighted 884 unsigned int num_reachable_blocks_; 885 GrowableArray<BasicBlockId>* dfs_order_; 886 GrowableArray<BasicBlockId>* dfs_post_order_; 887 GrowableArray<BasicBlockId>* dom_post_order_traversal_; 888 int* i_dom_list_; 889 ArenaBitVector** def_block_matrix_; // num_dalvik_register x num_blocks. 890 ArenaBitVector* temp_block_v_; 891 ArenaBitVector* temp_dalvik_register_v_; 892 ArenaBitVector* temp_ssa_register_v_; // num_ssa_regs. 893 static const int kInvalidEntry = -1; 894 GrowableArray<BasicBlock*> block_list_; 895 ArenaBitVector* try_block_addr_; 896 BasicBlock* entry_block_; 897 BasicBlock* exit_block_; 898 int num_blocks_; 899 const DexFile::CodeItem* current_code_item_; 900 GrowableArray<uint16_t> dex_pc_to_block_map_; // FindBlock lookup cache. 901 std::vector<DexCompilationUnit*> m_units_; // List of methods included in this graph 902 typedef std::pair<int, int> MIRLocation; // Insert point, (m_unit_ index, offset) 903 std::vector<MIRLocation> method_stack_; // Include stack 904 int current_method_; 905 DexOffset current_offset_; // Offset in code units 906 int def_count_; // Used to estimate size of ssa name storage. 907 int* opcode_count_; // Dex opcode coverage stats. 908 int num_ssa_regs_; // Number of names following SSA transformation. 909 std::vector<BasicBlockId> extended_basic_blocks_; // Heads of block "traces". 910 int method_sreg_; 911 unsigned int attributes_; 912 Checkstats* checkstats_; 913 ArenaAllocator* arena_; 914 int backward_branches_; 915 int forward_branches_; 916 GrowableArray<CompilerTemp*> compiler_temps_; 917 size_t num_non_special_compiler_temps_; 918 size_t max_available_non_special_compiler_temps_; 919 size_t max_available_special_compiler_temps_; 920 921 friend class LocalValueNumberingTest; 922}; 923 924} // namespace art 925 926#endif // ART_COMPILER_DEX_MIR_GRAPH_H_ 927