| // Copyright (c) 2018 Google LLC. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include <algorithm> |
| #include <memory> |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <utility> |
| #include <vector> |
| |
| #include "source/cfa.h" |
| #include "source/opt/cfg.h" |
| #include "source/opt/ir_builder.h" |
| #include "source/opt/ir_context.h" |
| #include "source/opt/loop_descriptor.h" |
| #include "source/opt/loop_utils.h" |
| |
| namespace spvtools { |
| namespace opt { |
| |
| namespace { |
| // Return true if |bb| is dominated by at least one block in |exits| |
| static inline bool DominatesAnExit(BasicBlock* bb, |
| const std::unordered_set<BasicBlock*>& exits, |
| const DominatorTree& dom_tree) { |
| for (BasicBlock* e_bb : exits) |
| if (dom_tree.Dominates(bb, e_bb)) return true; |
| return false; |
| } |
| |
| // Utility class to rewrite out-of-loop uses of an in-loop definition in terms |
| // of phi instructions to achieve a LCSSA form. |
| // For a given definition, the class user registers phi instructions using that |
| // definition in all loop exit blocks by which the definition escapes. |
| // Then, when rewriting a use of the definition, the rewriter walks the |
| // paths from the use the loop exits. At each step, it will insert a phi |
| // instruction to merge the incoming value according to exit blocks definition. |
| class LCSSARewriter { |
| public: |
| LCSSARewriter(IRContext* context, const DominatorTree& dom_tree, |
| const std::unordered_set<BasicBlock*>& exit_bb, |
| BasicBlock* merge_block) |
| : context_(context), |
| cfg_(context_->cfg()), |
| dom_tree_(dom_tree), |
| exit_bb_(exit_bb), |
| merge_block_id_(merge_block ? merge_block->id() : 0) {} |
| |
| struct UseRewriter { |
| explicit UseRewriter(LCSSARewriter* base, const Instruction& def_insn) |
| : base_(base), def_insn_(def_insn) {} |
| // Rewrites the use of |def_insn_| by the instruction |user| at the index |
| // |operand_index| in terms of phi instruction. This recursively builds new |
| // phi instructions from |user| to the loop exit blocks' phis. The use of |
| // |def_insn_| in |user| is replaced by the relevant phi instruction at the |
| // end of the operation. |
| // It is assumed that |user| does not dominates any of the loop exit basic |
| // block. This operation does not update the def/use manager, instead it |
| // records what needs to be updated. The actual update is performed by |
| // UpdateManagers. |
| void RewriteUse(BasicBlock* bb, Instruction* user, uint32_t operand_index) { |
| assert( |
| (user->opcode() != SpvOpPhi || bb != GetParent(user)) && |
| "The root basic block must be the incoming edge if |user| is a phi " |
| "instruction"); |
| assert((user->opcode() == SpvOpPhi || bb == GetParent(user)) && |
| "The root basic block must be the instruction parent if |user| is " |
| "not " |
| "phi instruction"); |
| |
| Instruction* new_def = GetOrBuildIncoming(bb->id()); |
| |
| user->SetOperand(operand_index, {new_def->result_id()}); |
| rewritten_.insert(user); |
| } |
| |
| // In-place update of some managers (avoid full invalidation). |
| inline void UpdateManagers() { |
| analysis::DefUseManager* def_use_mgr = base_->context_->get_def_use_mgr(); |
| // Register all new definitions. |
| for (Instruction* insn : rewritten_) { |
| def_use_mgr->AnalyzeInstDef(insn); |
| } |
| // Register all new uses. |
| for (Instruction* insn : rewritten_) { |
| def_use_mgr->AnalyzeInstUse(insn); |
| } |
| } |
| |
| private: |
| // Return the basic block that |instr| belongs to. |
| BasicBlock* GetParent(Instruction* instr) { |
| return base_->context_->get_instr_block(instr); |
| } |
| |
| // Builds a phi instruction for the basic block |bb|. The function assumes |
| // that |defining_blocks| contains the list of basic block that define the |
| // usable value for each predecessor of |bb|. |
| inline Instruction* CreatePhiInstruction( |
| BasicBlock* bb, const std::vector<uint32_t>& defining_blocks) { |
| std::vector<uint32_t> incomings; |
| const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); |
| assert(bb_preds.size() == defining_blocks.size()); |
| for (size_t i = 0; i < bb_preds.size(); i++) { |
| incomings.push_back( |
| GetOrBuildIncoming(defining_blocks[i])->result_id()); |
| incomings.push_back(bb_preds[i]); |
| } |
| InstructionBuilder builder(base_->context_, &*bb->begin(), |
| IRContext::kAnalysisInstrToBlockMapping); |
| Instruction* incoming_phi = |
| builder.AddPhi(def_insn_.type_id(), incomings); |
| |
| rewritten_.insert(incoming_phi); |
| return incoming_phi; |
| } |
| |
| // Builds a phi instruction for the basic block |bb|, all incoming values |
| // will be |value|. |
| inline Instruction* CreatePhiInstruction(BasicBlock* bb, |
| const Instruction& value) { |
| std::vector<uint32_t> incomings; |
| const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); |
| for (size_t i = 0; i < bb_preds.size(); i++) { |
| incomings.push_back(value.result_id()); |
| incomings.push_back(bb_preds[i]); |
| } |
| InstructionBuilder builder(base_->context_, &*bb->begin(), |
| IRContext::kAnalysisInstrToBlockMapping); |
| Instruction* incoming_phi = |
| builder.AddPhi(def_insn_.type_id(), incomings); |
| |
| rewritten_.insert(incoming_phi); |
| return incoming_phi; |
| } |
| |
| // Return the new def to use for the basic block |bb_id|. |
| // If |bb_id| does not have a suitable def to use then we: |
| // - return the common def used by all predecessors; |
| // - if there is no common def, then we build a new phi instr at the |
| // beginning of |bb_id| and return this new instruction. |
| Instruction* GetOrBuildIncoming(uint32_t bb_id) { |
| assert(base_->cfg_->block(bb_id) != nullptr && "Unknown basic block"); |
| |
| Instruction*& incoming_phi = bb_to_phi_[bb_id]; |
| if (incoming_phi) { |
| return incoming_phi; |
| } |
| |
| BasicBlock* bb = &*base_->cfg_->block(bb_id); |
| // If this is an exit basic block, look if there already is an eligible |
| // phi instruction. An eligible phi has |def_insn_| as all incoming |
| // values. |
| if (base_->exit_bb_.count(bb)) { |
| // Look if there is an eligible phi in this block. |
| if (!bb->WhileEachPhiInst([&incoming_phi, this](Instruction* phi) { |
| for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { |
| if (phi->GetSingleWordInOperand(i) != def_insn_.result_id()) |
| return true; |
| } |
| incoming_phi = phi; |
| rewritten_.insert(incoming_phi); |
| return false; |
| })) { |
| return incoming_phi; |
| } |
| incoming_phi = CreatePhiInstruction(bb, def_insn_); |
| return incoming_phi; |
| } |
| |
| // Get the block that defines the value to use for each predecessor. |
| // If the vector has 1 value, then it means that this block does not need |
| // to build a phi instruction unless |bb_id| is the loop merge block. |
| const std::vector<uint32_t>& defining_blocks = |
| base_->GetDefiningBlocks(bb_id); |
| |
| // Special case for structured loops: merge block might be different from |
| // the exit block set. To maintain structured properties it will ease |
| // transformations if the merge block also holds a phi instruction like |
| // the exit ones. |
| if (defining_blocks.size() > 1 || bb_id == base_->merge_block_id_) { |
| if (defining_blocks.size() > 1) { |
| incoming_phi = CreatePhiInstruction(bb, defining_blocks); |
| } else { |
| assert(bb_id == base_->merge_block_id_); |
| incoming_phi = |
| CreatePhiInstruction(bb, *GetOrBuildIncoming(defining_blocks[0])); |
| } |
| } else { |
| incoming_phi = GetOrBuildIncoming(defining_blocks[0]); |
| } |
| |
| return incoming_phi; |
| } |
| |
| LCSSARewriter* base_; |
| const Instruction& def_insn_; |
| std::unordered_map<uint32_t, Instruction*> bb_to_phi_; |
| std::unordered_set<Instruction*> rewritten_; |
| }; |
| |
| private: |
| // Return the new def to use for the basic block |bb_id|. |
| // If |bb_id| does not have a suitable def to use then we: |
| // - return the common def used by all predecessors; |
| // - if there is no common def, then we build a new phi instr at the |
| // beginning of |bb_id| and return this new instruction. |
| const std::vector<uint32_t>& GetDefiningBlocks(uint32_t bb_id) { |
| assert(cfg_->block(bb_id) != nullptr && "Unknown basic block"); |
| std::vector<uint32_t>& defining_blocks = bb_to_defining_blocks_[bb_id]; |
| |
| if (defining_blocks.size()) return defining_blocks; |
| |
| // Check if one of the loop exit basic block dominates |bb_id|. |
| for (const BasicBlock* e_bb : exit_bb_) { |
| if (dom_tree_.Dominates(e_bb->id(), bb_id)) { |
| defining_blocks.push_back(e_bb->id()); |
| return defining_blocks; |
| } |
| } |
| |
| // Process parents, they will returns their suitable blocks. |
| // If they are all the same, this means this basic block is dominated by a |
| // common block, so we won't need to build a phi instruction. |
| for (uint32_t pred_id : cfg_->preds(bb_id)) { |
| const std::vector<uint32_t>& pred_blocks = GetDefiningBlocks(pred_id); |
| if (pred_blocks.size() == 1) |
| defining_blocks.push_back(pred_blocks[0]); |
| else |
| defining_blocks.push_back(pred_id); |
| } |
| assert(defining_blocks.size()); |
| if (std::all_of(defining_blocks.begin(), defining_blocks.end(), |
| [&defining_blocks](uint32_t id) { |
| return id == defining_blocks[0]; |
| })) { |
| // No need for a phi. |
| defining_blocks.resize(1); |
| } |
| |
| return defining_blocks; |
| } |
| |
| IRContext* context_; |
| CFG* cfg_; |
| const DominatorTree& dom_tree_; |
| const std::unordered_set<BasicBlock*>& exit_bb_; |
| uint32_t merge_block_id_; |
| // This map represent the set of known paths. For each key, the vector |
| // represent the set of blocks holding the definition to be used to build the |
| // phi instruction. |
| // If the vector has 0 value, then the path is unknown yet, and must be built. |
| // If the vector has 1 value, then the value defined by that basic block |
| // should be used. |
| // If the vector has more than 1 value, then a phi node must be created, the |
| // basic block ordering is the same as the predecessor ordering. |
| std::unordered_map<uint32_t, std::vector<uint32_t>> bb_to_defining_blocks_; |
| }; |
| |
| // Make the set |blocks| closed SSA. The set is closed SSA if all the uses |
| // outside the set are phi instructions in exiting basic block set (hold by |
| // |lcssa_rewriter|). |
| inline void MakeSetClosedSSA(IRContext* context, Function* function, |
| const std::unordered_set<uint32_t>& blocks, |
| const std::unordered_set<BasicBlock*>& exit_bb, |
| LCSSARewriter* lcssa_rewriter) { |
| CFG& cfg = *context->cfg(); |
| DominatorTree& dom_tree = |
| context->GetDominatorAnalysis(function)->GetDomTree(); |
| analysis::DefUseManager* def_use_manager = context->get_def_use_mgr(); |
| |
| for (uint32_t bb_id : blocks) { |
| BasicBlock* bb = cfg.block(bb_id); |
| // If bb does not dominate an exit block, then it cannot have escaping defs. |
| if (!DominatesAnExit(bb, exit_bb, dom_tree)) continue; |
| for (Instruction& inst : *bb) { |
| LCSSARewriter::UseRewriter rewriter(lcssa_rewriter, inst); |
| def_use_manager->ForEachUse( |
| &inst, [&blocks, &rewriter, &exit_bb, context]( |
| Instruction* use, uint32_t operand_index) { |
| BasicBlock* use_parent = context->get_instr_block(use); |
| assert(use_parent); |
| if (blocks.count(use_parent->id())) return; |
| |
| if (use->opcode() == SpvOpPhi) { |
| // If the use is a Phi instruction and the incoming block is |
| // coming from the loop, then that's consistent with LCSSA form. |
| if (exit_bb.count(use_parent)) { |
| return; |
| } else { |
| // That's not an exit block, but the user is a phi instruction. |
| // Consider the incoming branch only. |
| use_parent = context->get_instr_block( |
| use->GetSingleWordOperand(operand_index + 1)); |
| } |
| } |
| // Rewrite the use. Note that this call does not invalidate the |
| // def/use manager. So this operation is safe. |
| rewriter.RewriteUse(use_parent, use, operand_index); |
| }); |
| rewriter.UpdateManagers(); |
| } |
| } |
| } |
| |
| } // namespace |
| |
| void LoopUtils::CreateLoopDedicatedExits() { |
| Function* function = loop_->GetHeaderBlock()->GetParent(); |
| LoopDescriptor& loop_desc = *context_->GetLoopDescriptor(function); |
| CFG& cfg = *context_->cfg(); |
| analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); |
| |
| const IRContext::Analysis PreservedAnalyses = |
| IRContext::kAnalysisDefUse | IRContext::kAnalysisInstrToBlockMapping; |
| |
| // Gathers the set of basic block that are not in this loop and have at least |
| // one predecessor in the loop and one not in the loop. |
| std::unordered_set<uint32_t> exit_bb_set; |
| loop_->GetExitBlocks(&exit_bb_set); |
| |
| std::unordered_set<BasicBlock*> new_loop_exits; |
| bool made_change = false; |
| // For each block, we create a new one that gathers all branches from |
| // the loop and fall into the block. |
| for (uint32_t non_dedicate_id : exit_bb_set) { |
| BasicBlock* non_dedicate = cfg.block(non_dedicate_id); |
| const std::vector<uint32_t>& bb_pred = cfg.preds(non_dedicate_id); |
| // Ignore the block if all the predecessors are in the loop. |
| if (std::all_of(bb_pred.begin(), bb_pred.end(), |
| [this](uint32_t id) { return loop_->IsInsideLoop(id); })) { |
| new_loop_exits.insert(non_dedicate); |
| continue; |
| } |
| |
| made_change = true; |
| Function::iterator insert_pt = function->begin(); |
| for (; insert_pt != function->end() && &*insert_pt != non_dedicate; |
| ++insert_pt) { |
| } |
| assert(insert_pt != function->end() && "Basic Block not found"); |
| |
| // Create the dedicate exit basic block. |
| // TODO(1841): Handle id overflow. |
| BasicBlock& exit = *insert_pt.InsertBefore(std::unique_ptr<BasicBlock>( |
| new BasicBlock(std::unique_ptr<Instruction>(new Instruction( |
| context_, SpvOpLabel, 0, context_->TakeNextId(), {}))))); |
| exit.SetParent(function); |
| |
| // Redirect in loop predecessors to |exit| block. |
| for (uint32_t exit_pred_id : bb_pred) { |
| if (loop_->IsInsideLoop(exit_pred_id)) { |
| BasicBlock* pred_block = cfg.block(exit_pred_id); |
| pred_block->ForEachSuccessorLabel([non_dedicate, &exit](uint32_t* id) { |
| if (*id == non_dedicate->id()) *id = exit.id(); |
| }); |
| // Update the CFG. |
| // |non_dedicate|'s predecessor list will be updated at the end of the |
| // loop. |
| cfg.RegisterBlock(pred_block); |
| } |
| } |
| |
| // Register the label to the def/use manager, requires for the phi patching. |
| def_use_mgr->AnalyzeInstDefUse(exit.GetLabelInst()); |
| context_->set_instr_block(exit.GetLabelInst(), &exit); |
| |
| InstructionBuilder builder(context_, &exit, PreservedAnalyses); |
| // Now jump from our dedicate basic block to the old exit. |
| // We also reset the insert point so all instructions are inserted before |
| // the branch. |
| builder.SetInsertPoint(builder.AddBranch(non_dedicate->id())); |
| non_dedicate->ForEachPhiInst( |
| [&builder, &exit, def_use_mgr, this](Instruction* phi) { |
| // New phi operands for this instruction. |
| std::vector<uint32_t> new_phi_op; |
| // Phi operands for the dedicated exit block. |
| std::vector<uint32_t> exit_phi_op; |
| for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { |
| uint32_t def_id = phi->GetSingleWordInOperand(i); |
| uint32_t incoming_id = phi->GetSingleWordInOperand(i + 1); |
| if (loop_->IsInsideLoop(incoming_id)) { |
| exit_phi_op.push_back(def_id); |
| exit_phi_op.push_back(incoming_id); |
| } else { |
| new_phi_op.push_back(def_id); |
| new_phi_op.push_back(incoming_id); |
| } |
| } |
| |
| // Build the new phi instruction dedicated exit block. |
| Instruction* exit_phi = builder.AddPhi(phi->type_id(), exit_phi_op); |
| // Build the new incoming branch. |
| new_phi_op.push_back(exit_phi->result_id()); |
| new_phi_op.push_back(exit.id()); |
| // Rewrite operands. |
| uint32_t idx = 0; |
| for (; idx < new_phi_op.size(); idx++) |
| phi->SetInOperand(idx, {new_phi_op[idx]}); |
| // Remove extra operands, from last to first (more efficient). |
| for (uint32_t j = phi->NumInOperands() - 1; j >= idx; j--) |
| phi->RemoveInOperand(j); |
| // Update the def/use manager for this |phi|. |
| def_use_mgr->AnalyzeInstUse(phi); |
| }); |
| // Update the CFG. |
| cfg.RegisterBlock(&exit); |
| cfg.RemoveNonExistingEdges(non_dedicate->id()); |
| new_loop_exits.insert(&exit); |
| // If non_dedicate is in a loop, add the new dedicated exit in that loop. |
| if (Loop* parent_loop = loop_desc[non_dedicate]) |
| parent_loop->AddBasicBlock(&exit); |
| } |
| |
| if (new_loop_exits.size() == 1) { |
| loop_->SetMergeBlock(*new_loop_exits.begin()); |
| } |
| |
| if (made_change) { |
| context_->InvalidateAnalysesExceptFor( |
| PreservedAnalyses | IRContext::kAnalysisCFG | |
| IRContext::Analysis::kAnalysisLoopAnalysis); |
| } |
| } |
| |
| void LoopUtils::MakeLoopClosedSSA() { |
| CreateLoopDedicatedExits(); |
| |
| Function* function = loop_->GetHeaderBlock()->GetParent(); |
| CFG& cfg = *context_->cfg(); |
| DominatorTree& dom_tree = |
| context_->GetDominatorAnalysis(function)->GetDomTree(); |
| |
| std::unordered_set<BasicBlock*> exit_bb; |
| { |
| std::unordered_set<uint32_t> exit_bb_id; |
| loop_->GetExitBlocks(&exit_bb_id); |
| for (uint32_t bb_id : exit_bb_id) { |
| exit_bb.insert(cfg.block(bb_id)); |
| } |
| } |
| |
| LCSSARewriter lcssa_rewriter(context_, dom_tree, exit_bb, |
| loop_->GetMergeBlock()); |
| MakeSetClosedSSA(context_, function, loop_->GetBlocks(), exit_bb, |
| &lcssa_rewriter); |
| |
| // Make sure all defs post-dominated by the merge block have their last use no |
| // further than the merge block. |
| if (loop_->GetMergeBlock()) { |
| std::unordered_set<uint32_t> merging_bb_id; |
| loop_->GetMergingBlocks(&merging_bb_id); |
| merging_bb_id.erase(loop_->GetMergeBlock()->id()); |
| // Reset the exit set, now only the merge block is the exit. |
| exit_bb.clear(); |
| exit_bb.insert(loop_->GetMergeBlock()); |
| // LCSSARewriter is reusable here only because it forces the creation of a |
| // phi instruction in the merge block. |
| MakeSetClosedSSA(context_, function, merging_bb_id, exit_bb, |
| &lcssa_rewriter); |
| } |
| |
| context_->InvalidateAnalysesExceptFor( |
| IRContext::Analysis::kAnalysisCFG | |
| IRContext::Analysis::kAnalysisDominatorAnalysis | |
| IRContext::Analysis::kAnalysisLoopAnalysis); |
| } |
| |
| Loop* LoopUtils::CloneLoop(LoopCloningResult* cloning_result) const { |
| // Compute the structured order of the loop basic blocks and store it in the |
| // vector ordered_loop_blocks. |
| std::vector<BasicBlock*> ordered_loop_blocks; |
| loop_->ComputeLoopStructuredOrder(&ordered_loop_blocks); |
| |
| // Clone the loop. |
| return CloneLoop(cloning_result, ordered_loop_blocks); |
| } |
| |
| Loop* LoopUtils::CloneAndAttachLoopToHeader(LoopCloningResult* cloning_result) { |
| // Clone the loop. |
| Loop* new_loop = CloneLoop(cloning_result); |
| |
| // Create a new exit block/label for the new loop. |
| // TODO(1841): Handle id overflow. |
| std::unique_ptr<Instruction> new_label{new Instruction( |
| context_, SpvOp::SpvOpLabel, 0, context_->TakeNextId(), {})}; |
| std::unique_ptr<BasicBlock> new_exit_bb{new BasicBlock(std::move(new_label))}; |
| new_exit_bb->SetParent(loop_->GetMergeBlock()->GetParent()); |
| |
| // Create an unconditional branch to the header block. |
| InstructionBuilder builder{context_, new_exit_bb.get()}; |
| builder.AddBranch(loop_->GetHeaderBlock()->id()); |
| |
| // Save the ids of the new and old merge block. |
| const uint32_t old_merge_block = loop_->GetMergeBlock()->id(); |
| const uint32_t new_merge_block = new_exit_bb->id(); |
| |
| // Replace the uses of the old merge block in the new loop with the new merge |
| // block. |
| for (std::unique_ptr<BasicBlock>& basic_block : cloning_result->cloned_bb_) { |
| for (Instruction& inst : *basic_block) { |
| // For each operand in each instruction check if it is using the old merge |
| // block and change it to be the new merge block. |
| auto replace_merge_use = [old_merge_block, |
| new_merge_block](uint32_t* id) { |
| if (*id == old_merge_block) *id = new_merge_block; |
| }; |
| inst.ForEachInOperand(replace_merge_use); |
| } |
| } |
| |
| const uint32_t old_header = loop_->GetHeaderBlock()->id(); |
| const uint32_t new_header = new_loop->GetHeaderBlock()->id(); |
| analysis::DefUseManager* def_use = context_->get_def_use_mgr(); |
| |
| def_use->ForEachUse(old_header, |
| [new_header, this](Instruction* inst, uint32_t operand) { |
| if (!this->loop_->IsInsideLoop(inst)) |
| inst->SetOperand(operand, {new_header}); |
| }); |
| |
| // TODO(1841): Handle failure to create pre-header. |
| def_use->ForEachUse( |
| loop_->GetOrCreatePreHeaderBlock()->id(), |
| [new_merge_block, this](Instruction* inst, uint32_t operand) { |
| if (this->loop_->IsInsideLoop(inst)) |
| inst->SetOperand(operand, {new_merge_block}); |
| |
| }); |
| new_loop->SetMergeBlock(new_exit_bb.get()); |
| |
| new_loop->SetPreHeaderBlock(loop_->GetPreHeaderBlock()); |
| |
| // Add the new block into the cloned instructions. |
| cloning_result->cloned_bb_.push_back(std::move(new_exit_bb)); |
| |
| return new_loop; |
| } |
| |
| Loop* LoopUtils::CloneLoop( |
| LoopCloningResult* cloning_result, |
| const std::vector<BasicBlock*>& ordered_loop_blocks) const { |
| analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); |
| |
| std::unique_ptr<Loop> new_loop = MakeUnique<Loop>(context_); |
| |
| CFG& cfg = *context_->cfg(); |
| |
| // Clone and place blocks in a SPIR-V compliant order (dominators first). |
| for (BasicBlock* old_bb : ordered_loop_blocks) { |
| // For each basic block in the loop, we clone it and register the mapping |
| // between old and new ids. |
| BasicBlock* new_bb = old_bb->Clone(context_); |
| new_bb->SetParent(&function_); |
| // TODO(1841): Handle id overflow. |
| new_bb->GetLabelInst()->SetResultId(context_->TakeNextId()); |
| def_use_mgr->AnalyzeInstDef(new_bb->GetLabelInst()); |
| context_->set_instr_block(new_bb->GetLabelInst(), new_bb); |
| cloning_result->cloned_bb_.emplace_back(new_bb); |
| |
| cloning_result->old_to_new_bb_[old_bb->id()] = new_bb; |
| cloning_result->new_to_old_bb_[new_bb->id()] = old_bb; |
| cloning_result->value_map_[old_bb->id()] = new_bb->id(); |
| |
| if (loop_->IsInsideLoop(old_bb)) new_loop->AddBasicBlock(new_bb); |
| |
| for (auto new_inst = new_bb->begin(), old_inst = old_bb->begin(); |
| new_inst != new_bb->end(); ++new_inst, ++old_inst) { |
| cloning_result->ptr_map_[&*new_inst] = &*old_inst; |
| if (new_inst->HasResultId()) { |
| // TODO(1841): Handle id overflow. |
| new_inst->SetResultId(context_->TakeNextId()); |
| cloning_result->value_map_[old_inst->result_id()] = |
| new_inst->result_id(); |
| |
| // Only look at the defs for now, uses are not updated yet. |
| def_use_mgr->AnalyzeInstDef(&*new_inst); |
| } |
| } |
| } |
| |
| // All instructions (including all labels) have been cloned, |
| // remap instruction operands id with the new ones. |
| for (std::unique_ptr<BasicBlock>& bb_ref : cloning_result->cloned_bb_) { |
| BasicBlock* bb = bb_ref.get(); |
| |
| for (Instruction& insn : *bb) { |
| insn.ForEachInId([cloning_result](uint32_t* old_id) { |
| // If the operand is defined in the loop, remap the id. |
| auto id_it = cloning_result->value_map_.find(*old_id); |
| if (id_it != cloning_result->value_map_.end()) { |
| *old_id = id_it->second; |
| } |
| }); |
| // Only look at what the instruction uses. All defs are register, so all |
| // should be fine now. |
| def_use_mgr->AnalyzeInstUse(&insn); |
| context_->set_instr_block(&insn, bb); |
| } |
| cfg.RegisterBlock(bb); |
| } |
| |
| PopulateLoopNest(new_loop.get(), *cloning_result); |
| |
| return new_loop.release(); |
| } |
| |
| void LoopUtils::PopulateLoopNest( |
| Loop* new_loop, const LoopCloningResult& cloning_result) const { |
| std::unordered_map<Loop*, Loop*> loop_mapping; |
| loop_mapping[loop_] = new_loop; |
| |
| if (loop_->HasParent()) loop_->GetParent()->AddNestedLoop(new_loop); |
| PopulateLoopDesc(new_loop, loop_, cloning_result); |
| |
| for (Loop& sub_loop : |
| make_range(++TreeDFIterator<Loop>(loop_), TreeDFIterator<Loop>())) { |
| Loop* cloned = new Loop(context_); |
| if (Loop* parent = loop_mapping[sub_loop.GetParent()]) |
| parent->AddNestedLoop(cloned); |
| loop_mapping[&sub_loop] = cloned; |
| PopulateLoopDesc(cloned, &sub_loop, cloning_result); |
| } |
| |
| loop_desc_->AddLoopNest(std::unique_ptr<Loop>(new_loop)); |
| } |
| |
| // Populates |new_loop| descriptor according to |old_loop|'s one. |
| void LoopUtils::PopulateLoopDesc( |
| Loop* new_loop, Loop* old_loop, |
| const LoopCloningResult& cloning_result) const { |
| for (uint32_t bb_id : old_loop->GetBlocks()) { |
| BasicBlock* bb = cloning_result.old_to_new_bb_.at(bb_id); |
| new_loop->AddBasicBlock(bb); |
| } |
| new_loop->SetHeaderBlock( |
| cloning_result.old_to_new_bb_.at(old_loop->GetHeaderBlock()->id())); |
| if (old_loop->GetLatchBlock()) |
| new_loop->SetLatchBlock( |
| cloning_result.old_to_new_bb_.at(old_loop->GetLatchBlock()->id())); |
| if (old_loop->GetContinueBlock()) |
| new_loop->SetContinueBlock( |
| cloning_result.old_to_new_bb_.at(old_loop->GetContinueBlock()->id())); |
| if (old_loop->GetMergeBlock()) { |
| auto it = |
| cloning_result.old_to_new_bb_.find(old_loop->GetMergeBlock()->id()); |
| BasicBlock* bb = it != cloning_result.old_to_new_bb_.end() |
| ? it->second |
| : old_loop->GetMergeBlock(); |
| new_loop->SetMergeBlock(bb); |
| } |
| if (old_loop->GetPreHeaderBlock()) { |
| auto it = |
| cloning_result.old_to_new_bb_.find(old_loop->GetPreHeaderBlock()->id()); |
| if (it != cloning_result.old_to_new_bb_.end()) { |
| new_loop->SetPreHeaderBlock(it->second); |
| } |
| } |
| } |
| |
| // Class to gather some metrics about a region of interest. |
| void CodeMetrics::Analyze(const Loop& loop) { |
| CFG& cfg = *loop.GetContext()->cfg(); |
| |
| roi_size_ = 0; |
| block_sizes_.clear(); |
| |
| for (uint32_t id : loop.GetBlocks()) { |
| const BasicBlock* bb = cfg.block(id); |
| size_t bb_size = 0; |
| bb->ForEachInst([&bb_size](const Instruction* insn) { |
| if (insn->opcode() == SpvOpLabel) return; |
| if (insn->IsNop()) return; |
| if (insn->opcode() == SpvOpPhi) return; |
| bb_size++; |
| }); |
| block_sizes_[bb->id()] = bb_size; |
| roi_size_ += bb_size; |
| } |
| } |
| |
| } // namespace opt |
| } // namespace spvtools |
