Lines Matching +full:structured +full:- +full:clone
7 // http://www.apache.org/licenses/LICENSE-2.0
42 // - The loop has any instruction that will prevent it;
43 // - The loop invariant condition is not uniform.
56 // - The loop has no instructions that prevents it (such as barrier);
57 // - The loop has one conditional branch or switch that do not depends on the
59 // - The loop invariant condition is uniform;
62 if (loop_->IsSafeToClone()) return false; in CanUnswitchLoop()
64 CFG& cfg = *context_->cfg(); in CanUnswitchLoop()
66 for (uint32_t bb_id : loop_->GetBlocks()) { in CanUnswitchLoop()
68 if (loop_->GetLatchBlock() == bb) { in CanUnswitchLoop()
72 if (bb->terminator()->IsBranch() && in CanUnswitchLoop()
73 bb->terminator()->opcode() != spv::Op::OpBranch) { in CanUnswitchLoop()
74 if (IsConditionNonConstantLoopInvariant(bb->terminator())) { in CanUnswitchLoop()
86 Function::iterator it = function_->FindBlock(bb_to_find->id()); in FindBasicBlockPosition()
87 assert(it != function_->end() && "Basic Block not found"); in FindBasicBlockPosition()
95 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in CreateBasicBlock()
100 context_, spv::Op::OpLabel, 0, context_->TakeNextId(), {}))))); in CreateBasicBlock()
101 bb->SetParent(function_); in CreateBasicBlock()
102 def_use_mgr->AnalyzeInstDef(bb->GetLabelInst()); in CreateBasicBlock()
103 context_->set_instr_block(bb->GetLabelInst(), bb); in CreateBasicBlock()
109 assert(switch_inst->opcode() == spv::Op::OpSwitch && in GetValueForDefaultPathForSwitch()
117 for (uint32_t i = 2; i < switch_inst->NumInOperands(); i += 2) { in GetValueForDefaultPathForSwitch()
118 existing_values.push_back(switch_inst->GetSingleWordInOperand(i)); in GetValueForDefaultPathForSwitch()
141 assert(loop_->GetPreHeaderBlock() && "This loop has no pre-header block"); in PerformUnswitch()
142 assert(loop_->IsLCSSA() && "This loop is not in LCSSA form"); in PerformUnswitch()
144 CFG& cfg = *context_->cfg(); in PerformUnswitch()
146 &context_->GetDominatorAnalysis(function_)->GetDomTree(); in PerformUnswitch()
147 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in PerformUnswitch()
151 // Step 1: Create the if merge block for structured modules. in PerformUnswitch()
154 // code the structured control flow imposes. in PerformUnswitch()
155 // For non structured program, the new loop will be connected to in PerformUnswitch()
160 BasicBlock* if_merge_block = loop_->GetMergeBlock(); in PerformUnswitch()
162 // have this guarantee for structured loops, for compute loop it will in PerformUnswitch()
163 // trivially help maintain both a structured-like form and LCSAA. in PerformUnswitch()
173 builder.AddBranch(if_merge_block->id()); in PerformUnswitch()
174 builder.SetInsertPoint(&*loop_merge_block->begin()); in PerformUnswitch()
176 def_use_mgr->AnalyzeInstDef(loop_merge_block->GetLabelInst()); in PerformUnswitch()
178 if_merge_block->ForEachPhiInst( in PerformUnswitch()
180 Instruction* cloned = phi->Clone(context_); in PerformUnswitch()
181 cloned->SetResultId(TakeNextId()); in PerformUnswitch()
183 phi->SetInOperand(0, {cloned->result_id()}); in PerformUnswitch()
184 phi->SetInOperand(1, {loop_merge_block->id()}); in PerformUnswitch()
185 for (uint32_t j = phi->NumInOperands() - 1; j > 1; j--) in PerformUnswitch()
186 phi->RemoveInOperand(j); in PerformUnswitch()
189 std::vector<uint32_t> preds = cfg.preds(if_merge_block->id()); in PerformUnswitch()
191 if (pid == loop_merge_block->id()) continue; in PerformUnswitch()
193 p_bb->ForEachSuccessorLabel( in PerformUnswitch()
195 if (*id == if_merge_block->id()) *id = loop_merge_block->id(); in PerformUnswitch()
197 cfg.AddEdge(pid, loop_merge_block->id()); in PerformUnswitch()
199 cfg.RemoveNonExistingEdges(if_merge_block->id()); in PerformUnswitch()
201 if (Loop* ploop = loop_->GetParent()) { in PerformUnswitch()
202 ploop->AddBasicBlock(loop_merge_block); in PerformUnswitch()
203 loop_desc_.SetBasicBlockToLoop(loop_merge_block->id(), ploop); in PerformUnswitch()
207 dom_tree->GetOrInsertNode(loop_merge_block); in PerformUnswitch()
209 dom_tree->GetOrInsertNode(if_merge_block); in PerformUnswitch()
210 loop_merge_dtn->parent_ = if_merge_block_dtn->parent_; in PerformUnswitch()
211 loop_merge_dtn->children_.push_back(if_merge_block_dtn); in PerformUnswitch()
212 loop_merge_dtn->parent_->children_.push_back(loop_merge_dtn); in PerformUnswitch()
213 if_merge_block_dtn->parent_->children_.erase(std::find( in PerformUnswitch()
214 if_merge_block_dtn->parent_->children_.begin(), in PerformUnswitch()
215 if_merge_block_dtn->parent_->children_.end(), if_merge_block_dtn)); in PerformUnswitch()
217 loop_->SetMergeBlock(loop_merge_block); in PerformUnswitch()
225 BasicBlock* if_block = loop_->GetPreHeaderBlock(); in PerformUnswitch()
233 .AddBranch(loop_->GetHeaderBlock()->id()); in PerformUnswitch()
235 if_block->tail()->SetInOperand(0, {loop_pre_header->id()}); in PerformUnswitch()
239 ploop->AddBasicBlock(loop_pre_header); in PerformUnswitch()
240 loop_desc_.SetBasicBlockToLoop(loop_pre_header->id(), ploop); in PerformUnswitch()
245 def_use_mgr->AnalyzeInstDef(loop_pre_header->GetLabelInst()); in PerformUnswitch()
246 cfg.AddEdge(if_block->id(), loop_pre_header->id()); in PerformUnswitch()
247 cfg.RemoveNonExistingEdges(loop_->GetHeaderBlock()->id()); in PerformUnswitch()
249 loop_->GetHeaderBlock()->ForEachPhiInst( in PerformUnswitch()
251 phi->ForEachInId([loop_pre_header, if_block](uint32_t* id) { in PerformUnswitch()
252 if (*id == if_block->id()) { in PerformUnswitch()
253 *id = loop_pre_header->id(); in PerformUnswitch()
257 loop_->SetPreHeaderBlock(loop_pre_header); in PerformUnswitch()
261 dom_tree->GetOrInsertNode(loop_pre_header); in PerformUnswitch()
262 DominatorTreeNode* if_block_dtn = dom_tree->GetTreeNode(if_block); in PerformUnswitch()
263 loop_pre_header_dtn->parent_ = if_block_dtn; in PerformUnswitch()
265 if_block_dtn->children_.size() == 1 && in PerformUnswitch()
268 loop_pre_header_dtn->children_.push_back(if_block_dtn->children_[0]); in PerformUnswitch()
269 if_block_dtn->children_.clear(); in PerformUnswitch()
270 if_block_dtn->children_.push_back(loop_pre_header_dtn); in PerformUnswitch()
273 dom_tree->ResetDFNumbering(); in PerformUnswitch()
275 // Compute an ordered list of basic block to clone: loop blocks + pre-header in PerformUnswitch()
277 loop_->ComputeLoopStructuredOrder(&ordered_loop_blocks_, true, true); in PerformUnswitch()
281 // - Clone the loop // in PerformUnswitch()
282 // - Connect exits // in PerformUnswitch()
283 // - Specialize the loop // in PerformUnswitch()
286 Instruction* iv_condition = &*switch_block_->tail(); in PerformUnswitch()
287 spv::Op iv_opcode = iv_condition->opcode(); in PerformUnswitch()
289 def_use_mgr->GetDef(iv_condition->GetOperand(0).words[0]); in PerformUnswitch()
291 analysis::ConstantManager* cst_mgr = context_->get_constant_mgr(); in PerformUnswitch()
293 context_->get_type_mgr()->GetType(condition->type_id()); in PerformUnswitch()
295 // Build the list of value for which we need to clone and specialize the in PerformUnswitch()
302 cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant(cond_type, {0})), in PerformUnswitch()
305 cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant(cond_type, {1})); in PerformUnswitch()
312 for (uint32_t i = 2; i < iv_condition->NumInOperands(); i += 2) { in PerformUnswitch()
314 cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant( in PerformUnswitch()
315 cond_type, iv_condition->GetInOperand(i).words)), in PerformUnswitch()
323 if (loop_->GetHeaderBlock()->GetLoopMergeInst()) { in PerformUnswitch()
324 if_merging_blocks.insert(if_merge_block->id()); in PerformUnswitch()
326 return loop_->IsInsideLoop(id) || loop_->GetMergeBlock()->id() == id; in PerformUnswitch()
329 loop_->GetExitBlocks(&if_merging_blocks); in PerformUnswitch()
331 return loop_->IsInsideLoop(id); in PerformUnswitch()
344 specialisation_pair.second = cloned_loop->GetPreHeaderBlock(); in PerformUnswitch()
358 BasicBlock* merge = context_->cfg()->block(merge_bb_id); in PerformUnswitch()
360 merge->ForEachPhiInst( in PerformUnswitch()
362 uint32_t num_in_operands = phi->NumInOperands(); in PerformUnswitch()
364 uint32_t pred = phi->GetSingleWordInOperand(i + 1); in PerformUnswitch()
367 uint32_t incoming_value_id = phi->GetSingleWordInOperand(i); in PerformUnswitch()
372 incoming_value_id = new_value->second; in PerformUnswitch()
374 phi->AddOperand({SPV_OPERAND_TYPE_ID, {incoming_value_id}}); in PerformUnswitch()
375 phi->AddOperand({SPV_OPERAND_TYPE_ID, {pred}}); in PerformUnswitch()
381 function_->AddBasicBlocks(clone_result.cloned_bb_.begin(), in PerformUnswitch()
388 BasicBlock* original_loop_target = loop_->GetPreHeaderBlock(); in PerformUnswitch()
395 context_->KillInst(&*if_block->tail()); in PerformUnswitch()
400 condition->result_id(), original_loop_target->id(), in PerformUnswitch()
401 constant_branch[0].second->id(), in PerformUnswitch()
402 if_merge_block ? if_merge_block->id() : kInvalidId); in PerformUnswitch()
406 targets.emplace_back(t.first->GetInOperand(0).words, t.second->id()); in PerformUnswitch()
409 builder.AddSwitch(condition->result_id(), original_loop_target->id(), in PerformUnswitch()
411 if_merge_block ? if_merge_block->id() : kInvalidId); in PerformUnswitch()
417 context_->InvalidateAnalysesExceptFor( in PerformUnswitch()
433 // The loop basic blocks in structured order.
439 return context_->TakeNextId(); in TakeNextId()
444 // basic blocks in a structured order (dominator first).
450 // - |loop| must be in the LCSSA form;
451 // - |cst_value| must be constant.
454 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in SpecializeLoop()
457 ignore_node = [loop](uint32_t bb_id) { return !loop->IsInsideLoop(bb_id); }; in SpecializeLoop()
460 def_use_mgr->ForEachUse(to_version_insn, in SpecializeLoop()
463 BasicBlock* bb = context_->get_instr_block(inst); in SpecializeLoop()
465 if (!bb || ignore_node(bb->id())) { in SpecializeLoop()
484 inst->SetOperand(operand_index, {cst_value->result_id()}); in SpecializeLoop()
485 def_use_mgr->AnalyzeInstUse(inst); in SpecializeLoop()
494 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in IsDynamicallyUniform()
496 auto it = dynamically_uniform_.find(var->result_id()); in IsDynamicallyUniform()
498 if (it != dynamically_uniform_.end()) return it->second; in IsDynamicallyUniform()
500 analysis::DecorationManager* dec_mgr = context_->get_decoration_mgr(); in IsDynamicallyUniform()
502 bool& is_uniform = dynamically_uniform_[var->result_id()]; in IsDynamicallyUniform()
505 dec_mgr->WhileEachDecoration(var->result_id(), in IsDynamicallyUniform()
515 BasicBlock* parent = context_->get_instr_block(var); in IsDynamicallyUniform()
520 if (!post_dom_tree.Dominates(parent->id(), entry->id())) { in IsDynamicallyUniform()
523 if (var->opcode() == spv::Op::OpLoad) { in IsDynamicallyUniform()
525 def_use_mgr->GetDef(var->GetSingleWordInOperand(0))->type_id(); in IsDynamicallyUniform()
526 const Instruction* PtrTypeInst = def_use_mgr->GetDef(PtrTypeId); in IsDynamicallyUniform()
528 PtrTypeInst->GetSingleWordInOperand(kTypePointerStorageClassInIdx)); in IsDynamicallyUniform()
534 if (!context_->IsCombinatorInstruction(var)) { in IsDynamicallyUniform()
539 return is_uniform = var->WhileEachInId([entry, &post_dom_tree, in IsDynamicallyUniform()
541 return IsDynamicallyUniform(context_->get_def_use_mgr()->GetDef(*id), in IsDynamicallyUniform()
549 assert(insn->IsBranch()); in IsConditionNonConstantLoopInvariant()
550 assert(insn->opcode() != spv::Op::OpBranch); in IsConditionNonConstantLoopInvariant()
551 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr(); in IsConditionNonConstantLoopInvariant()
553 Instruction* condition = def_use_mgr->GetDef(insn->GetOperand(0).words[0]); in IsConditionNonConstantLoopInvariant()
554 if (condition->IsConstant()) { in IsConditionNonConstantLoopInvariant()
558 if (loop_->IsInsideLoop(condition)) { in IsConditionNonConstantLoopInvariant()
563 condition, function_->entry().get(), in IsConditionNonConstantLoopInvariant()
564 context_->GetPostDominatorAnalysis(function_)->GetDomTree()); in IsConditionNonConstantLoopInvariant()
572 Module* module = context()->module(); in Process()
586 LoopDescriptor& loop_descriptor = *context()->GetLoopDescriptor(f); in ProcessFunction()