1 // Copyright (c) 2017 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "source/opt/loop_descriptor.h"
16
17 #include <algorithm>
18 #include <iostream>
19 #include <limits>
20 #include <stack>
21 #include <type_traits>
22 #include <utility>
23 #include <vector>
24
25 #include "source/opt/cfg.h"
26 #include "source/opt/constants.h"
27 #include "source/opt/dominator_tree.h"
28 #include "source/opt/ir_builder.h"
29 #include "source/opt/ir_context.h"
30 #include "source/opt/iterator.h"
31 #include "source/opt/tree_iterator.h"
32 #include "source/util/make_unique.h"
33
34 namespace spvtools {
35 namespace opt {
36
37 // Takes in a phi instruction |induction| and the loop |header| and returns the
38 // step operation of the loop.
GetInductionStepOperation(const Instruction * induction) const39 Instruction* Loop::GetInductionStepOperation(
40 const Instruction* induction) const {
41 // Induction must be a phi instruction.
42 assert(induction->opcode() == SpvOpPhi);
43
44 Instruction* step = nullptr;
45
46 analysis::DefUseManager* def_use_manager = context_->get_def_use_mgr();
47
48 // Traverse the incoming operands of the phi instruction.
49 for (uint32_t operand_id = 1; operand_id < induction->NumInOperands();
50 operand_id += 2) {
51 // Incoming edge.
52 BasicBlock* incoming_block =
53 context_->cfg()->block(induction->GetSingleWordInOperand(operand_id));
54
55 // Check if the block is dominated by header, and thus coming from within
56 // the loop.
57 if (IsInsideLoop(incoming_block)) {
58 step = def_use_manager->GetDef(
59 induction->GetSingleWordInOperand(operand_id - 1));
60 break;
61 }
62 }
63
64 if (!step || !IsSupportedStepOp(step->opcode())) {
65 return nullptr;
66 }
67
68 // The induction variable which binds the loop must only be modified once.
69 uint32_t lhs = step->GetSingleWordInOperand(0);
70 uint32_t rhs = step->GetSingleWordInOperand(1);
71
72 // One of the left hand side or right hand side of the step instruction must
73 // be the induction phi and the other must be an OpConstant.
74 if (lhs != induction->result_id() && rhs != induction->result_id()) {
75 return nullptr;
76 }
77
78 if (def_use_manager->GetDef(lhs)->opcode() != SpvOp::SpvOpConstant &&
79 def_use_manager->GetDef(rhs)->opcode() != SpvOp::SpvOpConstant) {
80 return nullptr;
81 }
82
83 return step;
84 }
85
86 // Returns true if the |step| operation is an induction variable step operation
87 // which is currently handled.
IsSupportedStepOp(SpvOp step) const88 bool Loop::IsSupportedStepOp(SpvOp step) const {
89 switch (step) {
90 case SpvOp::SpvOpISub:
91 case SpvOp::SpvOpIAdd:
92 return true;
93 default:
94 return false;
95 }
96 }
97
IsSupportedCondition(SpvOp condition) const98 bool Loop::IsSupportedCondition(SpvOp condition) const {
99 switch (condition) {
100 // <
101 case SpvOp::SpvOpULessThan:
102 case SpvOp::SpvOpSLessThan:
103 // >
104 case SpvOp::SpvOpUGreaterThan:
105 case SpvOp::SpvOpSGreaterThan:
106
107 // >=
108 case SpvOp::SpvOpSGreaterThanEqual:
109 case SpvOp::SpvOpUGreaterThanEqual:
110 // <=
111 case SpvOp::SpvOpSLessThanEqual:
112 case SpvOp::SpvOpULessThanEqual:
113
114 return true;
115 default:
116 return false;
117 }
118 }
119
GetResidualConditionValue(SpvOp condition,int64_t initial_value,int64_t step_value,size_t number_of_iterations,size_t factor)120 int64_t Loop::GetResidualConditionValue(SpvOp condition, int64_t initial_value,
121 int64_t step_value,
122 size_t number_of_iterations,
123 size_t factor) {
124 int64_t remainder =
125 initial_value + (number_of_iterations % factor) * step_value;
126
127 // We subtract or add one as the above formula calculates the remainder if the
128 // loop where just less than or greater than. Adding or subtracting one should
129 // give a functionally equivalent value.
130 switch (condition) {
131 case SpvOp::SpvOpSGreaterThanEqual:
132 case SpvOp::SpvOpUGreaterThanEqual: {
133 remainder -= 1;
134 break;
135 }
136 case SpvOp::SpvOpSLessThanEqual:
137 case SpvOp::SpvOpULessThanEqual: {
138 remainder += 1;
139 break;
140 }
141
142 default:
143 break;
144 }
145 return remainder;
146 }
147
GetConditionInst() const148 Instruction* Loop::GetConditionInst() const {
149 BasicBlock* condition_block = FindConditionBlock();
150 if (!condition_block) {
151 return nullptr;
152 }
153 Instruction* branch_conditional = &*condition_block->tail();
154 if (!branch_conditional ||
155 branch_conditional->opcode() != SpvOpBranchConditional) {
156 return nullptr;
157 }
158 Instruction* condition_inst = context_->get_def_use_mgr()->GetDef(
159 branch_conditional->GetSingleWordInOperand(0));
160 if (IsSupportedCondition(condition_inst->opcode())) {
161 return condition_inst;
162 }
163
164 return nullptr;
165 }
166
167 // Extract the initial value from the |induction| OpPhi instruction and store it
168 // in |value|. If the function couldn't find the initial value of |induction|
169 // return false.
GetInductionInitValue(const Instruction * induction,int64_t * value) const170 bool Loop::GetInductionInitValue(const Instruction* induction,
171 int64_t* value) const {
172 Instruction* constant_instruction = nullptr;
173 analysis::DefUseManager* def_use_manager = context_->get_def_use_mgr();
174
175 for (uint32_t operand_id = 0; operand_id < induction->NumInOperands();
176 operand_id += 2) {
177 BasicBlock* bb = context_->cfg()->block(
178 induction->GetSingleWordInOperand(operand_id + 1));
179
180 if (!IsInsideLoop(bb)) {
181 constant_instruction = def_use_manager->GetDef(
182 induction->GetSingleWordInOperand(operand_id));
183 }
184 }
185
186 if (!constant_instruction) return false;
187
188 const analysis::Constant* constant =
189 context_->get_constant_mgr()->FindDeclaredConstant(
190 constant_instruction->result_id());
191 if (!constant) return false;
192
193 if (value) {
194 const analysis::Integer* type = constant->type()->AsInteger();
195 if (!type) {
196 return false;
197 }
198
199 *value = type->IsSigned() ? constant->GetSignExtendedValue()
200 : constant->GetZeroExtendedValue();
201 }
202
203 return true;
204 }
205
Loop(IRContext * context,DominatorAnalysis * dom_analysis,BasicBlock * header,BasicBlock * continue_target,BasicBlock * merge_target)206 Loop::Loop(IRContext* context, DominatorAnalysis* dom_analysis,
207 BasicBlock* header, BasicBlock* continue_target,
208 BasicBlock* merge_target)
209 : context_(context),
210 loop_header_(header),
211 loop_continue_(continue_target),
212 loop_merge_(merge_target),
213 loop_preheader_(nullptr),
214 parent_(nullptr),
215 loop_is_marked_for_removal_(false) {
216 assert(context);
217 assert(dom_analysis);
218 loop_preheader_ = FindLoopPreheader(dom_analysis);
219 loop_latch_ = FindLatchBlock();
220 }
221
FindLoopPreheader(DominatorAnalysis * dom_analysis)222 BasicBlock* Loop::FindLoopPreheader(DominatorAnalysis* dom_analysis) {
223 CFG* cfg = context_->cfg();
224 DominatorTree& dom_tree = dom_analysis->GetDomTree();
225 DominatorTreeNode* header_node = dom_tree.GetTreeNode(loop_header_);
226
227 // The loop predecessor.
228 BasicBlock* loop_pred = nullptr;
229
230 auto header_pred = cfg->preds(loop_header_->id());
231 for (uint32_t p_id : header_pred) {
232 DominatorTreeNode* node = dom_tree.GetTreeNode(p_id);
233 if (node && !dom_tree.Dominates(header_node, node)) {
234 // The predecessor is not part of the loop, so potential loop preheader.
235 if (loop_pred && node->bb_ != loop_pred) {
236 // If we saw 2 distinct predecessors that are outside the loop, we don't
237 // have a loop preheader.
238 return nullptr;
239 }
240 loop_pred = node->bb_;
241 }
242 }
243 // Safe guard against invalid code, SPIR-V spec forbids loop with the entry
244 // node as header.
245 assert(loop_pred && "The header node is the entry block ?");
246
247 // So we have a unique basic block that can enter this loop.
248 // If this loop is the unique successor of this block, then it is a loop
249 // preheader.
250 bool is_preheader = true;
251 uint32_t loop_header_id = loop_header_->id();
252 const auto* const_loop_pred = loop_pred;
253 const_loop_pred->ForEachSuccessorLabel(
254 [&is_preheader, loop_header_id](const uint32_t id) {
255 if (id != loop_header_id) is_preheader = false;
256 });
257 if (is_preheader) return loop_pred;
258 return nullptr;
259 }
260
IsInsideLoop(Instruction * inst) const261 bool Loop::IsInsideLoop(Instruction* inst) const {
262 const BasicBlock* parent_block = context_->get_instr_block(inst);
263 if (!parent_block) return false;
264 return IsInsideLoop(parent_block);
265 }
266
IsBasicBlockInLoopSlow(const BasicBlock * bb)267 bool Loop::IsBasicBlockInLoopSlow(const BasicBlock* bb) {
268 assert(bb->GetParent() && "The basic block does not belong to a function");
269 DominatorAnalysis* dom_analysis =
270 context_->GetDominatorAnalysis(bb->GetParent());
271 if (dom_analysis->IsReachable(bb) &&
272 !dom_analysis->Dominates(GetHeaderBlock(), bb))
273 return false;
274
275 return true;
276 }
277
GetOrCreatePreHeaderBlock()278 BasicBlock* Loop::GetOrCreatePreHeaderBlock() {
279 if (loop_preheader_) return loop_preheader_;
280
281 CFG* cfg = context_->cfg();
282 loop_header_ = cfg->SplitLoopHeader(loop_header_);
283 return loop_preheader_;
284 }
285
SetContinueBlock(BasicBlock * continue_block)286 void Loop::SetContinueBlock(BasicBlock* continue_block) {
287 assert(IsInsideLoop(continue_block));
288 loop_continue_ = continue_block;
289 }
290
SetLatchBlock(BasicBlock * latch)291 void Loop::SetLatchBlock(BasicBlock* latch) {
292 #ifndef NDEBUG
293 assert(latch->GetParent() && "The basic block does not belong to a function");
294
295 const auto* const_latch = latch;
296 const_latch->ForEachSuccessorLabel([this](uint32_t id) {
297 assert((!IsInsideLoop(id) || id == GetHeaderBlock()->id()) &&
298 "A predecessor of the continue block does not belong to the loop");
299 });
300 #endif // NDEBUG
301 assert(IsInsideLoop(latch) && "The continue block is not in the loop");
302
303 SetLatchBlockImpl(latch);
304 }
305
SetMergeBlock(BasicBlock * merge)306 void Loop::SetMergeBlock(BasicBlock* merge) {
307 #ifndef NDEBUG
308 assert(merge->GetParent() && "The basic block does not belong to a function");
309 #endif // NDEBUG
310 assert(!IsInsideLoop(merge) && "The merge block is in the loop");
311
312 SetMergeBlockImpl(merge);
313 if (GetHeaderBlock()->GetLoopMergeInst()) {
314 UpdateLoopMergeInst();
315 }
316 }
317
SetPreHeaderBlock(BasicBlock * preheader)318 void Loop::SetPreHeaderBlock(BasicBlock* preheader) {
319 if (preheader) {
320 assert(!IsInsideLoop(preheader) && "The preheader block is in the loop");
321 assert(preheader->tail()->opcode() == SpvOpBranch &&
322 "The preheader block does not unconditionally branch to the header "
323 "block");
324 assert(preheader->tail()->GetSingleWordOperand(0) ==
325 GetHeaderBlock()->id() &&
326 "The preheader block does not unconditionally branch to the header "
327 "block");
328 }
329 loop_preheader_ = preheader;
330 }
331
FindLatchBlock()332 BasicBlock* Loop::FindLatchBlock() {
333 CFG* cfg = context_->cfg();
334
335 DominatorAnalysis* dominator_analysis =
336 context_->GetDominatorAnalysis(loop_header_->GetParent());
337
338 // Look at the predecessors of the loop header to find a predecessor block
339 // which is dominated by the loop continue target. There should only be one
340 // block which meets this criteria and this is the latch block, as per the
341 // SPIR-V spec.
342 for (uint32_t block_id : cfg->preds(loop_header_->id())) {
343 if (dominator_analysis->Dominates(loop_continue_->id(), block_id)) {
344 return cfg->block(block_id);
345 }
346 }
347
348 assert(
349 false &&
350 "Every loop should have a latch block dominated by the continue target");
351 return nullptr;
352 }
353
GetExitBlocks(std::unordered_set<uint32_t> * exit_blocks) const354 void Loop::GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const {
355 CFG* cfg = context_->cfg();
356 exit_blocks->clear();
357
358 for (uint32_t bb_id : GetBlocks()) {
359 const BasicBlock* bb = cfg->block(bb_id);
360 bb->ForEachSuccessorLabel([exit_blocks, this](uint32_t succ) {
361 if (!IsInsideLoop(succ)) {
362 exit_blocks->insert(succ);
363 }
364 });
365 }
366 }
367
GetMergingBlocks(std::unordered_set<uint32_t> * merging_blocks) const368 void Loop::GetMergingBlocks(
369 std::unordered_set<uint32_t>* merging_blocks) const {
370 assert(GetMergeBlock() && "This loop is not structured");
371 CFG* cfg = context_->cfg();
372 merging_blocks->clear();
373
374 std::stack<const BasicBlock*> to_visit;
375 to_visit.push(GetMergeBlock());
376 while (!to_visit.empty()) {
377 const BasicBlock* bb = to_visit.top();
378 to_visit.pop();
379 merging_blocks->insert(bb->id());
380 for (uint32_t pred_id : cfg->preds(bb->id())) {
381 if (!IsInsideLoop(pred_id) && !merging_blocks->count(pred_id)) {
382 to_visit.push(cfg->block(pred_id));
383 }
384 }
385 }
386 }
387
388 namespace {
389
IsBasicBlockSafeToClone(IRContext * context,BasicBlock * bb)390 static inline bool IsBasicBlockSafeToClone(IRContext* context, BasicBlock* bb) {
391 for (Instruction& inst : *bb) {
392 if (!inst.IsBranch() && !context->IsCombinatorInstruction(&inst))
393 return false;
394 }
395
396 return true;
397 }
398
399 } // namespace
400
IsSafeToClone() const401 bool Loop::IsSafeToClone() const {
402 CFG& cfg = *context_->cfg();
403
404 for (uint32_t bb_id : GetBlocks()) {
405 BasicBlock* bb = cfg.block(bb_id);
406 assert(bb);
407 if (!IsBasicBlockSafeToClone(context_, bb)) return false;
408 }
409
410 // Look at the merge construct.
411 if (GetHeaderBlock()->GetLoopMergeInst()) {
412 std::unordered_set<uint32_t> blocks;
413 GetMergingBlocks(&blocks);
414 blocks.erase(GetMergeBlock()->id());
415 for (uint32_t bb_id : blocks) {
416 BasicBlock* bb = cfg.block(bb_id);
417 assert(bb);
418 if (!IsBasicBlockSafeToClone(context_, bb)) return false;
419 }
420 }
421
422 return true;
423 }
424
IsLCSSA() const425 bool Loop::IsLCSSA() const {
426 CFG* cfg = context_->cfg();
427 analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();
428
429 std::unordered_set<uint32_t> exit_blocks;
430 GetExitBlocks(&exit_blocks);
431
432 // Declare ir_context so we can capture context_ in the below lambda
433 IRContext* ir_context = context_;
434
435 for (uint32_t bb_id : GetBlocks()) {
436 for (Instruction& insn : *cfg->block(bb_id)) {
437 // All uses must be either:
438 // - In the loop;
439 // - In an exit block and in a phi instruction.
440 if (!def_use_mgr->WhileEachUser(
441 &insn,
442 [&exit_blocks, ir_context, this](Instruction* use) -> bool {
443 BasicBlock* parent = ir_context->get_instr_block(use);
444 assert(parent && "Invalid analysis");
445 if (IsInsideLoop(parent)) return true;
446 if (use->opcode() != SpvOpPhi) return false;
447 return exit_blocks.count(parent->id());
448 }))
449 return false;
450 }
451 }
452 return true;
453 }
454
ShouldHoistInstruction(IRContext * context,Instruction * inst)455 bool Loop::ShouldHoistInstruction(IRContext* context, Instruction* inst) {
456 return AreAllOperandsOutsideLoop(context, inst) &&
457 inst->IsOpcodeCodeMotionSafe();
458 }
459
AreAllOperandsOutsideLoop(IRContext * context,Instruction * inst)460 bool Loop::AreAllOperandsOutsideLoop(IRContext* context, Instruction* inst) {
461 analysis::DefUseManager* def_use_mgr = context->get_def_use_mgr();
462 bool all_outside_loop = true;
463
464 const std::function<void(uint32_t*)> operand_outside_loop =
465 [this, &def_use_mgr, &all_outside_loop](uint32_t* id) {
466 if (this->IsInsideLoop(def_use_mgr->GetDef(*id))) {
467 all_outside_loop = false;
468 return;
469 }
470 };
471
472 inst->ForEachInId(operand_outside_loop);
473 return all_outside_loop;
474 }
475
ComputeLoopStructuredOrder(std::vector<BasicBlock * > * ordered_loop_blocks,bool include_pre_header,bool include_merge) const476 void Loop::ComputeLoopStructuredOrder(
477 std::vector<BasicBlock*>* ordered_loop_blocks, bool include_pre_header,
478 bool include_merge) const {
479 CFG& cfg = *context_->cfg();
480
481 // Reserve the memory: all blocks in the loop + extra if needed.
482 ordered_loop_blocks->reserve(GetBlocks().size() + include_pre_header +
483 include_merge);
484
485 if (include_pre_header && GetPreHeaderBlock())
486 ordered_loop_blocks->push_back(loop_preheader_);
487
488 bool is_shader =
489 context_->get_feature_mgr()->HasCapability(SpvCapabilityShader);
490 if (!is_shader) {
491 cfg.ForEachBlockInReversePostOrder(
492 loop_header_, [ordered_loop_blocks, this](BasicBlock* bb) {
493 if (IsInsideLoop(bb)) ordered_loop_blocks->push_back(bb);
494 });
495 } else {
496 // If this is a shader, it is possible that there are unreachable merge and
497 // continue blocks that must be copied to retain the structured order.
498 // The structured order will include these.
499 std::list<BasicBlock*> order;
500 cfg.ComputeStructuredOrder(loop_header_->GetParent(), loop_header_, &order);
501 for (BasicBlock* bb : order) {
502 if (bb == GetMergeBlock()) {
503 break;
504 }
505 ordered_loop_blocks->push_back(bb);
506 }
507 }
508 if (include_merge && GetMergeBlock())
509 ordered_loop_blocks->push_back(loop_merge_);
510 }
511
LoopDescriptor(IRContext * context,const Function * f)512 LoopDescriptor::LoopDescriptor(IRContext* context, const Function* f)
513 : loops_(), placeholder_top_loop_(nullptr) {
514 PopulateList(context, f);
515 }
516
~LoopDescriptor()517 LoopDescriptor::~LoopDescriptor() { ClearLoops(); }
518
PopulateList(IRContext * context,const Function * f)519 void LoopDescriptor::PopulateList(IRContext* context, const Function* f) {
520 DominatorAnalysis* dom_analysis = context->GetDominatorAnalysis(f);
521
522 ClearLoops();
523
524 // Post-order traversal of the dominator tree to find all the OpLoopMerge
525 // instructions.
526 DominatorTree& dom_tree = dom_analysis->GetDomTree();
527 for (DominatorTreeNode& node :
528 make_range(dom_tree.post_begin(), dom_tree.post_end())) {
529 Instruction* merge_inst = node.bb_->GetLoopMergeInst();
530 if (merge_inst) {
531 bool all_backedge_unreachable = true;
532 for (uint32_t pid : context->cfg()->preds(node.bb_->id())) {
533 if (dom_analysis->IsReachable(pid) &&
534 dom_analysis->Dominates(node.bb_->id(), pid)) {
535 all_backedge_unreachable = false;
536 break;
537 }
538 }
539 if (all_backedge_unreachable)
540 continue; // ignore this one, we actually never branch back.
541
542 // The id of the merge basic block of this loop.
543 uint32_t merge_bb_id = merge_inst->GetSingleWordOperand(0);
544
545 // The id of the continue basic block of this loop.
546 uint32_t continue_bb_id = merge_inst->GetSingleWordOperand(1);
547
548 // The merge target of this loop.
549 BasicBlock* merge_bb = context->cfg()->block(merge_bb_id);
550
551 // The continue target of this loop.
552 BasicBlock* continue_bb = context->cfg()->block(continue_bb_id);
553
554 // The basic block containing the merge instruction.
555 BasicBlock* header_bb = context->get_instr_block(merge_inst);
556
557 // Add the loop to the list of all the loops in the function.
558 Loop* current_loop =
559 new Loop(context, dom_analysis, header_bb, continue_bb, merge_bb);
560 loops_.push_back(current_loop);
561
562 // We have a bottom-up construction, so if this loop has nested-loops,
563 // they are by construction at the tail of the loop list.
564 for (auto itr = loops_.rbegin() + 1; itr != loops_.rend(); ++itr) {
565 Loop* previous_loop = *itr;
566
567 // If the loop already has a parent, then it has been processed.
568 if (previous_loop->HasParent()) continue;
569
570 // If the current loop does not dominates the previous loop then it is
571 // not nested loop.
572 if (!dom_analysis->Dominates(header_bb,
573 previous_loop->GetHeaderBlock()))
574 continue;
575 // If the current loop merge dominates the previous loop then it is
576 // not nested loop.
577 if (dom_analysis->Dominates(merge_bb, previous_loop->GetHeaderBlock()))
578 continue;
579
580 current_loop->AddNestedLoop(previous_loop);
581 }
582 DominatorTreeNode* dom_merge_node = dom_tree.GetTreeNode(merge_bb);
583 for (DominatorTreeNode& loop_node :
584 make_range(node.df_begin(), node.df_end())) {
585 // Check if we are in the loop.
586 if (dom_tree.Dominates(dom_merge_node, &loop_node)) continue;
587 current_loop->AddBasicBlock(loop_node.bb_);
588 basic_block_to_loop_.insert(
589 std::make_pair(loop_node.bb_->id(), current_loop));
590 }
591 }
592 }
593 for (Loop* loop : loops_) {
594 if (!loop->HasParent()) placeholder_top_loop_.nested_loops_.push_back(loop);
595 }
596 }
597
GetLoopsInBinaryLayoutOrder()598 std::vector<Loop*> LoopDescriptor::GetLoopsInBinaryLayoutOrder() {
599 std::vector<uint32_t> ids{};
600
601 for (size_t i = 0; i < NumLoops(); ++i) {
602 ids.push_back(GetLoopByIndex(i).GetHeaderBlock()->id());
603 }
604
605 std::vector<Loop*> loops{};
606 if (!ids.empty()) {
607 auto function = GetLoopByIndex(0).GetHeaderBlock()->GetParent();
608 for (const auto& block : *function) {
609 auto block_id = block.id();
610
611 auto element = std::find(std::begin(ids), std::end(ids), block_id);
612 if (element != std::end(ids)) {
613 loops.push_back(&GetLoopByIndex(element - std::begin(ids)));
614 }
615 }
616 }
617
618 return loops;
619 }
620
FindConditionBlock() const621 BasicBlock* Loop::FindConditionBlock() const {
622 if (!loop_merge_) {
623 return nullptr;
624 }
625 BasicBlock* condition_block = nullptr;
626
627 uint32_t in_loop_pred = 0;
628 for (uint32_t p : context_->cfg()->preds(loop_merge_->id())) {
629 if (IsInsideLoop(p)) {
630 if (in_loop_pred) {
631 // 2 in-loop predecessors.
632 return nullptr;
633 }
634 in_loop_pred = p;
635 }
636 }
637 if (!in_loop_pred) {
638 // Merge block is unreachable.
639 return nullptr;
640 }
641
642 BasicBlock* bb = context_->cfg()->block(in_loop_pred);
643
644 if (!bb) return nullptr;
645
646 const Instruction& branch = *bb->ctail();
647
648 // Make sure the branch is a conditional branch.
649 if (branch.opcode() != SpvOpBranchConditional) return nullptr;
650
651 // Make sure one of the two possible branches is to the merge block.
652 if (branch.GetSingleWordInOperand(1) == loop_merge_->id() ||
653 branch.GetSingleWordInOperand(2) == loop_merge_->id()) {
654 condition_block = bb;
655 }
656
657 return condition_block;
658 }
659
FindNumberOfIterations(const Instruction * induction,const Instruction * branch_inst,size_t * iterations_out,int64_t * step_value_out,int64_t * init_value_out) const660 bool Loop::FindNumberOfIterations(const Instruction* induction,
661 const Instruction* branch_inst,
662 size_t* iterations_out,
663 int64_t* step_value_out,
664 int64_t* init_value_out) const {
665 // From the branch instruction find the branch condition.
666 analysis::DefUseManager* def_use_manager = context_->get_def_use_mgr();
667
668 // Condition instruction from the OpConditionalBranch.
669 Instruction* condition =
670 def_use_manager->GetDef(branch_inst->GetSingleWordOperand(0));
671
672 assert(IsSupportedCondition(condition->opcode()));
673
674 // Get the constant manager from the ir context.
675 analysis::ConstantManager* const_manager = context_->get_constant_mgr();
676
677 // Find the constant value used by the condition variable. Exit out if it
678 // isn't a constant int.
679 const analysis::Constant* upper_bound =
680 const_manager->FindDeclaredConstant(condition->GetSingleWordOperand(3));
681 if (!upper_bound) return false;
682
683 // Must be integer because of the opcode on the condition.
684 const analysis::Integer* type = upper_bound->type()->AsInteger();
685
686 if (!type || type->width() > 64) {
687 return false;
688 }
689
690 int64_t condition_value = type->IsSigned()
691 ? upper_bound->GetSignExtendedValue()
692 : upper_bound->GetZeroExtendedValue();
693
694 // Find the instruction which is stepping through the loop.
695 //
696 // GetInductionStepOperation returns nullptr if |step_inst| is OpConstantNull.
697 Instruction* step_inst = GetInductionStepOperation(induction);
698 if (!step_inst) return false;
699
700 // Find the constant value used by the condition variable.
701 const analysis::Constant* step_constant =
702 const_manager->FindDeclaredConstant(step_inst->GetSingleWordOperand(3));
703 if (!step_constant) return false;
704
705 // Must be integer because of the opcode on the condition.
706 int64_t step_value = 0;
707
708 const analysis::Integer* step_type =
709 step_constant->AsIntConstant()->type()->AsInteger();
710
711 if (step_type->IsSigned()) {
712 step_value = step_constant->AsIntConstant()->GetS32BitValue();
713 } else {
714 step_value = step_constant->AsIntConstant()->GetU32BitValue();
715 }
716
717 // If this is a subtraction step we should negate the step value.
718 if (step_inst->opcode() == SpvOp::SpvOpISub) {
719 step_value = -step_value;
720 }
721
722 // Find the inital value of the loop and make sure it is a constant integer.
723 int64_t init_value = 0;
724 if (!GetInductionInitValue(induction, &init_value)) return false;
725
726 // If iterations is non null then store the value in that.
727 int64_t num_itrs = GetIterations(condition->opcode(), condition_value,
728 init_value, step_value);
729
730 // If the loop body will not be reached return false.
731 if (num_itrs <= 0) {
732 return false;
733 }
734
735 if (iterations_out) {
736 assert(static_cast<size_t>(num_itrs) <= std::numeric_limits<size_t>::max());
737 *iterations_out = static_cast<size_t>(num_itrs);
738 }
739
740 if (step_value_out) {
741 *step_value_out = step_value;
742 }
743
744 if (init_value_out) {
745 *init_value_out = init_value;
746 }
747
748 return true;
749 }
750
751 // We retrieve the number of iterations using the following formula, diff /
752 // |step_value| where diff is calculated differently according to the
753 // |condition| and uses the |condition_value| and |init_value|. If diff /
754 // |step_value| is NOT cleanly divisable then we add one to the sum.
GetIterations(SpvOp condition,int64_t condition_value,int64_t init_value,int64_t step_value) const755 int64_t Loop::GetIterations(SpvOp condition, int64_t condition_value,
756 int64_t init_value, int64_t step_value) const {
757 int64_t diff = 0;
758
759 switch (condition) {
760 case SpvOp::SpvOpSLessThan:
761 case SpvOp::SpvOpULessThan: {
762 // If the condition is not met to begin with the loop will never iterate.
763 if (!(init_value < condition_value)) return 0;
764
765 diff = condition_value - init_value;
766
767 // If the operation is a less then operation then the diff and step must
768 // have the same sign otherwise the induction will never cross the
769 // condition (either never true or always true).
770 if ((diff < 0 && step_value > 0) || (diff > 0 && step_value < 0)) {
771 return 0;
772 }
773
774 break;
775 }
776 case SpvOp::SpvOpSGreaterThan:
777 case SpvOp::SpvOpUGreaterThan: {
778 // If the condition is not met to begin with the loop will never iterate.
779 if (!(init_value > condition_value)) return 0;
780
781 diff = init_value - condition_value;
782
783 // If the operation is a greater than operation then the diff and step
784 // must have opposite signs. Otherwise the condition will always be true
785 // or will never be true.
786 if ((diff < 0 && step_value < 0) || (diff > 0 && step_value > 0)) {
787 return 0;
788 }
789
790 break;
791 }
792
793 case SpvOp::SpvOpSGreaterThanEqual:
794 case SpvOp::SpvOpUGreaterThanEqual: {
795 // If the condition is not met to begin with the loop will never iterate.
796 if (!(init_value >= condition_value)) return 0;
797
798 // We subract one to make it the same as SpvOpGreaterThan as it is
799 // functionally equivalent.
800 diff = init_value - (condition_value - 1);
801
802 // If the operation is a greater than operation then the diff and step
803 // must have opposite signs. Otherwise the condition will always be true
804 // or will never be true.
805 if ((diff > 0 && step_value > 0) || (diff < 0 && step_value < 0)) {
806 return 0;
807 }
808
809 break;
810 }
811
812 case SpvOp::SpvOpSLessThanEqual:
813 case SpvOp::SpvOpULessThanEqual: {
814 // If the condition is not met to begin with the loop will never iterate.
815 if (!(init_value <= condition_value)) return 0;
816
817 // We add one to make it the same as SpvOpLessThan as it is functionally
818 // equivalent.
819 diff = (condition_value + 1) - init_value;
820
821 // If the operation is a less than operation then the diff and step must
822 // have the same sign otherwise the induction will never cross the
823 // condition (either never true or always true).
824 if ((diff < 0 && step_value > 0) || (diff > 0 && step_value < 0)) {
825 return 0;
826 }
827
828 break;
829 }
830
831 default:
832 assert(false &&
833 "Could not retrieve number of iterations from the loop condition. "
834 "Condition is not supported.");
835 }
836
837 // Take the abs of - step values.
838 step_value = llabs(step_value);
839 diff = llabs(diff);
840 int64_t result = diff / step_value;
841
842 if (diff % step_value != 0) {
843 result += 1;
844 }
845 return result;
846 }
847
848 // Returns the list of induction variables within the loop.
GetInductionVariables(std::vector<Instruction * > & induction_variables) const849 void Loop::GetInductionVariables(
850 std::vector<Instruction*>& induction_variables) const {
851 for (Instruction& inst : *loop_header_) {
852 if (inst.opcode() == SpvOp::SpvOpPhi) {
853 induction_variables.push_back(&inst);
854 }
855 }
856 }
857
FindConditionVariable(const BasicBlock * condition_block) const858 Instruction* Loop::FindConditionVariable(
859 const BasicBlock* condition_block) const {
860 // Find the branch instruction.
861 const Instruction& branch_inst = *condition_block->ctail();
862
863 Instruction* induction = nullptr;
864 // Verify that the branch instruction is a conditional branch.
865 if (branch_inst.opcode() == SpvOp::SpvOpBranchConditional) {
866 // From the branch instruction find the branch condition.
867 analysis::DefUseManager* def_use_manager = context_->get_def_use_mgr();
868
869 // Find the instruction representing the condition used in the conditional
870 // branch.
871 Instruction* condition =
872 def_use_manager->GetDef(branch_inst.GetSingleWordOperand(0));
873
874 // Ensure that the condition is a less than operation.
875 if (condition && IsSupportedCondition(condition->opcode())) {
876 // The left hand side operand of the operation.
877 Instruction* variable_inst =
878 def_use_manager->GetDef(condition->GetSingleWordOperand(2));
879
880 // Make sure the variable instruction used is a phi.
881 if (!variable_inst || variable_inst->opcode() != SpvOpPhi) return nullptr;
882
883 // Make sure the phi instruction only has two incoming blocks. Each
884 // incoming block will be represented by two in operands in the phi
885 // instruction, the value and the block which that value came from. We
886 // assume the cannocalised phi will have two incoming values, one from the
887 // preheader and one from the continue block.
888 size_t max_supported_operands = 4;
889 if (variable_inst->NumInOperands() == max_supported_operands) {
890 // The operand index of the first incoming block label.
891 uint32_t operand_label_1 = 1;
892
893 // The operand index of the second incoming block label.
894 uint32_t operand_label_2 = 3;
895
896 // Make sure one of them is the preheader.
897 if (!IsInsideLoop(
898 variable_inst->GetSingleWordInOperand(operand_label_1)) &&
899 !IsInsideLoop(
900 variable_inst->GetSingleWordInOperand(operand_label_2))) {
901 return nullptr;
902 }
903
904 // And make sure that the other is the latch block.
905 if (variable_inst->GetSingleWordInOperand(operand_label_1) !=
906 loop_latch_->id() &&
907 variable_inst->GetSingleWordInOperand(operand_label_2) !=
908 loop_latch_->id()) {
909 return nullptr;
910 }
911 } else {
912 return nullptr;
913 }
914
915 if (!FindNumberOfIterations(variable_inst, &branch_inst, nullptr))
916 return nullptr;
917 induction = variable_inst;
918 }
919 }
920
921 return induction;
922 }
923
CreatePreHeaderBlocksIfMissing()924 bool LoopDescriptor::CreatePreHeaderBlocksIfMissing() {
925 auto modified = false;
926
927 for (auto& loop : *this) {
928 if (!loop.GetPreHeaderBlock()) {
929 modified = true;
930 // TODO(1841): Handle failure to create pre-header.
931 loop.GetOrCreatePreHeaderBlock();
932 }
933 }
934
935 return modified;
936 }
937
938 // Add and remove loops which have been marked for addition and removal to
939 // maintain the state of the loop descriptor class.
PostModificationCleanup()940 void LoopDescriptor::PostModificationCleanup() {
941 LoopContainerType loops_to_remove_;
942 for (Loop* loop : loops_) {
943 if (loop->IsMarkedForRemoval()) {
944 loops_to_remove_.push_back(loop);
945 if (loop->HasParent()) {
946 loop->GetParent()->RemoveChildLoop(loop);
947 }
948 }
949 }
950
951 for (Loop* loop : loops_to_remove_) {
952 loops_.erase(std::find(loops_.begin(), loops_.end(), loop));
953 delete loop;
954 }
955
956 for (auto& pair : loops_to_add_) {
957 Loop* parent = pair.first;
958 std::unique_ptr<Loop> loop = std::move(pair.second);
959
960 if (parent) {
961 loop->SetParent(nullptr);
962 parent->AddNestedLoop(loop.get());
963
964 for (uint32_t block_id : loop->GetBlocks()) {
965 parent->AddBasicBlock(block_id);
966 }
967 }
968
969 loops_.emplace_back(loop.release());
970 }
971
972 loops_to_add_.clear();
973 }
974
ClearLoops()975 void LoopDescriptor::ClearLoops() {
976 for (Loop* loop : loops_) {
977 delete loop;
978 }
979 loops_.clear();
980 }
981
982 // Adds a new loop nest to the descriptor set.
AddLoopNest(std::unique_ptr<Loop> new_loop)983 Loop* LoopDescriptor::AddLoopNest(std::unique_ptr<Loop> new_loop) {
984 Loop* loop = new_loop.release();
985 if (!loop->HasParent()) placeholder_top_loop_.nested_loops_.push_back(loop);
986 // Iterate from inner to outer most loop, adding basic block to loop mapping
987 // as we go.
988 for (Loop& current_loop :
989 make_range(iterator::begin(loop), iterator::end(nullptr))) {
990 loops_.push_back(¤t_loop);
991 for (uint32_t bb_id : current_loop.GetBlocks())
992 basic_block_to_loop_.insert(std::make_pair(bb_id, ¤t_loop));
993 }
994
995 return loop;
996 }
997
RemoveLoop(Loop * loop)998 void LoopDescriptor::RemoveLoop(Loop* loop) {
999 Loop* parent = loop->GetParent() ? loop->GetParent() : &placeholder_top_loop_;
1000 parent->nested_loops_.erase(std::find(parent->nested_loops_.begin(),
1001 parent->nested_loops_.end(), loop));
1002 std::for_each(
1003 loop->nested_loops_.begin(), loop->nested_loops_.end(),
1004 [loop](Loop* sub_loop) { sub_loop->SetParent(loop->GetParent()); });
1005 parent->nested_loops_.insert(parent->nested_loops_.end(),
1006 loop->nested_loops_.begin(),
1007 loop->nested_loops_.end());
1008 for (uint32_t bb_id : loop->GetBlocks()) {
1009 Loop* l = FindLoopForBasicBlock(bb_id);
1010 if (l == loop) {
1011 SetBasicBlockToLoop(bb_id, l->GetParent());
1012 } else {
1013 ForgetBasicBlock(bb_id);
1014 }
1015 }
1016
1017 LoopContainerType::iterator it =
1018 std::find(loops_.begin(), loops_.end(), loop);
1019 assert(it != loops_.end());
1020 delete loop;
1021 loops_.erase(it);
1022 }
1023
1024 } // namespace opt
1025 } // namespace spvtools
1026