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 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 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 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 101 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 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 120 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 130 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 146 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 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 245 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 250 Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const { 251 return block_labels_.GetRawStorage() + block->GetBlockId(); 252 } 253 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 275 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 300 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 360 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
