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