codegen_util.cc revision 6e07183e822a32856da9eb60006989496e06a9cc 
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#include "mir_to_lir-inl.h"
18
19#include "base/bit_vector-inl.h"
20#include "dex/mir_graph.h"
21#include "driver/compiler_driver.h"
22#include "driver/compiler_options.h"
23#include "driver/dex_compilation_unit.h"
24#include "dex_file-inl.h"
25#include "gc_map.h"
26#include "gc_map_builder.h"
27#include "mapping_table.h"
28#include "dex/quick/dex_file_method_inliner.h"
29#include "dex/quick/dex_file_to_method_inliner_map.h"
30#include "dex/verification_results.h"
31#include "dex/verified_method.h"
32#include "verifier/dex_gc_map.h"
33#include "verifier/method_verifier.h"
34#include "vmap_table.h"
35
36namespace art {
37
38namespace {
39
40/* Dump a mapping table */
41template <typename It>
42void DumpMappingTable(const char* table_name, const char* descriptor, const char* name,
43                      const Signature& signature, uint32_t size, It first) {
44  if (size != 0) {
45    std::string line(StringPrintf("\n  %s %s%s_%s_table[%u] = {", table_name,
46                     descriptor, name, signature.ToString().c_str(), size));
47    std::replace(line.begin(), line.end(), ';', '_');
48    LOG(INFO) << line;
49    for (uint32_t i = 0; i != size; ++i) {
50      line = StringPrintf("    {0x%05x, 0x%04x},", first.NativePcOffset(), first.DexPc());
51      ++first;
52      LOG(INFO) << line;
53    }
54    LOG(INFO) <<"  };\n\n";
55  }
56}
57
58}  // anonymous namespace
59
60bool Mir2Lir::IsInexpensiveConstant(RegLocation rl_src) {
61  bool res = false;
62  if (rl_src.is_const) {
63    if (rl_src.wide) {
64      // For wide registers, check whether we're the high partner. In that case we need to switch
65      // to the lower one for the correct value.
66      if (rl_src.high_word) {
67        rl_src.high_word = false;
68        rl_src.s_reg_low--;
69        rl_src.orig_sreg--;
70      }
71      if (rl_src.fp) {
72        res = InexpensiveConstantDouble(mir_graph_->ConstantValueWide(rl_src));
73      } else {
74        res = InexpensiveConstantLong(mir_graph_->ConstantValueWide(rl_src));
75      }
76    } else {
77      if (rl_src.fp) {
78        res = InexpensiveConstantFloat(mir_graph_->ConstantValue(rl_src));
79      } else {
80        res = InexpensiveConstantInt(mir_graph_->ConstantValue(rl_src));
81      }
82    }
83  }
84  return res;
85}
86
87void Mir2Lir::MarkSafepointPC(LIR* inst) {
88  DCHECK(!inst->flags.use_def_invalid);
89  inst->u.m.def_mask = &kEncodeAll;
90  LIR* safepoint_pc = NewLIR0(kPseudoSafepointPC);
91  DCHECK(safepoint_pc->u.m.def_mask->Equals(kEncodeAll));
92  DCHECK(current_mir_ != nullptr || (current_dalvik_offset_ == 0 && safepoints_.empty()));
93  safepoints_.emplace_back(safepoint_pc, current_mir_);
94}
95
96void Mir2Lir::MarkSafepointPCAfter(LIR* after) {
97  DCHECK(!after->flags.use_def_invalid);
98  after->u.m.def_mask = &kEncodeAll;
99  // As NewLIR0 uses Append, we need to create the LIR by hand.
100  LIR* safepoint_pc = RawLIR(current_dalvik_offset_, kPseudoSafepointPC);
101  if (after->next == nullptr) {
102    DCHECK_EQ(after, last_lir_insn_);
103    AppendLIR(safepoint_pc);
104  } else {
105    InsertLIRAfter(after, safepoint_pc);
106  }
107  DCHECK(safepoint_pc->u.m.def_mask->Equals(kEncodeAll));
108  DCHECK(current_mir_ != nullptr || (current_dalvik_offset_ == 0 && safepoints_.empty()));
109  safepoints_.emplace_back(safepoint_pc, current_mir_);
110}
111
112/* Remove a LIR from the list. */
113void Mir2Lir::UnlinkLIR(LIR* lir) {
114  if (UNLIKELY(lir == first_lir_insn_)) {
115    first_lir_insn_ = lir->next;
116    if (lir->next != nullptr) {
117      lir->next->prev = nullptr;
118    } else {
119      DCHECK(lir->next == nullptr);
120      DCHECK(lir == last_lir_insn_);
121      last_lir_insn_ = nullptr;
122    }
123  } else if (lir == last_lir_insn_) {
124    last_lir_insn_ = lir->prev;
125    lir->prev->next = nullptr;
126  } else if ((lir->prev != nullptr) && (lir->next != nullptr)) {
127    lir->prev->next = lir->next;
128    lir->next->prev = lir->prev;
129  }
130}
131
132/* Convert an instruction to a NOP */
133void Mir2Lir::NopLIR(LIR* lir) {
134  lir->flags.is_nop = true;
135  if (!cu_->verbose) {
136    UnlinkLIR(lir);
137  }
138}
139
140void Mir2Lir::SetMemRefType(LIR* lir, bool is_load, int mem_type) {
141  DCHECK(GetTargetInstFlags(lir->opcode) & (IS_LOAD | IS_STORE));
142  DCHECK(!lir->flags.use_def_invalid);
143  // TODO: Avoid the extra Arena allocation!
144  const ResourceMask** mask_ptr;
145  ResourceMask mask;
146  if (is_load) {
147    mask_ptr = &lir->u.m.use_mask;
148  } else {
149    mask_ptr = &lir->u.m.def_mask;
150  }
151  mask = **mask_ptr;
152  /* Clear out the memref flags */
153  mask.ClearBits(kEncodeMem);
154  /* ..and then add back the one we need */
155  switch (mem_type) {
156    case ResourceMask::kLiteral:
157      DCHECK(is_load);
158      mask.SetBit(ResourceMask::kLiteral);
159      break;
160    case ResourceMask::kDalvikReg:
161      mask.SetBit(ResourceMask::kDalvikReg);
162      break;
163    case ResourceMask::kHeapRef:
164      mask.SetBit(ResourceMask::kHeapRef);
165      break;
166    case ResourceMask::kMustNotAlias:
167      /* Currently only loads can be marked as kMustNotAlias */
168      DCHECK(!(GetTargetInstFlags(lir->opcode) & IS_STORE));
169      mask.SetBit(ResourceMask::kMustNotAlias);
170      break;
171    default:
172      LOG(FATAL) << "Oat: invalid memref kind - " << mem_type;
173  }
174  *mask_ptr = mask_cache_.GetMask(mask);
175}
176
177/*
178 * Mark load/store instructions that access Dalvik registers through the stack.
179 */
180void Mir2Lir::AnnotateDalvikRegAccess(LIR* lir, int reg_id, bool is_load,
181                                      bool is64bit) {
182  DCHECK((is_load ? lir->u.m.use_mask : lir->u.m.def_mask)->Intersection(kEncodeMem).Equals(
183      kEncodeDalvikReg));
184
185  /*
186   * Store the Dalvik register id in alias_info. Mark the MSB if it is a 64-bit
187   * access.
188   */
189  lir->flags.alias_info = ENCODE_ALIAS_INFO(reg_id, is64bit);
190}
191
192/*
193 * Debugging macros
194 */
195#define DUMP_RESOURCE_MASK(X)
196
197/* Pretty-print a LIR instruction */
198void Mir2Lir::DumpLIRInsn(LIR* lir, unsigned char* base_addr) {
199  int offset = lir->offset;
200  int dest = lir->operands[0];
201  const bool dump_nop = (cu_->enable_debug & (1 << kDebugShowNops));
202
203  /* Handle pseudo-ops individually, and all regular insns as a group */
204  switch (lir->opcode) {
205    case kPseudoMethodEntry:
206      LOG(INFO) << "-------- method entry "
207                << PrettyMethod(cu_->method_idx, *cu_->dex_file);
208      break;
209    case kPseudoMethodExit:
210      LOG(INFO) << "-------- Method_Exit";
211      break;
212    case kPseudoBarrier:
213      LOG(INFO) << "-------- BARRIER";
214      break;
215    case kPseudoEntryBlock:
216      LOG(INFO) << "-------- entry offset: 0x" << std::hex << dest;
217      break;
218    case kPseudoDalvikByteCodeBoundary:
219      if (lir->operands[0] == 0) {
220         // NOTE: only used for debug listings.
221         lir->operands[0] = WrapPointer(ArenaStrdup("No instruction string"));
222      }
223      LOG(INFO) << "-------- dalvik offset: 0x" << std::hex
224                << lir->dalvik_offset << " @ "
225                << UnwrapPointer<char>(lir->operands[0]);
226      break;
227    case kPseudoExitBlock:
228      LOG(INFO) << "-------- exit offset: 0x" << std::hex << dest;
229      break;
230    case kPseudoPseudoAlign4:
231      LOG(INFO) << reinterpret_cast<uintptr_t>(base_addr) + offset << " (0x" << std::hex
232                << offset << "): .align4";
233      break;
234    case kPseudoEHBlockLabel:
235      LOG(INFO) << "Exception_Handling:";
236      break;
237    case kPseudoTargetLabel:
238    case kPseudoNormalBlockLabel:
239      LOG(INFO) << "L" << reinterpret_cast<void*>(lir) << ":";
240      break;
241    case kPseudoThrowTarget:
242      LOG(INFO) << "LT" << reinterpret_cast<void*>(lir) << ":";
243      break;
244    case kPseudoIntrinsicRetry:
245      LOG(INFO) << "IR" << reinterpret_cast<void*>(lir) << ":";
246      break;
247    case kPseudoSuspendTarget:
248      LOG(INFO) << "LS" << reinterpret_cast<void*>(lir) << ":";
249      break;
250    case kPseudoSafepointPC:
251      LOG(INFO) << "LsafepointPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
252      break;
253    case kPseudoExportedPC:
254      LOG(INFO) << "LexportedPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
255      break;
256    case kPseudoCaseLabel:
257      LOG(INFO) << "LC" << reinterpret_cast<void*>(lir) << ": Case target 0x"
258                << std::hex << lir->operands[0] << "|" << std::dec <<
259        lir->operands[0];
260      break;
261    default:
262      if (lir->flags.is_nop && !dump_nop) {
263        break;
264      } else {
265        std::string op_name(BuildInsnString(GetTargetInstName(lir->opcode),
266                                               lir, base_addr));
267        std::string op_operands(BuildInsnString(GetTargetInstFmt(lir->opcode),
268                                                    lir, base_addr));
269        LOG(INFO) << StringPrintf("%5p: %-9s%s%s",
270                                  base_addr + offset,
271                                  op_name.c_str(), op_operands.c_str(),
272                                  lir->flags.is_nop ? "(nop)" : "");
273      }
274      break;
275  }
276
277  if (lir->u.m.use_mask && (!lir->flags.is_nop || dump_nop)) {
278    DUMP_RESOURCE_MASK(DumpResourceMask(lir, *lir->u.m.use_mask, "use"));
279  }
280  if (lir->u.m.def_mask && (!lir->flags.is_nop || dump_nop)) {
281    DUMP_RESOURCE_MASK(DumpResourceMask(lir, *lir->u.m.def_mask, "def"));
282  }
283}
284
285void Mir2Lir::DumpPromotionMap() {
286  uint32_t num_regs = mir_graph_->GetNumOfCodeAndTempVRs();
287  for (uint32_t i = 0; i < num_regs; i++) {
288    PromotionMap v_reg_map = promotion_map_[i];
289    std::string buf;
290    if (v_reg_map.fp_location == kLocPhysReg) {
291      StringAppendF(&buf, " : s%d", RegStorage::RegNum(v_reg_map.fp_reg));
292    }
293
294    std::string buf3;
295    if (i < mir_graph_->GetNumOfCodeVRs()) {
296      StringAppendF(&buf3, "%02d", i);
297    } else if (i == mir_graph_->GetNumOfCodeVRs()) {
298      buf3 = "Method*";
299    } else {
300      uint32_t diff = i - mir_graph_->GetNumOfCodeVRs();
301      StringAppendF(&buf3, "ct%d", diff);
302    }
303
304    LOG(INFO) << StringPrintf("V[%s] -> %s%d%s", buf3.c_str(),
305                              v_reg_map.core_location == kLocPhysReg ?
306                              "r" : "SP+", v_reg_map.core_location == kLocPhysReg ?
307                              v_reg_map.core_reg : SRegOffset(i),
308                              buf.c_str());
309  }
310}
311
312void Mir2Lir::UpdateLIROffsets() {
313  // Only used for code listings.
314  size_t offset = 0;
315  for (LIR* lir = first_lir_insn_; lir != nullptr; lir = lir->next) {
316    lir->offset = offset;
317    if (!lir->flags.is_nop && !IsPseudoLirOp(lir->opcode)) {
318      offset += GetInsnSize(lir);
319    } else if (lir->opcode == kPseudoPseudoAlign4) {
320      offset += (offset & 0x2);
321    }
322  }
323}
324
325void Mir2Lir::MarkGCCard(int opt_flags, RegStorage val_reg, RegStorage tgt_addr_reg) {
326  DCHECK(val_reg.Valid());
327  DCHECK_EQ(val_reg.Is64Bit(), cu_->target64);
328  if ((opt_flags & MIR_STORE_NON_NULL_VALUE) != 0) {
329    UnconditionallyMarkGCCard(tgt_addr_reg);
330  } else {
331    LIR* branch_over = OpCmpImmBranch(kCondEq, val_reg, 0, nullptr);
332    UnconditionallyMarkGCCard(tgt_addr_reg);
333    LIR* target = NewLIR0(kPseudoTargetLabel);
334    branch_over->target = target;
335  }
336}
337
338/* Dump instructions and constant pool contents */
339void Mir2Lir::CodegenDump() {
340  LOG(INFO) << "Dumping LIR insns for "
341            << PrettyMethod(cu_->method_idx, *cu_->dex_file);
342  LIR* lir_insn;
343  int insns_size = mir_graph_->GetNumDalvikInsns();
344
345  LOG(INFO) << "Regs (excluding ins) : " << mir_graph_->GetNumOfLocalCodeVRs();
346  LOG(INFO) << "Ins          : " << mir_graph_->GetNumOfInVRs();
347  LOG(INFO) << "Outs         : " << mir_graph_->GetNumOfOutVRs();
348  LOG(INFO) << "CoreSpills       : " << num_core_spills_;
349  LOG(INFO) << "FPSpills       : " << num_fp_spills_;
350  LOG(INFO) << "CompilerTemps    : " << mir_graph_->GetNumUsedCompilerTemps();
351  LOG(INFO) << "Frame size       : " << frame_size_;
352  LOG(INFO) << "code size is " << total_size_ <<
353    " bytes, Dalvik size is " << insns_size * 2;
354  LOG(INFO) << "expansion factor: "
355            << static_cast<float>(total_size_) / static_cast<float>(insns_size * 2);
356  DumpPromotionMap();
357  UpdateLIROffsets();
358  for (lir_insn = first_lir_insn_; lir_insn != nullptr; lir_insn = lir_insn->next) {
359    DumpLIRInsn(lir_insn, 0);
360  }
361  for (lir_insn = literal_list_; lir_insn != nullptr; lir_insn = lir_insn->next) {
362    LOG(INFO) << StringPrintf("%x (%04x): .word (%#x)", lir_insn->offset, lir_insn->offset,
363                              lir_insn->operands[0]);
364  }
365
366  const DexFile::MethodId& method_id =
367      cu_->dex_file->GetMethodId(cu_->method_idx);
368  const Signature signature = cu_->dex_file->GetMethodSignature(method_id);
369  const char* name = cu_->dex_file->GetMethodName(method_id);
370  const char* descriptor(cu_->dex_file->GetMethodDeclaringClassDescriptor(method_id));
371
372  // Dump mapping tables
373  if (!encoded_mapping_table_.empty()) {
374    MappingTable table(&encoded_mapping_table_[0]);
375    DumpMappingTable("PC2Dex_MappingTable", descriptor, name, signature,
376                     table.PcToDexSize(), table.PcToDexBegin());
377    DumpMappingTable("Dex2PC_MappingTable", descriptor, name, signature,
378                     table.DexToPcSize(), table.DexToPcBegin());
379  }
380}
381
382/*
383 * Search the existing constants in the literal pool for an exact or close match
384 * within specified delta (greater or equal to 0).
385 */
386LIR* Mir2Lir::ScanLiteralPool(LIR* data_target, int value, unsigned int delta) {
387  while (data_target) {
388    if ((static_cast<unsigned>(value - data_target->operands[0])) <= delta)
389      return data_target;
390    data_target = data_target->next;
391  }
392  return nullptr;
393}
394
395/* Search the existing constants in the literal pool for an exact wide match */
396LIR* Mir2Lir::ScanLiteralPoolWide(LIR* data_target, int val_lo, int val_hi) {
397  bool lo_match = false;
398  LIR* lo_target = nullptr;
399  while (data_target) {
400    if (lo_match && (data_target->operands[0] == val_hi)) {
401      // Record high word in case we need to expand this later.
402      lo_target->operands[1] = val_hi;
403      return lo_target;
404    }
405    lo_match = false;
406    if (data_target->operands[0] == val_lo) {
407      lo_match = true;
408      lo_target = data_target;
409    }
410    data_target = data_target->next;
411  }
412  return nullptr;
413}
414
415/* Search the existing constants in the literal pool for an exact method match */
416LIR* Mir2Lir::ScanLiteralPoolMethod(LIR* data_target, const MethodReference& method) {
417  while (data_target) {
418    if (static_cast<uint32_t>(data_target->operands[0]) == method.dex_method_index &&
419        UnwrapPointer<DexFile>(data_target->operands[1]) == method.dex_file) {
420      return data_target;
421    }
422    data_target = data_target->next;
423  }
424  return nullptr;
425}
426
427/* Search the existing constants in the literal pool for an exact class match */
428LIR* Mir2Lir::ScanLiteralPoolClass(LIR* data_target, const DexFile& dex_file, uint32_t type_idx) {
429  while (data_target) {
430    if (static_cast<uint32_t>(data_target->operands[0]) == type_idx &&
431        UnwrapPointer<DexFile>(data_target->operands[1]) == &dex_file) {
432      return data_target;
433    }
434    data_target = data_target->next;
435  }
436  return nullptr;
437}
438
439/*
440 * The following are building blocks to insert constants into the pool or
441 * instruction streams.
442 */
443
444/* Add a 32-bit constant to the constant pool */
445LIR* Mir2Lir::AddWordData(LIR* *constant_list_p, int value) {
446  /* Add the constant to the literal pool */
447  if (constant_list_p) {
448    LIR* new_value = static_cast<LIR*>(arena_->Alloc(sizeof(LIR), kArenaAllocData));
449    new_value->operands[0] = value;
450    new_value->next = *constant_list_p;
451    *constant_list_p = new_value;
452    estimated_native_code_size_ += sizeof(value);
453    return new_value;
454  }
455  return nullptr;
456}
457
458/* Add a 64-bit constant to the constant pool or mixed with code */
459LIR* Mir2Lir::AddWideData(LIR* *constant_list_p, int val_lo, int val_hi) {
460  AddWordData(constant_list_p, val_hi);
461  return AddWordData(constant_list_p, val_lo);
462}
463
464/**
465 * @brief Push a compressed reference which needs patching at link/patchoat-time.
466 * @details This needs to be kept consistent with the code which actually does the patching in
467 *   oat_writer.cc and in the patchoat tool.
468 */
469static void PushUnpatchedReference(CodeBuffer* buf) {
470  // Note that we can safely initialize the patches to zero. The code deduplication mechanism takes
471  // the patches into account when determining whether two pieces of codes are functionally
472  // equivalent.
473  Push32(buf, UINT32_C(0));
474}
475
476static void AlignBuffer(CodeBuffer* buf, size_t offset) {
477  DCHECK_LE(buf->size(), offset);
478  buf->insert(buf->end(), offset - buf->size(), 0u);
479}
480
481/* Write the literal pool to the output stream */
482void Mir2Lir::InstallLiteralPools() {
483  AlignBuffer(&code_buffer_, data_offset_);
484  LIR* data_lir = literal_list_;
485  while (data_lir != nullptr) {
486    Push32(&code_buffer_, data_lir->operands[0]);
487    data_lir = NEXT_LIR(data_lir);
488  }
489  // TODO: patches_.reserve() as needed.
490  // Push code and method literals, record offsets for the compiler to patch.
491  data_lir = code_literal_list_;
492  while (data_lir != nullptr) {
493    uint32_t target_method_idx = data_lir->operands[0];
494    const DexFile* target_dex_file = UnwrapPointer<DexFile>(data_lir->operands[1]);
495    patches_.push_back(LinkerPatch::CodePatch(code_buffer_.size(),
496                                              target_dex_file, target_method_idx));
497    PushUnpatchedReference(&code_buffer_);
498    data_lir = NEXT_LIR(data_lir);
499  }
500  data_lir = method_literal_list_;
501  while (data_lir != nullptr) {
502    uint32_t target_method_idx = data_lir->operands[0];
503    const DexFile* target_dex_file = UnwrapPointer<DexFile>(data_lir->operands[1]);
504    patches_.push_back(LinkerPatch::MethodPatch(code_buffer_.size(),
505                                                target_dex_file, target_method_idx));
506    PushUnpatchedReference(&code_buffer_);
507    data_lir = NEXT_LIR(data_lir);
508  }
509  // Push class literals.
510  data_lir = class_literal_list_;
511  while (data_lir != nullptr) {
512    uint32_t target_type_idx = data_lir->operands[0];
513    const DexFile* class_dex_file = UnwrapPointer<DexFile>(data_lir->operands[1]);
514    patches_.push_back(LinkerPatch::TypePatch(code_buffer_.size(),
515                                              class_dex_file, target_type_idx));
516    PushUnpatchedReference(&code_buffer_);
517    data_lir = NEXT_LIR(data_lir);
518  }
519}
520
521/* Write the switch tables to the output stream */
522void Mir2Lir::InstallSwitchTables() {
523  for (Mir2Lir::SwitchTable* tab_rec : switch_tables_) {
524    AlignBuffer(&code_buffer_, tab_rec->offset);
525    /*
526     * For Arm, our reference point is the address of the bx
527     * instruction that does the launch, so we have to subtract
528     * the auto pc-advance.  For other targets the reference point
529     * is a label, so we can use the offset as-is.
530     */
531    int bx_offset = INVALID_OFFSET;
532    switch (cu_->instruction_set) {
533      case kThumb2:
534        DCHECK(tab_rec->anchor->flags.fixup != kFixupNone);
535        bx_offset = tab_rec->anchor->offset + 4;
536        break;
537      case kX86:
538        bx_offset = 0;
539        break;
540      case kX86_64:
541        // RIP relative to switch table.
542        bx_offset = tab_rec->offset;
543        break;
544      case kArm64:
545      case kMips:
546      case kMips64:
547        bx_offset = tab_rec->anchor->offset;
548        break;
549      default: LOG(FATAL) << "Unexpected instruction set: " << cu_->instruction_set;
550    }
551    if (cu_->verbose) {
552      LOG(INFO) << "Switch table for offset 0x" << std::hex << bx_offset;
553    }
554    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
555      DCHECK(tab_rec->switch_mir != nullptr);
556      BasicBlock* bb = mir_graph_->GetBasicBlock(tab_rec->switch_mir->bb);
557      DCHECK(bb != nullptr);
558      int elems = 0;
559      for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
560        int key = successor_block_info->key;
561        int target = successor_block_info->block;
562        LIR* boundary_lir = InsertCaseLabel(target, key);
563        DCHECK(boundary_lir != nullptr);
564        int disp = boundary_lir->offset - bx_offset;
565        Push32(&code_buffer_, key);
566        Push32(&code_buffer_, disp);
567        if (cu_->verbose) {
568          LOG(INFO) << "  Case[" << elems << "] key: 0x"
569                    << std::hex << key << ", disp: 0x"
570                    << std::hex << disp;
571        }
572        elems++;
573      }
574      DCHECK_EQ(elems, tab_rec->table[1]);
575    } else {
576      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
577                static_cast<int>(Instruction::kPackedSwitchSignature));
578      DCHECK(tab_rec->switch_mir != nullptr);
579      BasicBlock* bb = mir_graph_->GetBasicBlock(tab_rec->switch_mir->bb);
580      DCHECK(bb != nullptr);
581      int elems = 0;
582      int low_key = s4FromSwitchData(&tab_rec->table[2]);
583      for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) {
584        int key = successor_block_info->key;
585        DCHECK_EQ(elems + low_key, key);
586        int target = successor_block_info->block;
587        LIR* boundary_lir = InsertCaseLabel(target, key);
588        DCHECK(boundary_lir != nullptr);
589        int disp = boundary_lir->offset - bx_offset;
590        Push32(&code_buffer_, disp);
591        if (cu_->verbose) {
592          LOG(INFO) << "  Case[" << elems << "] disp: 0x"
593                    << std::hex << disp;
594        }
595        elems++;
596      }
597      DCHECK_EQ(elems, tab_rec->table[1]);
598    }
599  }
600}
601
602/* Write the fill array dta to the output stream */
603void Mir2Lir::InstallFillArrayData() {
604  for (Mir2Lir::FillArrayData* tab_rec : fill_array_data_) {
605    AlignBuffer(&code_buffer_, tab_rec->offset);
606    for (int i = 0; i < (tab_rec->size + 1) / 2; i++) {
607      code_buffer_.push_back(tab_rec->table[i] & 0xFF);
608      code_buffer_.push_back((tab_rec->table[i] >> 8) & 0xFF);
609    }
610  }
611}
612
613static int AssignLiteralOffsetCommon(LIR* lir, CodeOffset offset) {
614  for (; lir != nullptr; lir = lir->next) {
615    lir->offset = offset;
616    offset += 4;
617  }
618  return offset;
619}
620
621static int AssignLiteralPointerOffsetCommon(LIR* lir, CodeOffset offset,
622                                            unsigned int element_size) {
623  // Align to natural pointer size.
624  offset = RoundUp(offset, element_size);
625  for (; lir != nullptr; lir = lir->next) {
626    lir->offset = offset;
627    offset += element_size;
628  }
629  return offset;
630}
631
632// Make sure we have a code address for every declared catch entry
633bool Mir2Lir::VerifyCatchEntries() {
634  MappingTable table(&encoded_mapping_table_[0]);
635  std::vector<uint32_t> dex_pcs;
636  dex_pcs.reserve(table.DexToPcSize());
637  for (auto it = table.DexToPcBegin(), end = table.DexToPcEnd(); it != end; ++it) {
638    dex_pcs.push_back(it.DexPc());
639  }
640  // Sort dex_pcs, so that we can quickly check it against the ordered mir_graph_->catches_.
641  std::sort(dex_pcs.begin(), dex_pcs.end());
642
643  bool success = true;
644  auto it = dex_pcs.begin(), end = dex_pcs.end();
645  for (uint32_t dex_pc : mir_graph_->catches_) {
646    while (it != end && *it < dex_pc) {
647      LOG(INFO) << "Unexpected catch entry @ dex pc 0x" << std::hex << *it;
648      ++it;
649      success = false;
650    }
651    if (it == end || *it > dex_pc) {
652      LOG(INFO) << "Missing native PC for catch entry @ 0x" << std::hex << dex_pc;
653      success = false;
654    } else {
655      ++it;
656    }
657  }
658  if (!success) {
659    LOG(INFO) << "Bad dex2pcMapping table in " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
660    LOG(INFO) << "Entries @ decode: " << mir_graph_->catches_.size() << ", Entries in table: "
661              << table.DexToPcSize();
662  }
663  return success;
664}
665
666
667void Mir2Lir::CreateMappingTables() {
668  bool generate_src_map = cu_->compiler_driver->GetCompilerOptions().GetIncludeDebugSymbols();
669
670  uint32_t pc2dex_data_size = 0u;
671  uint32_t pc2dex_entries = 0u;
672  uint32_t pc2dex_offset = 0u;
673  uint32_t pc2dex_dalvik_offset = 0u;
674  uint32_t pc2dex_src_entries = 0u;
675  uint32_t dex2pc_data_size = 0u;
676  uint32_t dex2pc_entries = 0u;
677  uint32_t dex2pc_offset = 0u;
678  uint32_t dex2pc_dalvik_offset = 0u;
679  for (LIR* tgt_lir = first_lir_insn_; tgt_lir != nullptr; tgt_lir = NEXT_LIR(tgt_lir)) {
680    pc2dex_src_entries++;
681    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
682      pc2dex_entries += 1;
683      DCHECK(pc2dex_offset <= tgt_lir->offset);
684      pc2dex_data_size += UnsignedLeb128Size(tgt_lir->offset - pc2dex_offset);
685      pc2dex_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
686                                           static_cast<int32_t>(pc2dex_dalvik_offset));
687      pc2dex_offset = tgt_lir->offset;
688      pc2dex_dalvik_offset = tgt_lir->dalvik_offset;
689    }
690    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
691      dex2pc_entries += 1;
692      DCHECK(dex2pc_offset <= tgt_lir->offset);
693      dex2pc_data_size += UnsignedLeb128Size(tgt_lir->offset - dex2pc_offset);
694      dex2pc_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
695                                           static_cast<int32_t>(dex2pc_dalvik_offset));
696      dex2pc_offset = tgt_lir->offset;
697      dex2pc_dalvik_offset = tgt_lir->dalvik_offset;
698    }
699  }
700
701  if (generate_src_map) {
702    src_mapping_table_.reserve(pc2dex_src_entries);
703  }
704
705  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
706  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
707  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
708  encoded_mapping_table_.resize(data_size);
709  uint8_t* write_pos = &encoded_mapping_table_[0];
710  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
711  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
712  DCHECK_EQ(static_cast<size_t>(write_pos - &encoded_mapping_table_[0]), hdr_data_size);
713  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
714
715  pc2dex_offset = 0u;
716  pc2dex_dalvik_offset = 0u;
717  dex2pc_offset = 0u;
718  dex2pc_dalvik_offset = 0u;
719  for (LIR* tgt_lir = first_lir_insn_; tgt_lir != nullptr; tgt_lir = NEXT_LIR(tgt_lir)) {
720    if (generate_src_map && !tgt_lir->flags.is_nop) {
721      src_mapping_table_.push_back(SrcMapElem({tgt_lir->offset,
722              static_cast<int32_t>(tgt_lir->dalvik_offset)}));
723    }
724    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
725      DCHECK(pc2dex_offset <= tgt_lir->offset);
726      write_pos = EncodeUnsignedLeb128(write_pos, tgt_lir->offset - pc2dex_offset);
727      write_pos = EncodeSignedLeb128(write_pos, static_cast<int32_t>(tgt_lir->dalvik_offset) -
728                                     static_cast<int32_t>(pc2dex_dalvik_offset));
729      pc2dex_offset = tgt_lir->offset;
730      pc2dex_dalvik_offset = tgt_lir->dalvik_offset;
731    }
732    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
733      DCHECK(dex2pc_offset <= tgt_lir->offset);
734      write_pos2 = EncodeUnsignedLeb128(write_pos2, tgt_lir->offset - dex2pc_offset);
735      write_pos2 = EncodeSignedLeb128(write_pos2, static_cast<int32_t>(tgt_lir->dalvik_offset) -
736                                      static_cast<int32_t>(dex2pc_dalvik_offset));
737      dex2pc_offset = tgt_lir->offset;
738      dex2pc_dalvik_offset = tgt_lir->dalvik_offset;
739    }
740  }
741  DCHECK_EQ(static_cast<size_t>(write_pos - &encoded_mapping_table_[0]),
742            hdr_data_size + pc2dex_data_size);
743  DCHECK_EQ(static_cast<size_t>(write_pos2 - &encoded_mapping_table_[0]), data_size);
744
745  if (kIsDebugBuild) {
746    CHECK(VerifyCatchEntries());
747
748    // Verify the encoded table holds the expected data.
749    MappingTable table(&encoded_mapping_table_[0]);
750    CHECK_EQ(table.TotalSize(), total_entries);
751    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
752    auto it = table.PcToDexBegin();
753    auto it2 = table.DexToPcBegin();
754    for (LIR* tgt_lir = first_lir_insn_; tgt_lir != nullptr; tgt_lir = NEXT_LIR(tgt_lir)) {
755      if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
756        CHECK_EQ(tgt_lir->offset, it.NativePcOffset());
757        CHECK_EQ(tgt_lir->dalvik_offset, it.DexPc());
758        ++it;
759      }
760      if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
761        CHECK_EQ(tgt_lir->offset, it2.NativePcOffset());
762        CHECK_EQ(tgt_lir->dalvik_offset, it2.DexPc());
763        ++it2;
764      }
765    }
766    CHECK(it == table.PcToDexEnd());
767    CHECK(it2 == table.DexToPcEnd());
768  }
769}
770
771void Mir2Lir::CreateNativeGcMap() {
772  if (UNLIKELY((cu_->disable_opt & (1u << kPromoteRegs)) != 0u)) {
773    // If we're not promoting to physical registers, it's safe to use the verifier's notion of
774    // references. (We disable register promotion when type inference finds a type conflict and
775    // in that the case we defer to the verifier to avoid using the compiler's conflicting info.)
776    CreateNativeGcMapWithoutRegisterPromotion();
777    return;
778  }
779
780  ArenaBitVector* references = new (arena_) ArenaBitVector(arena_, mir_graph_->GetNumSSARegs(),
781                                                           false);
782
783  // Calculate max native offset and max reference vreg.
784  MIR* prev_mir = nullptr;
785  int max_ref_vreg = -1;
786  CodeOffset max_native_offset = 0u;
787  for (const auto& entry : safepoints_) {
788    uint32_t native_offset = entry.first->offset;
789    max_native_offset = std::max(max_native_offset, native_offset);
790    MIR* mir = entry.second;
791    UpdateReferenceVRegs(mir, prev_mir, references);
792    max_ref_vreg = std::max(max_ref_vreg, references->GetHighestBitSet());
793    prev_mir = mir;
794  }
795
796#if defined(BYTE_ORDER) && (BYTE_ORDER == LITTLE_ENDIAN)
797  static constexpr bool kLittleEndian = true;
798#else
799  static constexpr bool kLittleEndian = false;
800#endif
801
802  // Build the GC map.
803  uint32_t reg_width = static_cast<uint32_t>((max_ref_vreg + 8) / 8);
804  GcMapBuilder native_gc_map_builder(&native_gc_map_,
805                                     safepoints_.size(),
806                                     max_native_offset, reg_width);
807  if (kLittleEndian) {
808    for (const auto& entry : safepoints_) {
809      uint32_t native_offset = entry.first->offset;
810      MIR* mir = entry.second;
811      UpdateReferenceVRegs(mir, prev_mir, references);
812      // For little-endian, the bytes comprising the bit vector's raw storage are what we need.
813      native_gc_map_builder.AddEntry(native_offset,
814                                     reinterpret_cast<const uint8_t*>(references->GetRawStorage()));
815      prev_mir = mir;
816    }
817  } else {
818    ArenaVector<uint8_t> references_buffer(arena_->Adapter());
819    references_buffer.resize(reg_width);
820    for (const auto& entry : safepoints_) {
821      uint32_t native_offset = entry.first->offset;
822      MIR* mir = entry.second;
823      UpdateReferenceVRegs(mir, prev_mir, references);
824      // Big-endian or unknown endianness, manually translate the bit vector data.
825      const auto* raw_storage = references->GetRawStorage();
826      for (size_t i = 0; i != reg_width; ++i) {
827        references_buffer[i] = static_cast<uint8_t>(
828            raw_storage[i / sizeof(raw_storage[0])] >> (8u * (i % sizeof(raw_storage[0]))));
829      }
830      native_gc_map_builder.AddEntry(native_offset, &references_buffer[0]);
831      prev_mir = mir;
832    }
833  }
834}
835
836void Mir2Lir::CreateNativeGcMapWithoutRegisterPromotion() {
837  DCHECK(!encoded_mapping_table_.empty());
838  MappingTable mapping_table(&encoded_mapping_table_[0]);
839  uint32_t max_native_offset = 0;
840  for (auto it = mapping_table.PcToDexBegin(), end = mapping_table.PcToDexEnd(); it != end; ++it) {
841    uint32_t native_offset = it.NativePcOffset();
842    if (native_offset > max_native_offset) {
843      max_native_offset = native_offset;
844    }
845  }
846  MethodReference method_ref(cu_->dex_file, cu_->method_idx);
847  const std::vector<uint8_t>& gc_map_raw =
848      mir_graph_->GetCurrentDexCompilationUnit()->GetVerifiedMethod()->GetDexGcMap();
849  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
850  DCHECK_EQ(gc_map_raw.size(), dex_gc_map.RawSize());
851  // Compute native offset to references size.
852  GcMapBuilder native_gc_map_builder(&native_gc_map_,
853                                     mapping_table.PcToDexSize(),
854                                     max_native_offset, dex_gc_map.RegWidth());
855
856  for (auto it = mapping_table.PcToDexBegin(), end = mapping_table.PcToDexEnd(); it != end; ++it) {
857    uint32_t native_offset = it.NativePcOffset();
858    uint32_t dex_pc = it.DexPc();
859    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
860    CHECK(references != nullptr) << "Missing ref for dex pc 0x" << std::hex << dex_pc <<
861        ": " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
862    native_gc_map_builder.AddEntry(native_offset, references);
863  }
864
865  // Maybe not necessary, but this could help prevent errors where we access the verified method
866  // after it has been deleted.
867  mir_graph_->GetCurrentDexCompilationUnit()->ClearVerifiedMethod();
868}
869
870/* Determine the offset of each literal field */
871int Mir2Lir::AssignLiteralOffset(CodeOffset offset) {
872  offset = AssignLiteralOffsetCommon(literal_list_, offset);
873  constexpr unsigned int ptr_size = sizeof(uint32_t);
874  static_assert(ptr_size >= sizeof(mirror::HeapReference<mirror::Object>),
875                "Pointer size cannot hold a heap reference");
876  offset = AssignLiteralPointerOffsetCommon(code_literal_list_, offset, ptr_size);
877  offset = AssignLiteralPointerOffsetCommon(method_literal_list_, offset, ptr_size);
878  offset = AssignLiteralPointerOffsetCommon(class_literal_list_, offset, ptr_size);
879  return offset;
880}
881
882int Mir2Lir::AssignSwitchTablesOffset(CodeOffset offset) {
883  for (Mir2Lir::SwitchTable* tab_rec : switch_tables_) {
884    tab_rec->offset = offset;
885    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
886      offset += tab_rec->table[1] * (sizeof(int) * 2);
887    } else {
888      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
889                static_cast<int>(Instruction::kPackedSwitchSignature));
890      offset += tab_rec->table[1] * sizeof(int);
891    }
892  }
893  return offset;
894}
895
896int Mir2Lir::AssignFillArrayDataOffset(CodeOffset offset) {
897  for (Mir2Lir::FillArrayData* tab_rec : fill_array_data_) {
898    tab_rec->offset = offset;
899    offset += tab_rec->size;
900    // word align
901    offset = RoundUp(offset, 4);
902  }
903  return offset;
904}
905
906/*
907 * Insert a kPseudoCaseLabel at the beginning of the Dalvik
908 * offset vaddr if pretty-printing, otherise use the standard block
909 * label.  The selected label will be used to fix up the case
910 * branch table during the assembly phase.  All resource flags
911 * are set to prevent code motion.  KeyVal is just there for debugging.
912 */
913LIR* Mir2Lir::InsertCaseLabel(uint32_t bbid, int keyVal) {
914  LIR* boundary_lir = &block_label_list_[bbid];
915  LIR* res = boundary_lir;
916  if (cu_->verbose) {
917    // Only pay the expense if we're pretty-printing.
918    LIR* new_label = static_cast<LIR*>(arena_->Alloc(sizeof(LIR), kArenaAllocLIR));
919    BasicBlock* bb = mir_graph_->GetBasicBlock(bbid);
920    DCHECK(bb != nullptr);
921    new_label->dalvik_offset = bb->start_offset;
922    new_label->opcode = kPseudoCaseLabel;
923    new_label->operands[0] = keyVal;
924    new_label->flags.fixup = kFixupLabel;
925    DCHECK(!new_label->flags.use_def_invalid);
926    new_label->u.m.def_mask = &kEncodeAll;
927    InsertLIRAfter(boundary_lir, new_label);
928  }
929  return res;
930}
931
932void Mir2Lir::DumpSparseSwitchTable(const uint16_t* table) {
933  /*
934   * Sparse switch data format:
935   *  ushort ident = 0x0200   magic value
936   *  ushort size       number of entries in the table; > 0
937   *  int keys[size]      keys, sorted low-to-high; 32-bit aligned
938   *  int targets[size]     branch targets, relative to switch opcode
939   *
940   * Total size is (2+size*4) 16-bit code units.
941   */
942  uint16_t ident = table[0];
943  int entries = table[1];
944  const int32_t* keys = reinterpret_cast<const int32_t*>(&table[2]);
945  const int32_t* targets = &keys[entries];
946  LOG(INFO) <<  "Sparse switch table - ident:0x" << std::hex << ident
947            << ", entries: " << std::dec << entries;
948  for (int i = 0; i < entries; i++) {
949    LOG(INFO) << "  Key[" << keys[i] << "] -> 0x" << std::hex << targets[i];
950  }
951}
952
953void Mir2Lir::DumpPackedSwitchTable(const uint16_t* table) {
954  /*
955   * Packed switch data format:
956   *  ushort ident = 0x0100   magic value
957   *  ushort size       number of entries in the table
958   *  int first_key       first (and lowest) switch case value
959   *  int targets[size]     branch targets, relative to switch opcode
960   *
961   * Total size is (4+size*2) 16-bit code units.
962   */
963  uint16_t ident = table[0];
964  const int32_t* targets = reinterpret_cast<const int32_t*>(&table[4]);
965  int entries = table[1];
966  int low_key = s4FromSwitchData(&table[2]);
967  LOG(INFO) << "Packed switch table - ident:0x" << std::hex << ident
968            << ", entries: " << std::dec << entries << ", low_key: " << low_key;
969  for (int i = 0; i < entries; i++) {
970    LOG(INFO) << "  Key[" << (i + low_key) << "] -> 0x" << std::hex
971              << targets[i];
972  }
973}
974
975/* Set up special LIR to mark a Dalvik byte-code instruction start for pretty printing */
976void Mir2Lir::MarkBoundary(DexOffset offset, const char* inst_str) {
977  UNUSED(offset);
978  // NOTE: only used for debug listings.
979  NewLIR1(kPseudoDalvikByteCodeBoundary, WrapPointer(ArenaStrdup(inst_str)));
980}
981
982// Convert relation of src1/src2 to src2/src1
983ConditionCode Mir2Lir::FlipComparisonOrder(ConditionCode before) {
984  ConditionCode res;
985  switch (before) {
986    case kCondEq: res = kCondEq; break;
987    case kCondNe: res = kCondNe; break;
988    case kCondLt: res = kCondGt; break;
989    case kCondGt: res = kCondLt; break;
990    case kCondLe: res = kCondGe; break;
991    case kCondGe: res = kCondLe; break;
992    default:
993      LOG(FATAL) << "Unexpected ccode " << before;
994      UNREACHABLE();
995  }
996  return res;
997}
998
999ConditionCode Mir2Lir::NegateComparison(ConditionCode before) {
1000  ConditionCode res;
1001  switch (before) {
1002    case kCondEq: res = kCondNe; break;
1003    case kCondNe: res = kCondEq; break;
1004    case kCondLt: res = kCondGe; break;
1005    case kCondGt: res = kCondLe; break;
1006    case kCondLe: res = kCondGt; break;
1007    case kCondGe: res = kCondLt; break;
1008    default:
1009      LOG(FATAL) << "Unexpected ccode " << before;
1010      UNREACHABLE();
1011  }
1012  return res;
1013}
1014
1015// TODO: move to mir_to_lir.cc
1016Mir2Lir::Mir2Lir(CompilationUnit* cu, MIRGraph* mir_graph, ArenaAllocator* arena)
1017    : literal_list_(nullptr),
1018      method_literal_list_(nullptr),
1019      class_literal_list_(nullptr),
1020      code_literal_list_(nullptr),
1021      first_fixup_(nullptr),
1022      arena_(arena),
1023      cu_(cu),
1024      mir_graph_(mir_graph),
1025      switch_tables_(arena->Adapter(kArenaAllocSwitchTable)),
1026      fill_array_data_(arena->Adapter(kArenaAllocFillArrayData)),
1027      tempreg_info_(arena->Adapter()),
1028      reginfo_map_(arena->Adapter()),
1029      pointer_storage_(arena->Adapter()),
1030      data_offset_(0),
1031      total_size_(0),
1032      block_label_list_(nullptr),
1033      promotion_map_(nullptr),
1034      current_dalvik_offset_(0),
1035      current_mir_(nullptr),
1036      estimated_native_code_size_(0),
1037      reg_pool_(nullptr),
1038      live_sreg_(0),
1039      code_buffer_(mir_graph->GetArena()->Adapter()),
1040      encoded_mapping_table_(mir_graph->GetArena()->Adapter()),
1041      core_vmap_table_(mir_graph->GetArena()->Adapter()),
1042      fp_vmap_table_(mir_graph->GetArena()->Adapter()),
1043      native_gc_map_(mir_graph->GetArena()->Adapter()),
1044      patches_(mir_graph->GetArena()->Adapter()),
1045      num_core_spills_(0),
1046      num_fp_spills_(0),
1047      frame_size_(0),
1048      core_spill_mask_(0),
1049      fp_spill_mask_(0),
1050      first_lir_insn_(nullptr),
1051      last_lir_insn_(nullptr),
1052      slow_paths_(arena->Adapter(kArenaAllocSlowPaths)),
1053      mem_ref_type_(ResourceMask::kHeapRef),
1054      mask_cache_(arena),
1055      safepoints_(arena->Adapter()),
1056      in_to_reg_storage_mapping_(arena) {
1057  switch_tables_.reserve(4);
1058  fill_array_data_.reserve(4);
1059  tempreg_info_.reserve(20);
1060  reginfo_map_.reserve(RegStorage::kMaxRegs);
1061  pointer_storage_.reserve(128);
1062  slow_paths_.reserve(32);
1063  // Reserve pointer id 0 for nullptr.
1064  size_t null_idx = WrapPointer<void>(nullptr);
1065  DCHECK_EQ(null_idx, 0U);
1066}
1067
1068void Mir2Lir::Materialize() {
1069  cu_->NewTimingSplit("RegisterAllocation");
1070  CompilerInitializeRegAlloc();  // Needs to happen after SSA naming
1071
1072  /* Allocate Registers using simple local allocation scheme */
1073  SimpleRegAlloc();
1074
1075  /* First try the custom light codegen for special cases. */
1076  DCHECK(cu_->compiler_driver->GetMethodInlinerMap() != nullptr);
1077  bool special_worked = cu_->compiler_driver->GetMethodInlinerMap()->GetMethodInliner(cu_->dex_file)
1078      ->GenSpecial(this, cu_->method_idx);
1079
1080  /* Take normal path for converting MIR to LIR only if the special codegen did not succeed. */
1081  if (special_worked == false) {
1082    MethodMIR2LIR();
1083  }
1084
1085  /* Method is not empty */
1086  if (first_lir_insn_) {
1087    /* Convert LIR into machine code. */
1088    AssembleLIR();
1089
1090    if ((cu_->enable_debug & (1 << kDebugCodegenDump)) != 0) {
1091      CodegenDump();
1092    }
1093  }
1094}
1095
1096CompiledMethod* Mir2Lir::GetCompiledMethod() {
1097  // Combine vmap tables - core regs, then fp regs - into vmap_table.
1098  Leb128EncodingVector vmap_encoder;
1099  if (frame_size_ > 0) {
1100    // Prefix the encoded data with its size.
1101    size_t size = core_vmap_table_.size() + 1 /* marker */ + fp_vmap_table_.size();
1102    vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
1103    vmap_encoder.PushBackUnsigned(size);
1104    // Core regs may have been inserted out of order - sort first.
1105    std::sort(core_vmap_table_.begin(), core_vmap_table_.end());
1106    for (size_t i = 0 ; i < core_vmap_table_.size(); ++i) {
1107      // Copy, stripping out the phys register sort key.
1108      vmap_encoder.PushBackUnsigned(
1109          ~(-1 << VREG_NUM_WIDTH) & (core_vmap_table_[i] + VmapTable::kEntryAdjustment));
1110    }
1111    // Push a marker to take place of lr.
1112    vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
1113    if (cu_->instruction_set == kThumb2) {
1114      // fp regs already sorted.
1115      for (uint32_t i = 0; i < fp_vmap_table_.size(); i++) {
1116        vmap_encoder.PushBackUnsigned(fp_vmap_table_[i] + VmapTable::kEntryAdjustment);
1117      }
1118    } else {
1119      // For other platforms regs may have been inserted out of order - sort first.
1120      std::sort(fp_vmap_table_.begin(), fp_vmap_table_.end());
1121      for (size_t i = 0 ; i < fp_vmap_table_.size(); ++i) {
1122        // Copy, stripping out the phys register sort key.
1123        vmap_encoder.PushBackUnsigned(
1124            ~(-1 << VREG_NUM_WIDTH) & (fp_vmap_table_[i] + VmapTable::kEntryAdjustment));
1125      }
1126    }
1127  } else {
1128    DCHECK_EQ(POPCOUNT(core_spill_mask_), 0);
1129    DCHECK_EQ(POPCOUNT(fp_spill_mask_), 0);
1130    DCHECK_EQ(core_vmap_table_.size(), 0u);
1131    DCHECK_EQ(fp_vmap_table_.size(), 0u);
1132    vmap_encoder.PushBackUnsigned(0u);  // Size is 0.
1133  }
1134
1135  // Sort patches by literal offset for better deduplication.
1136  std::sort(patches_.begin(), patches_.end(), [](const LinkerPatch& lhs, const LinkerPatch& rhs) {
1137    return lhs.LiteralOffset() < rhs.LiteralOffset();
1138  });
1139
1140  std::unique_ptr<std::vector<uint8_t>> cfi_info(
1141      cu_->compiler_driver->GetCompilerOptions().GetGenerateGDBInformation() ?
1142          ReturnFrameDescriptionEntry() :
1143          nullptr);
1144  ArrayRef<const uint8_t> cfi_ref;
1145  if (cfi_info.get() != nullptr) {
1146    cfi_ref = ArrayRef<const uint8_t>(*cfi_info);
1147  }
1148  return CompiledMethod::SwapAllocCompiledMethod(
1149      cu_->compiler_driver, cu_->instruction_set,
1150      ArrayRef<const uint8_t>(code_buffer_),
1151      frame_size_, core_spill_mask_, fp_spill_mask_,
1152      &src_mapping_table_,
1153      ArrayRef<const uint8_t>(encoded_mapping_table_),
1154      ArrayRef<const uint8_t>(vmap_encoder.GetData()),
1155      ArrayRef<const uint8_t>(native_gc_map_),
1156      cfi_ref,
1157      ArrayRef<LinkerPatch>(patches_));
1158}
1159
1160size_t Mir2Lir::GetMaxPossibleCompilerTemps() const {
1161  // Chose a reasonably small value in order to contain stack growth.
1162  // Backends that are smarter about spill region can return larger values.
1163  const size_t max_compiler_temps = 10;
1164  return max_compiler_temps;
1165}
1166
1167size_t Mir2Lir::GetNumBytesForCompilerTempSpillRegion() {
1168  // By default assume that the Mir2Lir will need one slot for each temporary.
1169  // If the backend can better determine temps that have non-overlapping ranges and
1170  // temps that do not need spilled, it can actually provide a small region.
1171  mir_graph_->CommitCompilerTemps();
1172  return mir_graph_->GetNumBytesForSpecialTemps() + mir_graph_->GetMaximumBytesForNonSpecialTemps();
1173}
1174
1175int Mir2Lir::ComputeFrameSize() {
1176  /* Figure out the frame size */
1177  uint32_t size = num_core_spills_ * GetBytesPerGprSpillLocation(cu_->instruction_set)
1178                  + num_fp_spills_ * GetBytesPerFprSpillLocation(cu_->instruction_set)
1179                  + sizeof(uint32_t)  // Filler.
1180                  + mir_graph_->GetNumOfLocalCodeVRs()  * sizeof(uint32_t)
1181                  + mir_graph_->GetNumOfOutVRs() * sizeof(uint32_t)
1182                  + GetNumBytesForCompilerTempSpillRegion();
1183  /* Align and set */
1184  return RoundUp(size, kStackAlignment);
1185}
1186
1187/*
1188 * Append an LIR instruction to the LIR list maintained by a compilation
1189 * unit
1190 */
1191void Mir2Lir::AppendLIR(LIR* lir) {
1192  if (first_lir_insn_ == nullptr) {
1193    DCHECK(last_lir_insn_ == nullptr);
1194    last_lir_insn_ = first_lir_insn_ = lir;
1195    lir->prev = lir->next = nullptr;
1196  } else {
1197    last_lir_insn_->next = lir;
1198    lir->prev = last_lir_insn_;
1199    lir->next = nullptr;
1200    last_lir_insn_ = lir;
1201  }
1202}
1203
1204/*
1205 * Insert an LIR instruction before the current instruction, which cannot be the
1206 * first instruction.
1207 *
1208 * prev_lir <-> new_lir <-> current_lir
1209 */
1210void Mir2Lir::InsertLIRBefore(LIR* current_lir, LIR* new_lir) {
1211  DCHECK(current_lir->prev != nullptr);
1212  LIR *prev_lir = current_lir->prev;
1213
1214  prev_lir->next = new_lir;
1215  new_lir->prev = prev_lir;
1216  new_lir->next = current_lir;
1217  current_lir->prev = new_lir;
1218}
1219
1220/*
1221 * Insert an LIR instruction after the current instruction, which cannot be the
1222 * last instruction.
1223 *
1224 * current_lir -> new_lir -> old_next
1225 */
1226void Mir2Lir::InsertLIRAfter(LIR* current_lir, LIR* new_lir) {
1227  new_lir->prev = current_lir;
1228  new_lir->next = current_lir->next;
1229  current_lir->next = new_lir;
1230  new_lir->next->prev = new_lir;
1231}
1232
1233bool Mir2Lir::PartiallyIntersects(RegLocation rl_src, RegLocation rl_dest) {
1234  DCHECK(rl_src.wide);
1235  DCHECK(rl_dest.wide);
1236  return (abs(mir_graph_->SRegToVReg(rl_src.s_reg_low) - mir_graph_->SRegToVReg(rl_dest.s_reg_low)) == 1);
1237}
1238
1239bool Mir2Lir::Intersects(RegLocation rl_src, RegLocation rl_dest) {
1240  DCHECK(rl_src.wide);
1241  DCHECK(rl_dest.wide);
1242  return (abs(mir_graph_->SRegToVReg(rl_src.s_reg_low) - mir_graph_->SRegToVReg(rl_dest.s_reg_low)) <= 1);
1243}
1244
1245LIR *Mir2Lir::OpCmpMemImmBranch(ConditionCode cond, RegStorage temp_reg, RegStorage base_reg,
1246                                int offset, int check_value, LIR* target, LIR** compare) {
1247  // Handle this for architectures that can't compare to memory.
1248  LIR* inst = Load32Disp(base_reg, offset, temp_reg);
1249  if (compare != nullptr) {
1250    *compare = inst;
1251  }
1252  LIR* branch = OpCmpImmBranch(cond, temp_reg, check_value, target);
1253  return branch;
1254}
1255
1256void Mir2Lir::AddSlowPath(LIRSlowPath* slowpath) {
1257  slow_paths_.push_back(slowpath);
1258  ResetDefTracking();
1259}
1260
1261void Mir2Lir::LoadCodeAddress(const MethodReference& target_method, InvokeType type,
1262                              SpecialTargetRegister symbolic_reg) {
1263  LIR* data_target = ScanLiteralPoolMethod(code_literal_list_, target_method);
1264  if (data_target == nullptr) {
1265    data_target = AddWordData(&code_literal_list_, target_method.dex_method_index);
1266    data_target->operands[1] = WrapPointer(const_cast<DexFile*>(target_method.dex_file));
1267    // NOTE: The invoke type doesn't contribute to the literal identity. In fact, we can have
1268    // the same method invoked with kVirtual, kSuper and kInterface but the class linker will
1269    // resolve these invokes to the same method, so we don't care which one we record here.
1270    data_target->operands[2] = type;
1271  }
1272  // Loads a code pointer. Code from oat file can be mapped anywhere.
1273  OpPcRelLoad(TargetPtrReg(symbolic_reg), data_target);
1274  DCHECK_NE(cu_->instruction_set, kMips) << reinterpret_cast<void*>(data_target);
1275  DCHECK_NE(cu_->instruction_set, kMips64) << reinterpret_cast<void*>(data_target);
1276}
1277
1278void Mir2Lir::LoadMethodAddress(const MethodReference& target_method, InvokeType type,
1279                                SpecialTargetRegister symbolic_reg) {
1280  LIR* data_target = ScanLiteralPoolMethod(method_literal_list_, target_method);
1281  if (data_target == nullptr) {
1282    data_target = AddWordData(&method_literal_list_, target_method.dex_method_index);
1283    data_target->operands[1] = WrapPointer(const_cast<DexFile*>(target_method.dex_file));
1284    // NOTE: The invoke type doesn't contribute to the literal identity. In fact, we can have
1285    // the same method invoked with kVirtual, kSuper and kInterface but the class linker will
1286    // resolve these invokes to the same method, so we don't care which one we record here.
1287    data_target->operands[2] = type;
1288  }
1289  // Loads an ArtMethod pointer, which is a reference as it lives in the heap.
1290  OpPcRelLoad(TargetReg(symbolic_reg, kRef), data_target);
1291  DCHECK_NE(cu_->instruction_set, kMips) << reinterpret_cast<void*>(data_target);
1292  DCHECK_NE(cu_->instruction_set, kMips64) << reinterpret_cast<void*>(data_target);
1293}
1294
1295void Mir2Lir::LoadClassType(const DexFile& dex_file, uint32_t type_idx,
1296                            SpecialTargetRegister symbolic_reg) {
1297  // Use the literal pool and a PC-relative load from a data word.
1298  LIR* data_target = ScanLiteralPoolClass(class_literal_list_, dex_file, type_idx);
1299  if (data_target == nullptr) {
1300    data_target = AddWordData(&class_literal_list_, type_idx);
1301    data_target->operands[1] = WrapPointer(const_cast<DexFile*>(&dex_file));
1302  }
1303  // Loads a Class pointer, which is a reference as it lives in the heap.
1304  OpPcRelLoad(TargetReg(symbolic_reg, kRef), data_target);
1305}
1306
1307std::vector<uint8_t>* Mir2Lir::ReturnFrameDescriptionEntry() {
1308  // Default case is to do nothing.
1309  return nullptr;
1310}
1311
1312RegLocation Mir2Lir::NarrowRegLoc(RegLocation loc) {
1313  if (loc.location == kLocPhysReg) {
1314    DCHECK(!loc.reg.Is32Bit());
1315    if (loc.reg.IsPair()) {
1316      RegisterInfo* info_lo = GetRegInfo(loc.reg.GetLow());
1317      RegisterInfo* info_hi = GetRegInfo(loc.reg.GetHigh());
1318      info_lo->SetIsWide(false);
1319      info_hi->SetIsWide(false);
1320      loc.reg = info_lo->GetReg();
1321    } else {
1322      RegisterInfo* info = GetRegInfo(loc.reg);
1323      RegisterInfo* info_new = info->FindMatchingView(RegisterInfo::k32SoloStorageMask);
1324      DCHECK(info_new != nullptr);
1325      if (info->IsLive() && (info->SReg() == loc.s_reg_low)) {
1326        info->MarkDead();
1327        info_new->MarkLive(loc.s_reg_low);
1328      }
1329      loc.reg = info_new->GetReg();
1330    }
1331    DCHECK(loc.reg.Valid());
1332  }
1333  loc.wide = false;
1334  return loc;
1335}
1336
1337void Mir2Lir::GenMachineSpecificExtendedMethodMIR(BasicBlock* bb, MIR* mir) {
1338  UNUSED(bb, mir);
1339  LOG(FATAL) << "Unknown MIR opcode not supported on this architecture";
1340  UNREACHABLE();
1341}
1342
1343void Mir2Lir::InitReferenceVRegs(BasicBlock* bb, BitVector* references) {
1344  // Mark the references coming from the first predecessor.
1345  DCHECK(bb != nullptr);
1346  DCHECK(bb->block_type == kEntryBlock || !bb->predecessors.empty());
1347  BasicBlock* first_bb =
1348      (bb->block_type == kEntryBlock) ? bb : mir_graph_->GetBasicBlock(bb->predecessors[0]);
1349  DCHECK(first_bb != nullptr);
1350  DCHECK(first_bb->data_flow_info != nullptr);
1351  DCHECK(first_bb->data_flow_info->vreg_to_ssa_map_exit != nullptr);
1352  const int32_t* first_vreg_to_ssa_map = first_bb->data_flow_info->vreg_to_ssa_map_exit;
1353  references->ClearAllBits();
1354  for (uint32_t vreg = 0, num_vregs = mir_graph_->GetNumOfCodeVRs(); vreg != num_vregs; ++vreg) {
1355    int32_t sreg = first_vreg_to_ssa_map[vreg];
1356    if (sreg != INVALID_SREG && mir_graph_->reg_location_[sreg].ref &&
1357        !mir_graph_->IsConstantNullRef(mir_graph_->reg_location_[sreg])) {
1358      references->SetBit(vreg);
1359    }
1360  }
1361  // Unmark the references that are merging with a different value.
1362  for (size_t i = 1u, num_pred = bb->predecessors.size(); i < num_pred; ++i) {
1363    BasicBlock* pred_bb = mir_graph_->GetBasicBlock(bb->predecessors[i]);
1364    DCHECK(pred_bb != nullptr);
1365    DCHECK(pred_bb->data_flow_info != nullptr);
1366    DCHECK(pred_bb->data_flow_info->vreg_to_ssa_map_exit != nullptr);
1367    const int32_t* pred_vreg_to_ssa_map = pred_bb->data_flow_info->vreg_to_ssa_map_exit;
1368    for (uint32_t vreg : references->Indexes()) {
1369      if (first_vreg_to_ssa_map[vreg] != pred_vreg_to_ssa_map[vreg]) {
1370        // NOTE: The BitVectorSet::IndexIterator will not check the pointed-to bit again,
1371        // so clearing the bit has no effect on the iterator.
1372        references->ClearBit(vreg);
1373      }
1374    }
1375  }
1376  if (bb->block_type != kEntryBlock && bb->first_mir_insn != nullptr &&
1377      static_cast<int>(bb->first_mir_insn->dalvikInsn.opcode) == kMirOpCheckPart2) {
1378    // In Mir2Lir::MethodBlockCodeGen() we have artificially moved the throwing
1379    // instruction to the previous block. However, the MIRGraph data used above
1380    // doesn't reflect that, so we still need to process that MIR insn here.
1381    DCHECK_EQ(bb->predecessors.size(), 1u);
1382    BasicBlock* pred_bb = mir_graph_->GetBasicBlock(bb->predecessors[0]);
1383    DCHECK(pred_bb != nullptr);
1384    DCHECK(pred_bb->last_mir_insn != nullptr);
1385    UpdateReferenceVRegsLocal(nullptr, pred_bb->last_mir_insn, references);
1386  }
1387}
1388
1389bool Mir2Lir::UpdateReferenceVRegsLocal(MIR* mir, MIR* prev_mir, BitVector* references) {
1390  DCHECK(mir == nullptr || mir->bb == prev_mir->bb);
1391  DCHECK(prev_mir != nullptr);
1392  while (prev_mir != nullptr) {
1393    if (prev_mir == mir) {
1394      return true;
1395    }
1396    const size_t num_defs = prev_mir->ssa_rep->num_defs;
1397    const int32_t* defs = prev_mir->ssa_rep->defs;
1398    if (num_defs == 1u && mir_graph_->reg_location_[defs[0]].ref &&
1399        !mir_graph_->IsConstantNullRef(mir_graph_->reg_location_[defs[0]])) {
1400      references->SetBit(mir_graph_->SRegToVReg(defs[0]));
1401    } else {
1402      for (size_t i = 0u; i != num_defs; ++i) {
1403        references->ClearBit(mir_graph_->SRegToVReg(defs[i]));
1404      }
1405    }
1406    prev_mir = prev_mir->next;
1407  }
1408  return false;
1409}
1410
1411void Mir2Lir::UpdateReferenceVRegs(MIR* mir, MIR* prev_mir, BitVector* references) {
1412  if (mir == nullptr) {
1413    // Safepoint in entry sequence.
1414    InitReferenceVRegs(mir_graph_->GetEntryBlock(), references);
1415    return;
1416  }
1417  if (IsInstructionReturn(mir->dalvikInsn.opcode) ||
1418      mir->dalvikInsn.opcode == Instruction::RETURN_VOID_NO_BARRIER) {
1419    references->ClearAllBits();
1420    if (mir->dalvikInsn.opcode == Instruction::RETURN_OBJECT) {
1421      references->SetBit(mir_graph_->SRegToVReg(mir->ssa_rep->uses[0]));
1422    }
1423    return;
1424  }
1425  if (prev_mir != nullptr && mir->bb == prev_mir->bb &&
1426      UpdateReferenceVRegsLocal(mir, prev_mir, references)) {
1427    return;
1428  }
1429  BasicBlock* bb = mir_graph_->GetBasicBlock(mir->bb);
1430  DCHECK(bb != nullptr);
1431  InitReferenceVRegs(bb, references);
1432  bool success = UpdateReferenceVRegsLocal(mir, bb->first_mir_insn, references);
1433  DCHECK(success) << "MIR @0x" << std::hex << mir->offset << " not in BB#" << std::dec << mir->bb;
1434}
1435
1436}  // namespace art
1437