Home | History | Annotate | Download | only in optimizing
      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