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