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