Home | History | Annotate | Download | only in quick
      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
   1278