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