block_builder.cc revision 92f7f3ce3b01f7c7df1c15b81c900e087248093f
1/* 2 * Copyright (C) 2016 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 "block_builder.h" 18 19#include "bytecode_utils.h" 20#include "quicken_info.h" 21 22namespace art { 23 24HBasicBlock* HBasicBlockBuilder::MaybeCreateBlockAt(uint32_t dex_pc) { 25 return MaybeCreateBlockAt(dex_pc, dex_pc); 26} 27 28HBasicBlock* HBasicBlockBuilder::MaybeCreateBlockAt(uint32_t semantic_dex_pc, 29 uint32_t store_dex_pc) { 30 HBasicBlock* block = branch_targets_[store_dex_pc]; 31 if (block == nullptr) { 32 block = new (allocator_) HBasicBlock(graph_, semantic_dex_pc); 33 branch_targets_[store_dex_pc] = block; 34 } 35 DCHECK_EQ(block->GetDexPc(), semantic_dex_pc); 36 return block; 37} 38 39bool HBasicBlockBuilder::CreateBranchTargets() { 40 // Create the first block for the dex instructions, single successor of the entry block. 41 MaybeCreateBlockAt(0u); 42 43 if (code_item_->tries_size_ != 0) { 44 // Create branch targets at the start/end of the TryItem range. These are 45 // places where the program might fall through into/out of the a block and 46 // where TryBoundary instructions will be inserted later. Other edges which 47 // enter/exit the try blocks are a result of branches/switches. 48 for (size_t idx = 0; idx < code_item_->tries_size_; ++idx) { 49 const DexFile::TryItem* try_item = DexFile::GetTryItems(*code_item_, idx); 50 uint32_t dex_pc_start = try_item->start_addr_; 51 uint32_t dex_pc_end = dex_pc_start + try_item->insn_count_; 52 MaybeCreateBlockAt(dex_pc_start); 53 if (dex_pc_end < code_item_->insns_size_in_code_units_) { 54 // TODO: Do not create block if the last instruction cannot fall through. 55 MaybeCreateBlockAt(dex_pc_end); 56 } else if (dex_pc_end == code_item_->insns_size_in_code_units_) { 57 // The TryItem spans until the very end of the CodeItem and therefore 58 // cannot have any code afterwards. 59 } else { 60 // The TryItem spans beyond the end of the CodeItem. This is invalid code. 61 return false; 62 } 63 } 64 65 // Create branch targets for exception handlers. 66 const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(*code_item_, 0); 67 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 68 for (uint32_t idx = 0; idx < handlers_size; ++idx) { 69 CatchHandlerIterator iterator(handlers_ptr); 70 for (; iterator.HasNext(); iterator.Next()) { 71 MaybeCreateBlockAt(iterator.GetHandlerAddress()); 72 } 73 handlers_ptr = iterator.EndDataPointer(); 74 } 75 } 76 77 // Iterate over all instructions and find branching instructions. Create blocks for 78 // the locations these instructions branch to. 79 IterationRange<DexInstructionIterator> instructions = code_item_->Instructions(); 80 for (const DexInstructionPcPair& pair : instructions) { 81 const uint32_t dex_pc = pair.DexPc(); 82 const Instruction& instruction = pair.Inst(); 83 84 if (instruction.IsBranch()) { 85 number_of_branches_++; 86 MaybeCreateBlockAt(dex_pc + instruction.GetTargetOffset()); 87 } else if (instruction.IsSwitch()) { 88 DexSwitchTable table(instruction, dex_pc); 89 for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) { 90 MaybeCreateBlockAt(dex_pc + s_it.CurrentTargetOffset()); 91 92 // Create N-1 blocks where we will insert comparisons of the input value 93 // against the Switch's case keys. 94 if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) { 95 // Store the block under dex_pc of the current key at the switch data 96 // instruction for uniqueness but give it the dex_pc of the SWITCH 97 // instruction which it semantically belongs to. 98 MaybeCreateBlockAt(dex_pc, s_it.GetDexPcForCurrentIndex()); 99 } 100 } 101 } else if (instruction.Opcode() == Instruction::MOVE_EXCEPTION) { 102 // End the basic block after MOVE_EXCEPTION. This simplifies the later 103 // stage of TryBoundary-block insertion. 104 } else { 105 continue; 106 } 107 108 if (instruction.CanFlowThrough()) { 109 DexInstructionIterator next(std::next(DexInstructionIterator(pair))); 110 if (next == instructions.end()) { 111 // In the normal case we should never hit this but someone can artificially forge a dex 112 // file to fall-through out the method code. In this case we bail out compilation. 113 return false; 114 } 115 MaybeCreateBlockAt(next.DexPc()); 116 } 117 } 118 119 return true; 120} 121 122void HBasicBlockBuilder::ConnectBasicBlocks() { 123 HBasicBlock* block = graph_->GetEntryBlock(); 124 graph_->AddBlock(block); 125 126 size_t quicken_index = 0; 127 bool is_throwing_block = false; 128 // Calculate the qucikening index here instead of CreateBranchTargets since it's easier to 129 // calculate in dex_pc order. 130 for (const DexInstructionPcPair& pair : code_item_->Instructions()) { 131 const uint32_t dex_pc = pair.DexPc(); 132 const Instruction& instruction = pair.Inst(); 133 134 // Check if this dex_pc address starts a new basic block. 135 HBasicBlock* next_block = GetBlockAt(dex_pc); 136 if (next_block != nullptr) { 137 // We only need quicken index entries for basic block boundaries. 138 quicken_index_for_dex_pc_.Put(dex_pc, quicken_index); 139 if (block != nullptr) { 140 // Last instruction did not end its basic block but a new one starts here. 141 // It must have been a block falling through into the next one. 142 block->AddSuccessor(next_block); 143 } 144 block = next_block; 145 is_throwing_block = false; 146 graph_->AddBlock(block); 147 } 148 // Make sure to increment this before the continues. 149 if (QuickenInfoTable::NeedsIndexForInstruction(&instruction)) { 150 ++quicken_index; 151 } 152 153 if (block == nullptr) { 154 // Ignore dead code. 155 continue; 156 } 157 158 if (!is_throwing_block && IsThrowingDexInstruction(instruction)) { 159 DCHECK(!ContainsElement(throwing_blocks_, block)); 160 is_throwing_block = true; 161 throwing_blocks_.push_back(block); 162 } 163 164 if (instruction.IsBranch()) { 165 uint32_t target_dex_pc = dex_pc + instruction.GetTargetOffset(); 166 block->AddSuccessor(GetBlockAt(target_dex_pc)); 167 } else if (instruction.IsReturn() || (instruction.Opcode() == Instruction::THROW)) { 168 block->AddSuccessor(graph_->GetExitBlock()); 169 } else if (instruction.IsSwitch()) { 170 DexSwitchTable table(instruction, dex_pc); 171 for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) { 172 uint32_t target_dex_pc = dex_pc + s_it.CurrentTargetOffset(); 173 block->AddSuccessor(GetBlockAt(target_dex_pc)); 174 175 if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) { 176 uint32_t next_case_dex_pc = s_it.GetDexPcForCurrentIndex(); 177 HBasicBlock* next_case_block = GetBlockAt(next_case_dex_pc); 178 block->AddSuccessor(next_case_block); 179 block = next_case_block; 180 graph_->AddBlock(block); 181 } 182 } 183 } else { 184 // Remaining code only applies to instructions which end their basic block. 185 continue; 186 } 187 188 // Go to the next instruction in case we read dex PC below. 189 if (instruction.CanFlowThrough()) { 190 block->AddSuccessor(GetBlockAt(std::next(DexInstructionIterator(pair)).DexPc())); 191 } 192 193 // The basic block ends here. Do not add any more instructions. 194 block = nullptr; 195 } 196 197 graph_->AddBlock(graph_->GetExitBlock()); 198} 199 200// Returns the TryItem stored for `block` or nullptr if there is no info for it. 201static const DexFile::TryItem* GetTryItem( 202 HBasicBlock* block, 203 const ScopedArenaSafeMap<uint32_t, const DexFile::TryItem*>& try_block_info) { 204 auto iterator = try_block_info.find(block->GetBlockId()); 205 return (iterator == try_block_info.end()) ? nullptr : iterator->second; 206} 207 208// Iterates over the exception handlers of `try_item`, finds the corresponding 209// catch blocks and makes them successors of `try_boundary`. The order of 210// successors matches the order in which runtime exception delivery searches 211// for a handler. 212static void LinkToCatchBlocks(HTryBoundary* try_boundary, 213 const DexFile::CodeItem& code_item, 214 const DexFile::TryItem* try_item, 215 const ScopedArenaSafeMap<uint32_t, HBasicBlock*>& catch_blocks) { 216 for (CatchHandlerIterator it(code_item, *try_item); it.HasNext(); it.Next()) { 217 try_boundary->AddExceptionHandler(catch_blocks.Get(it.GetHandlerAddress())); 218 } 219} 220 221bool HBasicBlockBuilder::MightHaveLiveNormalPredecessors(HBasicBlock* catch_block) { 222 if (kIsDebugBuild) { 223 DCHECK_NE(catch_block->GetDexPc(), kNoDexPc) << "Should not be called on synthetic blocks"; 224 DCHECK(!graph_->GetEntryBlock()->GetSuccessors().empty()) 225 << "Basic blocks must have been created and connected"; 226 for (HBasicBlock* predecessor : catch_block->GetPredecessors()) { 227 DCHECK(!predecessor->IsSingleTryBoundary()) 228 << "TryBoundary blocks must not have not been created yet"; 229 } 230 } 231 232 const Instruction& first = code_item_->InstructionAt(catch_block->GetDexPc()); 233 if (first.Opcode() == Instruction::MOVE_EXCEPTION) { 234 // Verifier guarantees that if a catch block begins with MOVE_EXCEPTION then 235 // it has no live normal predecessors. 236 return false; 237 } else if (catch_block->GetPredecessors().empty()) { 238 // Normal control-flow edges have already been created. Since block's list of 239 // predecessors is empty, it cannot have any live or dead normal predecessors. 240 return false; 241 } 242 243 // The catch block has normal predecessors but we do not know which are live 244 // and which will be removed during the initial DCE. Return `true` to signal 245 // that it may have live normal predecessors. 246 return true; 247} 248 249void HBasicBlockBuilder::InsertTryBoundaryBlocks() { 250 if (code_item_->tries_size_ == 0) { 251 return; 252 } 253 254 // Keep a map of all try blocks and their respective TryItems. We do not use 255 // the block's pointer but rather its id to ensure deterministic iteration. 256 ScopedArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info( 257 std::less<uint32_t>(), local_allocator_->Adapter(kArenaAllocGraphBuilder)); 258 259 // Obtain TryItem information for blocks with throwing instructions, and split 260 // blocks which are both try & catch to simplify the graph. 261 for (HBasicBlock* block : graph_->GetBlocks()) { 262 if (block->GetDexPc() == kNoDexPc) { 263 continue; 264 } 265 266 // Do not bother creating exceptional edges for try blocks which have no 267 // throwing instructions. In that case we simply assume that the block is 268 // not covered by a TryItem. This prevents us from creating a throw-catch 269 // loop for synchronized blocks. 270 if (ContainsElement(throwing_blocks_, block)) { 271 // Try to find a TryItem covering the block. 272 const int32_t try_item_idx = DexFile::FindTryItem(DexFile::GetTryItems(*code_item_, 0u), 273 code_item_->tries_size_, 274 block->GetDexPc()); 275 if (try_item_idx != -1) { 276 // Block throwing and in a TryItem. Store the try block information. 277 try_block_info.Put(block->GetBlockId(), DexFile::GetTryItems(*code_item_, try_item_idx)); 278 } 279 } 280 } 281 282 // Map from a handler dex_pc to the corresponding catch block. 283 ScopedArenaSafeMap<uint32_t, HBasicBlock*> catch_blocks( 284 std::less<uint32_t>(), local_allocator_->Adapter(kArenaAllocGraphBuilder)); 285 286 // Iterate over catch blocks, create artifical landing pads if necessary to 287 // simplify the CFG, and set metadata. 288 const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(*code_item_, 0); 289 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 290 for (uint32_t idx = 0; idx < handlers_size; ++idx) { 291 CatchHandlerIterator iterator(handlers_ptr); 292 for (; iterator.HasNext(); iterator.Next()) { 293 uint32_t address = iterator.GetHandlerAddress(); 294 if (catch_blocks.find(address) != catch_blocks.end()) { 295 // Catch block already processed. 296 continue; 297 } 298 299 // Check if we should create an artifical landing pad for the catch block. 300 // We create one if the catch block is also a try block because we do not 301 // have a strategy for inserting TryBoundaries on exceptional edges. 302 // We also create one if the block might have normal predecessors so as to 303 // simplify register allocation. 304 HBasicBlock* catch_block = GetBlockAt(address); 305 bool is_try_block = (try_block_info.find(catch_block->GetBlockId()) != try_block_info.end()); 306 if (is_try_block || MightHaveLiveNormalPredecessors(catch_block)) { 307 HBasicBlock* new_catch_block = new (allocator_) HBasicBlock(graph_, address); 308 new_catch_block->AddInstruction(new (allocator_) HGoto(address)); 309 new_catch_block->AddSuccessor(catch_block); 310 graph_->AddBlock(new_catch_block); 311 catch_block = new_catch_block; 312 } 313 314 catch_blocks.Put(address, catch_block); 315 catch_block->SetTryCatchInformation( 316 new (allocator_) TryCatchInformation(iterator.GetHandlerTypeIndex(), *dex_file_)); 317 } 318 handlers_ptr = iterator.EndDataPointer(); 319 } 320 321 // Do a pass over the try blocks and insert entering TryBoundaries where at 322 // least one predecessor is not covered by the same TryItem as the try block. 323 // We do not split each edge separately, but rather create one boundary block 324 // that all predecessors are relinked to. This preserves loop headers (b/23895756). 325 for (const auto& entry : try_block_info) { 326 uint32_t block_id = entry.first; 327 const DexFile::TryItem* try_item = entry.second; 328 HBasicBlock* try_block = graph_->GetBlocks()[block_id]; 329 for (HBasicBlock* predecessor : try_block->GetPredecessors()) { 330 if (GetTryItem(predecessor, try_block_info) != try_item) { 331 // Found a predecessor not covered by the same TryItem. Insert entering 332 // boundary block. 333 HTryBoundary* try_entry = new (allocator_) HTryBoundary( 334 HTryBoundary::BoundaryKind::kEntry, try_block->GetDexPc()); 335 try_block->CreateImmediateDominator()->AddInstruction(try_entry); 336 LinkToCatchBlocks(try_entry, *code_item_, try_item, catch_blocks); 337 break; 338 } 339 } 340 } 341 342 // Do a second pass over the try blocks and insert exit TryBoundaries where 343 // the successor is not in the same TryItem. 344 for (const auto& entry : try_block_info) { 345 uint32_t block_id = entry.first; 346 const DexFile::TryItem* try_item = entry.second; 347 HBasicBlock* try_block = graph_->GetBlocks()[block_id]; 348 // NOTE: Do not use iterators because SplitEdge would invalidate them. 349 for (size_t i = 0, e = try_block->GetSuccessors().size(); i < e; ++i) { 350 HBasicBlock* successor = try_block->GetSuccessors()[i]; 351 352 // If the successor is a try block, all of its predecessors must be 353 // covered by the same TryItem. Otherwise the previous pass would have 354 // created a non-throwing boundary block. 355 if (GetTryItem(successor, try_block_info) != nullptr) { 356 DCHECK_EQ(try_item, GetTryItem(successor, try_block_info)); 357 continue; 358 } 359 360 // Insert TryBoundary and link to catch blocks. 361 HTryBoundary* try_exit = 362 new (allocator_) HTryBoundary(HTryBoundary::BoundaryKind::kExit, successor->GetDexPc()); 363 graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit); 364 LinkToCatchBlocks(try_exit, *code_item_, try_item, catch_blocks); 365 } 366 } 367} 368 369bool HBasicBlockBuilder::Build() { 370 DCHECK(code_item_ != nullptr); 371 DCHECK(graph_->GetBlocks().empty()); 372 373 graph_->SetEntryBlock(new (allocator_) HBasicBlock(graph_, kNoDexPc)); 374 graph_->SetExitBlock(new (allocator_) HBasicBlock(graph_, kNoDexPc)); 375 376 // TODO(dbrazdil): Do CreateBranchTargets and ConnectBasicBlocks in one pass. 377 if (!CreateBranchTargets()) { 378 return false; 379 } 380 381 ConnectBasicBlocks(); 382 InsertTryBoundaryBlocks(); 383 384 return true; 385} 386 387void HBasicBlockBuilder::BuildIntrinsic() { 388 DCHECK(code_item_ == nullptr); 389 DCHECK(graph_->GetBlocks().empty()); 390 391 // Create blocks. 392 HBasicBlock* entry_block = new (allocator_) HBasicBlock(graph_, kNoDexPc); 393 HBasicBlock* exit_block = new (allocator_) HBasicBlock(graph_, kNoDexPc); 394 HBasicBlock* body = MaybeCreateBlockAt(/* semantic_dex_pc */ kNoDexPc, /* store_dex_pc */ 0u); 395 396 // Add blocks to the graph. 397 graph_->AddBlock(entry_block); 398 graph_->AddBlock(body); 399 graph_->AddBlock(exit_block); 400 graph_->SetEntryBlock(entry_block); 401 graph_->SetExitBlock(exit_block); 402 403 // Connect blocks. 404 entry_block->AddSuccessor(body); 405 body->AddSuccessor(exit_block); 406} 407 408size_t HBasicBlockBuilder::GetQuickenIndex(uint32_t dex_pc) const { 409 return quicken_index_for_dex_pc_.Get(dex_pc); 410} 411 412} // namespace art 413