codegen_util.cc revision 479f83c196d5a95e36196eac548dc6019e70a5be 
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 "mir_to_lir-inl.h"
21#include "verifier/dex_gc_map.h"
22#include "verifier/method_verifier.h"
23
24namespace art {
25
26bool Mir2Lir::IsInexpensiveConstant(RegLocation rl_src) {
27  bool res = false;
28  if (rl_src.is_const) {
29    if (rl_src.wide) {
30      if (rl_src.fp) {
31         res = InexpensiveConstantDouble(mir_graph_->ConstantValueWide(rl_src));
32      } else {
33         res = InexpensiveConstantLong(mir_graph_->ConstantValueWide(rl_src));
34      }
35    } else {
36      if (rl_src.fp) {
37         res = InexpensiveConstantFloat(mir_graph_->ConstantValue(rl_src));
38      } else {
39         res = InexpensiveConstantInt(mir_graph_->ConstantValue(rl_src));
40      }
41    }
42  }
43  return res;
44}
45
46void Mir2Lir::MarkSafepointPC(LIR* inst) {
47  inst->def_mask = ENCODE_ALL;
48  LIR* safepoint_pc = NewLIR0(kPseudoSafepointPC);
49  DCHECK_EQ(safepoint_pc->def_mask, ENCODE_ALL);
50}
51
52bool Mir2Lir::FastInstance(uint32_t field_idx, int& field_offset, bool& is_volatile, bool is_put) {
53  return cu_->compiler_driver->ComputeInstanceFieldInfo(
54      field_idx, mir_graph_->GetCurrentDexCompilationUnit(), field_offset, is_volatile, is_put);
55}
56
57/* Convert an instruction to a NOP */
58void Mir2Lir::NopLIR(LIR* lir) {
59  lir->flags.is_nop = true;
60}
61
62void Mir2Lir::SetMemRefType(LIR* lir, bool is_load, int mem_type) {
63  uint64_t *mask_ptr;
64  uint64_t mask = ENCODE_MEM;
65  DCHECK(GetTargetInstFlags(lir->opcode) & (IS_LOAD | IS_STORE));
66  if (is_load) {
67    mask_ptr = &lir->use_mask;
68  } else {
69    mask_ptr = &lir->def_mask;
70  }
71  /* Clear out the memref flags */
72  *mask_ptr &= ~mask;
73  /* ..and then add back the one we need */
74  switch (mem_type) {
75    case kLiteral:
76      DCHECK(is_load);
77      *mask_ptr |= ENCODE_LITERAL;
78      break;
79    case kDalvikReg:
80      *mask_ptr |= ENCODE_DALVIK_REG;
81      break;
82    case kHeapRef:
83      *mask_ptr |= ENCODE_HEAP_REF;
84      break;
85    case kMustNotAlias:
86      /* Currently only loads can be marked as kMustNotAlias */
87      DCHECK(!(GetTargetInstFlags(lir->opcode) & IS_STORE));
88      *mask_ptr |= ENCODE_MUST_NOT_ALIAS;
89      break;
90    default:
91      LOG(FATAL) << "Oat: invalid memref kind - " << mem_type;
92  }
93}
94
95/*
96 * Mark load/store instructions that access Dalvik registers through the stack.
97 */
98void Mir2Lir::AnnotateDalvikRegAccess(LIR* lir, int reg_id, bool is_load,
99                                      bool is64bit) {
100  SetMemRefType(lir, is_load, kDalvikReg);
101
102  /*
103   * Store the Dalvik register id in alias_info. Mark the MSB if it is a 64-bit
104   * access.
105   */
106  lir->alias_info = ENCODE_ALIAS_INFO(reg_id, is64bit);
107}
108
109/*
110 * Debugging macros
111 */
112#define DUMP_RESOURCE_MASK(X)
113
114/* Pretty-print a LIR instruction */
115void Mir2Lir::DumpLIRInsn(LIR* lir, unsigned char* base_addr) {
116  int offset = lir->offset;
117  int dest = lir->operands[0];
118  const bool dump_nop = (cu_->enable_debug & (1 << kDebugShowNops));
119
120  /* Handle pseudo-ops individually, and all regular insns as a group */
121  switch (lir->opcode) {
122    case kPseudoMethodEntry:
123      LOG(INFO) << "-------- method entry "
124                << PrettyMethod(cu_->method_idx, *cu_->dex_file);
125      break;
126    case kPseudoMethodExit:
127      LOG(INFO) << "-------- Method_Exit";
128      break;
129    case kPseudoBarrier:
130      LOG(INFO) << "-------- BARRIER";
131      break;
132    case kPseudoEntryBlock:
133      LOG(INFO) << "-------- entry offset: 0x" << std::hex << dest;
134      break;
135    case kPseudoDalvikByteCodeBoundary:
136      if (lir->operands[0] == 0) {
137         lir->operands[0] = reinterpret_cast<uintptr_t>("No instruction string");
138      }
139      LOG(INFO) << "-------- dalvik offset: 0x" << std::hex
140                << lir->dalvik_offset << " @ " << reinterpret_cast<char*>(lir->operands[0]);
141      break;
142    case kPseudoExitBlock:
143      LOG(INFO) << "-------- exit offset: 0x" << std::hex << dest;
144      break;
145    case kPseudoPseudoAlign4:
146      LOG(INFO) << reinterpret_cast<uintptr_t>(base_addr) + offset << " (0x" << std::hex
147                << offset << "): .align4";
148      break;
149    case kPseudoEHBlockLabel:
150      LOG(INFO) << "Exception_Handling:";
151      break;
152    case kPseudoTargetLabel:
153    case kPseudoNormalBlockLabel:
154      LOG(INFO) << "L" << reinterpret_cast<void*>(lir) << ":";
155      break;
156    case kPseudoThrowTarget:
157      LOG(INFO) << "LT" << reinterpret_cast<void*>(lir) << ":";
158      break;
159    case kPseudoIntrinsicRetry:
160      LOG(INFO) << "IR" << reinterpret_cast<void*>(lir) << ":";
161      break;
162    case kPseudoSuspendTarget:
163      LOG(INFO) << "LS" << reinterpret_cast<void*>(lir) << ":";
164      break;
165    case kPseudoSafepointPC:
166      LOG(INFO) << "LsafepointPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
167      break;
168    case kPseudoExportedPC:
169      LOG(INFO) << "LexportedPC_0x" << std::hex << lir->offset << "_" << lir->dalvik_offset << ":";
170      break;
171    case kPseudoCaseLabel:
172      LOG(INFO) << "LC" << reinterpret_cast<void*>(lir) << ": Case target 0x"
173                << std::hex << lir->operands[0] << "|" << std::dec <<
174        lir->operands[0];
175      break;
176    default:
177      if (lir->flags.is_nop && !dump_nop) {
178        break;
179      } else {
180        std::string op_name(BuildInsnString(GetTargetInstName(lir->opcode),
181                                               lir, base_addr));
182        std::string op_operands(BuildInsnString(GetTargetInstFmt(lir->opcode),
183                                                    lir, base_addr));
184        LOG(INFO) << StringPrintf("%05x: %-9s%s%s",
185                                  reinterpret_cast<unsigned int>(base_addr + offset),
186                                  op_name.c_str(), op_operands.c_str(),
187                                  lir->flags.is_nop ? "(nop)" : "");
188      }
189      break;
190  }
191
192  if (lir->use_mask && (!lir->flags.is_nop || dump_nop)) {
193    DUMP_RESOURCE_MASK(DumpResourceMask(lir, lir->use_mask, "use"));
194  }
195  if (lir->def_mask && (!lir->flags.is_nop || dump_nop)) {
196    DUMP_RESOURCE_MASK(DumpResourceMask(lir, lir->def_mask, "def"));
197  }
198}
199
200void Mir2Lir::DumpPromotionMap() {
201  int num_regs = cu_->num_dalvik_registers + cu_->num_compiler_temps + 1;
202  for (int i = 0; i < num_regs; i++) {
203    PromotionMap v_reg_map = promotion_map_[i];
204    std::string buf;
205    if (v_reg_map.fp_location == kLocPhysReg) {
206      StringAppendF(&buf, " : s%d", v_reg_map.FpReg & FpRegMask());
207    }
208
209    std::string buf3;
210    if (i < cu_->num_dalvik_registers) {
211      StringAppendF(&buf3, "%02d", i);
212    } else if (i == mir_graph_->GetMethodSReg()) {
213      buf3 = "Method*";
214    } else {
215      StringAppendF(&buf3, "ct%d", i - cu_->num_dalvik_registers);
216    }
217
218    LOG(INFO) << StringPrintf("V[%s] -> %s%d%s", buf3.c_str(),
219                              v_reg_map.core_location == kLocPhysReg ?
220                              "r" : "SP+", v_reg_map.core_location == kLocPhysReg ?
221                              v_reg_map.core_reg : SRegOffset(i),
222                              buf.c_str());
223  }
224}
225
226/* Dump a mapping table */
227void Mir2Lir::DumpMappingTable(const char* table_name, const std::string& descriptor,
228                               const std::string& name, const std::string& signature,
229                               const std::vector<uint32_t>& v) {
230  if (v.size() > 0) {
231    std::string line(StringPrintf("\n  %s %s%s_%s_table[%zu] = {", table_name,
232                     descriptor.c_str(), name.c_str(), signature.c_str(), v.size()));
233    std::replace(line.begin(), line.end(), ';', '_');
234    LOG(INFO) << line;
235    for (uint32_t i = 0; i < v.size(); i+=2) {
236      line = StringPrintf("    {0x%05x, 0x%04x},", v[i], v[i+1]);
237      LOG(INFO) << line;
238    }
239    LOG(INFO) <<"  };\n\n";
240  }
241}
242
243/* Dump instructions and constant pool contents */
244void Mir2Lir::CodegenDump() {
245  LOG(INFO) << "Dumping LIR insns for "
246            << PrettyMethod(cu_->method_idx, *cu_->dex_file);
247  LIR* lir_insn;
248  int insns_size = cu_->code_item->insns_size_in_code_units_;
249
250  LOG(INFO) << "Regs (excluding ins) : " << cu_->num_regs;
251  LOG(INFO) << "Ins          : " << cu_->num_ins;
252  LOG(INFO) << "Outs         : " << cu_->num_outs;
253  LOG(INFO) << "CoreSpills       : " << num_core_spills_;
254  LOG(INFO) << "FPSpills       : " << num_fp_spills_;
255  LOG(INFO) << "CompilerTemps    : " << cu_->num_compiler_temps;
256  LOG(INFO) << "Frame size       : " << frame_size_;
257  LOG(INFO) << "code size is " << total_size_ <<
258    " bytes, Dalvik size is " << insns_size * 2;
259  LOG(INFO) << "expansion factor: "
260            << static_cast<float>(total_size_) / static_cast<float>(insns_size * 2);
261  DumpPromotionMap();
262  for (lir_insn = first_lir_insn_; lir_insn != NULL; lir_insn = lir_insn->next) {
263    DumpLIRInsn(lir_insn, 0);
264  }
265  for (lir_insn = literal_list_; lir_insn != NULL; lir_insn = lir_insn->next) {
266    LOG(INFO) << StringPrintf("%x (%04x): .word (%#x)", lir_insn->offset, lir_insn->offset,
267                              lir_insn->operands[0]);
268  }
269
270  const DexFile::MethodId& method_id =
271      cu_->dex_file->GetMethodId(cu_->method_idx);
272  std::string signature(cu_->dex_file->GetMethodSignature(method_id));
273  std::string name(cu_->dex_file->GetMethodName(method_id));
274  std::string descriptor(cu_->dex_file->GetMethodDeclaringClassDescriptor(method_id));
275
276  // Dump mapping tables
277  DumpMappingTable("PC2Dex_MappingTable", descriptor, name, signature, pc2dex_mapping_table_);
278  DumpMappingTable("Dex2PC_MappingTable", descriptor, name, signature, dex2pc_mapping_table_);
279}
280
281/*
282 * Search the existing constants in the literal pool for an exact or close match
283 * within specified delta (greater or equal to 0).
284 */
285LIR* Mir2Lir::ScanLiteralPool(LIR* data_target, int value, unsigned int delta) {
286  while (data_target) {
287    if ((static_cast<unsigned>(value - data_target->operands[0])) <= delta)
288      return data_target;
289    data_target = data_target->next;
290  }
291  return NULL;
292}
293
294/* Search the existing constants in the literal pool for an exact wide match */
295LIR* Mir2Lir::ScanLiteralPoolWide(LIR* data_target, int val_lo, int val_hi) {
296  bool lo_match = false;
297  LIR* lo_target = NULL;
298  while (data_target) {
299    if (lo_match && (data_target->operands[0] == val_hi)) {
300      // Record high word in case we need to expand this later.
301      lo_target->operands[1] = val_hi;
302      return lo_target;
303    }
304    lo_match = false;
305    if (data_target->operands[0] == val_lo) {
306      lo_match = true;
307      lo_target = data_target;
308    }
309    data_target = data_target->next;
310  }
311  return NULL;
312}
313
314/*
315 * The following are building blocks to insert constants into the pool or
316 * instruction streams.
317 */
318
319/* Add a 32-bit constant to the constant pool */
320LIR* Mir2Lir::AddWordData(LIR* *constant_list_p, int value) {
321  /* Add the constant to the literal pool */
322  if (constant_list_p) {
323    LIR* new_value = static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocData));
324    new_value->operands[0] = value;
325    new_value->next = *constant_list_p;
326    *constant_list_p = new_value;
327    return new_value;
328  }
329  return NULL;
330}
331
332/* Add a 64-bit constant to the constant pool or mixed with code */
333LIR* Mir2Lir::AddWideData(LIR* *constant_list_p, int val_lo, int val_hi) {
334  AddWordData(constant_list_p, val_hi);
335  return AddWordData(constant_list_p, val_lo);
336}
337
338static void PushWord(std::vector<uint8_t>&buf, int data) {
339  buf.push_back(data & 0xff);
340  buf.push_back((data >> 8) & 0xff);
341  buf.push_back((data >> 16) & 0xff);
342  buf.push_back((data >> 24) & 0xff);
343}
344
345static void AlignBuffer(std::vector<uint8_t>&buf, size_t offset) {
346  while (buf.size() < offset) {
347    buf.push_back(0);
348  }
349}
350
351/* Write the literal pool to the output stream */
352void Mir2Lir::InstallLiteralPools() {
353  AlignBuffer(code_buffer_, data_offset_);
354  LIR* data_lir = literal_list_;
355  while (data_lir != NULL) {
356    PushWord(code_buffer_, data_lir->operands[0]);
357    data_lir = NEXT_LIR(data_lir);
358  }
359  // Push code and method literals, record offsets for the compiler to patch.
360  data_lir = code_literal_list_;
361  while (data_lir != NULL) {
362    uint32_t target = data_lir->operands[0];
363    cu_->compiler_driver->AddCodePatch(cu_->dex_file,
364                                      cu_->method_idx,
365                                      cu_->invoke_type,
366                                      target,
367                                      static_cast<InvokeType>(data_lir->operands[1]),
368                                      code_buffer_.size());
369    const DexFile::MethodId& id = cu_->dex_file->GetMethodId(target);
370    // unique based on target to ensure code deduplication works
371    uint32_t unique_patch_value = reinterpret_cast<uint32_t>(&id);
372    PushWord(code_buffer_, unique_patch_value);
373    data_lir = NEXT_LIR(data_lir);
374  }
375  data_lir = method_literal_list_;
376  while (data_lir != NULL) {
377    uint32_t target = data_lir->operands[0];
378    cu_->compiler_driver->AddMethodPatch(cu_->dex_file,
379                                        cu_->method_idx,
380                                        cu_->invoke_type,
381                                        target,
382                                        static_cast<InvokeType>(data_lir->operands[1]),
383                                        code_buffer_.size());
384    const DexFile::MethodId& id = cu_->dex_file->GetMethodId(target);
385    // unique based on target to ensure code deduplication works
386    uint32_t unique_patch_value = reinterpret_cast<uint32_t>(&id);
387    PushWord(code_buffer_, unique_patch_value);
388    data_lir = NEXT_LIR(data_lir);
389  }
390}
391
392/* Write the switch tables to the output stream */
393void Mir2Lir::InstallSwitchTables() {
394  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
395  while (true) {
396    Mir2Lir::SwitchTable* tab_rec = iterator.Next();
397    if (tab_rec == NULL) break;
398    AlignBuffer(code_buffer_, tab_rec->offset);
399    /*
400     * For Arm, our reference point is the address of the bx
401     * instruction that does the launch, so we have to subtract
402     * the auto pc-advance.  For other targets the reference point
403     * is a label, so we can use the offset as-is.
404     */
405    int bx_offset = INVALID_OFFSET;
406    switch (cu_->instruction_set) {
407      case kThumb2:
408        bx_offset = tab_rec->anchor->offset + 4;
409        break;
410      case kX86:
411        bx_offset = 0;
412        break;
413      case kMips:
414        bx_offset = tab_rec->anchor->offset;
415        break;
416      default: LOG(FATAL) << "Unexpected instruction set: " << cu_->instruction_set;
417    }
418    if (cu_->verbose) {
419      LOG(INFO) << "Switch table for offset 0x" << std::hex << bx_offset;
420    }
421    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
422      const int* keys = reinterpret_cast<const int*>(&(tab_rec->table[2]));
423      for (int elems = 0; elems < tab_rec->table[1]; elems++) {
424        int disp = tab_rec->targets[elems]->offset - bx_offset;
425        if (cu_->verbose) {
426          LOG(INFO) << "  Case[" << elems << "] key: 0x"
427                    << std::hex << keys[elems] << ", disp: 0x"
428                    << std::hex << disp;
429        }
430        PushWord(code_buffer_, keys[elems]);
431        PushWord(code_buffer_,
432          tab_rec->targets[elems]->offset - bx_offset);
433      }
434    } else {
435      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
436                static_cast<int>(Instruction::kPackedSwitchSignature));
437      for (int elems = 0; elems < tab_rec->table[1]; elems++) {
438        int disp = tab_rec->targets[elems]->offset - bx_offset;
439        if (cu_->verbose) {
440          LOG(INFO) << "  Case[" << elems << "] disp: 0x"
441                    << std::hex << disp;
442        }
443        PushWord(code_buffer_, tab_rec->targets[elems]->offset - bx_offset);
444      }
445    }
446  }
447}
448
449/* Write the fill array dta to the output stream */
450void Mir2Lir::InstallFillArrayData() {
451  GrowableArray<FillArrayData*>::Iterator iterator(&fill_array_data_);
452  while (true) {
453    Mir2Lir::FillArrayData *tab_rec = iterator.Next();
454    if (tab_rec == NULL) break;
455    AlignBuffer(code_buffer_, tab_rec->offset);
456    for (int i = 0; i < (tab_rec->size + 1) / 2; i++) {
457      code_buffer_.push_back(tab_rec->table[i] & 0xFF);
458      code_buffer_.push_back((tab_rec->table[i] >> 8) & 0xFF);
459    }
460  }
461}
462
463static int AssignLiteralOffsetCommon(LIR* lir, int offset) {
464  for (; lir != NULL; lir = lir->next) {
465    lir->offset = offset;
466    offset += 4;
467  }
468  return offset;
469}
470
471// Make sure we have a code address for every declared catch entry
472bool Mir2Lir::VerifyCatchEntries() {
473  bool success = true;
474  for (std::set<uint32_t>::const_iterator it = mir_graph_->catches_.begin();
475       it != mir_graph_->catches_.end(); ++it) {
476    uint32_t dex_pc = *it;
477    bool found = false;
478    for (size_t i = 0; i < dex2pc_mapping_table_.size(); i += 2) {
479      if (dex_pc == dex2pc_mapping_table_[i+1]) {
480        found = true;
481        break;
482      }
483    }
484    if (!found) {
485      LOG(INFO) << "Missing native PC for catch entry @ 0x" << std::hex << dex_pc;
486      success = false;
487    }
488  }
489  // Now, try in the other direction
490  for (size_t i = 0; i < dex2pc_mapping_table_.size(); i += 2) {
491    uint32_t dex_pc = dex2pc_mapping_table_[i+1];
492    if (mir_graph_->catches_.find(dex_pc) == mir_graph_->catches_.end()) {
493      LOG(INFO) << "Unexpected catch entry @ dex pc 0x" << std::hex << dex_pc;
494      success = false;
495    }
496  }
497  if (!success) {
498    LOG(INFO) << "Bad dex2pcMapping table in " << PrettyMethod(cu_->method_idx, *cu_->dex_file);
499    LOG(INFO) << "Entries @ decode: " << mir_graph_->catches_.size() << ", Entries in table: "
500              << dex2pc_mapping_table_.size()/2;
501  }
502  return success;
503}
504
505
506void Mir2Lir::CreateMappingTables() {
507  for (LIR* tgt_lir = first_lir_insn_; tgt_lir != NULL; tgt_lir = NEXT_LIR(tgt_lir)) {
508    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
509      pc2dex_mapping_table_.push_back(tgt_lir->offset);
510      pc2dex_mapping_table_.push_back(tgt_lir->dalvik_offset);
511    }
512    if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
513      dex2pc_mapping_table_.push_back(tgt_lir->offset);
514      dex2pc_mapping_table_.push_back(tgt_lir->dalvik_offset);
515    }
516  }
517  if (kIsDebugBuild) {
518    DCHECK(VerifyCatchEntries());
519  }
520  combined_mapping_table_.push_back(pc2dex_mapping_table_.size() +
521                                        dex2pc_mapping_table_.size());
522  combined_mapping_table_.push_back(pc2dex_mapping_table_.size());
523  combined_mapping_table_.insert(combined_mapping_table_.end(), pc2dex_mapping_table_.begin(),
524                                 pc2dex_mapping_table_.end());
525  combined_mapping_table_.insert(combined_mapping_table_.end(), dex2pc_mapping_table_.begin(),
526                                 dex2pc_mapping_table_.end());
527}
528
529class NativePcToReferenceMapBuilder {
530 public:
531  NativePcToReferenceMapBuilder(std::vector<uint8_t>* table,
532                                size_t entries, uint32_t max_native_offset,
533                                size_t references_width) : entries_(entries),
534                                references_width_(references_width), in_use_(entries),
535                                table_(table) {
536    // Compute width in bytes needed to hold max_native_offset.
537    native_offset_width_ = 0;
538    while (max_native_offset != 0) {
539      native_offset_width_++;
540      max_native_offset >>= 8;
541    }
542    // Resize table and set up header.
543    table->resize((EntryWidth() * entries) + sizeof(uint32_t));
544    CHECK_LT(native_offset_width_, 1U << 3);
545    (*table)[0] = native_offset_width_ & 7;
546    CHECK_LT(references_width_, 1U << 13);
547    (*table)[0] |= (references_width_ << 3) & 0xFF;
548    (*table)[1] = (references_width_ >> 5) & 0xFF;
549    CHECK_LT(entries, 1U << 16);
550    (*table)[2] = entries & 0xFF;
551    (*table)[3] = (entries >> 8) & 0xFF;
552  }
553
554  void AddEntry(uint32_t native_offset, const uint8_t* references) {
555    size_t table_index = TableIndex(native_offset);
556    while (in_use_[table_index]) {
557      table_index = (table_index + 1) % entries_;
558    }
559    in_use_[table_index] = true;
560    SetNativeOffset(table_index, native_offset);
561    DCHECK_EQ(native_offset, GetNativeOffset(table_index));
562    SetReferences(table_index, references);
563  }
564
565 private:
566  size_t TableIndex(uint32_t native_offset) {
567    return NativePcOffsetToReferenceMap::Hash(native_offset) % entries_;
568  }
569
570  uint32_t GetNativeOffset(size_t table_index) {
571    uint32_t native_offset = 0;
572    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
573    for (size_t i = 0; i < native_offset_width_; i++) {
574      native_offset |= (*table_)[table_offset + i] << (i * 8);
575    }
576    return native_offset;
577  }
578
579  void SetNativeOffset(size_t table_index, uint32_t native_offset) {
580    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
581    for (size_t i = 0; i < native_offset_width_; i++) {
582      (*table_)[table_offset + i] = (native_offset >> (i * 8)) & 0xFF;
583    }
584  }
585
586  void SetReferences(size_t table_index, const uint8_t* references) {
587    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
588    memcpy(&(*table_)[table_offset + native_offset_width_], references, references_width_);
589  }
590
591  size_t EntryWidth() const {
592    return native_offset_width_ + references_width_;
593  }
594
595  // Number of entries in the table.
596  const size_t entries_;
597  // Number of bytes used to encode the reference bitmap.
598  const size_t references_width_;
599  // Number of bytes used to encode a native offset.
600  size_t native_offset_width_;
601  // Entries that are in use.
602  std::vector<bool> in_use_;
603  // The table we're building.
604  std::vector<uint8_t>* const table_;
605};
606
607void Mir2Lir::CreateNativeGcMap() {
608  const std::vector<uint32_t>& mapping_table = pc2dex_mapping_table_;
609  uint32_t max_native_offset = 0;
610  for (size_t i = 0; i < mapping_table.size(); i += 2) {
611    uint32_t native_offset = mapping_table[i + 0];
612    if (native_offset > max_native_offset) {
613      max_native_offset = native_offset;
614    }
615  }
616  MethodReference method_ref(cu_->dex_file, cu_->method_idx);
617  const std::vector<uint8_t>* gc_map_raw = verifier::MethodVerifier::GetDexGcMap(method_ref);
618  verifier::DexPcToReferenceMap dex_gc_map(&(*gc_map_raw)[4], gc_map_raw->size() - 4);
619  // Compute native offset to references size.
620  NativePcToReferenceMapBuilder native_gc_map_builder(&native_gc_map_,
621                                                      mapping_table.size() / 2, max_native_offset,
622                                                      dex_gc_map.RegWidth());
623
624  for (size_t i = 0; i < mapping_table.size(); i += 2) {
625    uint32_t native_offset = mapping_table[i + 0];
626    uint32_t dex_pc = mapping_table[i + 1];
627    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
628    CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
629    native_gc_map_builder.AddEntry(native_offset, references);
630  }
631}
632
633/* Determine the offset of each literal field */
634int Mir2Lir::AssignLiteralOffset(int offset) {
635  offset = AssignLiteralOffsetCommon(literal_list_, offset);
636  offset = AssignLiteralOffsetCommon(code_literal_list_, offset);
637  offset = AssignLiteralOffsetCommon(method_literal_list_, offset);
638  return offset;
639}
640
641int Mir2Lir::AssignSwitchTablesOffset(int offset) {
642  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
643  while (true) {
644    Mir2Lir::SwitchTable *tab_rec = iterator.Next();
645    if (tab_rec == NULL) break;
646    tab_rec->offset = offset;
647    if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
648      offset += tab_rec->table[1] * (sizeof(int) * 2);
649    } else {
650      DCHECK_EQ(static_cast<int>(tab_rec->table[0]),
651                static_cast<int>(Instruction::kPackedSwitchSignature));
652      offset += tab_rec->table[1] * sizeof(int);
653    }
654  }
655  return offset;
656}
657
658int Mir2Lir::AssignFillArrayDataOffset(int offset) {
659  GrowableArray<FillArrayData*>::Iterator iterator(&fill_array_data_);
660  while (true) {
661    Mir2Lir::FillArrayData *tab_rec = iterator.Next();
662    if (tab_rec == NULL) break;
663    tab_rec->offset = offset;
664    offset += tab_rec->size;
665    // word align
666    offset = (offset + 3) & ~3;
667    }
668  return offset;
669}
670
671// LIR offset assignment.
672int Mir2Lir::AssignInsnOffsets() {
673  LIR* lir;
674  int offset = 0;
675
676  for (lir = first_lir_insn_; lir != NULL; lir = NEXT_LIR(lir)) {
677    lir->offset = offset;
678    if (lir->opcode >= 0) {
679      if (!lir->flags.is_nop) {
680        offset += lir->flags.size;
681      }
682    } else if (lir->opcode == kPseudoPseudoAlign4) {
683      if (offset & 0x2) {
684        offset += 2;
685        lir->operands[0] = 1;
686      } else {
687        lir->operands[0] = 0;
688      }
689    }
690    /* Pseudo opcodes don't consume space */
691  }
692
693  return offset;
694}
695
696/*
697 * Walk the compilation unit and assign offsets to instructions
698 * and literals and compute the total size of the compiled unit.
699 */
700void Mir2Lir::AssignOffsets() {
701  int offset = AssignInsnOffsets();
702
703  /* Const values have to be word aligned */
704  offset = (offset + 3) & ~3;
705
706  /* Set up offsets for literals */
707  data_offset_ = offset;
708
709  offset = AssignLiteralOffset(offset);
710
711  offset = AssignSwitchTablesOffset(offset);
712
713  offset = AssignFillArrayDataOffset(offset);
714
715  total_size_ = offset;
716}
717
718/*
719 * Go over each instruction in the list and calculate the offset from the top
720 * before sending them off to the assembler. If out-of-range branch distance is
721 * seen rearrange the instructions a bit to correct it.
722 */
723void Mir2Lir::AssembleLIR() {
724  AssignOffsets();
725  int assembler_retries = 0;
726  /*
727   * Assemble here.  Note that we generate code with optimistic assumptions
728   * and if found now to work, we'll have to redo the sequence and retry.
729   */
730
731  while (true) {
732    AssemblerStatus res = AssembleInstructions(0);
733    if (res == kSuccess) {
734      break;
735    } else {
736      assembler_retries++;
737      if (assembler_retries > MAX_ASSEMBLER_RETRIES) {
738        CodegenDump();
739        LOG(FATAL) << "Assembler error - too many retries";
740      }
741      // Redo offsets and try again
742      AssignOffsets();
743      code_buffer_.clear();
744    }
745  }
746
747  // Install literals
748  InstallLiteralPools();
749
750  // Install switch tables
751  InstallSwitchTables();
752
753  // Install fill array data
754  InstallFillArrayData();
755
756  // Create the mapping table and native offset to reference map.
757  CreateMappingTables();
758
759  CreateNativeGcMap();
760}
761
762/*
763 * Insert a kPseudoCaseLabel at the beginning of the Dalvik
764 * offset vaddr.  This label will be used to fix up the case
765 * branch table during the assembly phase.  Be sure to set
766 * all resource flags on this to prevent code motion across
767 * target boundaries.  KeyVal is just there for debugging.
768 */
769LIR* Mir2Lir::InsertCaseLabel(int vaddr, int keyVal) {
770  SafeMap<unsigned int, LIR*>::iterator it;
771  it = boundary_map_.find(vaddr);
772  if (it == boundary_map_.end()) {
773    LOG(FATAL) << "Error: didn't find vaddr 0x" << std::hex << vaddr;
774  }
775  LIR* new_label = static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR));
776  new_label->dalvik_offset = vaddr;
777  new_label->opcode = kPseudoCaseLabel;
778  new_label->operands[0] = keyVal;
779  InsertLIRAfter(it->second, new_label);
780  return new_label;
781}
782
783void Mir2Lir::MarkPackedCaseLabels(Mir2Lir::SwitchTable *tab_rec) {
784  const uint16_t* table = tab_rec->table;
785  int base_vaddr = tab_rec->vaddr;
786  const int *targets = reinterpret_cast<const int*>(&table[4]);
787  int entries = table[1];
788  int low_key = s4FromSwitchData(&table[2]);
789  for (int i = 0; i < entries; i++) {
790    tab_rec->targets[i] = InsertCaseLabel(base_vaddr + targets[i], i + low_key);
791  }
792}
793
794void Mir2Lir::MarkSparseCaseLabels(Mir2Lir::SwitchTable *tab_rec) {
795  const uint16_t* table = tab_rec->table;
796  int base_vaddr = tab_rec->vaddr;
797  int entries = table[1];
798  const int* keys = reinterpret_cast<const int*>(&table[2]);
799  const int* targets = &keys[entries];
800  for (int i = 0; i < entries; i++) {
801    tab_rec->targets[i] = InsertCaseLabel(base_vaddr + targets[i], keys[i]);
802  }
803}
804
805void Mir2Lir::ProcessSwitchTables() {
806  GrowableArray<SwitchTable*>::Iterator iterator(&switch_tables_);
807  while (true) {
808    Mir2Lir::SwitchTable *tab_rec = iterator.Next();
809    if (tab_rec == NULL) break;
810    if (tab_rec->table[0] == Instruction::kPackedSwitchSignature) {
811      MarkPackedCaseLabels(tab_rec);
812    } else if (tab_rec->table[0] == Instruction::kSparseSwitchSignature) {
813      MarkSparseCaseLabels(tab_rec);
814    } else {
815      LOG(FATAL) << "Invalid switch table";
816    }
817  }
818}
819
820void Mir2Lir::DumpSparseSwitchTable(const uint16_t* table) {
821  /*
822   * Sparse switch data format:
823   *  ushort ident = 0x0200   magic value
824   *  ushort size       number of entries in the table; > 0
825   *  int keys[size]      keys, sorted low-to-high; 32-bit aligned
826   *  int targets[size]     branch targets, relative to switch opcode
827   *
828   * Total size is (2+size*4) 16-bit code units.
829   */
830  uint16_t ident = table[0];
831  int entries = table[1];
832  const int* keys = reinterpret_cast<const int*>(&table[2]);
833  const int* targets = &keys[entries];
834  LOG(INFO) <<  "Sparse switch table - ident:0x" << std::hex << ident
835            << ", entries: " << std::dec << entries;
836  for (int i = 0; i < entries; i++) {
837    LOG(INFO) << "  Key[" << keys[i] << "] -> 0x" << std::hex << targets[i];
838  }
839}
840
841void Mir2Lir::DumpPackedSwitchTable(const uint16_t* table) {
842  /*
843   * Packed switch data format:
844   *  ushort ident = 0x0100   magic value
845   *  ushort size       number of entries in the table
846   *  int first_key       first (and lowest) switch case value
847   *  int targets[size]     branch targets, relative to switch opcode
848   *
849   * Total size is (4+size*2) 16-bit code units.
850   */
851  uint16_t ident = table[0];
852  const int* targets = reinterpret_cast<const int*>(&table[4]);
853  int entries = table[1];
854  int low_key = s4FromSwitchData(&table[2]);
855  LOG(INFO) << "Packed switch table - ident:0x" << std::hex << ident
856            << ", entries: " << std::dec << entries << ", low_key: " << low_key;
857  for (int i = 0; i < entries; i++) {
858    LOG(INFO) << "  Key[" << (i + low_key) << "] -> 0x" << std::hex
859              << targets[i];
860  }
861}
862
863/*
864 * Set up special LIR to mark a Dalvik byte-code instruction start and
865 * record it in the boundary_map.  NOTE: in cases such as kMirOpCheck in
866 * which we split a single Dalvik instruction, only the first MIR op
867 * associated with a Dalvik PC should be entered into the map.
868 */
869LIR* Mir2Lir::MarkBoundary(int offset, const char* inst_str) {
870  LIR* res = NewLIR1(kPseudoDalvikByteCodeBoundary, reinterpret_cast<uintptr_t>(inst_str));
871  if (boundary_map_.find(offset) == boundary_map_.end()) {
872    boundary_map_.Put(offset, res);
873  }
874  return res;
875}
876
877bool Mir2Lir::EvaluateBranch(Instruction::Code opcode, int32_t src1, int32_t src2) {
878  bool is_taken;
879  switch (opcode) {
880    case Instruction::IF_EQ: is_taken = (src1 == src2); break;
881    case Instruction::IF_NE: is_taken = (src1 != src2); break;
882    case Instruction::IF_LT: is_taken = (src1 < src2); break;
883    case Instruction::IF_GE: is_taken = (src1 >= src2); break;
884    case Instruction::IF_GT: is_taken = (src1 > src2); break;
885    case Instruction::IF_LE: is_taken = (src1 <= src2); break;
886    case Instruction::IF_EQZ: is_taken = (src1 == 0); break;
887    case Instruction::IF_NEZ: is_taken = (src1 != 0); break;
888    case Instruction::IF_LTZ: is_taken = (src1 < 0); break;
889    case Instruction::IF_GEZ: is_taken = (src1 >= 0); break;
890    case Instruction::IF_GTZ: is_taken = (src1 > 0); break;
891    case Instruction::IF_LEZ: is_taken = (src1 <= 0); break;
892    default:
893      LOG(FATAL) << "Unexpected opcode " << opcode;
894      is_taken = false;
895  }
896  return is_taken;
897}
898
899// Convert relation of src1/src2 to src2/src1
900ConditionCode Mir2Lir::FlipComparisonOrder(ConditionCode before) {
901  ConditionCode res;
902  switch (before) {
903    case kCondEq: res = kCondEq; break;
904    case kCondNe: res = kCondNe; break;
905    case kCondLt: res = kCondGt; break;
906    case kCondGt: res = kCondLt; break;
907    case kCondLe: res = kCondGe; break;
908    case kCondGe: res = kCondLe; break;
909    default:
910      res = static_cast<ConditionCode>(0);
911      LOG(FATAL) << "Unexpected ccode " << before;
912  }
913  return res;
914}
915
916// TODO: move to mir_to_lir.cc
917Mir2Lir::Mir2Lir(CompilationUnit* cu, MIRGraph* mir_graph, ArenaAllocator* arena)
918    : Backend(arena),
919      literal_list_(NULL),
920      method_literal_list_(NULL),
921      code_literal_list_(NULL),
922      cu_(cu),
923      mir_graph_(mir_graph),
924      switch_tables_(arena, 4, kGrowableArraySwitchTables),
925      fill_array_data_(arena, 4, kGrowableArrayFillArrayData),
926      throw_launchpads_(arena, 2048, kGrowableArrayThrowLaunchPads),
927      suspend_launchpads_(arena, 4, kGrowableArraySuspendLaunchPads),
928      intrinsic_launchpads_(arena, 2048, kGrowableArrayMisc),
929      data_offset_(0),
930      total_size_(0),
931      block_label_list_(NULL),
932      current_dalvik_offset_(0),
933      reg_pool_(NULL),
934      live_sreg_(0),
935      num_core_spills_(0),
936      num_fp_spills_(0),
937      frame_size_(0),
938      core_spill_mask_(0),
939      fp_spill_mask_(0),
940      first_lir_insn_(NULL),
941      last_lir_insn_(NULL) {
942  promotion_map_ = static_cast<PromotionMap*>
943      (arena_->NewMem((cu_->num_dalvik_registers  + cu_->num_compiler_temps + 1) *
944                      sizeof(promotion_map_[0]), true, ArenaAllocator::kAllocRegAlloc));
945}
946
947void Mir2Lir::Materialize() {
948  CompilerInitializeRegAlloc();  // Needs to happen after SSA naming
949
950  /* Allocate Registers using simple local allocation scheme */
951  SimpleRegAlloc();
952
953  if (mir_graph_->IsSpecialCase()) {
954      /*
955       * Custom codegen for special cases.  If for any reason the
956       * special codegen doesn't succeed, first_lir_insn_ will
957       * set to NULL;
958       */
959      SpecialMIR2LIR(mir_graph_->GetSpecialCase());
960    }
961
962  /* Convert MIR to LIR, etc. */
963  if (first_lir_insn_ == NULL) {
964    MethodMIR2LIR();
965  }
966
967  /* Method is not empty */
968  if (first_lir_insn_) {
969    // mark the targets of switch statement case labels
970    ProcessSwitchTables();
971
972    /* Convert LIR into machine code. */
973    AssembleLIR();
974
975    if (cu_->verbose) {
976      CodegenDump();
977    }
978  }
979}
980
981CompiledMethod* Mir2Lir::GetCompiledMethod() {
982  // Combine vmap tables - core regs, then fp regs - into vmap_table
983  std::vector<uint16_t> vmap_table;
984  // Core regs may have been inserted out of order - sort first
985  std::sort(core_vmap_table_.begin(), core_vmap_table_.end());
986  for (size_t i = 0 ; i < core_vmap_table_.size(); i++) {
987    // Copy, stripping out the phys register sort key
988    vmap_table.push_back(~(-1 << VREG_NUM_WIDTH) & core_vmap_table_[i]);
989  }
990  // If we have a frame, push a marker to take place of lr
991  if (frame_size_ > 0) {
992    vmap_table.push_back(INVALID_VREG);
993  } else {
994    DCHECK_EQ(__builtin_popcount(core_spill_mask_), 0);
995    DCHECK_EQ(__builtin_popcount(fp_spill_mask_), 0);
996  }
997  // Combine vmap tables - core regs, then fp regs. fp regs already sorted
998  for (uint32_t i = 0; i < fp_vmap_table_.size(); i++) {
999    vmap_table.push_back(fp_vmap_table_[i]);
1000  }
1001  CompiledMethod* result =
1002      new CompiledMethod(cu_->instruction_set, code_buffer_,
1003                         frame_size_, core_spill_mask_, fp_spill_mask_,
1004                         combined_mapping_table_, vmap_table, native_gc_map_);
1005  return result;
1006}
1007
1008int Mir2Lir::ComputeFrameSize() {
1009  /* Figure out the frame size */
1010  static const uint32_t kAlignMask = kStackAlignment - 1;
1011  uint32_t size = (num_core_spills_ + num_fp_spills_ +
1012                   1 /* filler word */ + cu_->num_regs + cu_->num_outs +
1013                   cu_->num_compiler_temps + 1 /* cur_method* */)
1014                   * sizeof(uint32_t);
1015  /* Align and set */
1016  return (size + kAlignMask) & ~(kAlignMask);
1017}
1018
1019/*
1020 * Append an LIR instruction to the LIR list maintained by a compilation
1021 * unit
1022 */
1023void Mir2Lir::AppendLIR(LIR* lir) {
1024  if (first_lir_insn_ == NULL) {
1025    DCHECK(last_lir_insn_ == NULL);
1026    last_lir_insn_ = first_lir_insn_ = lir;
1027    lir->prev = lir->next = NULL;
1028  } else {
1029    last_lir_insn_->next = lir;
1030    lir->prev = last_lir_insn_;
1031    lir->next = NULL;
1032    last_lir_insn_ = lir;
1033  }
1034}
1035
1036/*
1037 * Insert an LIR instruction before the current instruction, which cannot be the
1038 * first instruction.
1039 *
1040 * prev_lir <-> new_lir <-> current_lir
1041 */
1042void Mir2Lir::InsertLIRBefore(LIR* current_lir, LIR* new_lir) {
1043  DCHECK(current_lir->prev != NULL);
1044  LIR *prev_lir = current_lir->prev;
1045
1046  prev_lir->next = new_lir;
1047  new_lir->prev = prev_lir;
1048  new_lir->next = current_lir;
1049  current_lir->prev = new_lir;
1050}
1051
1052/*
1053 * Insert an LIR instruction after the current instruction, which cannot be the
1054 * first instruction.
1055 *
1056 * current_lir -> new_lir -> old_next
1057 */
1058void Mir2Lir::InsertLIRAfter(LIR* current_lir, LIR* new_lir) {
1059  new_lir->prev = current_lir;
1060  new_lir->next = current_lir->next;
1061  current_lir->next = new_lir;
1062  new_lir->next->prev = new_lir;
1063}
1064
1065
1066} // namespace art
1067