compiler_ir.h revision fa57c47f1b72916371a9c2d5c1389219bce655b4
1/* 2 * Copyright (C) 2011 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_SRC_COMPILER_COMPILER_IR_H_ 18#define ART_SRC_COMPILER_COMPILER_IR_H_ 19 20#include <vector> 21#include "dex_instruction.h" 22#include "compiler.h" 23#include "compiler_utility.h" 24#include "oat_compilation_unit.h" 25#include "safe_map.h" 26#include "greenland/ir_builder.h" 27#include "llvm/Module.h" 28#include "compiler_enums.h" 29 30namespace art { 31 32#define SLOW_FIELD_PATH (cu->enable_debug & (1 << kDebugSlowFieldPath)) 33#define SLOW_INVOKE_PATH (cu->enable_debug & (1 << kDebugSlowInvokePath)) 34#define SLOW_STRING_PATH (cu->enable_debug & (1 << kDebugSlowStringPath)) 35#define SLOW_TYPE_PATH (cu->enable_debug & (1 << kDebugSlowTypePath)) 36#define EXERCISE_SLOWEST_STRING_PATH (cu->enable_debug & \ 37 (1 << kDebugSlowestStringPath)) 38 39// Minimum field size to contain Dalvik v_reg number 40#define VREG_NUM_WIDTH 16 41 42struct ArenaBitVector; 43struct LIR; 44class LLVMInfo; 45 46struct PromotionMap { 47 RegLocationType core_location:3; 48 uint8_t core_reg; 49 RegLocationType fp_location:3; 50 uint8_t FpReg; 51 bool first_in_pair; 52}; 53 54struct RegLocation { 55 RegLocationType location:3; 56 unsigned wide:1; 57 unsigned defined:1; // Do we know the type? 58 unsigned is_const:1; // Constant, value in cu->constant_values[] 59 unsigned fp:1; // Floating point? 60 unsigned core:1; // Non-floating point? 61 unsigned ref:1; // Something GC cares about 62 unsigned high_word:1; // High word of pair? 63 unsigned home:1; // Does this represent the home location? 64 uint8_t low_reg; // First physical register 65 uint8_t high_reg; // 2nd physical register (if wide) 66 int32_t s_reg_low; // SSA name for low Dalvik word 67 int32_t orig_sreg; // TODO: remove after Bitcode gen complete 68 // and consolodate usage w/ s_reg_low 69}; 70 71struct CompilerTemp { 72 int s_reg; 73 ArenaBitVector* bv; 74}; 75 76struct CallInfo { 77 int num_arg_words; // Note: word count, not arg count 78 RegLocation* args; // One for each word of arguments 79 RegLocation result; // Eventual target of MOVE_RESULT 80 int opt_flags; 81 InvokeType type; 82 uint32_t dex_idx; 83 uint32_t index; // Method idx for invokes, type idx for FilledNewArray 84 uintptr_t direct_code; 85 uintptr_t direct_method; 86 RegLocation target; // Target of following move_result 87 bool skip_this; 88 bool is_range; 89 int offset; // Dalvik offset 90}; 91 92 /* 93 * Data structure tracking the mapping between a Dalvik register (pair) and a 94 * native register (pair). The idea is to reuse the previously loaded value 95 * if possible, otherwise to keep the value in a native register as long as 96 * possible. 97 */ 98struct RegisterInfo { 99 int reg; // Reg number 100 bool in_use; // Has it been allocated? 101 bool is_temp; // Can allocate as temp? 102 bool pair; // Part of a register pair? 103 int partner; // If pair, other reg of pair 104 bool live; // Is there an associated SSA name? 105 bool dirty; // If live, is it dirty? 106 int s_reg; // Name of live value 107 LIR *def_start; // Starting inst in last def sequence 108 LIR *def_end; // Ending inst in last def sequence 109}; 110 111struct RegisterPool { 112 int num_core_regs; 113 RegisterInfo *core_regs; 114 int next_core_reg; 115 int num_fp_regs; 116 RegisterInfo *FPRegs; 117 int next_fp_reg; 118}; 119 120#define INVALID_SREG (-1) 121#define INVALID_VREG (0xFFFFU) 122#define INVALID_REG (0xFF) 123#define INVALID_OFFSET (0xDEADF00FU) 124 125/* SSA encodings for special registers */ 126#define SSA_METHOD_BASEREG (-2) 127/* First compiler temp basereg, grows smaller */ 128#define SSA_CTEMP_BASEREG (SSA_METHOD_BASEREG - 1) 129 130/* 131 * Some code patterns cause the generation of excessively large 132 * methods - in particular initialization sequences. There isn't much 133 * benefit in optimizing these methods, and the cost can be very high. 134 * We attempt to identify these cases, and avoid performing most dataflow 135 * analysis. Two thresholds are used - one for known initializers and one 136 * for everything else. 137 */ 138#define MANY_BLOCKS_INITIALIZER 1000 /* Threshold for switching dataflow off */ 139#define MANY_BLOCKS 4000 /* Non-initializer threshold */ 140 141/* Utility macros to traverse the LIR list */ 142#define NEXT_LIR(lir) (lir->next) 143#define PREV_LIR(lir) (lir->prev) 144 145/* Defines for alias_info (tracks Dalvik register references) */ 146#define DECODE_ALIAS_INFO_REG(X) (X & 0xffff) 147#define DECODE_ALIAS_INFO_WIDE_FLAG (0x80000000) 148#define DECODE_ALIAS_INFO_WIDE(X) ((X & DECODE_ALIAS_INFO_WIDE_FLAG) ? 1 : 0) 149#define ENCODE_ALIAS_INFO(REG, ISWIDE) (REG | (ISWIDE ? DECODE_ALIAS_INFO_WIDE_FLAG : 0)) 150 151/* Common resource macros */ 152#define ENCODE_CCODE (1ULL << kCCode) 153#define ENCODE_FP_STATUS (1ULL << kFPStatus) 154 155/* Abstract memory locations */ 156#define ENCODE_DALVIK_REG (1ULL << kDalvikReg) 157#define ENCODE_LITERAL (1ULL << kLiteral) 158#define ENCODE_HEAP_REF (1ULL << kHeapRef) 159#define ENCODE_MUST_NOT_ALIAS (1ULL << kMustNotAlias) 160 161#define ENCODE_ALL (~0ULL) 162#define ENCODE_MEM (ENCODE_DALVIK_REG | ENCODE_LITERAL | \ 163 ENCODE_HEAP_REF | ENCODE_MUST_NOT_ALIAS) 164 165#define is_pseudo_opcode(opcode) (static_cast<int>(opcode) < 0) 166 167struct LIR { 168 int offset; // Offset of this instruction 169 int dalvik_offset; // Offset of Dalvik opcode 170 LIR* next; 171 LIR* prev; 172 LIR* target; 173 int opcode; 174 int operands[5]; // [0..4] = [dest, src1, src2, extra, extra2] 175 struct { 176 bool is_nop:1; // LIR is optimized away 177 bool pcRelFixup:1; // May need pc-relative fixup 178 unsigned int size:5; // in bytes 179 unsigned int unused:25; 180 } flags; 181 int alias_info; // For Dalvik register & litpool disambiguation 182 uint64_t use_mask; // Resource mask for use 183 uint64_t def_mask; // Resource mask for def 184}; 185 186extern const char* extended_mir_op_names[kMirOpLast - kMirOpFirst]; 187 188struct SSARepresentation; 189 190#define MIR_IGNORE_NULL_CHECK (1 << kMIRIgnoreNullCheck) 191#define MIR_NULL_CHECK_ONLY (1 << kMIRNullCheckOnly) 192#define MIR_IGNORE_RANGE_CHECK (1 << kMIRIgnoreRangeCheck) 193#define MIR_RANGE_CHECK_ONLY (1 << kMIRRangeCheckOnly) 194#define MIR_INLINED (1 << kMIRInlined) 195#define MIR_INLINED_PRED (1 << kMIRInlinedPred) 196#define MIR_CALLEE (1 << kMIRCallee) 197#define MIR_IGNORE_SUSPEND_CHECK (1 << kMIRIgnoreSuspendCheck) 198#define MIR_DUP (1 << kMIRDup) 199#define MIR_MARK (1 << kMIRMark) 200 201struct Checkstats { 202 int null_checks; 203 int null_checks_eliminated; 204 int range_checks; 205 int range_checks_eliminated; 206}; 207 208struct MIR { 209 DecodedInstruction dalvikInsn; 210 unsigned int width; 211 unsigned int offset; 212 MIR* prev; 213 MIR* next; 214 SSARepresentation* ssa_rep; 215 int optimization_flags; 216 union { 217 // Used to quickly locate all Phi opcodes 218 MIR* phi_next; 219 // Establish link between two halves of throwing instructions 220 MIR* throw_insn; 221 } meta; 222}; 223 224struct BasicBlockDataFlow; 225 226struct BasicBlock { 227 int id; 228 int dfs_id; 229 bool visited; 230 bool hidden; 231 bool catch_entry; 232 bool explicit_throw; 233 bool conditional_branch; 234 bool has_return; 235 uint16_t start_offset; 236 uint16_t nesting_depth; 237 BBType block_type; 238 MIR* first_mir_insn; 239 MIR* last_mir_insn; 240 BasicBlock* fall_through; 241 BasicBlock* taken; 242 BasicBlock* i_dom; // Immediate dominator 243 BasicBlockDataFlow* data_flow_info; 244 GrowableList* predecessors; 245 ArenaBitVector* dominators; 246 ArenaBitVector* i_dominated; // Set nodes being immediately dominated 247 ArenaBitVector* dom_frontier; // Dominance frontier 248 struct { // For one-to-many successors like 249 BlockListType block_list_type; // switch and exception handling 250 GrowableList blocks; 251 } successor_block_list; 252}; 253 254/* 255 * The "blocks" field in "successor_block_list" points to an array of 256 * elements with the type "SuccessorBlockInfo". 257 * For catch blocks, key is type index for the exception. 258 * For swtich blocks, key is the case value. 259 */ 260struct SuccessorBlockInfo { 261 BasicBlock* block; 262 int key; 263}; 264 265struct LoopAnalysis; 266struct RegisterPool; 267struct ArenaMemBlock; 268struct Memstats; 269 270#define NOTVISITED (-1) 271 272struct CompilationUnit { 273 CompilationUnit() 274 : num_blocks(0), 275 compiler(NULL), 276 class_linker(NULL), 277 dex_file(NULL), 278 class_loader(NULL), 279 method_idx(0), 280 code_item(NULL), 281 access_flags(0), 282 invoke_type(kDirect), 283 shorty(NULL), 284 first_lir_insn(NULL), 285 last_lir_insn(NULL), 286 literal_list(NULL), 287 method_literal_list(NULL), 288 code_literal_list(NULL), 289 disable_opt(0), 290 enable_debug(0), 291 data_offset(0), 292 total_size(0), 293 assembler_status(kSuccess), 294 assembler_retries(0), 295 verbose(false), 296 has_loop(false), 297 has_invoke(false), 298 qd_mode(false), 299 reg_pool(NULL), 300 instruction_set(kNone), 301 num_ssa_regs(0), 302 ssa_base_vregs(NULL), 303 ssa_subscripts(NULL), 304 ssa_strings(NULL), 305 vreg_to_ssa_map(NULL), 306 ssa_last_defs(NULL), 307 is_constant_v(NULL), 308 constant_values(NULL), 309 phi_alias_map(NULL), 310 phi_list(NULL), 311 reg_location(NULL), 312 promotion_map(NULL), 313 method_sreg(0), 314 num_reachable_blocks(0), 315 num_dalvik_registers(0), 316 entry_block(NULL), 317 exit_block(NULL), 318 cur_block(NULL), 319 i_dom_list(NULL), 320 try_block_addr(NULL), 321 def_block_matrix(NULL), 322 temp_block_v(NULL), 323 temp_dalvik_register_v(NULL), 324 temp_ssa_register_v(NULL), 325 temp_ssa_block_id_v(NULL), 326 block_label_list(NULL), 327 num_ins(0), 328 num_outs(0), 329 num_regs(0), 330 num_core_spills(0), 331 num_fp_spills(0), 332 num_compiler_temps(0), 333 frame_size(0), 334 core_spill_mask(0U), 335 fp_spill_mask(0U), 336 attrs(0U), 337 current_dalvik_offset(0), 338 insns(NULL), 339 insns_size(0U), 340 disable_dataflow(false), 341 def_count(0), 342 compiler_flip_match(false), 343 arena_head(NULL), 344 current_arena(NULL), 345 num_arena_blocks(0), 346 mstats(NULL), 347 checkstats(NULL), 348 gen_bitcode(false), 349 context(NULL), 350 module(NULL), 351 func(NULL), 352 intrinsic_helper(NULL), 353 irb(NULL), 354 placeholder_bb(NULL), 355 entry_bb(NULL), 356 entryTarget_bb(NULL), 357 temp_name(0), 358 num_shadow_frame_entries(0), 359 shadow_map(NULL), 360#ifndef NDEBUG 361 live_sreg(0), 362#endif 363 opcode_count(NULL) {} 364 365 int num_blocks; 366 GrowableList block_list; 367 Compiler* compiler; // Compiler driving this compiler 368 ClassLinker* class_linker; // Linker to resolve fields and methods 369 const DexFile* dex_file; // DexFile containing the method being compiled 370 jobject class_loader; // compiling method's class loader 371 uint32_t method_idx; // compiling method's index into method_ids of DexFile 372 const DexFile::CodeItem* code_item; // compiling method's DexFile code_item 373 uint32_t access_flags; // compiling method's access flags 374 InvokeType invoke_type; // compiling method's invocation type 375 const char* shorty; // compiling method's shorty 376 LIR* first_lir_insn; 377 LIR* last_lir_insn; 378 LIR* literal_list; // Constants 379 LIR* method_literal_list; // Method literals requiring patching 380 LIR* code_literal_list; // Code literals requiring patching 381 uint32_t disable_opt; // opt_control_vector flags 382 uint32_t enable_debug; // debugControlVector flags 383 int data_offset; // starting offset of literal pool 384 int total_size; // header + code size 385 AssemblerStatus assembler_status; // Success or fix and retry 386 int assembler_retries; 387 std::vector<uint8_t> code_buffer; 388 /* 389 * Holds mapping from native PC to dex PC for safepoints where we may deoptimize. 390 * Native PC is on the return address of the safepointed operation. Dex PC is for 391 * the instruction being executed at the safepoint. 392 */ 393 std::vector<uint32_t> pc2dexMappingTable; 394 /* 395 * Holds mapping from Dex PC to native PC for catch entry points. Native PC and Dex PC 396 * immediately preceed the instruction. 397 */ 398 std::vector<uint32_t> dex2pcMappingTable; 399 std::vector<uint32_t> combined_mapping_table; 400 std::vector<uint32_t> core_vmap_table; 401 std::vector<uint32_t> fp_vmap_table; 402 std::vector<uint8_t> native_gc_map; 403 bool verbose; 404 bool has_loop; // Contains a loop 405 bool has_invoke; // Contains an invoke instruction 406 bool qd_mode; // Compile for code size/compile time 407 RegisterPool* reg_pool; 408 InstructionSet instruction_set; 409 /* Number of total regs used in the whole cu after SSA transformation */ 410 int num_ssa_regs; 411 /* Map SSA reg i to the base virtual register/subscript */ 412 GrowableList* ssa_base_vregs; 413 GrowableList* ssa_subscripts; 414 GrowableList* ssa_strings; 415 416 /* The following are new data structures to support SSA representations */ 417 /* Map original Dalvik virtual reg i to the current SSA name */ 418 int* vreg_to_ssa_map; // length == method->registers_size 419 int* ssa_last_defs; // length == method->registers_size 420 ArenaBitVector* is_constant_v; // length == num_ssa_reg 421 int* constant_values; // length == num_ssa_reg 422 int* phi_alias_map; // length == num_ssa_reg 423 MIR* phi_list; 424 425 /* Use counts of ssa names */ 426 GrowableList use_counts; // Weighted by nesting depth 427 GrowableList raw_use_counts; // Not weighted 428 429 /* Optimization support */ 430 GrowableList loop_headers; 431 432 /* Map SSA names to location */ 433 RegLocation* reg_location; 434 435 /* Keep track of Dalvik v_reg to physical register mappings */ 436 PromotionMap* promotion_map; 437 438 /* SSA name for Method* */ 439 int method_sreg; 440 RegLocation method_loc; // Describes location of method* 441 442 int num_reachable_blocks; 443 int num_dalvik_registers; // method->registers_size 444 BasicBlock* entry_block; 445 BasicBlock* exit_block; 446 BasicBlock* cur_block; 447 GrowableList dfs_order; 448 GrowableList dfs_post_order; 449 GrowableList dom_post_order_traversal; 450 GrowableList throw_launchpads; 451 GrowableList suspend_launchpads; 452 GrowableList intrinsic_launchpads; 453 GrowableList compiler_temps; 454 int* i_dom_list; 455 ArenaBitVector* try_block_addr; 456 ArenaBitVector** def_block_matrix; // num_dalvik_register x num_blocks 457 ArenaBitVector* temp_block_v; 458 ArenaBitVector* temp_dalvik_register_v; 459 ArenaBitVector* temp_ssa_register_v; // num_ssa_regs 460 int* temp_ssa_block_id_v; // working storage for Phi labels 461 LIR* block_label_list; 462 /* 463 * Frame layout details. 464 * NOTE: for debug support it will be necessary to add a structure 465 * to map the Dalvik virtual registers to the promoted registers. 466 * NOTE: "num" fields are in 4-byte words, "Size" and "Offset" in bytes. 467 */ 468 int num_ins; 469 int num_outs; 470 int num_regs; // Unlike num_dalvik_registers, does not include ins 471 int num_core_spills; 472 int num_fp_spills; 473 int num_compiler_temps; 474 int frame_size; 475 unsigned int core_spill_mask; 476 unsigned int fp_spill_mask; 477 unsigned int attrs; 478 /* 479 * CLEANUP/RESTRUCTURE: The code generation utilities don't have a built-in 480 * mechanism to propagate the original Dalvik opcode address to the 481 * associated generated instructions. For the trace compiler, this wasn't 482 * necessary because the interpreter handled all throws and debugging 483 * requests. For now we'll handle this by placing the Dalvik offset 484 * in the CompilationUnit struct before codegen for each instruction. 485 * The low-level LIR creation utilites will pull it from here. Should 486 * be rewritten. 487 */ 488 int current_dalvik_offset; 489 GrowableList switch_tables; 490 GrowableList fill_array_data; 491 const uint16_t* insns; 492 uint32_t insns_size; 493 bool disable_dataflow; // Skip dataflow analysis if possible 494 SafeMap<unsigned int, BasicBlock*> block_map; // FindBlock lookup cache 495 SafeMap<unsigned int, unsigned int> block_id_map; // Block collapse lookup cache 496 SafeMap<unsigned int, LIR*> boundary_map; // boundary lookup cache 497 int def_count; // Used to estimate number of SSA names 498 499 // If non-empty, apply optimizer/debug flags only to matching methods. 500 std::string compiler_method_match; 501 // Flips sense of compiler_method_match - apply flags if doesn't match. 502 bool compiler_flip_match; 503 ArenaMemBlock* arena_head; 504 ArenaMemBlock* current_arena; 505 int num_arena_blocks; 506 Memstats* mstats; 507 Checkstats* checkstats; 508 bool gen_bitcode; 509 LLVMInfo* llvm_info; 510 llvm::LLVMContext* context; 511 llvm::Module* module; 512 llvm::Function* func; 513 greenland::IntrinsicHelper* intrinsic_helper; 514 greenland::IRBuilder* irb; 515 llvm::BasicBlock* placeholder_bb; 516 llvm::BasicBlock* entry_bb; 517 llvm::BasicBlock* entryTarget_bb; 518 std::string bitcode_filename; 519 GrowableList llvm_values; 520 int32_t temp_name; 521 SafeMap<llvm::BasicBlock*, LIR*> block_to_label_map; // llvm bb -> LIR label 522 SafeMap<int32_t, llvm::BasicBlock*> id_to_block_map; // block id -> llvm bb 523 SafeMap<llvm::Value*, RegLocation> loc_map; // llvm Value to loc rec 524 int num_shadow_frame_entries; 525 int* shadow_map; 526 std::set<llvm::BasicBlock*> llvm_blocks; 527#ifndef NDEBUG 528 /* 529 * Sanity checking for the register temp tracking. The same ssa 530 * name should never be associated with one temp register per 531 * instruction compilation. 532 */ 533 int live_sreg; 534#endif 535 std::set<uint32_t> catches; 536 int* opcode_count; // Count Dalvik opcodes for tuning 537}; 538 539struct SwitchTable { 540 int offset; 541 const uint16_t* table; // Original dex table 542 int vaddr; // Dalvik offset of switch opcode 543 LIR* anchor; // Reference instruction for relative offsets 544 LIR** targets; // Array of case targets 545}; 546 547struct FillArrayData { 548 int offset; 549 const uint16_t* table; // Original dex table 550 int size; 551 int vaddr; // Dalvik offset of FILL_ARRAY_DATA opcode 552}; 553 554#define MAX_PATTERN_LEN 5 555 556struct CodePattern { 557 const Instruction::Code opcodes[MAX_PATTERN_LEN]; 558 const SpecialCaseHandler handler_code; 559}; 560 561static const CodePattern special_patterns[] = { 562 {{Instruction::RETURN_VOID}, kNullMethod}, 563 {{Instruction::CONST, Instruction::RETURN}, kConstFunction}, 564 {{Instruction::CONST_4, Instruction::RETURN}, kConstFunction}, 565 {{Instruction::CONST_4, Instruction::RETURN_OBJECT}, kConstFunction}, 566 {{Instruction::CONST_16, Instruction::RETURN}, kConstFunction}, 567 {{Instruction::IGET, Instruction:: RETURN}, kIGet}, 568 {{Instruction::IGET_BOOLEAN, Instruction::RETURN}, kIGetBoolean}, 569 {{Instruction::IGET_OBJECT, Instruction::RETURN_OBJECT}, kIGetObject}, 570 {{Instruction::IGET_BYTE, Instruction::RETURN}, kIGetByte}, 571 {{Instruction::IGET_CHAR, Instruction::RETURN}, kIGetChar}, 572 {{Instruction::IGET_SHORT, Instruction::RETURN}, kIGetShort}, 573 {{Instruction::IGET_WIDE, Instruction::RETURN_WIDE}, kIGetWide}, 574 {{Instruction::IPUT, Instruction::RETURN_VOID}, kIPut}, 575 {{Instruction::IPUT_BOOLEAN, Instruction::RETURN_VOID}, kIPutBoolean}, 576 {{Instruction::IPUT_OBJECT, Instruction::RETURN_VOID}, kIPutObject}, 577 {{Instruction::IPUT_BYTE, Instruction::RETURN_VOID}, kIPutByte}, 578 {{Instruction::IPUT_CHAR, Instruction::RETURN_VOID}, kIPutChar}, 579 {{Instruction::IPUT_SHORT, Instruction::RETURN_VOID}, kIPutShort}, 580 {{Instruction::IPUT_WIDE, Instruction::RETURN_VOID}, kIPutWide}, 581 {{Instruction::RETURN}, kIdentity}, 582 {{Instruction::RETURN_OBJECT}, kIdentity}, 583 {{Instruction::RETURN_WIDE}, kIdentity}, 584}; 585 586BasicBlock* NewMemBB(CompilationUnit* cu, BBType block_type, int block_id); 587 588void AppendMIR(BasicBlock* bb, MIR* mir); 589 590void PrependMIR(BasicBlock* bb, MIR* mir); 591 592void InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir); 593 594void AppendLIR(CompilationUnit* cu, LIR* lir); 595 596void InsertLIRBefore(LIR* current_lir, LIR* new_lir); 597 598void InsertLIRAfter(LIR* current_lir, LIR* new_lir); 599 600MIR* FindMoveResult(CompilationUnit* cu, BasicBlock* bb, MIR* mir); 601/* Debug Utilities */ 602void DumpCompilationUnit(CompilationUnit* cu); 603 604} // namespace art 605 606#endif // ART_SRC_COMPILER_COMPILER_IR_H_ 607