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