Lines Matching +full:structured +full:- +full:clone
7 // http://www.apache.org/licenses/LICENSE-2.0
41 // Utility class to rewrite out-of-loop uses of an in-loop definition in terms
54 cfg_(context_->cfg()), in LCSSARewriter()
57 merge_block_id_(merge_block ? merge_block->id() : 0) {} in LCSSARewriter()
73 (user->opcode() != spv::Op::OpPhi || bb != GetParent(user)) && in RewriteUse()
76 assert((user->opcode() == spv::Op::OpPhi || bb == GetParent(user)) && in RewriteUse()
81 Instruction* new_def = GetOrBuildIncoming(bb->id()); in RewriteUse()
83 user->SetOperand(operand_index, {new_def->result_id()}); in RewriteUse()
87 // In-place update of some managers (avoid full invalidation).
89 analysis::DefUseManager* def_use_mgr = base_->context_->get_def_use_mgr(); in UpdateManagers()
92 def_use_mgr->AnalyzeInstDef(insn); in UpdateManagers()
96 def_use_mgr->AnalyzeInstUse(insn); in UpdateManagers()
103 return base_->context_->get_instr_block(instr); in GetParent()
112 const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); in CreatePhiInstruction()
116 GetOrBuildIncoming(defining_blocks[i])->result_id()); in CreatePhiInstruction()
119 InstructionBuilder builder(base_->context_, &*bb->begin(), in CreatePhiInstruction()
133 const std::vector<uint32_t>& bb_preds = base_->cfg_->preds(bb->id()); in CreatePhiInstruction()
138 InstructionBuilder builder(base_->context_, &*bb->begin(), in CreatePhiInstruction()
149 // - return the common def used by all predecessors;
150 // - if there is no common def, then we build a new phi instr at the
153 assert(base_->cfg_->block(bb_id) != nullptr && "Unknown basic block"); in GetOrBuildIncoming()
160 BasicBlock* bb = &*base_->cfg_->block(bb_id); in GetOrBuildIncoming()
164 if (base_->exit_bb_.count(bb)) { in GetOrBuildIncoming()
166 if (!bb->WhileEachPhiInst([&incoming_phi, this](Instruction* phi) { in GetOrBuildIncoming()
167 for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { in GetOrBuildIncoming()
168 if (phi->GetSingleWordInOperand(i) != def_insn_.result_id()) in GetOrBuildIncoming()
185 base_->GetDefiningBlocks(bb_id); in GetOrBuildIncoming()
187 // Special case for structured loops: merge block might be different from in GetOrBuildIncoming()
188 // the exit block set. To maintain structured properties it will ease in GetOrBuildIncoming()
191 if (defining_blocks.size() > 1 || bb_id == base_->merge_block_id_) { in GetOrBuildIncoming()
195 assert(bb_id == base_->merge_block_id_); in GetOrBuildIncoming()
215 // - return the common def used by all predecessors;
216 // - if there is no common def, then we build a new phi instr at the
219 assert(cfg_->block(bb_id) != nullptr && "Unknown basic block"); in GetDefiningBlocks()
226 if (dom_tree_.Dominates(e_bb->id(), bb_id)) { in GetDefiningBlocks()
227 defining_blocks.push_back(e_bb->id()); in GetDefiningBlocks()
235 for (uint32_t pred_id : cfg_->preds(bb_id)) { in GetDefiningBlocks()
277 CFG& cfg = *context->cfg(); in MakeSetClosedSSA()
279 context->GetDominatorAnalysis(function)->GetDomTree(); in MakeSetClosedSSA()
280 analysis::DefUseManager* def_use_manager = context->get_def_use_mgr(); in MakeSetClosedSSA()
288 def_use_manager->ForEachUse( in MakeSetClosedSSA()
291 BasicBlock* use_parent = context->get_instr_block(use); in MakeSetClosedSSA()
293 if (blocks.count(use_parent->id())) return; in MakeSetClosedSSA()
295 if (use->opcode() == spv::Op::OpPhi) { in MakeSetClosedSSA()
303 use_parent = context->get_instr_block( in MakeSetClosedSSA()
304 use->GetSingleWordOperand(operand_index + 1)); in MakeSetClosedSSA()
319 Function* function = loop_->GetHeaderBlock()->GetParent(); in CreateLoopDedicatedExits()
320 LoopDescriptor& loop_desc = *context_->GetLoopDescriptor(function); in CreateLoopDedicatedExits()
321 CFG& cfg = *context_->cfg(); in CreateLoopDedicatedExits()
322 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in CreateLoopDedicatedExits()
330 loop_->GetExitBlocks(&exit_bb_set); in CreateLoopDedicatedExits()
341 [this](uint32_t id) { return loop_->IsInsideLoop(id); })) { in CreateLoopDedicatedExits()
347 Function::iterator insert_pt = function->begin(); in CreateLoopDedicatedExits()
348 for (; insert_pt != function->end() && &*insert_pt != non_dedicate; in CreateLoopDedicatedExits()
351 assert(insert_pt != function->end() && "Basic Block not found"); in CreateLoopDedicatedExits()
357 context_, spv::Op::OpLabel, 0, context_->TakeNextId(), {}))))); in CreateLoopDedicatedExits()
362 if (loop_->IsInsideLoop(exit_pred_id)) { in CreateLoopDedicatedExits()
364 pred_block->ForEachSuccessorLabel([non_dedicate, &exit](uint32_t* id) { in CreateLoopDedicatedExits()
365 if (*id == non_dedicate->id()) *id = exit.id(); in CreateLoopDedicatedExits()
375 def_use_mgr->AnalyzeInstDefUse(exit.GetLabelInst()); in CreateLoopDedicatedExits()
376 context_->set_instr_block(exit.GetLabelInst(), &exit); in CreateLoopDedicatedExits()
382 builder.SetInsertPoint(builder.AddBranch(non_dedicate->id())); in CreateLoopDedicatedExits()
383 non_dedicate->ForEachPhiInst( in CreateLoopDedicatedExits()
389 for (uint32_t i = 0; i < phi->NumInOperands(); i += 2) { in CreateLoopDedicatedExits()
390 uint32_t def_id = phi->GetSingleWordInOperand(i); in CreateLoopDedicatedExits()
391 uint32_t incoming_id = phi->GetSingleWordInOperand(i + 1); in CreateLoopDedicatedExits()
392 if (loop_->IsInsideLoop(incoming_id)) { in CreateLoopDedicatedExits()
402 Instruction* exit_phi = builder.AddPhi(phi->type_id(), exit_phi_op); in CreateLoopDedicatedExits()
404 new_phi_op.push_back(exit_phi->result_id()); in CreateLoopDedicatedExits()
409 phi->SetInOperand(idx, {new_phi_op[idx]}); in CreateLoopDedicatedExits()
411 for (uint32_t j = phi->NumInOperands() - 1; j >= idx; j--) in CreateLoopDedicatedExits()
412 phi->RemoveInOperand(j); in CreateLoopDedicatedExits()
414 def_use_mgr->AnalyzeInstUse(phi); in CreateLoopDedicatedExits()
418 cfg.RemoveNonExistingEdges(non_dedicate->id()); in CreateLoopDedicatedExits()
422 parent_loop->AddBasicBlock(&exit); in CreateLoopDedicatedExits()
426 loop_->SetMergeBlock(*new_loop_exits.begin()); in CreateLoopDedicatedExits()
430 context_->InvalidateAnalysesExceptFor( in CreateLoopDedicatedExits()
439 Function* function = loop_->GetHeaderBlock()->GetParent(); in MakeLoopClosedSSA()
440 CFG& cfg = *context_->cfg(); in MakeLoopClosedSSA()
442 context_->GetDominatorAnalysis(function)->GetDomTree(); in MakeLoopClosedSSA()
447 loop_->GetExitBlocks(&exit_bb_id); in MakeLoopClosedSSA()
454 loop_->GetMergeBlock()); in MakeLoopClosedSSA()
455 MakeSetClosedSSA(context_, function, loop_->GetBlocks(), exit_bb, in MakeLoopClosedSSA()
458 // Make sure all defs post-dominated by the merge block have their last use no in MakeLoopClosedSSA()
460 if (loop_->GetMergeBlock()) { in MakeLoopClosedSSA()
462 loop_->GetMergingBlocks(&merging_bb_id); in MakeLoopClosedSSA()
463 merging_bb_id.erase(loop_->GetMergeBlock()->id()); in MakeLoopClosedSSA()
466 exit_bb.insert(loop_->GetMergeBlock()); in MakeLoopClosedSSA()
473 context_->InvalidateAnalysesExceptFor( in MakeLoopClosedSSA()
480 // Compute the structured order of the loop basic blocks and store it in the in CloneLoop()
483 loop_->ComputeLoopStructuredOrder(&ordered_loop_blocks); in CloneLoop()
485 // Clone the loop. in CloneLoop()
490 // Clone the loop. in CloneAndAttachLoopToHeader()
496 context_, spv::Op::OpLabel, 0, context_->TakeNextId(), {})}; in CloneAndAttachLoopToHeader()
498 new_exit_bb->SetParent(loop_->GetMergeBlock()->GetParent()); in CloneAndAttachLoopToHeader()
502 builder.AddBranch(loop_->GetHeaderBlock()->id()); in CloneAndAttachLoopToHeader()
505 const uint32_t old_merge_block = loop_->GetMergeBlock()->id(); in CloneAndAttachLoopToHeader()
506 const uint32_t new_merge_block = new_exit_bb->id(); in CloneAndAttachLoopToHeader()
510 for (std::unique_ptr<BasicBlock>& basic_block : cloning_result->cloned_bb_) { in CloneAndAttachLoopToHeader()
522 const uint32_t old_header = loop_->GetHeaderBlock()->id(); in CloneAndAttachLoopToHeader()
523 const uint32_t new_header = new_loop->GetHeaderBlock()->id(); in CloneAndAttachLoopToHeader()
524 analysis::DefUseManager* def_use = context_->get_def_use_mgr(); in CloneAndAttachLoopToHeader()
526 def_use->ForEachUse(old_header, in CloneAndAttachLoopToHeader()
528 if (!this->loop_->IsInsideLoop(inst)) in CloneAndAttachLoopToHeader()
529 inst->SetOperand(operand, {new_header}); in CloneAndAttachLoopToHeader()
532 // TODO(1841): Handle failure to create pre-header. in CloneAndAttachLoopToHeader()
533 def_use->ForEachUse( in CloneAndAttachLoopToHeader()
534 loop_->GetOrCreatePreHeaderBlock()->id(), in CloneAndAttachLoopToHeader()
536 if (this->loop_->IsInsideLoop(inst)) in CloneAndAttachLoopToHeader()
537 inst->SetOperand(operand, {new_merge_block}); in CloneAndAttachLoopToHeader()
540 new_loop->SetMergeBlock(new_exit_bb.get()); in CloneAndAttachLoopToHeader()
542 new_loop->SetPreHeaderBlock(loop_->GetPreHeaderBlock()); in CloneAndAttachLoopToHeader()
545 cloning_result->cloned_bb_.push_back(std::move(new_exit_bb)); in CloneAndAttachLoopToHeader()
553 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in CloneLoop()
557 CFG& cfg = *context_->cfg(); in CloneLoop()
559 // Clone and place blocks in a SPIR-V compliant order (dominators first). in CloneLoop()
561 // For each basic block in the loop, we clone it and register the mapping in CloneLoop()
563 BasicBlock* new_bb = old_bb->Clone(context_); in CloneLoop()
564 new_bb->SetParent(&function_); in CloneLoop()
566 new_bb->GetLabelInst()->SetResultId(context_->TakeNextId()); in CloneLoop()
567 def_use_mgr->AnalyzeInstDef(new_bb->GetLabelInst()); in CloneLoop()
568 context_->set_instr_block(new_bb->GetLabelInst(), new_bb); in CloneLoop()
569 cloning_result->cloned_bb_.emplace_back(new_bb); in CloneLoop()
571 cloning_result->old_to_new_bb_[old_bb->id()] = new_bb; in CloneLoop()
572 cloning_result->new_to_old_bb_[new_bb->id()] = old_bb; in CloneLoop()
573 cloning_result->value_map_[old_bb->id()] = new_bb->id(); in CloneLoop()
575 if (loop_->IsInsideLoop(old_bb)) new_loop->AddBasicBlock(new_bb); in CloneLoop()
577 for (auto new_inst = new_bb->begin(), old_inst = old_bb->begin(); in CloneLoop()
578 new_inst != new_bb->end(); ++new_inst, ++old_inst) { in CloneLoop()
579 cloning_result->ptr_map_[&*new_inst] = &*old_inst; in CloneLoop()
580 if (new_inst->HasResultId()) { in CloneLoop()
582 new_inst->SetResultId(context_->TakeNextId()); in CloneLoop()
583 cloning_result->value_map_[old_inst->result_id()] = in CloneLoop()
584 new_inst->result_id(); in CloneLoop()
587 def_use_mgr->AnalyzeInstDef(&*new_inst); in CloneLoop()
594 for (std::unique_ptr<BasicBlock>& bb_ref : cloning_result->cloned_bb_) { in CloneLoop()
600 auto id_it = cloning_result->value_map_.find(*old_id); in CloneLoop()
601 if (id_it != cloning_result->value_map_.end()) { in CloneLoop()
602 *old_id = id_it->second; in CloneLoop()
607 def_use_mgr->AnalyzeInstUse(&insn); in CloneLoop()
608 context_->set_instr_block(&insn, bb); in CloneLoop()
623 if (loop_->HasParent()) loop_->GetParent()->AddNestedLoop(new_loop); in PopulateLoopNest()
630 parent->AddNestedLoop(cloned); in PopulateLoopNest()
635 loop_desc_->AddLoopNest(std::unique_ptr<Loop>(new_loop)); in PopulateLoopNest()
642 for (uint32_t bb_id : old_loop->GetBlocks()) { in PopulateLoopDesc()
644 new_loop->AddBasicBlock(bb); in PopulateLoopDesc()
646 new_loop->SetHeaderBlock( in PopulateLoopDesc()
647 cloning_result.old_to_new_bb_.at(old_loop->GetHeaderBlock()->id())); in PopulateLoopDesc()
648 if (old_loop->GetLatchBlock()) in PopulateLoopDesc()
649 new_loop->SetLatchBlock( in PopulateLoopDesc()
650 cloning_result.old_to_new_bb_.at(old_loop->GetLatchBlock()->id())); in PopulateLoopDesc()
651 if (old_loop->GetContinueBlock()) in PopulateLoopDesc()
652 new_loop->SetContinueBlock( in PopulateLoopDesc()
653 cloning_result.old_to_new_bb_.at(old_loop->GetContinueBlock()->id())); in PopulateLoopDesc()
654 if (old_loop->GetMergeBlock()) { in PopulateLoopDesc()
656 cloning_result.old_to_new_bb_.find(old_loop->GetMergeBlock()->id()); in PopulateLoopDesc()
658 ? it->second in PopulateLoopDesc()
659 : old_loop->GetMergeBlock(); in PopulateLoopDesc()
660 new_loop->SetMergeBlock(bb); in PopulateLoopDesc()
662 if (old_loop->GetPreHeaderBlock()) { in PopulateLoopDesc()
664 cloning_result.old_to_new_bb_.find(old_loop->GetPreHeaderBlock()->id()); in PopulateLoopDesc()
666 new_loop->SetPreHeaderBlock(it->second); in PopulateLoopDesc()
673 CFG& cfg = *loop.GetContext()->cfg(); in Analyze()
681 bb->ForEachInst([&bb_size](const Instruction* insn) { in Analyze()
682 if (insn->opcode() == spv::Op::OpLabel) return; in Analyze()
683 if (insn->IsNop()) return; in Analyze()
684 if (insn->opcode() == spv::Op::OpPhi) return; in Analyze()
687 block_sizes_[bb->id()] = bb_size; in Analyze()