compiler/dex/quick/codegen_util.cc

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