1 /*
2  * Copyright (C) 2014 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 "code_generator.h"
18 
19 #include "code_generator_arm.h"
20 #include "code_generator_x86.h"
21 #include "code_generator_x86_64.h"
22 #include "dex/verified_method.h"
23 #include "driver/dex_compilation_unit.h"
24 #include "gc_map_builder.h"
25 #include "leb128.h"
26 #include "mapping_table.h"
27 #include "utils/assembler.h"
28 #include "verifier/dex_gc_map.h"
29 #include "vmap_table.h"
30 
31 namespace art {
32 
CompileBaseline(CodeAllocator * allocator,bool is_leaf)33 void CodeGenerator::CompileBaseline(CodeAllocator* allocator, bool is_leaf) {
34   const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
35   DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
36   DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
37   block_labels_.SetSize(blocks.Size());
38 
39   DCHECK_EQ(frame_size_, kUninitializedFrameSize);
40   if (!is_leaf) {
41     MarkNotLeaf();
42   }
43   ComputeFrameSize(GetGraph()->GetMaximumNumberOfOutVRegs()
44                    + GetGraph()->GetNumberOfLocalVRegs()
45                    + GetGraph()->GetNumberOfTemporaries()
46                    + 1 /* filler */);
47   GenerateFrameEntry();
48 
49   for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
50     HBasicBlock* block = blocks.Get(i);
51     Bind(GetLabelOf(block));
52     HGraphVisitor* location_builder = GetLocationBuilder();
53     HGraphVisitor* instruction_visitor = GetInstructionVisitor();
54     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
55       HInstruction* current = it.Current();
56       current->Accept(location_builder);
57       InitLocations(current);
58       current->Accept(instruction_visitor);
59     }
60   }
61   GenerateSlowPaths();
62 
63   size_t code_size = GetAssembler()->CodeSize();
64   uint8_t* buffer = allocator->Allocate(code_size);
65   MemoryRegion code(buffer, code_size);
66   GetAssembler()->FinalizeInstructions(code);
67 }
68 
CompileOptimized(CodeAllocator * allocator)69 void CodeGenerator::CompileOptimized(CodeAllocator* allocator) {
70   // The frame size has already been computed during register allocation.
71   DCHECK_NE(frame_size_, kUninitializedFrameSize);
72   const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
73   DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
74   DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
75   block_labels_.SetSize(blocks.Size());
76 
77   GenerateFrameEntry();
78   for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
79     HBasicBlock* block = blocks.Get(i);
80     Bind(GetLabelOf(block));
81     HGraphVisitor* instruction_visitor = GetInstructionVisitor();
82     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
83       HInstruction* current = it.Current();
84       current->Accept(instruction_visitor);
85     }
86   }
87   GenerateSlowPaths();
88 
89   size_t code_size = GetAssembler()->CodeSize();
90   uint8_t* buffer = allocator->Allocate(code_size);
91   MemoryRegion code(buffer, code_size);
92   GetAssembler()->FinalizeInstructions(code);
93 }
94 
GenerateSlowPaths()95 void CodeGenerator::GenerateSlowPaths() {
96   for (size_t i = 0, e = slow_paths_.Size(); i < e; ++i) {
97     slow_paths_.Get(i)->EmitNativeCode(this);
98   }
99 }
100 
AllocateFreeRegisterInternal(bool * blocked_registers,size_t number_of_registers) const101 size_t CodeGenerator::AllocateFreeRegisterInternal(
102     bool* blocked_registers, size_t number_of_registers) const {
103   for (size_t regno = 0; regno < number_of_registers; regno++) {
104     if (!blocked_registers[regno]) {
105       blocked_registers[regno] = true;
106       return regno;
107     }
108   }
109   return -1;
110 }
111 
ComputeFrameSize(size_t number_of_spill_slots)112 void CodeGenerator::ComputeFrameSize(size_t number_of_spill_slots) {
113   SetFrameSize(RoundUp(
114       number_of_spill_slots * kVRegSize
115       + kVRegSize  // Art method
116       + FrameEntrySpillSize(),
117       kStackAlignment));
118 }
119 
GetTemporaryLocation(HTemporary * temp) const120 Location CodeGenerator::GetTemporaryLocation(HTemporary* temp) const {
121   uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
122   // Use the temporary region (right below the dex registers).
123   int32_t slot = GetFrameSize() - FrameEntrySpillSize()
124                                 - kVRegSize  // filler
125                                 - (number_of_locals * kVRegSize)
126                                 - ((1 + temp->GetIndex()) * kVRegSize);
127   return Location::StackSlot(slot);
128 }
129 
GetStackSlot(HLocal * local) const130 int32_t CodeGenerator::GetStackSlot(HLocal* local) const {
131   uint16_t reg_number = local->GetRegNumber();
132   uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
133   if (reg_number >= number_of_locals) {
134     // Local is a parameter of the method. It is stored in the caller's frame.
135     return GetFrameSize() + kVRegSize  // ART method
136                           + (reg_number - number_of_locals) * kVRegSize;
137   } else {
138     // Local is a temporary in this method. It is stored in this method's frame.
139     return GetFrameSize() - FrameEntrySpillSize()
140                           - kVRegSize  // filler.
141                           - (number_of_locals * kVRegSize)
142                           + (reg_number * kVRegSize);
143   }
144 }
145 
AllocateRegistersLocally(HInstruction * instruction) const146 void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
147   LocationSummary* locations = instruction->GetLocations();
148   if (locations == nullptr) return;
149 
150   for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) {
151     blocked_registers_[i] = false;
152   }
153 
154   // Mark all fixed input, temp and output registers as used.
155   for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
156     Location loc = locations->InAt(i);
157     if (loc.IsRegister()) {
158       // Check that a register is not specified twice in the summary.
159       DCHECK(!blocked_registers_[loc.GetEncoding()]);
160       blocked_registers_[loc.GetEncoding()] = true;
161     }
162   }
163 
164   for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
165     Location loc = locations->GetTemp(i);
166     if (loc.IsRegister()) {
167       // Check that a register is not specified twice in the summary.
168       DCHECK(!blocked_registers_[loc.GetEncoding()]);
169       blocked_registers_[loc.GetEncoding()] = true;
170     }
171   }
172 
173   SetupBlockedRegisters(blocked_registers_);
174 
175   // Allocate all unallocated input locations.
176   for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
177     Location loc = locations->InAt(i);
178     HInstruction* input = instruction->InputAt(i);
179     if (loc.IsUnallocated()) {
180       if (loc.GetPolicy() == Location::kRequiresRegister) {
181         loc = Location::RegisterLocation(
182             AllocateFreeRegister(input->GetType(), blocked_registers_));
183       } else {
184         DCHECK_EQ(loc.GetPolicy(), Location::kAny);
185         HLoadLocal* load = input->AsLoadLocal();
186         if (load != nullptr) {
187           loc = GetStackLocation(load);
188         } else {
189           loc = Location::RegisterLocation(
190               AllocateFreeRegister(input->GetType(), blocked_registers_));
191         }
192       }
193       locations->SetInAt(i, loc);
194     }
195   }
196 
197   // Allocate all unallocated temp locations.
198   for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
199     Location loc = locations->GetTemp(i);
200     if (loc.IsUnallocated()) {
201       DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
202       // TODO: Adjust handling of temps. We currently consider temps to use
203       // core registers. They may also use floating point registers at some point.
204       loc = Location::RegisterLocation(static_cast<ManagedRegister>(
205           AllocateFreeRegister(Primitive::kPrimInt, blocked_registers_)));
206       locations->SetTempAt(i, loc);
207     }
208   }
209   Location result_location = locations->Out();
210   if (result_location.IsUnallocated()) {
211     switch (result_location.GetPolicy()) {
212       case Location::kAny:
213       case Location::kRequiresRegister:
214         result_location = Location::RegisterLocation(
215             AllocateFreeRegister(instruction->GetType(), blocked_registers_));
216         break;
217       case Location::kSameAsFirstInput:
218         result_location = locations->InAt(0);
219         break;
220     }
221     locations->SetOut(result_location);
222   }
223 }
224 
InitLocations(HInstruction * instruction)225 void CodeGenerator::InitLocations(HInstruction* instruction) {
226   if (instruction->GetLocations() == nullptr) {
227     if (instruction->IsTemporary()) {
228       HInstruction* previous = instruction->GetPrevious();
229       Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
230       Move(previous, temp_location, instruction);
231       previous->GetLocations()->SetOut(temp_location);
232     }
233     return;
234   }
235   AllocateRegistersLocally(instruction);
236   for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
237     Location location = instruction->GetLocations()->InAt(i);
238     if (location.IsValid()) {
239       // Move the input to the desired location.
240       Move(instruction->InputAt(i), location, instruction);
241     }
242   }
243 }
244 
GoesToNextBlock(HBasicBlock * current,HBasicBlock * next) const245 bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
246   // We currently iterate over the block in insertion order.
247   return current->GetBlockId() + 1 == next->GetBlockId();
248 }
249 
GetLabelOf(HBasicBlock * block) const250 Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
251   return block_labels_.GetRawStorage() + block->GetBlockId();
252 }
253 
Create(ArenaAllocator * allocator,HGraph * graph,InstructionSet instruction_set)254 CodeGenerator* CodeGenerator::Create(ArenaAllocator* allocator,
255                                      HGraph* graph,
256                                      InstructionSet instruction_set) {
257   switch (instruction_set) {
258     case kArm:
259     case kThumb2: {
260       return new (allocator) arm::CodeGeneratorARM(graph);
261     }
262     case kMips:
263       return nullptr;
264     case kX86: {
265       return new (allocator) x86::CodeGeneratorX86(graph);
266     }
267     case kX86_64: {
268       return new (allocator) x86_64::CodeGeneratorX86_64(graph);
269     }
270     default:
271       return nullptr;
272   }
273 }
274 
BuildNativeGCMap(std::vector<uint8_t> * data,const DexCompilationUnit & dex_compilation_unit) const275 void CodeGenerator::BuildNativeGCMap(
276     std::vector<uint8_t>* data, const DexCompilationUnit& dex_compilation_unit) const {
277   const std::vector<uint8_t>& gc_map_raw =
278       dex_compilation_unit.GetVerifiedMethod()->GetDexGcMap();
279   verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
280 
281   uint32_t max_native_offset = 0;
282   for (size_t i = 0; i < pc_infos_.Size(); i++) {
283     uint32_t native_offset = pc_infos_.Get(i).native_pc;
284     if (native_offset > max_native_offset) {
285       max_native_offset = native_offset;
286     }
287   }
288 
289   GcMapBuilder builder(data, pc_infos_.Size(), max_native_offset, dex_gc_map.RegWidth());
290   for (size_t i = 0; i < pc_infos_.Size(); i++) {
291     struct PcInfo pc_info = pc_infos_.Get(i);
292     uint32_t native_offset = pc_info.native_pc;
293     uint32_t dex_pc = pc_info.dex_pc;
294     const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
295     CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
296     builder.AddEntry(native_offset, references);
297   }
298 }
299 
BuildMappingTable(std::vector<uint8_t> * data) const300 void CodeGenerator::BuildMappingTable(std::vector<uint8_t>* data) const {
301   uint32_t pc2dex_data_size = 0u;
302   uint32_t pc2dex_entries = pc_infos_.Size();
303   uint32_t pc2dex_offset = 0u;
304   int32_t pc2dex_dalvik_offset = 0;
305   uint32_t dex2pc_data_size = 0u;
306   uint32_t dex2pc_entries = 0u;
307 
308   // We currently only have pc2dex entries.
309   for (size_t i = 0; i < pc2dex_entries; i++) {
310     struct PcInfo pc_info = pc_infos_.Get(i);
311     pc2dex_data_size += UnsignedLeb128Size(pc_info.native_pc - pc2dex_offset);
312     pc2dex_data_size += SignedLeb128Size(pc_info.dex_pc - pc2dex_dalvik_offset);
313     pc2dex_offset = pc_info.native_pc;
314     pc2dex_dalvik_offset = pc_info.dex_pc;
315   }
316 
317   uint32_t total_entries = pc2dex_entries + dex2pc_entries;
318   uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
319   uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
320   data->resize(data_size);
321 
322   uint8_t* data_ptr = &(*data)[0];
323   uint8_t* write_pos = data_ptr;
324   write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
325   write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
326   DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size);
327   uint8_t* write_pos2 = write_pos + pc2dex_data_size;
328 
329   pc2dex_offset = 0u;
330   pc2dex_dalvik_offset = 0u;
331   for (size_t i = 0; i < pc2dex_entries; i++) {
332     struct PcInfo pc_info = pc_infos_.Get(i);
333     DCHECK(pc2dex_offset <= pc_info.native_pc);
334     write_pos = EncodeUnsignedLeb128(write_pos, pc_info.native_pc - pc2dex_offset);
335     write_pos = EncodeSignedLeb128(write_pos, pc_info.dex_pc - pc2dex_dalvik_offset);
336     pc2dex_offset = pc_info.native_pc;
337     pc2dex_dalvik_offset = pc_info.dex_pc;
338   }
339   DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size + pc2dex_data_size);
340   DCHECK_EQ(static_cast<size_t>(write_pos2 - data_ptr), data_size);
341 
342   if (kIsDebugBuild) {
343     // Verify the encoded table holds the expected data.
344     MappingTable table(data_ptr);
345     CHECK_EQ(table.TotalSize(), total_entries);
346     CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
347     auto it = table.PcToDexBegin();
348     auto it2 = table.DexToPcBegin();
349     for (size_t i = 0; i < pc2dex_entries; i++) {
350       struct PcInfo pc_info = pc_infos_.Get(i);
351       CHECK_EQ(pc_info.native_pc, it.NativePcOffset());
352       CHECK_EQ(pc_info.dex_pc, it.DexPc());
353       ++it;
354     }
355     CHECK(it == table.PcToDexEnd());
356     CHECK(it2 == table.DexToPcEnd());
357   }
358 }
359 
BuildVMapTable(std::vector<uint8_t> * data) const360 void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const {
361   Leb128EncodingVector vmap_encoder;
362   // We currently don't use callee-saved registers.
363   size_t size = 0 + 1 /* marker */ + 0;
364   vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
365   vmap_encoder.PushBackUnsigned(size);
366   vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
367 
368   *data = vmap_encoder.GetData();
369 }
370 
371 }  // namespace art
372