codegen_util.cc revision ae9fd93c39a341e2dffe15c61cc7d9e841fa92c4 
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 "dex/compiler_internals.h"
18#include "dex_file-inl.h"
19#include "gc_map.h"
20#include "mapping_table.h"
21#include "mir_to_lir-inl.h"
22#include "dex/quick/dex_file_method_inliner.h"
23#include "dex/quick/dex_file_to_method_inliner_map.h"
24#include "dex/verification_results.h"
25#include "dex/verified_method.h"
26#include "verifier/dex_gc_map.h"
27#include "verifier/method_verifier.h"
28#include "vmap_table.h"
29
30namespace art {
31
32namespace {
33
34/* Dump a mapping table */
35template <typename It>
36void DumpMappingTable(const char* table_name, const char* descriptor, const char* name,
37                      const Signature& signature, uint32_t size, It first) {
38  if (size != 0) {
39    std::string line(StringPrintf("\n  %s %s%s_%s_table[%u] = {", table_name,
40                     descriptor, name, signature.ToString().c_str(), size));
41    std::replace(line.begin(), line.end(), ';', '_');
42    LOG(INFO) << line;
43    for (uint32_t i = 0; i != size; ++i) {
44      line = StringPrintf("    {0x%05x, 0x%04x},", first.NativePcOffset(), first.DexPc());
45      ++first;
46      LOG(INFO) << line;
47    }
48    LOG(INFO) <<"  };\n\n";
49  }
50}
51
52}  // anonymous namespace
53
54bool Mir2Lir::IsInexpensiveConstant(RegLocation rl_src) {
55  bool res = false;
56  if (rl_src.is_const) {
57    if (rl_src.wide) {
58      if (rl_src.fp) {
59         res = InexpensiveConstantDouble(mir_graph_->ConstantValueWide(rl_src));
60      } else {
61         res = InexpensiveConstantLong(mir_graph_->ConstantValueWide(rl_src));
62      }
63    } else {
64      if (rl_src.fp) {
65         res = InexpensiveConstantFloat(mir_graph_->ConstantValue(rl_src));
66      } else {
67         res = InexpensiveConstantInt(mir_graph_->ConstantValue(rl_src));
68      }
69    }
70  }
71  return res;
72}
73
74void Mir2Lir::MarkSafepointPC(LIR* inst) {
75  DCHECK(!inst->flags.use_def_invalid);
76  inst->u.m.def_mask = ENCODE_ALL;
77  LIR* safepoint_pc = NewLIR0(kPseudoSafepointPC);
78  DCHECK_EQ(safepoint_pc->u.m.def_mask, ENCODE_ALL);
79}
80
81bool Mir2Lir::FastInstance(uint32_t field_idx, bool is_put, int* field_offset, bool* is_volatile) {
82  return cu_->compiler_driver->ComputeInstanceFieldInfo(
83      field_idx, mir_graph_->GetCurrentDexCompilationUnit(), is_put, field_offset, is_volatile);
84}
85
86/* Remove a LIR from the list. */
87void Mir2Lir::UnlinkLIR(LIR* lir) {
88  if (UNLIKELY(lir == first_lir_insn_)) {
89    first_lir_insn_ = lir->next;
90    if (lir->next != NULL) {
91      lir->next->prev = NULL;
92    } else {
93      DCHECK(lir->next == NULL);
94      DCHECK(lir == last_lir_insn_);
95      last_lir_insn_ = NULL;
96    }
97  } else if (lir == last_lir_insn_) {
98    last_lir_insn_ = lir->prev;
99    lir->prev->next = NULL;
100  } else if ((lir->prev != NULL) && (lir->next != NULL)) {
101    lir->prev->next = lir->next;
102    lir->next->prev = lir->prev;
103  }
104}
105
106/* Convert an instruction to a NOP */
107void Mir2Lir::NopLIR(LIR* lir) {
108  lir->flags.is_nop = true;
109  if (!cu_->verbose) {
110    UnlinkLIR(lir);
111  }
112}
113
114void Mir2Lir::SetMemRefType(LIR* lir, bool is_load, int mem_type) {
115  uint64_t *mask_ptr;
116  uint64_t mask = ENCODE_MEM;
117  DCHECK(GetTargetInstFlags(lir->opcode) & (IS_LOAD | IS_STORE));
118  DCHECK(!lir->flags.use_def_invalid);
119  if (is_load) {
120    mask_ptr = &lir->u.m.use_mask;
121  } else {
122    mask_ptr = &lir->u.m.def_mask;
123  }
124  /* Clear out the memref flags */
125  *mask_ptr &= ~mask;
126  /* ..and then add back the one we need */
127  switch (mem_type) {
128    case kLiteral:
129      DCHECK(is_load);
130      *mask_ptr |= ENCODE_LITERAL;
131      break;
132    case kDalvikReg:
133      *mask_ptr |= ENCODE_DALVIK_REG;
134      break;
135    case kHeapRef:
136      *mask_ptr |= ENCODE_HEAP_REF;
137      break;
138    case kMustNotAlias:
139      /* Currently only loads can be marked as kMustNotAlias */
140      DCHECK(!(GetTargetInstFlags(lir->opcode) & IS_STORE));
141      *mask_ptr |= ENCODE_MUST_NOT_ALIAS;
142      break;
143    default:
144      LOG(FATAL) << "Oat: invalid memref kind - " << mem_type;
145  }
146}
147
148/*
149 * Mark load/store instructions that access Dalvik registers through the stack.
150 */
151void Mir2Lir::AnnotateDalvikRegAccess(LIR* lir, int reg_id, bool is_load,
152                                      bool is64bit) {
153  SetMemRefType(lir, is_load, kDalvikReg);
154
155  /*
156   * Store the Dalvik register id in alias_info. Mark the MSB if it is a 64-bit
157   * access.
158   */
159  lir->flags.alias_info = ENCODE_ALIAS_INFO(reg_id, is64bit);
160}
161
162/*
163 * Debugging macros
164 */
165#define DUMP_RESOURCE_MASK(X)
166
167/* Pretty-print a LIR instruction */
168void Mir2Lir::DumpLIRInsn(LIR* lir, unsigned char* base_addr) {
169  int offset = lir->offset;
170  int dest = lir->operands[0];
171  const bool dump_nop = (cu_->enable_debug & (1 << kDebugShowNops));
172
173  /* Handle pseudo-ops individually, and all regular insns as a group */
174  switch (lir->opcode) {
175    case kPseudoMethodEntry:
176      LOG(INFO) << "-------- method entry "
177                << PrettyMethod(cu_->method_idx, *cu_->dex_file);
178      break;
179    case kPseudoMethodExit:
180      LOG(INFO) << "-------- Method_Exit";
181      break;
182    case kPseudoBarrier:
183      LOG(INFO) << "-------- BARRIER";
184      break;
185    case kPseudoEntryBlock:
186      LOG(INFO) << "-------- entry offset: 0x" << std::hex << dest;
187      break;
188    case kPseudoDalvikByteCodeBoundary:
189      if (lir->operands[0] == 0) {
190         // NOTE: only used for debug listings.
191         lir->operands[0] = WrapPointer(ArenaStrdup("No instruction string"));
192      }
193      LOG(INFO) << "-------- dalvik offset: 0x" << std::hex
194                << lir->dalvik_offset << " @ "
195                << reinterpret_cast<char*>(UnwrapPointer(lir->operands[0]));
196      break;
197    case kPseudoExitBlock:
198      LOG(INFO) << "-------- exit offset: 0x" << std::hex << dest;
199      break;
200    case kPseudoPseudoAlign4:
201      LOG(INFO) << reinterpret_cast<uintptr_t>(base_addr) + offset << " (0x" << std::hex
202                << offset << "): .align4";
203      break;
204    case kPseudoEHBlockLabel:
205      LOG(INFO) << "Exception_Handling:";
206      break;
207    case kPseudoTargetLabel:
208    case kPseudoNormalBlockLabel:
209      LOG(INFO) << "L" << reinterpret_cast<void*>(lir) << ":";
210      break;
211    case kPseudoThrowTarget:
212      LOG(INFO) << "LT" << reinterpret_cast<void*>(lir) << ":";
213      break;
214    case kPseudoIntrinsicRetry:
215      LOG(INFO) << "IR" << reinterpret_cast<void*>(lir) << ":";
216      break;
217    case kPseudoSuspendTarget:
218      LOG(INFO) << "LS" << reinterpret_cast<void*>(lir) << ":";
219      break;
220    case kPseudoSafepointPC:
221      LOG(INFO) << "LsafepointPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
222      break;
223    case kPseudoExportedPC:
224      LOG(INFO) << "LexportedPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
225      break;
226    case kPseudoCaseLabel:
227      LOG(INFO) << "LC" << reinterpret_cast<void*>(lir) << ": Case target 0x"
228                << std::hex << lir->operands[0] << "|" << std::dec <<
229        lir->operands[0];
230      break;
231    default:
232      if (lir->flags.is_nop && !dump_nop) {
233        break;
234      } else {
235        std::string op_name(BuildInsnString(GetTargetInstName(lir->opcode),
236                                               lir, base_addr));
237        std::string op_operands(BuildInsnString(GetTargetInstFmt(lir->opcode),
238                                                    lir, base_addr));
239        LOG(INFO) << StringPrintf("%5p: %-9s%s%s",
240                                  base_addr + offset,
241                                  op_name.c_str(), op_operands.c_str(),
242                                  lir->flags.is_nop ? "(nop)" : "");
243      }
244      break;
245  }
246
247  if (lir->u.m.use_mask && (!lir->flags.is_nop || dump_nop)) {
248    DUMP_RESOURCE_MASK(DumpResourceMask(lir, lir->u.m.use_mask, "use"));
249  }
250  if (lir->u.m.def_mask && (!lir->flags.is_nop || dump_nop)) {
251    DUMP_RESOURCE_MASK(DumpResourceMask(lir, lir->u.m.def_mask, "def"));
252  }
253}
254
255void Mir2Lir::DumpPromotionMap() {
256  int num_regs = cu_->num_dalvik_registers + mir_graph_->GetNumUsedCompilerTemps();
257  for (int i = 0; i < num_regs; i++) {
258    PromotionMap v_reg_map = promotion_map_[i];
259    std::string buf;
260    if (v_reg_map.fp_location == kLocPhysReg) {
261      StringAppendF(&buf, " : s%d", v_reg_map.FpReg & FpRegMask());
262    }
263
264    std::string buf3;
265    if (i < cu_->num_dalvik_registers) {
266      StringAppendF(&buf3, "%02d", i);
267    } else if (i == mir_graph_->GetMethodSReg()) {
268      buf3 = "Method*";
269    } else {
270      StringAppendF(&buf3, "ct%d", i - cu_->num_dalvik_registers);
271    }
272
273    LOG(INFO) << StringPrintf("V[%s] -> %s%d%s", buf3.c_str(),
274                              v_reg_map.core_location == kLocPhysReg ?
275                              "r" : "SP+", v_reg_map.core_location == kLocPhysReg ?
276                              v_reg_map.core_reg : SRegOffset(i),
277                              buf.c_str());
278  }
279}
280
281/* Dump instructions and constant pool contents */
282void Mir2Lir::CodegenDump() {
283  LOG(INFO) << "Dumping LIR insns for "
284            << PrettyMethod(cu_->method_idx, *cu_->dex_file);
285  LIR* lir_insn;
286  int insns_size = cu_->code_item->insns_size_in_code_units_;
287
288  LOG(INFO) << "Regs (excluding ins) : " << cu_->num_regs;
289  LOG(INFO) << "Ins          : " << cu_->num_ins;
290  LOG(INFO) << "Outs         : " << cu_->num_outs;
291  LOG(INFO) << "CoreSpills       : " << num_core_spills_;
292  LOG(INFO) << "FPSpills       : " << num_fp_spills_;
293  LOG(INFO) << "CompilerTemps    : " << mir_graph_->GetNumUsedCompilerTemps();
294  LOG(INFO) << "Frame size       : " << frame_size_;
295  LOG(INFO) << "code size is " << total_size_ <<
296    " bytes, Dalvik size is " << insns_size * 2;
297  LOG(INFO) << "expansion factor: "
298            << static_cast<float>(total_size_) / static_cast<float>(insns_size * 2);
299  DumpPromotionMap();
300  for (lir_insn = first_lir_insn_; lir_insn != NULL; lir_insn = lir_insn->next) {
301    DumpLIRInsn(lir_insn, 0);
302  }
303  for (lir_insn = literal_list_; lir_insn != NULL; lir_insn = lir_insn->next) {
304    LOG(INFO) << StringPrintf("%x (%04x): .word (%#x)", lir_insn->offset, lir_insn->offset,
305                              lir_insn->operands[0]);
306  }
307
308  const DexFile::MethodId& method_id =
309      cu_->dex_file->GetMethodId(cu_->method_idx);
310  const Signature signature = cu_->dex_file->GetMethodSignature(method_id);
311  const char* name = cu_->dex_file->GetMethodName(method_id);
312  const char* descriptor(cu_->dex_file->GetMethodDeclaringClassDescriptor(method_id));
313
314  // Dump mapping tables
315  if (!encoded_mapping_table_.empty()) {
316    MappingTable table(&encoded_mapping_table_[0]);
317    DumpMappingTable("PC2Dex_MappingTable", descriptor, name, signature,
318                     table.PcToDexSize(), table.PcToDexBegin());
319    DumpMappingTable("Dex2PC_MappingTable", descriptor, name, signature,
320                     table.DexToPcSize(), table.DexToPcBegin());
321  }
322}
323
324/*
325 * Search the existing constants in the literal pool for an exact or close match
326 * within specified delta (greater or equal to 0).
327 */
328LIR* Mir2Lir::ScanLiteralPool(LIR* data_target, int value, unsigned int delta) {
329  while (data_target) {
330    if ((static_cast<unsigned>(value - data_target->operands[0])) <= delta)
331      return data_target;
332    data_target = data_target->next;
333  }
334  return NULL;
335}
336
337/* Search the existing constants in the literal pool for an exact wide match */
338LIR* Mir2Lir::ScanLiteralPoolWide(LIR* data_target, int val_lo, int val_hi) {
339  bool lo_match = false;
340  LIR* lo_target = NULL;
341  while (data_target) {
342    if (lo_match && (data_target->operands[0] == val_hi)) {
343      // Record high word in case we need to expand this later.
344      lo_target->operands[1] = val_hi;
345      return lo_target;
346    }
347    lo_match = false;
348    if (data_target->operands[0] == val_lo) {
349      lo_match = true;
350      lo_target = data_target;
351    }
352    data_target = data_target->next;
353  }
354  return NULL;
355}
356
357/*
358 * The following are building blocks to insert constants into the pool or
359 * instruction streams.
360 */
361
362/* Add a 32-bit constant to the constant pool */
363LIR* Mir2Lir::AddWordData(LIR* *constant_list_p, int value) {
364  /* Add the constant to the literal pool */
365  if (constant_list_p) {
366    LIR* new_value = static_cast<LIR*>(arena_->Alloc(sizeof(LIR), ArenaAllocator::kAllocData));
367    new_value->operands[0] = value;
368    new_value->next = *constant_list_p;
369    *constant_list_p = new_value;
370    estimated_native_code_size_ += sizeof(value);
371    return new_value;
372  }
373  return NULL;
374}
375
376/* Add a 64-bit constant to the constant pool or mixed with code */
377LIR* Mir2Lir::AddWideData(LIR* *constant_list_p, int val_lo, int val_hi) {
378  AddWordData(constant_list_p, val_hi);
379  return AddWordData(constant_list_p, val_lo);
380}
381
382static void PushWord(std::vector<uint8_t>&buf, int data) {
383  buf.push_back(data & 0xff);
384  buf.push_back((data >> 8) & 0xff);
385  buf.push_back((data >> 16) & 0xff);
386  buf.push_back((data >> 24) & 0xff);
387}
388
389// Push 8 bytes on 64-bit systems; 4 on 32-bit systems.
390static void PushPointer(std::vector<uint8_t>&buf, void const* pointer) {
391  uintptr_t data = reinterpret_cast<uintptr_t>(pointer);
392  if (sizeof(void*) == sizeof(uint64_t)) {
393    PushWord(buf, (data >> (sizeof(void*) * 4)) & 0xFFFFFFFF);
394    PushWord(buf, data & 0xFFFFFFFF);
395  } else {
396    PushWord(buf, data);
397  }
398}
399
400static void AlignBuffer(std::vector<uint8_t>&buf, size_t offset) {
401  while (buf.size() < offset) {
402    buf.push_back(0);
403  }
404}
405
406/* Write the literal pool to the output stream */
407void Mir2Lir::InstallLiteralPools() {
408  AlignBuffer(code_buffer_, data_offset_);
409  LIR* data_lir = literal_list_;
410  while (data_lir != NULL) {
411    PushWord(code_buffer_, data_lir->operands[0]);
412    data_lir = NEXT_LIR(data_lir);
413  }
414  // Push code and method literals, record offsets for the compiler to patch.
415  data_lir = code_literal_list_;
416  while (data_lir != NULL) {
417    uint32_t target = data_lir->operands[0];
418    cu_->compiler_driver->AddCodePatch(cu_->dex_file,
419                                       cu_->class_def_idx,
420                                       cu_->method_idx,
421                                       cu_->invoke_type,
422                                       target,
423                                       static_cast<InvokeType>(data_lir->operands[1]),
424                                       code_buffer_.size());
425    const DexFile::MethodId& id = cu_->dex_file->GetMethodId(target);
426    // unique value based on target to ensure code deduplication works
427    PushPointer(code_buffer_, &id);
428    data_lir = NEXT_LIR(data_lir);
429  }
430  data_lir = method_literal_list_;
431  while (data_lir != NULL) {
432    uint32_t target = data_lir->operands[0];
433    cu_->compiler_driver->AddMethodPatch(cu_->dex_file,
434                                         cu_->class_def_idx,
435                                         cu_->method_idx,
436                                         cu_->invoke_type,
437                                         target,
438                                         static_cast<InvokeType>(data_lir->operands[1]),
439                                         code_buffer_.size());
440    const DexFile::MethodId& id = cu_->dex_file->GetMethodId(target);
441    // unique value based on target to ensure code deduplication works
442    PushPointer(code_buffer_, &id);
443    data_lir = NEXT_LIR(data_lir);
444  }
445  // Push class literals.
446  data_lir = class_literal_list_;
447  while (data_lir != NULL) {
448    uint32_t target = data_lir->operands[0];
449    cu_->compiler_driver->AddClassPatch(cu_->dex_file,
450                                        cu_->class_def_idx,
451                                        cu_->method_idx,
452                                        target,
453                                        code_buffer_.size());
454    const DexFile::TypeId& id = cu_->dex_file->GetTypeId(target);
455    // unique value based on target to ensure code deduplication works
456    PushPointer(code_buffer_, &id);
457    data_lir = NEXT_LIR(data_lir);
458  }
459}
460
461/* Write the switch tables to the output stream */
462void Mir2Lir::InstallSwitchTables() {
463  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
464  while (true) {
465    Mir2Lir::SwitchTable* tab_rec = iterator.Next();
466    if (tab_rec == NULL) break;
467    AlignBuffer(code_buffer_, tab_rec->offset);
468    /*
469     * For Arm, our reference point is the address of the bx
470     * instruction that does the launch, so we have to subtract
471     * the auto pc-advance.  For other targets the reference point
472     * is a label, so we can use the offset as-is.
473     */
474    int bx_offset = INVALID_OFFSET;
475    switch (cu_->instruction_set) {
476      case kThumb2:
477        DCHECK(tab_rec->anchor->flags.fixup != kFixupNone);
478        bx_offset = tab_rec->anchor->offset + 4;
479        break;
480      case kX86:
481        bx_offset = 0;
482        break;
483      case kMips:
484        bx_offset = tab_rec->anchor->offset;
485        break;
486      default: LOG(FATAL) << "Unexpected instruction set: " << cu_->instruction_set;
487    }
488    if (cu_->verbose) {
489      LOG(INFO) << "Switch table for offset 0x" << std::hex << bx_offset;
490    }
491    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
492      const int32_t* keys = reinterpret_cast<const int32_t*>(&(tab_rec->table[2]));
493      for (int elems = 0; elems < tab_rec->table[1]; elems++) {
494        int disp = tab_rec->targets[elems]->offset - bx_offset;
495        if (cu_->verbose) {
496          LOG(INFO) << "  Case[" << elems << "] key: 0x"
497                    << std::hex << keys[elems] << ", disp: 0x"
498                    << std::hex << disp;
499        }
500        PushWord(code_buffer_, keys[elems]);
501        PushWord(code_buffer_,
502          tab_rec->targets[elems]->offset - bx_offset);
503      }
504    } else {
505      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
506                static_cast<int>(Instruction::kPackedSwitchSignature));
507      for (int elems = 0; elems < tab_rec->table[1]; elems++) {
508        int disp = tab_rec->targets[elems]->offset - bx_offset;
509        if (cu_->verbose) {
510          LOG(INFO) << "  Case[" << elems << "] disp: 0x"
511                    << std::hex << disp;
512        }
513        PushWord(code_buffer_, tab_rec->targets[elems]->offset - bx_offset);
514      }
515    }
516  }
517}
518
519/* Write the fill array dta to the output stream */
520void Mir2Lir::InstallFillArrayData() {
521  GrowableArray<FillArrayData*>::Iterator iterator(&fill_array_data_);
522  while (true) {
523    Mir2Lir::FillArrayData *tab_rec = iterator.Next();
524    if (tab_rec == NULL) break;
525    AlignBuffer(code_buffer_, tab_rec->offset);
526    for (int i = 0; i < (tab_rec->size + 1) / 2; i++) {
527      code_buffer_.push_back(tab_rec->table[i] & 0xFF);
528      code_buffer_.push_back((tab_rec->table[i] >> 8) & 0xFF);
529    }
530  }
531}
532
533static int AssignLiteralOffsetCommon(LIR* lir, CodeOffset offset) {
534  for (; lir != NULL; lir = lir->next) {
535    lir->offset = offset;
536    offset += 4;
537  }
538  return offset;
539}
540
541static int AssignLiteralPointerOffsetCommon(LIR* lir, CodeOffset offset) {
542  unsigned int element_size = sizeof(void*);
543  // Align to natural pointer size.
544  offset = (offset + (element_size - 1)) & ~(element_size - 1);
545  for (; lir != NULL; lir = lir->next) {
546    lir->offset = offset;
547    offset += element_size;
548  }
549  return offset;
550}
551
552// Make sure we have a code address for every declared catch entry
553bool Mir2Lir::VerifyCatchEntries() {
554  MappingTable table(&encoded_mapping_table_[0]);
555  std::vector<uint32_t> dex_pcs;
556  dex_pcs.reserve(table.DexToPcSize());
557  for (auto it = table.DexToPcBegin(), end = table.DexToPcEnd(); it != end; ++it) {
558    dex_pcs.push_back(it.DexPc());
559  }
560  // Sort dex_pcs, so that we can quickly check it against the ordered mir_graph_->catches_.
561  std::sort(dex_pcs.begin(), dex_pcs.end());
562
563  bool success = true;
564  auto it = dex_pcs.begin(), end = dex_pcs.end();
565  for (uint32_t dex_pc : mir_graph_->catches_) {
566    while (it != end && *it < dex_pc) {
567      LOG(INFO) << "Unexpected catch entry @ dex pc 0x" << std::hex << *it;
568      ++it;
569      success = false;
570    }
571    if (it == end || *it > dex_pc) {
572      LOG(INFO) << "Missing native PC for catch entry @ 0x" << std::hex << dex_pc;
573      success = false;
574    } else {
575      ++it;
576    }
577  }
578  if (!success) {
579    LOG(INFO) << "Bad dex2pcMapping table in " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
580    LOG(INFO) << "Entries @ decode: " << mir_graph_->catches_.size() << ", Entries in table: "
581              << table.DexToPcSize();
582  }
583  return success;
584}
585
586
587void Mir2Lir::CreateMappingTables() {
588  uint32_t pc2dex_data_size = 0u;
589  uint32_t pc2dex_entries = 0u;
590  uint32_t pc2dex_offset = 0u;
591  uint32_t pc2dex_dalvik_offset = 0u;
592  uint32_t dex2pc_data_size = 0u;
593  uint32_t dex2pc_entries = 0u;
594  uint32_t dex2pc_offset = 0u;
595  uint32_t dex2pc_dalvik_offset = 0u;
596  for (LIR* tgt_lir = first_lir_insn_; tgt_lir != NULL; tgt_lir = NEXT_LIR(tgt_lir)) {
597    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
598      pc2dex_entries += 1;
599      DCHECK(pc2dex_offset <= tgt_lir->offset);
600      pc2dex_data_size += UnsignedLeb128Size(tgt_lir->offset - pc2dex_offset);
601      pc2dex_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
602                                           static_cast<int32_t>(pc2dex_dalvik_offset));
603      pc2dex_offset = tgt_lir->offset;
604      pc2dex_dalvik_offset = tgt_lir->dalvik_offset;
605    }
606    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
607      dex2pc_entries += 1;
608      DCHECK(dex2pc_offset <= tgt_lir->offset);
609      dex2pc_data_size += UnsignedLeb128Size(tgt_lir->offset - dex2pc_offset);
610      dex2pc_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
611                                           static_cast<int32_t>(dex2pc_dalvik_offset));
612      dex2pc_offset = tgt_lir->offset;
613      dex2pc_dalvik_offset = tgt_lir->dalvik_offset;
614    }
615  }
616
617  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
618  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
619  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
620  encoded_mapping_table_.resize(data_size);
621  uint8_t* write_pos = &encoded_mapping_table_[0];
622  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
623  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
624  DCHECK_EQ(static_cast<size_t>(write_pos - &encoded_mapping_table_[0]), hdr_data_size);
625  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
626
627  pc2dex_offset = 0u;
628  pc2dex_dalvik_offset = 0u;
629  dex2pc_offset = 0u;
630  dex2pc_dalvik_offset = 0u;
631  for (LIR* tgt_lir = first_lir_insn_; tgt_lir != NULL; tgt_lir = NEXT_LIR(tgt_lir)) {
632    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
633      DCHECK(pc2dex_offset <= tgt_lir->offset);
634      write_pos = EncodeUnsignedLeb128(write_pos, tgt_lir->offset - pc2dex_offset);
635      write_pos = EncodeSignedLeb128(write_pos, static_cast<int32_t>(tgt_lir->dalvik_offset) -
636                                     static_cast<int32_t>(pc2dex_dalvik_offset));
637      pc2dex_offset = tgt_lir->offset;
638      pc2dex_dalvik_offset = tgt_lir->dalvik_offset;
639    }
640    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
641      DCHECK(dex2pc_offset <= tgt_lir->offset);
642      write_pos2 = EncodeUnsignedLeb128(write_pos2, tgt_lir->offset - dex2pc_offset);
643      write_pos2 = EncodeSignedLeb128(write_pos2, static_cast<int32_t>(tgt_lir->dalvik_offset) -
644                                      static_cast<int32_t>(dex2pc_dalvik_offset));
645      dex2pc_offset = tgt_lir->offset;
646      dex2pc_dalvik_offset = tgt_lir->dalvik_offset;
647    }
648  }
649  DCHECK_EQ(static_cast<size_t>(write_pos - &encoded_mapping_table_[0]),
650            hdr_data_size + pc2dex_data_size);
651  DCHECK_EQ(static_cast<size_t>(write_pos2 - &encoded_mapping_table_[0]), data_size);
652
653  if (kIsDebugBuild) {
654    CHECK(VerifyCatchEntries());
655
656    // Verify the encoded table holds the expected data.
657    MappingTable table(&encoded_mapping_table_[0]);
658    CHECK_EQ(table.TotalSize(), total_entries);
659    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
660    auto it = table.PcToDexBegin();
661    auto it2 = table.DexToPcBegin();
662    for (LIR* tgt_lir = first_lir_insn_; tgt_lir != NULL; tgt_lir = NEXT_LIR(tgt_lir)) {
663      if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
664        CHECK_EQ(tgt_lir->offset, it.NativePcOffset());
665        CHECK_EQ(tgt_lir->dalvik_offset, it.DexPc());
666        ++it;
667      }
668      if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
669        CHECK_EQ(tgt_lir->offset, it2.NativePcOffset());
670        CHECK_EQ(tgt_lir->dalvik_offset, it2.DexPc());
671        ++it2;
672      }
673    }
674    CHECK(it == table.PcToDexEnd());
675    CHECK(it2 == table.DexToPcEnd());
676  }
677}
678
679class NativePcToReferenceMapBuilder {
680 public:
681  NativePcToReferenceMapBuilder(std::vector<uint8_t>* table,
682                                size_t entries, uint32_t max_native_offset,
683                                size_t references_width) : entries_(entries),
684                                references_width_(references_width), in_use_(entries),
685                                table_(table) {
686    // Compute width in bytes needed to hold max_native_offset.
687    native_offset_width_ = 0;
688    while (max_native_offset != 0) {
689      native_offset_width_++;
690      max_native_offset >>= 8;
691    }
692    // Resize table and set up header.
693    table->resize((EntryWidth() * entries) + sizeof(uint32_t));
694    CHECK_LT(native_offset_width_, 1U << 3);
695    (*table)[0] = native_offset_width_ & 7;
696    CHECK_LT(references_width_, 1U << 13);
697    (*table)[0] |= (references_width_ << 3) & 0xFF;
698    (*table)[1] = (references_width_ >> 5) & 0xFF;
699    CHECK_LT(entries, 1U << 16);
700    (*table)[2] = entries & 0xFF;
701    (*table)[3] = (entries >> 8) & 0xFF;
702  }
703
704  void AddEntry(uint32_t native_offset, const uint8_t* references) {
705    size_t table_index = TableIndex(native_offset);
706    while (in_use_[table_index]) {
707      table_index = (table_index + 1) % entries_;
708    }
709    in_use_[table_index] = true;
710    SetCodeOffset(table_index, native_offset);
711    DCHECK_EQ(native_offset, GetCodeOffset(table_index));
712    SetReferences(table_index, references);
713  }
714
715 private:
716  size_t TableIndex(uint32_t native_offset) {
717    return NativePcOffsetToReferenceMap::Hash(native_offset) % entries_;
718  }
719
720  uint32_t GetCodeOffset(size_t table_index) {
721    uint32_t native_offset = 0;
722    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
723    for (size_t i = 0; i < native_offset_width_; i++) {
724      native_offset |= (*table_)[table_offset + i] << (i * 8);
725    }
726    return native_offset;
727  }
728
729  void SetCodeOffset(size_t table_index, uint32_t native_offset) {
730    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
731    for (size_t i = 0; i < native_offset_width_; i++) {
732      (*table_)[table_offset + i] = (native_offset >> (i * 8)) & 0xFF;
733    }
734  }
735
736  void SetReferences(size_t table_index, const uint8_t* references) {
737    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
738    memcpy(&(*table_)[table_offset + native_offset_width_], references, references_width_);
739  }
740
741  size_t EntryWidth() const {
742    return native_offset_width_ + references_width_;
743  }
744
745  // Number of entries in the table.
746  const size_t entries_;
747  // Number of bytes used to encode the reference bitmap.
748  const size_t references_width_;
749  // Number of bytes used to encode a native offset.
750  size_t native_offset_width_;
751  // Entries that are in use.
752  std::vector<bool> in_use_;
753  // The table we're building.
754  std::vector<uint8_t>* const table_;
755};
756
757void Mir2Lir::CreateNativeGcMap() {
758  DCHECK(!encoded_mapping_table_.empty());
759  MappingTable mapping_table(&encoded_mapping_table_[0]);
760  uint32_t max_native_offset = 0;
761  for (auto it = mapping_table.PcToDexBegin(), end = mapping_table.PcToDexEnd(); it != end; ++it) {
762    uint32_t native_offset = it.NativePcOffset();
763    if (native_offset > max_native_offset) {
764      max_native_offset = native_offset;
765    }
766  }
767  MethodReference method_ref(cu_->dex_file, cu_->method_idx);
768  const std::vector<uint8_t>& gc_map_raw =
769      mir_graph_->GetCurrentDexCompilationUnit()->GetVerifiedMethod()->GetDexGcMap();
770  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
771  DCHECK_EQ(gc_map_raw.size(), dex_gc_map.RawSize());
772  // Compute native offset to references size.
773  NativePcToReferenceMapBuilder native_gc_map_builder(&native_gc_map_,
774                                                      mapping_table.PcToDexSize(),
775                                                      max_native_offset, dex_gc_map.RegWidth());
776
777  for (auto it = mapping_table.PcToDexBegin(), end = mapping_table.PcToDexEnd(); it != end; ++it) {
778    uint32_t native_offset = it.NativePcOffset();
779    uint32_t dex_pc = it.DexPc();
780    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
781    CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
782    native_gc_map_builder.AddEntry(native_offset, references);
783  }
784}
785
786/* Determine the offset of each literal field */
787int Mir2Lir::AssignLiteralOffset(CodeOffset offset) {
788  offset = AssignLiteralOffsetCommon(literal_list_, offset);
789  offset = AssignLiteralPointerOffsetCommon(code_literal_list_, offset);
790  offset = AssignLiteralPointerOffsetCommon(method_literal_list_, offset);
791  offset = AssignLiteralPointerOffsetCommon(class_literal_list_, offset);
792  return offset;
793}
794
795int Mir2Lir::AssignSwitchTablesOffset(CodeOffset offset) {
796  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
797  while (true) {
798    Mir2Lir::SwitchTable* tab_rec = iterator.Next();
799    if (tab_rec == NULL) break;
800    tab_rec->offset = offset;
801    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
802      offset += tab_rec->table[1] * (sizeof(int) * 2);
803    } else {
804      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
805                static_cast<int>(Instruction::kPackedSwitchSignature));
806      offset += tab_rec->table[1] * sizeof(int);
807    }
808  }
809  return offset;
810}
811
812int Mir2Lir::AssignFillArrayDataOffset(CodeOffset offset) {
813  GrowableArray<FillArrayData*>::Iterator iterator(&fill_array_data_);
814  while (true) {
815    Mir2Lir::FillArrayData *tab_rec = iterator.Next();
816    if (tab_rec == NULL) break;
817    tab_rec->offset = offset;
818    offset += tab_rec->size;
819    // word align
820    offset = (offset + 3) & ~3;
821    }
822  return offset;
823}
824
825/*
826 * Insert a kPseudoCaseLabel at the beginning of the Dalvik
827 * offset vaddr if pretty-printing, otherise use the standard block
828 * label.  The selected label will be used to fix up the case
829 * branch table during the assembly phase.  All resource flags
830 * are set to prevent code motion.  KeyVal is just there for debugging.
831 */
832LIR* Mir2Lir::InsertCaseLabel(DexOffset vaddr, int keyVal) {
833  LIR* boundary_lir = &block_label_list_[mir_graph_->FindBlock(vaddr)->id];
834  LIR* res = boundary_lir;
835  if (cu_->verbose) {
836    // Only pay the expense if we're pretty-printing.
837    LIR* new_label = static_cast<LIR*>(arena_->Alloc(sizeof(LIR), ArenaAllocator::kAllocLIR));
838    new_label->dalvik_offset = vaddr;
839    new_label->opcode = kPseudoCaseLabel;
840    new_label->operands[0] = keyVal;
841    new_label->flags.fixup = kFixupLabel;
842    DCHECK(!new_label->flags.use_def_invalid);
843    new_label->u.m.def_mask = ENCODE_ALL;
844    InsertLIRAfter(boundary_lir, new_label);
845    res = new_label;
846  }
847  return res;
848}
849
850void Mir2Lir::MarkPackedCaseLabels(Mir2Lir::SwitchTable* tab_rec) {
851  const uint16_t* table = tab_rec->table;
852  DexOffset base_vaddr = tab_rec->vaddr;
853  const int32_t *targets = reinterpret_cast<const int32_t*>(&table[4]);
854  int entries = table[1];
855  int low_key = s4FromSwitchData(&table[2]);
856  for (int i = 0; i < entries; i++) {
857    tab_rec->targets[i] = InsertCaseLabel(base_vaddr + targets[i], i + low_key);
858  }
859}
860
861void Mir2Lir::MarkSparseCaseLabels(Mir2Lir::SwitchTable* tab_rec) {
862  const uint16_t* table = tab_rec->table;
863  DexOffset base_vaddr = tab_rec->vaddr;
864  int entries = table[1];
865  const int32_t* keys = reinterpret_cast<const int32_t*>(&table[2]);
866  const int32_t* targets = &keys[entries];
867  for (int i = 0; i < entries; i++) {
868    tab_rec->targets[i] = InsertCaseLabel(base_vaddr + targets[i], keys[i]);
869  }
870}
871
872void Mir2Lir::ProcessSwitchTables() {
873  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
874  while (true) {
875    Mir2Lir::SwitchTable *tab_rec = iterator.Next();
876    if (tab_rec == NULL) break;
877    if (tab_rec->table[0] == Instruction::kPackedSwitchSignature) {
878      MarkPackedCaseLabels(tab_rec);
879    } else if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
880      MarkSparseCaseLabels(tab_rec);
881    } else {
882      LOG(FATAL) << "Invalid switch table";
883    }
884  }
885}
886
887void Mir2Lir::DumpSparseSwitchTable(const uint16_t* table) {
888  /*
889   * Sparse switch data format:
890   *  ushort ident = 0x0200   magic value
891   *  ushort size       number of entries in the table; > 0
892   *  int keys[size]      keys, sorted low-to-high; 32-bit aligned
893   *  int targets[size]     branch targets, relative to switch opcode
894   *
895   * Total size is (2+size*4) 16-bit code units.
896   */
897  uint16_t ident = table[0];
898  int entries = table[1];
899  const int32_t* keys = reinterpret_cast<const int32_t*>(&table[2]);
900  const int32_t* targets = &keys[entries];
901  LOG(INFO) <<  "Sparse switch table - ident:0x" << std::hex << ident
902            << ", entries: " << std::dec << entries;
903  for (int i = 0; i < entries; i++) {
904    LOG(INFO) << "  Key[" << keys[i] << "] -> 0x" << std::hex << targets[i];
905  }
906}
907
908void Mir2Lir::DumpPackedSwitchTable(const uint16_t* table) {
909  /*
910   * Packed switch data format:
911   *  ushort ident = 0x0100   magic value
912   *  ushort size       number of entries in the table
913   *  int first_key       first (and lowest) switch case value
914   *  int targets[size]     branch targets, relative to switch opcode
915   *
916   * Total size is (4+size*2) 16-bit code units.
917   */
918  uint16_t ident = table[0];
919  const int32_t* targets = reinterpret_cast<const int32_t*>(&table[4]);
920  int entries = table[1];
921  int low_key = s4FromSwitchData(&table[2]);
922  LOG(INFO) << "Packed switch table - ident:0x" << std::hex << ident
923            << ", entries: " << std::dec << entries << ", low_key: " << low_key;
924  for (int i = 0; i < entries; i++) {
925    LOG(INFO) << "  Key[" << (i + low_key) << "] -> 0x" << std::hex
926              << targets[i];
927  }
928}
929
930/* Set up special LIR to mark a Dalvik byte-code instruction start for pretty printing */
931void Mir2Lir::MarkBoundary(DexOffset offset, const char* inst_str) {
932  // NOTE: only used for debug listings.
933  NewLIR1(kPseudoDalvikByteCodeBoundary, WrapPointer(ArenaStrdup(inst_str)));
934}
935
936bool Mir2Lir::EvaluateBranch(Instruction::Code opcode, int32_t src1, int32_t src2) {
937  bool is_taken;
938  switch (opcode) {
939    case Instruction::IF_EQ: is_taken = (src1 == src2); break;
940    case Instruction::IF_NE: is_taken = (src1 != src2); break;
941    case Instruction::IF_LT: is_taken = (src1 < src2); break;
942    case Instruction::IF_GE: is_taken = (src1 >= src2); break;
943    case Instruction::IF_GT: is_taken = (src1 > src2); break;
944    case Instruction::IF_LE: is_taken = (src1 <= src2); break;
945    case Instruction::IF_EQZ: is_taken = (src1 == 0); break;
946    case Instruction::IF_NEZ: is_taken = (src1 != 0); break;
947    case Instruction::IF_LTZ: is_taken = (src1 < 0); break;
948    case Instruction::IF_GEZ: is_taken = (src1 >= 0); break;
949    case Instruction::IF_GTZ: is_taken = (src1 > 0); break;
950    case Instruction::IF_LEZ: is_taken = (src1 <= 0); break;
951    default:
952      LOG(FATAL) << "Unexpected opcode " << opcode;
953      is_taken = false;
954  }
955  return is_taken;
956}
957
958// Convert relation of src1/src2 to src2/src1
959ConditionCode Mir2Lir::FlipComparisonOrder(ConditionCode before) {
960  ConditionCode res;
961  switch (before) {
962    case kCondEq: res = kCondEq; break;
963    case kCondNe: res = kCondNe; break;
964    case kCondLt: res = kCondGt; break;
965    case kCondGt: res = kCondLt; break;
966    case kCondLe: res = kCondGe; break;
967    case kCondGe: res = kCondLe; break;
968    default:
969      res = static_cast<ConditionCode>(0);
970      LOG(FATAL) << "Unexpected ccode " << before;
971  }
972  return res;
973}
974
975// TODO: move to mir_to_lir.cc
976Mir2Lir::Mir2Lir(CompilationUnit* cu, MIRGraph* mir_graph, ArenaAllocator* arena)
977    : Backend(arena),
978      literal_list_(NULL),
979      method_literal_list_(NULL),
980      class_literal_list_(NULL),
981      code_literal_list_(NULL),
982      first_fixup_(NULL),
983      cu_(cu),
984      mir_graph_(mir_graph),
985      switch_tables_(arena, 4, kGrowableArraySwitchTables),
986      fill_array_data_(arena, 4, kGrowableArrayFillArrayData),
987      throw_launchpads_(arena, 2048, kGrowableArrayThrowLaunchPads),
988      suspend_launchpads_(arena, 4, kGrowableArraySuspendLaunchPads),
989      intrinsic_launchpads_(arena, 2048, kGrowableArrayMisc),
990      tempreg_info_(arena, 20, kGrowableArrayMisc),
991      reginfo_map_(arena, 64, kGrowableArrayMisc),
992      pointer_storage_(arena, 128, kGrowableArrayMisc),
993      data_offset_(0),
994      total_size_(0),
995      block_label_list_(NULL),
996      promotion_map_(NULL),
997      current_dalvik_offset_(0),
998      estimated_native_code_size_(0),
999      reg_pool_(NULL),
1000      live_sreg_(0),
1001      num_core_spills_(0),
1002      num_fp_spills_(0),
1003      frame_size_(0),
1004      core_spill_mask_(0),
1005      fp_spill_mask_(0),
1006      first_lir_insn_(NULL),
1007      last_lir_insn_(NULL),
1008      slow_paths_(arena, 32, kGrowableArraySlowPaths) {
1009  // Reserve pointer id 0 for NULL.
1010  size_t null_idx = WrapPointer(NULL);
1011  DCHECK_EQ(null_idx, 0U);
1012}
1013
1014void Mir2Lir::Materialize() {
1015  cu_->NewTimingSplit("RegisterAllocation");
1016  CompilerInitializeRegAlloc();  // Needs to happen after SSA naming
1017
1018  /* Allocate Registers using simple local allocation scheme */
1019  SimpleRegAlloc();
1020
1021  /* First try the custom light codegen for special cases. */
1022  DCHECK(cu_->compiler_driver->GetMethodInlinerMap() != nullptr);
1023  bool special_worked = cu_->compiler_driver->GetMethodInlinerMap()->GetMethodInliner(cu_->dex_file)
1024      ->GenSpecial(this, cu_->method_idx);
1025
1026  /* Take normal path for converting MIR to LIR only if the special codegen did not succeed. */
1027  if (special_worked == false) {
1028    MethodMIR2LIR();
1029  }
1030
1031  /* Method is not empty */
1032  if (first_lir_insn_) {
1033    // mark the targets of switch statement case labels
1034    ProcessSwitchTables();
1035
1036    /* Convert LIR into machine code. */
1037    AssembleLIR();
1038
1039    if (cu_->verbose) {
1040      CodegenDump();
1041    }
1042  }
1043}
1044
1045CompiledMethod* Mir2Lir::GetCompiledMethod() {
1046  // Combine vmap tables - core regs, then fp regs - into vmap_table.
1047  Leb128EncodingVector vmap_encoder;
1048  if (frame_size_ > 0) {
1049    // Prefix the encoded data with its size.
1050    size_t size = core_vmap_table_.size() + 1 /* marker */ + fp_vmap_table_.size();
1051    vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
1052    vmap_encoder.PushBackUnsigned(size);
1053    // Core regs may have been inserted out of order - sort first.
1054    std::sort(core_vmap_table_.begin(), core_vmap_table_.end());
1055    for (size_t i = 0 ; i < core_vmap_table_.size(); ++i) {
1056      // Copy, stripping out the phys register sort key.
1057      vmap_encoder.PushBackUnsigned(
1058          ~(-1 << VREG_NUM_WIDTH) & (core_vmap_table_[i] + VmapTable::kEntryAdjustment));
1059    }
1060    // Push a marker to take place of lr.
1061    vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
1062    // fp regs already sorted.
1063    for (uint32_t i = 0; i < fp_vmap_table_.size(); i++) {
1064      vmap_encoder.PushBackUnsigned(fp_vmap_table_[i] + VmapTable::kEntryAdjustment);
1065    }
1066  } else {
1067    DCHECK_EQ(__builtin_popcount(core_spill_mask_), 0);
1068    DCHECK_EQ(__builtin_popcount(fp_spill_mask_), 0);
1069    DCHECK_EQ(core_vmap_table_.size(), 0u);
1070    DCHECK_EQ(fp_vmap_table_.size(), 0u);
1071    vmap_encoder.PushBackUnsigned(0u);  // Size is 0.
1072  }
1073
1074  UniquePtr<std::vector<uint8_t> > cfi_info(ReturnCallFrameInformation());
1075  CompiledMethod* result =
1076      new CompiledMethod(*cu_->compiler_driver, cu_->instruction_set, code_buffer_, frame_size_,
1077                         core_spill_mask_, fp_spill_mask_, encoded_mapping_table_,
1078                         vmap_encoder.GetData(), native_gc_map_, cfi_info.get());
1079  return result;
1080}
1081
1082size_t Mir2Lir::GetMaxPossibleCompilerTemps() const {
1083  // Chose a reasonably small value in order to contain stack growth.
1084  // Backends that are smarter about spill region can return larger values.
1085  const size_t max_compiler_temps = 10;
1086  return max_compiler_temps;
1087}
1088
1089size_t Mir2Lir::GetNumBytesForCompilerTempSpillRegion() {
1090  // By default assume that the Mir2Lir will need one slot for each temporary.
1091  // If the backend can better determine temps that have non-overlapping ranges and
1092  // temps that do not need spilled, it can actually provide a small region.
1093  return (mir_graph_->GetNumUsedCompilerTemps() * sizeof(uint32_t));
1094}
1095
1096int Mir2Lir::ComputeFrameSize() {
1097  /* Figure out the frame size */
1098  static const uint32_t kAlignMask = kStackAlignment - 1;
1099  uint32_t size = ((num_core_spills_ + num_fp_spills_ +
1100                   1 /* filler word */ + cu_->num_regs + cu_->num_outs)
1101                   * sizeof(uint32_t)) +
1102                   GetNumBytesForCompilerTempSpillRegion();
1103  /* Align and set */
1104  return (size + kAlignMask) & ~(kAlignMask);
1105}
1106
1107/*
1108 * Append an LIR instruction to the LIR list maintained by a compilation
1109 * unit
1110 */
1111void Mir2Lir::AppendLIR(LIR* lir) {
1112  if (first_lir_insn_ == NULL) {
1113    DCHECK(last_lir_insn_ == NULL);
1114    last_lir_insn_ = first_lir_insn_ = lir;
1115    lir->prev = lir->next = NULL;
1116  } else {
1117    last_lir_insn_->next = lir;
1118    lir->prev = last_lir_insn_;
1119    lir->next = NULL;
1120    last_lir_insn_ = lir;
1121  }
1122}
1123
1124/*
1125 * Insert an LIR instruction before the current instruction, which cannot be the
1126 * first instruction.
1127 *
1128 * prev_lir <-> new_lir <-> current_lir
1129 */
1130void Mir2Lir::InsertLIRBefore(LIR* current_lir, LIR* new_lir) {
1131  DCHECK(current_lir->prev != NULL);
1132  LIR *prev_lir = current_lir->prev;
1133
1134  prev_lir->next = new_lir;
1135  new_lir->prev = prev_lir;
1136  new_lir->next = current_lir;
1137  current_lir->prev = new_lir;
1138}
1139
1140/*
1141 * Insert an LIR instruction after the current instruction, which cannot be the
1142 * first instruction.
1143 *
1144 * current_lir -> new_lir -> old_next
1145 */
1146void Mir2Lir::InsertLIRAfter(LIR* current_lir, LIR* new_lir) {
1147  new_lir->prev = current_lir;
1148  new_lir->next = current_lir->next;
1149  current_lir->next = new_lir;
1150  new_lir->next->prev = new_lir;
1151}
1152
1153bool Mir2Lir::IsPowerOfTwo(uint64_t x) {
1154  return (x & (x - 1)) == 0;
1155}
1156
1157// Returns the index of the lowest set bit in 'x'.
1158int32_t Mir2Lir::LowestSetBit(uint64_t x) {
1159  int bit_posn = 0;
1160  while ((x & 0xf) == 0) {
1161    bit_posn += 4;
1162    x >>= 4;
1163  }
1164  while ((x & 1) == 0) {
1165    bit_posn++;
1166    x >>= 1;
1167  }
1168  return bit_posn;
1169}
1170
1171bool Mir2Lir::BadOverlap(RegLocation rl_src, RegLocation rl_dest) {
1172  DCHECK(rl_src.wide);
1173  DCHECK(rl_dest.wide);
1174  return (abs(mir_graph_->SRegToVReg(rl_src.s_reg_low) - mir_graph_->SRegToVReg(rl_dest.s_reg_low)) == 1);
1175}
1176
1177LIR *Mir2Lir::OpCmpMemImmBranch(ConditionCode cond, int temp_reg, int base_reg,
1178                                int offset, int check_value, LIR* target) {
1179  // Handle this for architectures that can't compare to memory.
1180  LoadWordDisp(base_reg, offset, temp_reg);
1181  LIR* branch = OpCmpImmBranch(cond, temp_reg, check_value, target);
1182  return branch;
1183}
1184
1185void Mir2Lir::AddSlowPath(LIRSlowPath* slowpath) {
1186  slow_paths_.Insert(slowpath);
1187}
1188
1189void Mir2Lir::LoadCodeAddress(int dex_method_index, InvokeType type, SpecialTargetRegister symbolic_reg) {
1190  LIR* data_target = ScanLiteralPool(code_literal_list_, dex_method_index, 0);
1191  if (data_target == NULL) {
1192    data_target = AddWordData(&code_literal_list_, dex_method_index);
1193    data_target->operands[1] = type;
1194  }
1195  LIR* load_pc_rel = OpPcRelLoad(TargetReg(symbolic_reg), data_target);
1196  AppendLIR(load_pc_rel);
1197  DCHECK_NE(cu_->instruction_set, kMips) << reinterpret_cast<void*>(data_target);
1198}
1199
1200void Mir2Lir::LoadMethodAddress(int dex_method_index, InvokeType type, SpecialTargetRegister symbolic_reg) {
1201  LIR* data_target = ScanLiteralPool(method_literal_list_, dex_method_index, 0);
1202  if (data_target == NULL) {
1203    data_target = AddWordData(&method_literal_list_, dex_method_index);
1204    data_target->operands[1] = type;
1205  }
1206  LIR* load_pc_rel = OpPcRelLoad(TargetReg(symbolic_reg), data_target);
1207  AppendLIR(load_pc_rel);
1208  DCHECK_NE(cu_->instruction_set, kMips) << reinterpret_cast<void*>(data_target);
1209}
1210
1211void Mir2Lir::LoadClassType(uint32_t type_idx, SpecialTargetRegister symbolic_reg) {
1212  // Use the literal pool and a PC-relative load from a data word.
1213  LIR* data_target = ScanLiteralPool(class_literal_list_, type_idx, 0);
1214  if (data_target == nullptr) {
1215    data_target = AddWordData(&class_literal_list_, type_idx);
1216  }
1217  LIR* load_pc_rel = OpPcRelLoad(TargetReg(symbolic_reg), data_target);
1218  AppendLIR(load_pc_rel);
1219}
1220
1221std::vector<uint8_t>* Mir2Lir::ReturnCallFrameInformation() {
1222  // Default case is to do nothing.
1223  return nullptr;
1224}
1225
1226}  // namespace art
1227