17f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov/* 27f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * Copyright (C) 2017 The Android Open Source Project 37f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * 47f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * Licensed under the Apache License, Version 2.0 (the "License"); 57f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * you may not use this file except in compliance with the License. 67f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * You may obtain a copy of the License at 77f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * 87f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * http://www.apache.org/licenses/LICENSE-2.0 97f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * 107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * Unless required by applicable law or agreed to in writing, software 117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * distributed under the License is distributed on an "AS IS" BASIS, 127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * See the License for the specific language governing permissions and 147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov * limitations under the License. 157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov */ 167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov#include "superblock_cloner.h" 187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov#include "common_dominator.h" 207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov#include "graph_checker.h" 217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov#include <iostream> 237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovnamespace art { 257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovusing HBasicBlockMap = SuperblockCloner::HBasicBlockMap; 277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovusing HInstructionMap = SuperblockCloner::HInstructionMap; 287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovusing HBasicBlockSet = SuperblockCloner::HBasicBlockSet; 297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovusing HEdgeSet = SuperblockCloner::HEdgeSet; 307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid HEdge::Dump(std::ostream& stream) const { 327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov stream << "(" << from_ << "->" << to_ << ")"; 337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Static helper methods. 377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Returns whether instruction has any uses (regular or environmental) outside the region, 407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// defined by basic block set. 417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovstatic bool IsUsedOutsideRegion(const HInstruction* instr, const HBasicBlockSet& bb_set) { 427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov auto& uses = instr->GetUses(); 437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto use_node = uses.begin(), e = uses.end(); use_node != e; ++use_node) { 447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* user = use_node->GetUser(); 457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!bb_set.IsBitSet(user->GetBlock()->GetBlockId())) { 467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return true; 477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov auto& env_uses = instr->GetEnvUses(); 517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto use_node = env_uses.begin(), e = env_uses.end(); use_node != e; ++use_node) { 527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* user = use_node->GetUser()->GetHolder(); 537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!bb_set.IsBitSet(user->GetBlock()->GetBlockId())) { 547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return true; 557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return false; 597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Returns whether the phi's inputs are the same HInstruction. 627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovstatic bool ArePhiInputsTheSame(const HPhi* phi) { 637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* first_input = phi->InputAt(0); 647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 1, e = phi->InputCount(); i < e; i++) { 657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (phi->InputAt(i) != first_input) { 667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return false; 677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return true; 717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Returns a common predecessor of loop1 and loop2 in the loop tree or nullptr if it is the whole 747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// graph. 757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovstatic HLoopInformation* FindCommonLoop(HLoopInformation* loop1, HLoopInformation* loop2) { 767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (loop1 != nullptr || loop2 != nullptr) { 777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return nullptr; 787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (loop1->IsIn(*loop2)) { 817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return loop2; 827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else if (loop2->IsIn(*loop1)) { 837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return loop1; 847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block = CommonDominator::ForPair(loop1->GetHeader(), loop2->GetHeader()); 867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return block->GetLoopInformation(); 877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Calls HGraph::OrderLoopHeaderPredecessors for each loop in the graph. 907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovstatic void OrderLoopsHeadersPredecessors(HGraph* graph) { 917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* block : graph->GetPostOrder()) { 927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (block->IsLoopHeader()) { 937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph->OrderLoopHeaderPredecessors(block); 947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Helpers for CloneBasicBlock. 1007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 1017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::ReplaceInputsWithCopies(HInstruction* copy_instr) { 1037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(!copy_instr->IsPhi()); 1047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 0, e = copy_instr->InputCount(); i < e; i++) { 1057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Copy instruction holds the same input as the original instruction holds. 1067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_input = copy_instr->InputAt(i); 1077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(orig_input->GetBlock())) { 1087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Defined outside the subgraph. 1097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 1107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_input = GetInstrCopy(orig_input); 1127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // copy_instr will be registered as a user of copy_inputs after returning from this function: 1137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // 'copy_block->AddInstruction(copy_instr)'. 1147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_instr->SetRawInputAt(i, copy_input); 1157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 1177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::DeepCloneEnvironmentWithRemapping(HInstruction* copy_instr, 1197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov const HEnvironment* orig_env) { 1207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (orig_env->GetParent() != nullptr) { 1217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DeepCloneEnvironmentWithRemapping(copy_instr, orig_env->GetParent()); 1227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HEnvironment* copy_env = new (arena_) HEnvironment(arena_, *orig_env, copy_instr); 1247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 0; i < orig_env->Size(); i++) { 1267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* env_input = orig_env->GetInstructionAt(i); 1277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (env_input != nullptr && IsInOrigBBSet(env_input->GetBlock())) { 1287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov env_input = GetInstrCopy(env_input); 1297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(env_input != nullptr && env_input->GetBlock() != nullptr); 1307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_env->SetRawEnvAt(i, env_input); 1327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (env_input != nullptr) { 1337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov env_input->AddEnvUseAt(copy_env, i); 1347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // InsertRawEnvironment assumes that instruction already has an environment that's why we use 1377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // SetRawEnvironment in the 'else' case. 1387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // As this function calls itself recursively with the same copy_instr - this copy_instr may 1397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // have partially copied chain of HEnvironments. 1407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (copy_instr->HasEnvironment()) { 1417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_instr->InsertRawEnvironment(copy_env); 1427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else { 1437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_instr->SetRawEnvironment(copy_env); 1447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 1467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 1487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Helpers for RemapEdgesSuccessors. 1497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 1507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::RemapOrigInternalOrIncomingEdge(HBasicBlock* orig_block, 1527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_succ) { 1537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(IsInOrigBBSet(orig_succ)); 1547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_succ = GetBlockCopy(orig_succ); 1557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov size_t this_index = orig_succ->GetPredecessorIndexOf(orig_block); 1577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov size_t phi_input_count = 0; 1587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // This flag reflects whether the original successor has at least one phi and this phi 1597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // has been already processed in the loop. Used for validation purposes in DCHECK to check that 1607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // in the end all of the phis in the copy successor have the same number of inputs - the number 1617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // of copy successor's predecessors. 1627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov bool first_phi_met = false; 1637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 1647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* orig_phi = it.Current()->AsPhi(); 1657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 1667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_phi_input = orig_phi->InputAt(this_index); 1677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Remove corresponding input for original phi. 1687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_phi->RemoveInputAt(this_index); 1697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Copy phi doesn't yet have either orig_block as predecessor or the input that corresponds 1707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // to orig_block, so add the input at the end of the list. 1717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_phi->AddInput(orig_phi_input); 1727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!first_phi_met) { 1737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov phi_input_count = copy_phi->InputCount(); 1747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov first_phi_met = true; 1757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else { 1767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK_EQ(phi_input_count, copy_phi->InputCount()); 1777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // orig_block will be put at the end of the copy_succ's predecessors list; that corresponds 1807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // to the previously added phi inputs position. 1817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_block->ReplaceSuccessor(orig_succ, copy_succ); 1827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(!first_phi_met || copy_succ->GetPredecessors().size() == phi_input_count); 1837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 1847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::AddCopyInternalEdge(HBasicBlock* orig_block, 1867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_succ) { 1877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(IsInOrigBBSet(orig_succ)); 1887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = GetBlockCopy(orig_block); 1897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_succ = GetBlockCopy(orig_succ); 1907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->AddSuccessor(copy_succ); 1917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 1927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov size_t orig_index = orig_succ->GetPredecessorIndexOf(orig_block); 1937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 1947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* orig_phi = it.Current()->AsPhi(); 1957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 1967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_phi_input = orig_phi->InputAt(orig_index); 1977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_phi->AddInput(orig_phi_input); 1987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 1997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 2007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::RemapCopyInternalEdge(HBasicBlock* orig_block, 2027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_succ) { 2037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(IsInOrigBBSet(orig_succ)); 2047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = GetBlockCopy(orig_block); 2057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->AddSuccessor(orig_succ); 2067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(copy_block->HasSuccessor(orig_succ)); 2077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov size_t orig_index = orig_succ->GetPredecessorIndexOf(orig_block); 2097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_succ->GetPhis()); !it.Done(); it.Advance()) { 2107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* orig_phi = it.Current()->AsPhi(); 2117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_phi_input = orig_phi->InputAt(orig_index); 2127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_phi->AddInput(orig_phi_input); 2137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 2157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 2177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Local versions of CF calculation/adjustment routines. 2187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 2197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// TODO: merge with the original version in nodes.cc. The concern is that we don't want to affect 2217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// the performance of the base version by checking the local set. 2227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// TODO: this version works when updating the back edges info for natural loop-based local_set. 2237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Check which exactly types of subgraphs can be analysed or rename it to 2247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// FindBackEdgesInTheNaturalLoop. 2257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::FindBackEdgesLocal(HBasicBlock* entry_block, ArenaBitVector* local_set) { 2267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaBitVector visited(arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 2277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks. 2287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK_EQ(visited.GetHighestBitSet(), -1); 2297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Nodes that we're currently visiting, indexed by block id. 2317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaBitVector visiting(arena_, graph_->GetBlocks().size(), false, kArenaAllocGraphBuilder); 2327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Number of successors visited from a given node, indexed by block id. 2337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaVector<size_t> successors_visited(graph_->GetBlocks().size(), 2347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 0u, 2357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov arena_->Adapter(kArenaAllocGraphBuilder)); 2367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Stack of nodes that we're currently visiting (same as marked in "visiting" above). 2377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaVector<HBasicBlock*> worklist(arena_->Adapter(kArenaAllocGraphBuilder)); 2387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov constexpr size_t kDefaultWorklistSize = 8; 2397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov worklist.reserve(kDefaultWorklistSize); 2407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov visited.SetBit(entry_block->GetBlockId()); 2427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov visiting.SetBit(entry_block->GetBlockId()); 2437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov worklist.push_back(entry_block); 2447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov while (!worklist.empty()) { 2467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* current = worklist.back(); 2477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov uint32_t current_id = current->GetBlockId(); 2487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (successors_visited[current_id] == current->GetSuccessors().size()) { 2497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov visiting.ClearBit(current_id); 2507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov worklist.pop_back(); 2517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else { 2527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++]; 2537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov uint32_t successor_id = successor->GetBlockId(); 2547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!local_set->IsBitSet(successor_id)) { 2557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 2567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (visiting.IsBitSet(successor_id)) { 2597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(ContainsElement(worklist, successor)); 2607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov successor->AddBackEdgeWhileUpdating(current); 2617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else if (!visited.IsBitSet(successor_id)) { 2627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov visited.SetBit(successor_id); 2637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov visiting.SetBit(successor_id); 2647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov worklist.push_back(successor); 2657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 2697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::RecalculateBackEdgesInfo(ArenaBitVector* outer_loop_bb_set) { 2717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: DCHECK that after the transformation the graph is connected. 2727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block_entry = nullptr; 2737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (outer_loop_ == nullptr) { 2757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto block : graph_->GetBlocks()) { 2767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (block != nullptr) { 2777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_bb_set->SetBit(block->GetBlockId()); 2787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* info = block->GetLoopInformation(); 2797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (info != nullptr) { 2807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov info->ResetBasicBlockData(); 2817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov block_entry = graph_->GetEntryBlock(); 2857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else { 2867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_bb_set->Copy(&outer_loop_bb_set_); 2877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov block_entry = outer_loop_->GetHeader(); 2887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Add newly created copy blocks. 2907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto entry : *bb_map_) { 2917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_bb_set->SetBit(entry.second->GetBlockId()); 2927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 2937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 2947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Clear loop_info for the whole outer loop. 2957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (uint32_t idx : outer_loop_bb_set->Indexes()) { 2967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block = GetBlockById(idx); 2977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* info = block->GetLoopInformation(); 2987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (info != nullptr) { 2997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov info->ResetBasicBlockData(); 3007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov FindBackEdgesLocal(block_entry, outer_loop_bb_set); 3057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (uint32_t idx : outer_loop_bb_set->Indexes()) { 3077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block = GetBlockById(idx); 3087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* info = block->GetLoopInformation(); 3097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Reset LoopInformation for regular blocks and old headers which are no longer loop headers. 3107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (info != nullptr && 3117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov (info->GetHeader() != block || info->NumberOfBackEdges() == 0)) { 3127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov block->SetLoopInformation(nullptr); 3137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 3167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// This is a modified version of HGraph::AnalyzeLoops. 3187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem SerovGraphAnalysisResult SuperblockCloner::AnalyzeLoopsLocally(ArenaBitVector* outer_loop_bb_set) { 3197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // We iterate post order to ensure we visit inner loops before outer loops. 3207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // `PopulateRecursive` needs this guarantee to know whether a natural loop 3217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // contains an irreducible loop. 3227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* block : graph_->GetPostOrder()) { 3237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!outer_loop_bb_set->IsBitSet(block->GetBlockId())) { 3247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 3257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (block->IsLoopHeader()) { 3277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (block->IsCatchBlock()) { 3287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: Dealing with exceptional back edges could be tricky because 3297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // they only approximate the real control flow. Bail out for now. 3307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return kAnalysisFailThrowCatchLoop; 3317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov block->GetLoopInformation()->Populate(); 3337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* block : graph_->GetPostOrder()) { 3377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!outer_loop_bb_set->IsBitSet(block->GetBlockId())) { 3387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 3397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (block->IsLoopHeader()) { 3417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* cur_loop = block->GetLoopInformation(); 3427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* outer_loop = cur_loop->GetPreHeader()->GetLoopInformation(); 3437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (outer_loop != nullptr) { 3447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop->PopulateInnerLoopUpwards(cur_loop); 3457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return kAnalysisSuccess; 3507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 3517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::CleanUpControlFlow() { 3537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: full control flow clean up for now, optimize it. 3547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->ClearDominanceInformation(); 3557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaBitVector outer_loop_bb_set( 3577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 3587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RecalculateBackEdgesInfo(&outer_loop_bb_set); 3597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: do it locally. 3617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->SimplifyCFG(); 3627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->ComputeDominanceInformation(); 3637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // AnalyzeLoopsLocally requires a correct post-ordering information which was calculated just 3657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // before in ComputeDominanceInformation. 3667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov GraphAnalysisResult result = AnalyzeLoopsLocally(&outer_loop_bb_set); 3677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK_EQ(result, kAnalysisSuccess); 3687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: do it locally 3707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov OrderLoopsHeadersPredecessors(graph_); 3717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->ComputeTryBlockInformation(); 3737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 3747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 3767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Helpers for ResolveDataFlow 3777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 3787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::ResolvePhi(HPhi* phi) { 3807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* phi_block = phi->GetBlock(); 3817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 0, e = phi->InputCount(); i < e; i++) { 3827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* input = phi->InputAt(i); 3837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* input_block = input->GetBlock(); 3847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Originally defined outside the region. 3867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(input_block)) { 3877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 3887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* corresponding_block = phi_block->GetPredecessors()[i]; 3907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(corresponding_block)) { 3917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov phi->ReplaceInput(GetInstrCopy(input), i); 3927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 3947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 3957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 3967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 3977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Main algorithm methods. 3987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 3997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::SearchForSubgraphExits(ArenaVector<HBasicBlock*>* exits) { 4017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(exits->empty()); 4027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (uint32_t block_id : orig_bb_set_.Indexes()) { 4037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block = GetBlockById(block_id); 4047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* succ : block->GetSuccessors()) { 4057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(succ)) { 4067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov exits->push_back(succ); 4077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 4117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::FindAndSetLocalAreaForAdjustments() { 4137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(outer_loop_ == nullptr); 4147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaVector<HBasicBlock*> exits(arena_->Adapter(kArenaAllocSuperblockCloner)); 4157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov SearchForSubgraphExits(&exits); 4167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // For a reducible graph we need to update back-edges and dominance information only for 4187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // the outermost loop which is affected by the transformation - it can be found by picking 4197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // the common most outer loop of loops to which the subgraph exits blocks belong. 4207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Note: it can a loop or the whole graph (outer_loop_ will be nullptr in this case). 4217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* exit : exits) { 4227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HLoopInformation* loop_exit_loop_info = exit->GetLoopInformation(); 4237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (loop_exit_loop_info == nullptr) { 4247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_ = nullptr; 4257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov break; 4267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_ = FindCommonLoop(outer_loop_, loop_exit_loop_info); 4287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (outer_loop_ != nullptr) { 4317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Save the loop population info as it will be changed later. 4327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_bb_set_.Copy(&outer_loop_->GetBlocks()); 4337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 4357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::RemapEdgesSuccessors() { 4377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Redirect incoming edges. 4387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HEdge e : *remap_incoming_) { 4397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_block = GetBlockById(e.GetFrom()); 4407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_succ = GetBlockById(e.GetTo()); 4417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RemapOrigInternalOrIncomingEdge(orig_block, orig_succ); 4427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Redirect internal edges. 4457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (uint32_t orig_block_id : orig_bb_set_.Indexes()) { 4467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_block = GetBlockById(orig_block_id); 4477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* orig_succ : orig_block->GetSuccessors()) { 4497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov uint32_t orig_succ_id = orig_succ->GetBlockId(); 4507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Check for outgoing edge. 4527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(orig_succ)) { 4537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = GetBlockCopy(orig_block); 4547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->AddSuccessor(orig_succ); 4557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 4567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov auto orig_redir = remap_orig_internal_->Find(HEdge(orig_block_id, orig_succ_id)); 4597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov auto copy_redir = remap_copy_internal_->Find(HEdge(orig_block_id, orig_succ_id)); 4607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Due to construction all successors of copied block were set to original. 4627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (copy_redir != remap_copy_internal_->end()) { 4637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RemapCopyInternalEdge(orig_block, orig_succ); 4647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } else { 4657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov AddCopyInternalEdge(orig_block, orig_succ); 4667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (orig_redir != remap_orig_internal_->end()) { 4697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RemapOrigInternalOrIncomingEdge(orig_block, orig_succ); 4707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 4747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::AdjustControlFlowInfo() { 4767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ArenaBitVector outer_loop_bb_set( 4777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov arena_, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 4787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RecalculateBackEdgesInfo(&outer_loop_bb_set); 4797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->ClearDominanceInformation(); 4817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: Do it locally. 4827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph_->ComputeDominanceInformation(); 4837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 4847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// TODO: Current FastCase restriction guarantees that instructions' inputs are already mapped to 4867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// the valid values; only phis' inputs must be adjusted. 4877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::ResolveDataFlow() { 4887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto entry : *bb_map_) { 4897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_block = entry.first; 4907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 4917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_block->GetPhis()); !it.Done(); it.Advance()) { 4927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* orig_phi = it.Current()->AsPhi(); 4937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* copy_phi = GetInstrCopy(orig_phi)->AsPhi(); 4947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ResolvePhi(orig_phi); 4957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ResolvePhi(copy_phi); 4967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 4977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (kIsDebugBuild) { 4987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Inputs of instruction copies must be already mapped to correspondent inputs copies. 4997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_block->GetInstructions()); !it.Done(); it.Advance()) { 5007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov CheckInstructionInputsRemapping(it.Current()); 5017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 5057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 5077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Debug and logging methods. 5087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 5097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::CheckInstructionInputsRemapping(HInstruction* orig_instr) { 5117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(!orig_instr->IsPhi()); 5127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_instr = GetInstrCopy(orig_instr); 5137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) { 5147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_input = orig_instr->InputAt(i); 5157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(orig_input->GetBlock()->Dominates(orig_instr->GetBlock())); 5167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // If original input is defined outside the region then it will remain for both original 5187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // instruction and the copy after the transformation. 5197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(orig_input->GetBlock())) { 5207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 5217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_input = GetInstrCopy(orig_input); 5237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(copy_input->GetBlock()->Dominates(copy_instr->GetBlock())); 5247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Resolve environment. 5277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (orig_instr->HasEnvironment()) { 5287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HEnvironment* orig_env = orig_instr->GetEnvironment(); 5297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (size_t i = 0, e = orig_env->Size(); i < e; ++i) { 5317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_input = orig_env->GetInstructionAt(i); 5327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // If original input is defined outside the region then it will remain for both original 5347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // instruction and the copy after the transformation. 5357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (orig_input == nullptr || !IsInOrigBBSet(orig_input->GetBlock())) { 5367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 5377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_input = GetInstrCopy(orig_input); 5407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(copy_input->GetBlock()->Dominates(copy_instr->GetBlock())); 5417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 5447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 5467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// Public methods. 5477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov// 5487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem SerovSuperblockCloner::SuperblockCloner(HGraph* graph, 5507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov const HBasicBlockSet* orig_bb_set, 5517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlockMap* bb_map, 5527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstructionMap* hir_map) 5537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov : graph_(graph), 5547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov arena_(graph->GetAllocator()), 5557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner), 5567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_orig_internal_(nullptr), 5577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_copy_internal_(nullptr), 5587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_incoming_(nullptr), 5597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov bb_map_(bb_map), 5607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov hir_map_(hir_map), 5617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_(nullptr), 5627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov outer_loop_bb_set_(arena_, orig_bb_set->GetSizeOf(), true, kArenaAllocSuperblockCloner) { 5637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_bb_set_.Copy(orig_bb_set); 5647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 5657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::SetSuccessorRemappingInfo(const HEdgeSet* remap_orig_internal, 5677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov const HEdgeSet* remap_copy_internal, 5687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov const HEdgeSet* remap_incoming) { 5697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_orig_internal_ = remap_orig_internal; 5707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_copy_internal_ = remap_copy_internal; 5717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_incoming_ = remap_incoming; 5727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 5737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovbool SuperblockCloner::IsSubgraphClonable() const { 5757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: Support irreducible graphs and graphs with try-catch. 5767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (graph_->HasIrreducibleLoops() || graph_->HasTryCatch()) { 5777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return false; 5787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Check that there are no instructions defined in the subgraph and used outside. 5817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // TODO: Improve this by accepting graph with such uses but only one exit. 5827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (uint32_t idx : orig_bb_set_.Indexes()) { 5837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* block = GetBlockById(idx); 5847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 5867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* instr = it.Current(); 5877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!instr->IsClonable() || 5887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov IsUsedOutsideRegion(instr, orig_bb_set_)) { 5897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return false; 5907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 5937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 5947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* instr = it.Current(); 5957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!instr->IsClonable() || 5967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov IsUsedOutsideRegion(instr, orig_bb_set_)) { 5977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return false; 5987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 5997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return true; 6037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 6047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6057f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::Run() { 6067f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(bb_map_ != nullptr); 6077f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(hir_map_ != nullptr); 6087f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(remap_orig_internal_ != nullptr && 6097f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_copy_internal_ != nullptr && 6107f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov remap_incoming_ != nullptr); 6117f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(IsSubgraphClonable()); 6127f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6137f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Find an area in the graph for which control flow information should be adjusted. 6147f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov FindAndSetLocalAreaForAdjustments(); 6157f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Clone the basic blocks from the orig_bb_set_; data flow is invalid after the call and is to be 6167f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // adjusted. 6177f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov CloneBasicBlocks(); 6187f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Connect the blocks together/remap successors and fix phis which are directly affected my the 6197f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // remapping. 6207f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov RemapEdgesSuccessors(); 6217f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Recalculate dominance and backedge information which is required by the next stage. 6227f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov AdjustControlFlowInfo(); 6237f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Fix data flow of the graph. 6247f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ResolveDataFlow(); 6257f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 6267f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6277f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::CleanUp() { 6287f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov CleanUpControlFlow(); 6297f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6307f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Remove phis which have all inputs being same. 6317f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // When a block has a single predecessor it must not have any phis. However after the 6327f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // transformation it could happen that there is such block with a phi with a single input. 6337f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // As this is needed to be processed we also simplify phis with multiple same inputs here. 6347f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (auto entry : *bb_map_) { 6357f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* orig_block = entry.first; 6367f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator inst_it(orig_block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 6377f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* phi = inst_it.Current()->AsPhi(); 6387f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (ArePhiInputsTheSame(phi)) { 6397f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov phi->ReplaceWith(phi->InputAt(0)); 6407f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov orig_block->RemovePhi(phi); 6417f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6427f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6437f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6447f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = GetBlockCopy(orig_block); 6457f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator inst_it(copy_block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 6467f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HPhi* phi = inst_it.Current()->AsPhi(); 6477f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (ArePhiInputsTheSame(phi)) { 6487f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov phi->ReplaceWith(phi->InputAt(0)); 6497f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->RemovePhi(phi); 6507f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6517f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6527f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6537f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 6547f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6557f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem SerovHBasicBlock* SuperblockCloner::CloneBasicBlock(const HBasicBlock* orig_block) { 6567f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HGraph* graph = orig_block->GetGraph(); 6577f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = new (arena_) HBasicBlock(graph, orig_block->GetDexPc()); 6587f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov graph->AddBlock(copy_block); 6597f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6607f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Clone all the phis and add them to the map. 6617f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_block->GetPhis()); !it.Done(); it.Advance()) { 6627f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_instr = it.Current(); 6637f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_instr = orig_instr->Clone(arena_); 6647f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->AddPhi(copy_instr->AsPhi()); 6657f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_instr->AsPhi()->RemoveAllInputs(); 6667f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DCHECK(!orig_instr->HasEnvironment()); 6677f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov hir_map_->Put(orig_instr, copy_instr); 6687f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6697f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6707f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // Clone all the instructions and add them to the map. 6717f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HInstructionIterator it(orig_block->GetInstructions()); !it.Done(); it.Advance()) { 6727f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* orig_instr = it.Current(); 6737f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HInstruction* copy_instr = orig_instr->Clone(arena_); 6747f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov ReplaceInputsWithCopies(copy_instr); 6757f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov copy_block->AddInstruction(copy_instr); 6767f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (orig_instr->HasEnvironment()) { 6777f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov DeepCloneEnvironmentWithRemapping(copy_instr, orig_instr->GetEnvironment()); 6787f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6797f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov hir_map_->Put(orig_instr, copy_instr); 6807f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6817f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6827f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov return copy_block; 6837f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 6847f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 6857f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serovvoid SuperblockCloner::CloneBasicBlocks() { 6867f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // By this time ReversePostOrder must be valid: in 'CloneBasicBlock' inputs of the copied 6877f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // instructions might be replaced by copies of the original inputs (depending where those inputs 6887f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // are defined). So the definitions of the original inputs must be visited before their original 6897f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // uses. The property of the reducible graphs "if 'A' dom 'B' then rpo_num('A') >= rpo_num('B')" 6907f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov // guarantees that. 6917f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov for (HBasicBlock* orig_block : graph_->GetReversePostOrder()) { 6927f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (!IsInOrigBBSet(orig_block)) { 6937f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov continue; 6947f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 6957f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov HBasicBlock* copy_block = CloneBasicBlock(orig_block); 6967f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov bb_map_->Put(orig_block, copy_block); 6977f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov if (kSuperblockClonerLogging) { 6987f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov std::cout << "new block :" << copy_block->GetBlockId() << ": " << orig_block->GetBlockId() << 6997f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov std::endl; 7007f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 7017f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov } 7027f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} 7037f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov 7047f4aff6705f46f411874b5ca8c4856b8ed5bfb13Artem Serov} // namespace art 705