1 /* 2 * Copyright (C) 2017 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 "superblock_cloner.h" 18 19 #include "common_dominator.h" 20 #include "graph_checker.h" 21 22 #include <iostream> 23 24 namespace art { 25 26 using HBasicBlockMap = SuperblockCloner::HBasicBlockMap; 27 using HInstructionMap = SuperblockCloner::HInstructionMap; 28 using HBasicBlockSet = SuperblockCloner::HBasicBlockSet; 29 using HEdgeSet = SuperblockCloner::HEdgeSet; 30 31 void HEdge::Dump(std::ostream& stream) const { 32 stream << "(" << from_ << "->" << to_ << ")"; 33 } 34 35 // 36 // Static helper methods. 37 // 38 39 // Returns whether instruction has any uses (regular or environmental) outside the region, 40 // defined by basic block set. 41 static bool IsUsedOutsideRegion(const HInstruction* instr, const HBasicBlockSet& bb_set) { 42 auto& uses = instr->GetUses(); 43 for (auto use_node = uses.begin(), e = uses.end(); use_node != e; ++use_node) { 44 HInstruction* user = use_node->GetUser(); 45 if (!bb_set.IsBitSet(user->GetBlock()->GetBlockId())) { 46 return true; 47 } 48 } 49 50 auto& env_uses = instr->GetEnvUses(); 51 for (auto use_node = env_uses.begin(), e = env_uses.end(); use_node != e; ++use_node) { 52 HInstruction* user = use_node->GetUser()->GetHolder(); 53 if (!bb_set.IsBitSet(user->GetBlock()->GetBlockId())) { 54 return true; 55 } 56 } 57 58 return false; 59 } 60 61 // Returns whether the phi's inputs are the same HInstruction. 62 static bool ArePhiInputsTheSame(const HPhi* phi) { 63 HInstruction* first_input = phi->InputAt(0); 64 for (size_t i = 1, e = phi->InputCount(); i < e; i++) { 65 if (phi->InputAt(i) != first_input) { 66 return false; 67 } 68 } 69 70 return true; 71 } 72 73 // Returns a common predecessor of loop1 and loop2 in the loop tree or nullptr if it is the whole 74 // graph. 75 static HLoopInformation* FindCommonLoop(HLoopInformation* loop1, HLoopInformation* loop2) { 76 if (loop1 != nullptr || loop2 != nullptr) { 77 return nullptr; 78 } 79 80 if (loop1->IsIn(*loop2)) { 81 return loop2; 82 } else if (loop2->IsIn(*loop1)) { 83 return loop1; 84 } 85 HBasicBlock* block = CommonDominator::ForPair(loop1->GetHeader(), loop2->GetHeader()); 86 return block->GetLoopInformation(); 87 } 88 89 // Calls HGraph::OrderLoopHeaderPredecessors for each loop in the graph. 90 static void OrderLoopsHeadersPredecessors(HGraph* graph) { 91 for (HBasicBlock* block : graph->GetPostOrder()) { 92 if (block->IsLoopHeader()) { 93 graph->OrderLoopHeaderPredecessors(block); 94 } 95 } 96 } 97 98 // 99 // Helpers for CloneBasicBlock. 100 // 101 102 void SuperblockCloner::ReplaceInputsWithCopies(HInstruction* copy_instr) { 103 DCHECK(!copy_instr->IsPhi()); 104 for (size_t i = 0, e = copy_instr->InputCount(); i < e; i++) { 105 // Copy instruction holds the same input as the original instruction holds. 106 HInstruction* orig_input = copy_instr->InputAt(i); 107 if (!IsInOrigBBSet(orig_input->GetBlock())) { 108 // Defined outside the subgraph. 109 continue; 110 } 111 HInstruction* copy_input = GetInstrCopy(orig_input); 112 // copy_instr will be registered as a user of copy_inputs after returning from this function: 113 // 'copy_block->AddInstruction(copy_instr)'. 114 copy_instr->SetRawInputAt(i, copy_input); 115 } 116 } 117 118 void SuperblockCloner::DeepCloneEnvironmentWithRemapping(HInstruction* copy_instr, 119 const HEnvironment* orig_env) { 120 if (orig_env->GetParent() != nullptr) { 121 DeepCloneEnvironmentWithRemapping(copy_instr, orig_env->GetParent()); 122 } 123 HEnvironment* copy_env = new (arena_) HEnvironment(arena_, *orig_env, copy_instr); 124 125 for (size_t i = 0; i < orig_env->Size(); i++) { 126 HInstruction* env_input = orig_env->GetInstructionAt(i); 127 if (env_input != nullptr && IsInOrigBBSet(env_input->GetBlock())) { 128 env_input = GetInstrCopy(env_input); 129 DCHECK(env_input != nullptr && env_input->GetBlock() != nullptr); 130 } 131 copy_env->SetRawEnvAt(i, env_input); 132 if (env_input != nullptr) { 133 env_input->AddEnvUseAt(copy_env, i); 134 } 135 } 136 // InsertRawEnvironment assumes that instruction already has an environment that's why we use 137 // SetRawEnvironment in the 'else' case. 138 // As this function calls itself recursively with the same copy_instr - this copy_instr may 139 // have partially copied chain of HEnvironments. 140 if (copy_instr->HasEnvironment()) { 141 copy_instr->InsertRawEnvironment(copy_env); 142 } else { 143 copy_instr->SetRawEnvironment(copy_env); 144 } 145 } 146 147 // 148 // Helpers for RemapEdgesSuccessors. 149 // 150 151 void SuperblockCloner::RemapOrigInternalOrIncomingEdge(HBasicBlock* orig_block, 152 HBasicBlock* orig_succ) { 153 DCHECK(IsInOrigBBSet(orig_succ)); 154 HBasicBlock* copy_succ = GetBlockCopy(orig_succ); 155 156 size_t this_index = orig_succ->GetPredecessorIndexOf(orig_block); 157 size_t phi_input_count = 0; 158 // This flag reflects whether the original successor has at least one phi and this phi 159 // has been already processed in the loop. Used for validation purposes in DCHECK to check that 160 // in the end all of the phis in the copy successor have the same number of inputs - the number 161 // of copy successor's predecessors. 162 bool first_phi_met = false; 163 for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 164 HPhi* orig_phi = it.Current()->AsPhi(); 165 HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 166 HInstruction* orig_phi_input = orig_phi->InputAt(this_index); 167 // Remove corresponding input for original phi. 168 orig_phi->RemoveInputAt(this_index); 169 // Copy phi doesn't yet have either orig_block as predecessor or the input that corresponds 170 // to orig_block, so add the input at the end of the list. 171 copy_phi->AddInput(orig_phi_input); 172 if (!first_phi_met) { 173 phi_input_count = copy_phi->InputCount(); 174 first_phi_met = true; 175 } else { 176 DCHECK_EQ(phi_input_count, copy_phi->InputCount()); 177 } 178 } 179 // orig_block will be put at the end of the copy_succ's predecessors list; that corresponds 180 // to the previously added phi inputs position. 181 orig_block->ReplaceSuccessor(orig_succ, copy_succ); 182 DCHECK(!first_phi_met || copy_succ->GetPredecessors().size() == phi_input_count); 183 } 184 185 void SuperblockCloner::AddCopyInternalEdge(HBasicBlock* orig_block, 186 HBasicBlock* orig_succ) { 187 DCHECK(IsInOrigBBSet(orig_succ)); 188 HBasicBlock* copy_block = GetBlockCopy(orig_block); 189 HBasicBlock* copy_succ = GetBlockCopy(orig_succ); 190 copy_block->AddSuccessor(copy_succ); 191 192 size_t orig_index = orig_succ->GetPredecessorIndexOf(orig_block); 193 for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 194 HPhi* orig_phi = it.Current()->AsPhi(); 195 HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 196 HInstruction* orig_phi_input = orig_phi->InputAt(orig_index); 197 copy_phi->AddInput(orig_phi_input); 198 } 199 } 200 201 void SuperblockCloner::RemapCopyInternalEdge(HBasicBlock* orig_block, 202 HBasicBlock* orig_succ) { 203 DCHECK(IsInOrigBBSet(orig_succ)); 204 HBasicBlock* copy_block = GetBlockCopy(orig_block); 205 copy_block->AddSuccessor(orig_succ); 206 DCHECK(copy_block->HasSuccessor(orig_succ)); 207 208 size_t orig_index = orig_succ->GetPredecessorIndexOf(orig_block); 209 for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 210 HPhi* orig_phi = it.Current()->AsPhi(); 211 HInstruction* orig_phi_input = orig_phi->InputAt(orig_index); 212 orig_phi->AddInput(orig_phi_input); 213 } 214 } 215 216 // 217 // Local versions of CF calculation/adjustment routines. 218 // 219 220 // TODO: merge with the original version in nodes.cc. The concern is that we don't want to affect 221 // the performance of the base version by checking the local set. 222 // TODO: this version works when updating the back edges info for natural loop-based local_set. 223 // Check which exactly types of subgraphs can be analysed or rename it to 224 // FindBackEdgesInTheNaturalLoop. 225 void SuperblockCloner::FindBackEdgesLocal(HBasicBlock* entry_block, ArenaBitVector* local_set) { 226 ArenaBitVector visited(arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 227 // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks. 228 DCHECK_EQ(visited.GetHighestBitSet(), -1); 229 230 // Nodes that we're currently visiting, indexed by block id. 231 ArenaBitVector visiting(arena_, graph_->GetBlocks().size(), false, kArenaAllocGraphBuilder); 232 // Number of successors visited from a given node, indexed by block id. 233 ArenaVector<size_t> successors_visited(graph_->GetBlocks().size(), 234 0u, 235 arena_->Adapter(kArenaAllocGraphBuilder)); 236 // Stack of nodes that we're currently visiting (same as marked in "visiting" above). 237 ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder)); 238 constexpr size_t kDefaultWorklistSize = 8; 239 worklist.reserve(kDefaultWorklistSize); 240 241 visited.SetBit(entry_block->GetBlockId()); 242 visiting.SetBit(entry_block->GetBlockId()); 243 worklist.push_back(entry_block); 244 245 while (!worklist.empty()) { 246 HBasicBlock* current = worklist.back(); 247 uint32_t current_id = current->GetBlockId(); 248 if (successors_visited[current_id] == current->GetSuccessors().size()) { 249 visiting.ClearBit(current_id); 250 worklist.pop_back(); 251 } else { 252 HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 253 uint32_t successor_id = successor->GetBlockId(); 254 if (!local_set->IsBitSet(successor_id)) { 255 continue; 256 } 257 258 if (visiting.IsBitSet(successor_id)) { 259 DCHECK(ContainsElement(worklist, successor)); 260 successor->AddBackEdgeWhileUpdating(current); 261 } else if (!visited.IsBitSet(successor_id)) { 262 visited.SetBit(successor_id); 263 visiting.SetBit(successor_id); 264 worklist.push_back(successor); 265 } 266 } 267 } 268 } 269 270 void SuperblockCloner::RecalculateBackEdgesInfo(ArenaBitVector* outer_loop_bb_set) { 271 // TODO: DCHECK that after the transformation the graph is connected. 272 HBasicBlock* block_entry = nullptr; 273 274 if (outer_loop_ == nullptr) { 275 for (auto block : graph_->GetBlocks()) { 276 if (block != nullptr) { 277 outer_loop_bb_set->SetBit(block->GetBlockId()); 278 HLoopInformation* info = block->GetLoopInformation(); 279 if (info != nullptr) { 280 info->ResetBasicBlockData(); 281 } 282 } 283 } 284 block_entry = graph_->GetEntryBlock(); 285 } else { 286 outer_loop_bb_set->Copy(&outer_loop_bb_set_); 287 block_entry = outer_loop_->GetHeader(); 288 289 // Add newly created copy blocks. 290 for (auto entry : *bb_map_) { 291 outer_loop_bb_set->SetBit(entry.second->GetBlockId()); 292 } 293 294 // Clear loop_info for the whole outer loop. 295 for (uint32_t idx : outer_loop_bb_set->Indexes()) { 296 HBasicBlock* block = GetBlockById(idx); 297 HLoopInformation* info = block->GetLoopInformation(); 298 if (info != nullptr) { 299 info->ResetBasicBlockData(); 300 } 301 } 302 } 303 304 FindBackEdgesLocal(block_entry, outer_loop_bb_set); 305 306 for (uint32_t idx : outer_loop_bb_set->Indexes()) { 307 HBasicBlock* block = GetBlockById(idx); 308 HLoopInformation* info = block->GetLoopInformation(); 309 // Reset LoopInformation for regular blocks and old headers which are no longer loop headers. 310 if (info != nullptr && 311 (info->GetHeader() != block || info->NumberOfBackEdges() == 0)) { 312 block->SetLoopInformation(nullptr); 313 } 314 } 315 } 316 317 // This is a modified version of HGraph::AnalyzeLoops. 318 GraphAnalysisResult SuperblockCloner::AnalyzeLoopsLocally(ArenaBitVector* outer_loop_bb_set) { 319 // We iterate post order to ensure we visit inner loops before outer loops. 320 // `PopulateRecursive` needs this guarantee to know whether a natural loop 321 // contains an irreducible loop. 322 for (HBasicBlock* block : graph_->GetPostOrder()) { 323 if (!outer_loop_bb_set->IsBitSet(block->GetBlockId())) { 324 continue; 325 } 326 if (block->IsLoopHeader()) { 327 if (block->IsCatchBlock()) { 328 // TODO: Dealing with exceptional back edges could be tricky because 329 // they only approximate the real control flow. Bail out for now. 330 return kAnalysisFailThrowCatchLoop; 331 } 332 block->GetLoopInformation()->Populate(); 333 } 334 } 335 336 for (HBasicBlock* block : graph_->GetPostOrder()) { 337 if (!outer_loop_bb_set->IsBitSet(block->GetBlockId())) { 338 continue; 339 } 340 if (block->IsLoopHeader()) { 341 HLoopInformation* cur_loop = block->GetLoopInformation(); 342 HLoopInformation* outer_loop = cur_loop->GetPreHeader()->GetLoopInformation(); 343 if (outer_loop != nullptr) { 344 outer_loop->PopulateInnerLoopUpwards(cur_loop); 345 } 346 } 347 } 348 349 return kAnalysisSuccess; 350 } 351 352 void SuperblockCloner::CleanUpControlFlow() { 353 // TODO: full control flow clean up for now, optimize it. 354 graph_->ClearDominanceInformation(); 355 356 ArenaBitVector outer_loop_bb_set( 357 arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 358 RecalculateBackEdgesInfo(&outer_loop_bb_set); 359 360 // TODO: do it locally. 361 graph_->SimplifyCFG(); 362 graph_->ComputeDominanceInformation(); 363 364 // AnalyzeLoopsLocally requires a correct post-ordering information which was calculated just 365 // before in ComputeDominanceInformation. 366 GraphAnalysisResult result = AnalyzeLoopsLocally(&outer_loop_bb_set); 367 DCHECK_EQ(result, kAnalysisSuccess); 368 369 // TODO: do it locally 370 OrderLoopsHeadersPredecessors(graph_); 371 372 graph_->ComputeTryBlockInformation(); 373 } 374 375 // 376 // Helpers for ResolveDataFlow 377 // 378 379 void SuperblockCloner::ResolvePhi(HPhi* phi) { 380 HBasicBlock* phi_block = phi->GetBlock(); 381 for (size_t i = 0, e = phi->InputCount(); i < e; i++) { 382 HInstruction* input = phi->InputAt(i); 383 HBasicBlock* input_block = input->GetBlock(); 384 385 // Originally defined outside the region. 386 if (!IsInOrigBBSet(input_block)) { 387 continue; 388 } 389 HBasicBlock* corresponding_block = phi_block->GetPredecessors()[i]; 390 if (!IsInOrigBBSet(corresponding_block)) { 391 phi->ReplaceInput(GetInstrCopy(input), i); 392 } 393 } 394 } 395 396 // 397 // Main algorithm methods. 398 // 399 400 void SuperblockCloner::SearchForSubgraphExits(ArenaVector<HBasicBlock*>* exits) { 401 DCHECK(exits->empty()); 402 for (uint32_t block_id : orig_bb_set_.Indexes()) { 403 HBasicBlock* block = GetBlockById(block_id); 404 for (HBasicBlock* succ : block->GetSuccessors()) { 405 if (!IsInOrigBBSet(succ)) { 406 exits->push_back(succ); 407 } 408 } 409 } 410 } 411 412 void SuperblockCloner::FindAndSetLocalAreaForAdjustments() { 413 DCHECK(outer_loop_ == nullptr); 414 ArenaVector<HBasicBlock*> exits(arena_->Adapter(kArenaAllocSuperblockCloner)); 415 SearchForSubgraphExits(&exits); 416 417 // For a reducible graph we need to update back-edges and dominance information only for 418 // the outermost loop which is affected by the transformation - it can be found by picking 419 // the common most outer loop of loops to which the subgraph exits blocks belong. 420 // Note: it can a loop or the whole graph (outer_loop_ will be nullptr in this case). 421 for (HBasicBlock* exit : exits) { 422 HLoopInformation* loop_exit_loop_info = exit->GetLoopInformation(); 423 if (loop_exit_loop_info == nullptr) { 424 outer_loop_ = nullptr; 425 break; 426 } 427 outer_loop_ = FindCommonLoop(outer_loop_, loop_exit_loop_info); 428 } 429 430 if (outer_loop_ != nullptr) { 431 // Save the loop population info as it will be changed later. 432 outer_loop_bb_set_.Copy(&outer_loop_->GetBlocks()); 433 } 434 } 435 436 void SuperblockCloner::RemapEdgesSuccessors() { 437 // Redirect incoming edges. 438 for (HEdge e : *remap_incoming_) { 439 HBasicBlock* orig_block = GetBlockById(e.GetFrom()); 440 HBasicBlock* orig_succ = GetBlockById(e.GetTo()); 441 RemapOrigInternalOrIncomingEdge(orig_block, orig_succ); 442 } 443 444 // Redirect internal edges. 445 for (uint32_t orig_block_id : orig_bb_set_.Indexes()) { 446 HBasicBlock* orig_block = GetBlockById(orig_block_id); 447 448 for (HBasicBlock* orig_succ : orig_block->GetSuccessors()) { 449 uint32_t orig_succ_id = orig_succ->GetBlockId(); 450 451 // Check for outgoing edge. 452 if (!IsInOrigBBSet(orig_succ)) { 453 HBasicBlock* copy_block = GetBlockCopy(orig_block); 454 copy_block->AddSuccessor(orig_succ); 455 continue; 456 } 457 458 auto orig_redir = remap_orig_internal_->Find(HEdge(orig_block_id, orig_succ_id)); 459 auto copy_redir = remap_copy_internal_->Find(HEdge(orig_block_id, orig_succ_id)); 460 461 // Due to construction all successors of copied block were set to original. 462 if (copy_redir != remap_copy_internal_->end()) { 463 RemapCopyInternalEdge(orig_block, orig_succ); 464 } else { 465 AddCopyInternalEdge(orig_block, orig_succ); 466 } 467 468 if (orig_redir != remap_orig_internal_->end()) { 469 RemapOrigInternalOrIncomingEdge(orig_block, orig_succ); 470 } 471 } 472 } 473 } 474 475 void SuperblockCloner::AdjustControlFlowInfo() { 476 ArenaBitVector outer_loop_bb_set( 477 arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 478 RecalculateBackEdgesInfo(&outer_loop_bb_set); 479 480 graph_->ClearDominanceInformation(); 481 // TODO: Do it locally. 482 graph_->ComputeDominanceInformation(); 483 } 484 485 // TODO: Current FastCase restriction guarantees that instructions' inputs are already mapped to 486 // the valid values; only phis' inputs must be adjusted. 487 void SuperblockCloner::ResolveDataFlow() { 488 for (auto entry : *bb_map_) { 489 HBasicBlock* orig_block = entry.first; 490 491 for (HInstructionIterator it(orig_block->GetPhis()); !it.Done(); it.Advance()) { 492 HPhi* orig_phi = it.Current()->AsPhi(); 493 HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 494 ResolvePhi(orig_phi); 495 ResolvePhi(copy_phi); 496 } 497 if (kIsDebugBuild) { 498 // Inputs of instruction copies must be already mapped to correspondent inputs copies. 499 for (HInstructionIterator it(orig_block->GetInstructions()); !it.Done(); it.Advance()) { 500 CheckInstructionInputsRemapping(it.Current()); 501 } 502 } 503 } 504 } 505 506 // 507 // Debug and logging methods. 508 // 509 510 void SuperblockCloner::CheckInstructionInputsRemapping(HInstruction* orig_instr) { 511 DCHECK(!orig_instr->IsPhi()); 512 HInstruction* copy_instr = GetInstrCopy(orig_instr); 513 for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) { 514 HInstruction* orig_input = orig_instr->InputAt(i); 515 DCHECK(orig_input->GetBlock()->Dominates(orig_instr->GetBlock())); 516 517 // If original input is defined outside the region then it will remain for both original 518 // instruction and the copy after the transformation. 519 if (!IsInOrigBBSet(orig_input->GetBlock())) { 520 continue; 521 } 522 HInstruction* copy_input = GetInstrCopy(orig_input); 523 DCHECK(copy_input->GetBlock()->Dominates(copy_instr->GetBlock())); 524 } 525 526 // Resolve environment. 527 if (orig_instr->HasEnvironment()) { 528 HEnvironment* orig_env = orig_instr->GetEnvironment(); 529 530 for (size_t i = 0, e = orig_env->Size(); i < e; ++i) { 531 HInstruction* orig_input = orig_env->GetInstructionAt(i); 532 533 // If original input is defined outside the region then it will remain for both original 534 // instruction and the copy after the transformation. 535 if (orig_input == nullptr || !IsInOrigBBSet(orig_input->GetBlock())) { 536 continue; 537 } 538 539 HInstruction* copy_input = GetInstrCopy(orig_input); 540 DCHECK(copy_input->GetBlock()->Dominates(copy_instr->GetBlock())); 541 } 542 } 543 } 544 545 // 546 // Public methods. 547 // 548 549 SuperblockCloner::SuperblockCloner(HGraph* graph, 550 const HBasicBlockSet* orig_bb_set, 551 HBasicBlockMap* bb_map, 552 HInstructionMap* hir_map) 553 : graph_(graph), 554 arena_(graph->GetAllocator()), 555 orig_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner), 556 remap_orig_internal_(nullptr), 557 remap_copy_internal_(nullptr), 558 remap_incoming_(nullptr), 559 bb_map_(bb_map), 560 hir_map_(hir_map), 561 outer_loop_(nullptr), 562 outer_loop_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner) { 563 orig_bb_set_.Copy(orig_bb_set); 564 } 565 566 void SuperblockCloner::SetSuccessorRemappingInfo(const HEdgeSet* remap_orig_internal, 567 const HEdgeSet* remap_copy_internal, 568 const HEdgeSet* remap_incoming) { 569 remap_orig_internal_ = remap_orig_internal; 570 remap_copy_internal_ = remap_copy_internal; 571 remap_incoming_ = remap_incoming; 572 } 573 574 bool SuperblockCloner::IsSubgraphClonable() const { 575 // TODO: Support irreducible graphs and graphs with try-catch. 576 if (graph_->HasIrreducibleLoops() || graph_->HasTryCatch()) { 577 return false; 578 } 579 580 // Check that there are no instructions defined in the subgraph and used outside. 581 // TODO: Improve this by accepting graph with such uses but only one exit. 582 for (uint32_t idx : orig_bb_set_.Indexes()) { 583 HBasicBlock* block = GetBlockById(idx); 584 585 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 586 HInstruction* instr = it.Current(); 587 if (!instr->IsClonable() || 588 IsUsedOutsideRegion(instr, orig_bb_set_)) { 589 return false; 590 } 591 } 592 593 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 594 HInstruction* instr = it.Current(); 595 if (!instr->IsClonable() || 596 IsUsedOutsideRegion(instr, orig_bb_set_)) { 597 return false; 598 } 599 } 600 } 601 602 return true; 603 } 604 605 void SuperblockCloner::Run() { 606 DCHECK(bb_map_ != nullptr); 607 DCHECK(hir_map_ != nullptr); 608 DCHECK(remap_orig_internal_ != nullptr && 609 remap_copy_internal_ != nullptr && 610 remap_incoming_ != nullptr); 611 DCHECK(IsSubgraphClonable()); 612 613 // Find an area in the graph for which control flow information should be adjusted. 614 FindAndSetLocalAreaForAdjustments(); 615 // Clone the basic blocks from the orig_bb_set_; data flow is invalid after the call and is to be 616 // adjusted. 617 CloneBasicBlocks(); 618 // Connect the blocks together/remap successors and fix phis which are directly affected my the 619 // remapping. 620 RemapEdgesSuccessors(); 621 // Recalculate dominance and backedge information which is required by the next stage. 622 AdjustControlFlowInfo(); 623 // Fix data flow of the graph. 624 ResolveDataFlow(); 625 } 626 627 void SuperblockCloner::CleanUp() { 628 CleanUpControlFlow(); 629 630 // Remove phis which have all inputs being same. 631 // When a block has a single predecessor it must not have any phis. However after the 632 // transformation it could happen that there is such block with a phi with a single input. 633 // As this is needed to be processed we also simplify phis with multiple same inputs here. 634 for (auto entry : *bb_map_) { 635 HBasicBlock* orig_block = entry.first; 636 for (HInstructionIterator inst_it(orig_block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 637 HPhi* phi = inst_it.Current()->AsPhi(); 638 if (ArePhiInputsTheSame(phi)) { 639 phi->ReplaceWith(phi->InputAt(0)); 640 orig_block->RemovePhi(phi); 641 } 642 } 643 644 HBasicBlock* copy_block = GetBlockCopy(orig_block); 645 for (HInstructionIterator inst_it(copy_block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 646 HPhi* phi = inst_it.Current()->AsPhi(); 647 if (ArePhiInputsTheSame(phi)) { 648 phi->ReplaceWith(phi->InputAt(0)); 649 copy_block->RemovePhi(phi); 650 } 651 } 652 } 653 } 654 655 HBasicBlock* SuperblockCloner::CloneBasicBlock(const HBasicBlock* orig_block) { 656 HGraph* graph = orig_block->GetGraph(); 657 HBasicBlock* copy_block = new (arena_) HBasicBlock(graph, orig_block->GetDexPc()); 658 graph->AddBlock(copy_block); 659 660 // Clone all the phis and add them to the map. 661 for (HInstructionIterator it(orig_block->GetPhis()); !it.Done(); it.Advance()) { 662 HInstruction* orig_instr = it.Current(); 663 HInstruction* copy_instr = orig_instr->Clone(arena_); 664 copy_block->AddPhi(copy_instr->AsPhi()); 665 copy_instr->AsPhi()->RemoveAllInputs(); 666 DCHECK(!orig_instr->HasEnvironment()); 667 hir_map_->Put(orig_instr, copy_instr); 668 } 669 670 // Clone all the instructions and add them to the map. 671 for (HInstructionIterator it(orig_block->GetInstructions()); !it.Done(); it.Advance()) { 672 HInstruction* orig_instr = it.Current(); 673 HInstruction* copy_instr = orig_instr->Clone(arena_); 674 ReplaceInputsWithCopies(copy_instr); 675 copy_block->AddInstruction(copy_instr); 676 if (orig_instr->HasEnvironment()) { 677 DeepCloneEnvironmentWithRemapping(copy_instr, orig_instr->GetEnvironment()); 678 } 679 hir_map_->Put(orig_instr, copy_instr); 680 } 681 682 return copy_block; 683 } 684 685 void SuperblockCloner::CloneBasicBlocks() { 686 // By this time ReversePostOrder must be valid: in 'CloneBasicBlock' inputs of the copied 687 // instructions might be replaced by copies of the original inputs (depending where those inputs 688 // are defined). So the definitions of the original inputs must be visited before their original 689 // uses. The property of the reducible graphs "if 'A' dom 'B' then rpo_num('A') >= rpo_num('B')" 690 // guarantees that. 691 for (HBasicBlock* orig_block : graph_->GetReversePostOrder()) { 692 if (!IsInOrigBBSet(orig_block)) { 693 continue; 694 } 695 HBasicBlock* copy_block = CloneBasicBlock(orig_block); 696 bb_map_->Put(orig_block, copy_block); 697 if (kSuperblockClonerLogging) { 698 std::cout << "new block :" << copy_block->GetBlockId() << ": " << orig_block->GetBlockId() << 699 std::endl; 700 } 701 } 702 } 703 704 } // namespace art 705