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 22 namespace art { 23 24 HBasicBlock* HBasicBlockBuilder::MaybeCreateBlockAt(uint32_t dex_pc) { 25 return MaybeCreateBlockAt(dex_pc, dex_pc); 26 } 27 28 HBasicBlock* 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 (arena_) 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 39 bool 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 for (CodeItemIterator it(code_item_); !it.Done(); it.Advance()) { 80 uint32_t dex_pc = it.CurrentDexPc(); 81 const Instruction& instruction = it.CurrentInstruction(); 82 83 if (instruction.IsBranch()) { 84 number_of_branches_++; 85 MaybeCreateBlockAt(dex_pc + instruction.GetTargetOffset()); 86 } else if (instruction.IsSwitch()) { 87 DexSwitchTable table(instruction, dex_pc); 88 for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) { 89 MaybeCreateBlockAt(dex_pc + s_it.CurrentTargetOffset()); 90 91 // Create N-1 blocks where we will insert comparisons of the input value 92 // against the Switch's case keys. 93 if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) { 94 // Store the block under dex_pc of the current key at the switch data 95 // instruction for uniqueness but give it the dex_pc of the SWITCH 96 // instruction which it semantically belongs to. 97 MaybeCreateBlockAt(dex_pc, s_it.GetDexPcForCurrentIndex()); 98 } 99 } 100 } else if (instruction.Opcode() == Instruction::MOVE_EXCEPTION) { 101 // End the basic block after MOVE_EXCEPTION. This simplifies the later 102 // stage of TryBoundary-block insertion. 103 } else { 104 continue; 105 } 106 107 if (instruction.CanFlowThrough()) { 108 if (it.IsLast()) { 109 // In the normal case we should never hit this but someone can artificially forge a dex 110 // file to fall-through out the method code. In this case we bail out compilation. 111 return false; 112 } else { 113 MaybeCreateBlockAt(dex_pc + it.CurrentInstruction().SizeInCodeUnits()); 114 } 115 } 116 } 117 118 return true; 119 } 120 121 void HBasicBlockBuilder::ConnectBasicBlocks() { 122 HBasicBlock* block = graph_->GetEntryBlock(); 123 graph_->AddBlock(block); 124 125 size_t quicken_index = 0; 126 bool is_throwing_block = false; 127 // Calculate the qucikening index here instead of CreateBranchTargets since it's easier to 128 // calculate in dex_pc order. 129 for (CodeItemIterator it(code_item_); !it.Done(); it.Advance()) { 130 uint32_t dex_pc = it.CurrentDexPc(); 131 132 // Check if this dex_pc address starts a new basic block. 133 HBasicBlock* next_block = GetBlockAt(dex_pc); 134 if (next_block != nullptr) { 135 // We only need quicken index entries for basic block boundaries. 136 quicken_index_for_dex_pc_.Put(dex_pc, quicken_index); 137 if (block != nullptr) { 138 // Last instruction did not end its basic block but a new one starts here. 139 // It must have been a block falling through into the next one. 140 block->AddSuccessor(next_block); 141 } 142 block = next_block; 143 is_throwing_block = false; 144 graph_->AddBlock(block); 145 } 146 // Make sure to increment this before the continues. 147 if (QuickenInfoTable::NeedsIndexForInstruction(&it.CurrentInstruction())) { 148 ++quicken_index; 149 } 150 151 if (block == nullptr) { 152 // Ignore dead code. 153 continue; 154 } 155 156 const Instruction& instruction = it.CurrentInstruction(); 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 if (instruction.CanFlowThrough()) { 189 uint32_t next_dex_pc = dex_pc + instruction.SizeInCodeUnits(); 190 block->AddSuccessor(GetBlockAt(next_dex_pc)); 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. 201 static const DexFile::TryItem* GetTryItem( 202 HBasicBlock* block, 203 const ArenaSafeMap<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. 212 static void LinkToCatchBlocks(HTryBoundary* try_boundary, 213 const DexFile::CodeItem& code_item, 214 const DexFile::TryItem* try_item, 215 const ArenaSafeMap<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 221 bool 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 = GetDexInstructionAt(code_item_, 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 249 void 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 ArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info( 257 std::less<uint32_t>(), arena_->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(code_item_, block->GetDexPc()); 273 if (try_item_idx != -1) { 274 // Block throwing and in a TryItem. Store the try block information. 275 try_block_info.Put(block->GetBlockId(), DexFile::GetTryItems(code_item_, try_item_idx)); 276 } 277 } 278 } 279 280 // Map from a handler dex_pc to the corresponding catch block. 281 ArenaSafeMap<uint32_t, HBasicBlock*> catch_blocks( 282 std::less<uint32_t>(), arena_->Adapter(kArenaAllocGraphBuilder)); 283 284 // Iterate over catch blocks, create artifical landing pads if necessary to 285 // simplify the CFG, and set metadata. 286 const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item_, 0); 287 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 288 for (uint32_t idx = 0; idx < handlers_size; ++idx) { 289 CatchHandlerIterator iterator(handlers_ptr); 290 for (; iterator.HasNext(); iterator.Next()) { 291 uint32_t address = iterator.GetHandlerAddress(); 292 if (catch_blocks.find(address) != catch_blocks.end()) { 293 // Catch block already processed. 294 continue; 295 } 296 297 // Check if we should create an artifical landing pad for the catch block. 298 // We create one if the catch block is also a try block because we do not 299 // have a strategy for inserting TryBoundaries on exceptional edges. 300 // We also create one if the block might have normal predecessors so as to 301 // simplify register allocation. 302 HBasicBlock* catch_block = GetBlockAt(address); 303 bool is_try_block = (try_block_info.find(catch_block->GetBlockId()) != try_block_info.end()); 304 if (is_try_block || MightHaveLiveNormalPredecessors(catch_block)) { 305 HBasicBlock* new_catch_block = new (arena_) HBasicBlock(graph_, address); 306 new_catch_block->AddInstruction(new (arena_) HGoto(address)); 307 new_catch_block->AddSuccessor(catch_block); 308 graph_->AddBlock(new_catch_block); 309 catch_block = new_catch_block; 310 } 311 312 catch_blocks.Put(address, catch_block); 313 catch_block->SetTryCatchInformation( 314 new (arena_) TryCatchInformation(iterator.GetHandlerTypeIndex(), *dex_file_)); 315 } 316 handlers_ptr = iterator.EndDataPointer(); 317 } 318 319 // Do a pass over the try blocks and insert entering TryBoundaries where at 320 // least one predecessor is not covered by the same TryItem as the try block. 321 // We do not split each edge separately, but rather create one boundary block 322 // that all predecessors are relinked to. This preserves loop headers (b/23895756). 323 for (const auto& entry : try_block_info) { 324 uint32_t block_id = entry.first; 325 const DexFile::TryItem* try_item = entry.second; 326 HBasicBlock* try_block = graph_->GetBlocks()[block_id]; 327 for (HBasicBlock* predecessor : try_block->GetPredecessors()) { 328 if (GetTryItem(predecessor, try_block_info) != try_item) { 329 // Found a predecessor not covered by the same TryItem. Insert entering 330 // boundary block. 331 HTryBoundary* try_entry = 332 new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kEntry, try_block->GetDexPc()); 333 try_block->CreateImmediateDominator()->AddInstruction(try_entry); 334 LinkToCatchBlocks(try_entry, code_item_, try_item, catch_blocks); 335 break; 336 } 337 } 338 } 339 340 // Do a second pass over the try blocks and insert exit TryBoundaries where 341 // the successor is not in the same TryItem. 342 for (const auto& entry : try_block_info) { 343 uint32_t block_id = entry.first; 344 const DexFile::TryItem* try_item = entry.second; 345 HBasicBlock* try_block = graph_->GetBlocks()[block_id]; 346 // NOTE: Do not use iterators because SplitEdge would invalidate them. 347 for (size_t i = 0, e = try_block->GetSuccessors().size(); i < e; ++i) { 348 HBasicBlock* successor = try_block->GetSuccessors()[i]; 349 350 // If the successor is a try block, all of its predecessors must be 351 // covered by the same TryItem. Otherwise the previous pass would have 352 // created a non-throwing boundary block. 353 if (GetTryItem(successor, try_block_info) != nullptr) { 354 DCHECK_EQ(try_item, GetTryItem(successor, try_block_info)); 355 continue; 356 } 357 358 // Insert TryBoundary and link to catch blocks. 359 HTryBoundary* try_exit = 360 new (arena_) HTryBoundary(HTryBoundary::BoundaryKind::kExit, successor->GetDexPc()); 361 graph_->SplitEdge(try_block, successor)->AddInstruction(try_exit); 362 LinkToCatchBlocks(try_exit, code_item_, try_item, catch_blocks); 363 } 364 } 365 } 366 367 bool HBasicBlockBuilder::Build() { 368 DCHECK(graph_->GetBlocks().empty()); 369 370 graph_->SetEntryBlock(new (arena_) HBasicBlock(graph_, kNoDexPc)); 371 graph_->SetExitBlock(new (arena_) HBasicBlock(graph_, kNoDexPc)); 372 373 // TODO(dbrazdil): Do CreateBranchTargets and ConnectBasicBlocks in one pass. 374 if (!CreateBranchTargets()) { 375 return false; 376 } 377 378 ConnectBasicBlocks(); 379 InsertTryBoundaryBlocks(); 380 381 return true; 382 } 383 384 size_t HBasicBlockBuilder::GetQuickenIndex(uint32_t dex_pc) const { 385 return quicken_index_for_dex_pc_.Get(dex_pc); 386 } 387 388 } // namespace art 389