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#ifndef SOURCE_OPT_LOOP_DESCRIPTOR_H_
16#define SOURCE_OPT_LOOP_DESCRIPTOR_H_
17
18#include <algorithm>
19#include <cstdint>
20#include <map>
21#include <memory>
22#include <unordered_map>
23#include <unordered_set>
24#include <utility>
25#include <vector>
26
27#include "source/opt/basic_block.h"
28#include "source/opt/dominator_analysis.h"
29#include "source/opt/module.h"
30#include "source/opt/tree_iterator.h"
31
32namespace spvtools {
33namespace opt {
34
35class IRContext;
36class CFG;
37class LoopDescriptor;
38
39// A class to represent and manipulate a loop in structured control flow.
40class Loop {
41 // The type used to represent nested child loops.
42 using ChildrenList = std::vector<Loop*>;
43
44 public:
45 using iterator = ChildrenList::iterator;
46 using const_iterator = ChildrenList::const_iterator;
47 using BasicBlockListTy = std::unordered_set<uint32_t>;
48
49 explicit Loop(IRContext* context)
50 : context_(context),
51 loop_header_(nullptr),
52 loop_continue_(nullptr),
53 loop_merge_(nullptr),
54 loop_preheader_(nullptr),
55 loop_latch_(nullptr),
56 parent_(nullptr),
57 loop_is_marked_for_removal_(false) {}
58
59 Loop(IRContext* context, DominatorAnalysis* analysis, BasicBlock* header,
60 BasicBlock* continue_target, BasicBlock* merge_target);
61
62 // Iterators over the immediate sub-loops.
63 inline iterator begin() { return nested_loops_.begin(); }
64 inline iterator end() { return nested_loops_.end(); }
65 inline const_iterator begin() const { return cbegin(); }
66 inline const_iterator end() const { return cend(); }
67 inline const_iterator cbegin() const { return nested_loops_.begin(); }
68 inline const_iterator cend() const { return nested_loops_.end(); }
69
70 // Returns the header (first basic block of the loop). This block contains the
71 // OpLoopMerge instruction.
72 inline BasicBlock* GetHeaderBlock() { return loop_header_; }
73 inline const BasicBlock* GetHeaderBlock() const { return loop_header_; }
74 inline void SetHeaderBlock(BasicBlock* header) { loop_header_ = header; }
75
76 // Updates the OpLoopMerge instruction to reflect the current state of the
77 // loop.
78 inline void UpdateLoopMergeInst() {
79 assert(GetHeaderBlock()->GetLoopMergeInst() &&
80 "The loop is not structured");
81 Instruction* merge_inst = GetHeaderBlock()->GetLoopMergeInst();
82 merge_inst->SetInOperand(0, {GetMergeBlock()->id()});
83 }
84
85 // Returns the continue target basic block. This is the block designated as
86 // the continue target by the OpLoopMerge instruction.
87 inline BasicBlock* GetContinueBlock() { return loop_continue_; }
88 inline const BasicBlock* GetContinueBlock() const { return loop_continue_; }
89
90 // Returns the latch basic block (basic block that holds the back-edge).
91 // These functions return nullptr if the loop is not structured (i.e. if it
92 // has more than one backedge).
93 inline BasicBlock* GetLatchBlock() { return loop_latch_; }
94 inline const BasicBlock* GetLatchBlock() const { return loop_latch_; }
95
96 // Sets |latch| as the loop unique block branching back to the header.
97 // A latch block must have the following properties:
98 // - |latch| must be in the loop;
99 // - must be the only block branching back to the header block.
100 void SetLatchBlock(BasicBlock* latch);
101
102 // Sets |continue_block| as the continue block of the loop. This should be the
103 // continue target of the OpLoopMerge and should dominate the latch block.
104 void SetContinueBlock(BasicBlock* continue_block);
105
106 // Returns the basic block which marks the end of the loop.
107 // These functions return nullptr if the loop is not structured.
108 inline BasicBlock* GetMergeBlock() { return loop_merge_; }
109 inline const BasicBlock* GetMergeBlock() const { return loop_merge_; }
110 // Sets |merge| as the loop merge block. A merge block must have the following
111 // properties:
112 // - |merge| must not be in the loop;
113 // - all its predecessors must be in the loop.
114 // - it must not be already used as merge block.
115 // If the loop has an OpLoopMerge in its header, this instruction is also
116 // updated.
117 void SetMergeBlock(BasicBlock* merge);
118
119 // Returns the loop pre-header, nullptr means that the loop predecessor does
120 // not qualify as a preheader.
121 // The preheader is the unique predecessor that:
122 // - Dominates the loop header;
123 // - Has only the loop header as successor.
124 inline BasicBlock* GetPreHeaderBlock() { return loop_preheader_; }
125
126 // Returns the loop pre-header.
127 inline const BasicBlock* GetPreHeaderBlock() const { return loop_preheader_; }
128 // Sets |preheader| as the loop preheader block. A preheader block must have
129 // the following properties:
130 // - |merge| must not be in the loop;
131 // - have an unconditional branch to the loop header.
132 void SetPreHeaderBlock(BasicBlock* preheader);
133
134 // Returns the loop pre-header, if there is no suitable preheader it will be
135 // created. Returns |nullptr| if it fails to create the preheader.
136 BasicBlock* GetOrCreatePreHeaderBlock();
137
138 // Returns true if this loop contains any nested loops.
139 inline bool HasNestedLoops() const { return nested_loops_.size() != 0; }
140
141 // Clears and fills |exit_blocks| with all basic blocks that are not in the
142 // loop and has at least one predecessor in the loop.
143 void GetExitBlocks(std::unordered_set<uint32_t>* exit_blocks) const;
144
145 // Clears and fills |merging_blocks| with all basic blocks that are
146 // post-dominated by the merge block. The merge block must exist.
147 // The set |merging_blocks| will only contain the merge block if it is
148 // unreachable.
149 void GetMergingBlocks(std::unordered_set<uint32_t>* merging_blocks) const;
150
151 // Returns true if the loop is in a Loop Closed SSA form.
152 // In LCSSA form, all in-loop definitions are used in the loop or in phi
153 // instructions in the loop exit blocks.
154 bool IsLCSSA() const;
155
156 // Returns the depth of this loop in the loop nest.
157 // The outer-most loop has a depth of 1.
158 inline size_t GetDepth() const {
159 size_t lvl = 1;
160 for (const Loop* loop = GetParent(); loop; loop = loop->GetParent()) lvl++;
161 return lvl;
162 }
163
164 inline size_t NumImmediateChildren() const { return nested_loops_.size(); }
165
166 inline bool HasChildren() const { return !nested_loops_.empty(); }
167 // Adds |nested| as a nested loop of this loop. Automatically register |this|
168 // as the parent of |nested|.
169 inline void AddNestedLoop(Loop* nested) {
170 assert(!nested->GetParent() && "The loop has another parent.");
171 nested_loops_.push_back(nested);
172 nested->SetParent(this);
173 }
174
175 inline Loop* GetParent() { return parent_; }
176 inline const Loop* GetParent() const { return parent_; }
177
178 inline bool HasParent() const { return parent_; }
179
180 // Returns true if this loop is itself nested within another loop.
181 inline bool IsNested() const { return parent_ != nullptr; }
182
183 // Returns the set of all basic blocks contained within the loop. Will be all
184 // BasicBlocks dominated by the header which are not also dominated by the
185 // loop merge block.
186 inline const BasicBlockListTy& GetBlocks() const {
187 return loop_basic_blocks_;
188 }
189
190 // Returns true if the basic block |bb| is inside this loop.
191 inline bool IsInsideLoop(const BasicBlock* bb) const {
192 return IsInsideLoop(bb->id());
193 }
194
195 // Returns true if the basic block id |bb_id| is inside this loop.
196 inline bool IsInsideLoop(uint32_t bb_id) const {
197 return loop_basic_blocks_.count(bb_id);
198 }
199
200 // Returns true if the instruction |inst| is inside this loop.
201 bool IsInsideLoop(Instruction* inst) const;
202
203 // Adds the Basic Block |bb| to this loop and its parents.
204 void AddBasicBlock(const BasicBlock* bb) { AddBasicBlock(bb->id()); }
205
206 // Adds the Basic Block with |id| to this loop and its parents.
207 void AddBasicBlock(uint32_t id) {
208 for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {
209 loop->loop_basic_blocks_.insert(id);
210 }
211 }
212
213 // Removes the Basic Block id |bb_id| from this loop and its parents.
214 // It the user responsibility to make sure the removed block is not a merge,
215 // header or continue block.
216 void RemoveBasicBlock(uint32_t bb_id) {
217 for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {
218 loop->loop_basic_blocks_.erase(bb_id);
219 }
220 }
221
222 // Removes all the basic blocks from the set of basic blocks within the loop.
223 // This does not affect any of the stored pointers to the header, preheader,
224 // merge, or continue blocks.
225 void ClearBlocks() { loop_basic_blocks_.clear(); }
226
227 // Adds the Basic Block |bb| this loop and its parents.
228 void AddBasicBlockToLoop(const BasicBlock* bb) {
229 assert(IsBasicBlockInLoopSlow(bb) &&
230 "Basic block does not belong to the loop");
231
232 AddBasicBlock(bb);
233 }
234
235 // Returns the list of induction variables within the loop.
236 void GetInductionVariables(std::vector<Instruction*>& inductions) const;
237
238 // This function uses the |condition| to find the induction variable which is
239 // used by the loop condition within the loop. This only works if the loop is
240 // bound by a single condition and single induction variable.
241 Instruction* FindConditionVariable(const BasicBlock* condition) const;
242
243 // Returns the number of iterations within a loop when given the |induction|
244 // variable and the loop |condition| check. It stores the found number of
245 // iterations in the output parameter |iterations| and optionally, the step
246 // value in |step_value| and the initial value of the induction variable in
247 // |init_value|.
248 bool FindNumberOfIterations(const Instruction* induction,
249 const Instruction* condition, size_t* iterations,
250 int64_t* step_amount = nullptr,
251 int64_t* init_value = nullptr) const;
252
253 // Returns the value of the OpLoopMerge control operand as a bool. Loop
254 // control can be None(0), Unroll(1), or DontUnroll(2). This function returns
255 // true if it is set to Unroll.
256 inline bool HasUnrollLoopControl() const {
257 assert(loop_header_);
258 if (!loop_header_->GetLoopMergeInst()) return false;
259
260 return loop_header_->GetLoopMergeInst()->GetSingleWordOperand(2) == 1;
261 }
262
263 // Finds the conditional block with a branch to the merge and continue blocks
264 // within the loop body.
265 BasicBlock* FindConditionBlock() const;
266
267 // Remove the child loop form this loop.
268 inline void RemoveChildLoop(Loop* loop) {
269 nested_loops_.erase(
270 std::find(nested_loops_.begin(), nested_loops_.end(), loop));
271 loop->SetParent(nullptr);
272 }
273
274 // Mark this loop to be removed later by a call to
275 // LoopDescriptor::PostModificationCleanup.
276 inline void MarkLoopForRemoval() { loop_is_marked_for_removal_ = true; }
277
278 // Returns whether or not this loop has been marked for removal.
279 inline bool IsMarkedForRemoval() const { return loop_is_marked_for_removal_; }
280
281 // Returns true if all nested loops have been marked for removal.
282 inline bool AreAllChildrenMarkedForRemoval() const {
283 for (const Loop* child : nested_loops_) {
284 if (!child->IsMarkedForRemoval()) {
285 return false;
286 }
287 }
288 return true;
289 }
290
291 // Checks if the loop contains any instruction that will prevent it from being
292 // cloned. If the loop is structured, the merge construct is also considered.
293 bool IsSafeToClone() const;
294
295 // Sets the parent loop of this loop, that is, a loop which contains this loop
296 // as a nested child loop.
297 inline void SetParent(Loop* parent) { parent_ = parent; }
298
299 // Returns true is the instruction is invariant and safe to move wrt loop
300 bool ShouldHoistInstruction(IRContext* context, Instruction* inst);
301
302 // Returns true if all operands of inst are in basic blocks not contained in
303 // loop
304 bool AreAllOperandsOutsideLoop(IRContext* context, Instruction* inst);
305
306 // Extract the initial value from the |induction| variable and store it in
307 // |value|. If the function couldn't find the initial value of |induction|
308 // return false.
309 bool GetInductionInitValue(const Instruction* induction,
310 int64_t* value) const;
311
312 // Takes in a phi instruction |induction| and the loop |header| and returns
313 // the step operation of the loop.
314 Instruction* GetInductionStepOperation(const Instruction* induction) const;
315
316 // Returns true if we can deduce the number of loop iterations in the step
317 // operation |step|. IsSupportedCondition must also be true for the condition
318 // instruction.
319 bool IsSupportedStepOp(SpvOp step) const;
320
321 // Returns true if we can deduce the number of loop iterations in the
322 // condition operation |condition|. IsSupportedStepOp must also be true for
323 // the step instruction.
324 bool IsSupportedCondition(SpvOp condition) const;
325
326 // Creates the list of the loop's basic block in structured order and store
327 // the result in |ordered_loop_blocks|. If |include_pre_header| is true, the
328 // pre-header block will also be included at the beginning of the list if it
329 // exist. If |include_merge| is true, the merge block will also be included at
330 // the end of the list if it exist.
331 void ComputeLoopStructuredOrder(std::vector<BasicBlock*>* ordered_loop_blocks,
332 bool include_pre_header = false,
333 bool include_merge = false) const;
334
335 // Given the loop |condition|, |initial_value|, |step_value|, the trip count
336 // |number_of_iterations|, and the |unroll_factor| requested, get the new
337 // condition value for the residual loop.
338 static int64_t GetResidualConditionValue(SpvOp condition,
339 int64_t initial_value,
340 int64_t step_value,
341 size_t number_of_iterations,
342 size_t unroll_factor);
343
344 // Returns the condition instruction for entry into the loop
345 // Returns nullptr if it can't be found.
346 Instruction* GetConditionInst() const;
347
348 // Returns the context associated this loop.
349 IRContext* GetContext() const { return context_; }
350
351 // Looks at all the blocks with a branch to the header block to find one
352 // which is also dominated by the loop continue block. This block is the latch
353 // block. The specification mandates that this block should exist, therefore
354 // this function will assert if it is not found.
355 BasicBlock* FindLatchBlock();
356
357 private:
358 IRContext* context_;
359 // The block which marks the start of the loop.
360 BasicBlock* loop_header_;
361
362 // The block which begins the body of the loop.
363 BasicBlock* loop_continue_;
364
365 // The block which marks the end of the loop.
366 BasicBlock* loop_merge_;
367
368 // The block immediately before the loop header.
369 BasicBlock* loop_preheader_;
370
371 // The block containing the backedge to the loop header.
372 BasicBlock* loop_latch_;
373
374 // A parent of a loop is the loop which contains it as a nested child loop.
375 Loop* parent_;
376
377 // Nested child loops of this loop.
378 ChildrenList nested_loops_;
379
380 // A set of all the basic blocks which comprise the loop structure. Will be
381 // computed only when needed on demand.
382 BasicBlockListTy loop_basic_blocks_;
383
384 // Check that |bb| is inside the loop using domination property.
385 // Note: this is for assertion purposes only, IsInsideLoop should be used
386 // instead.
387 bool IsBasicBlockInLoopSlow(const BasicBlock* bb);
388
389 // Returns the loop preheader if it exists, returns nullptr otherwise.
390 BasicBlock* FindLoopPreheader(DominatorAnalysis* dom_analysis);
391
392 // Sets |latch| as the loop unique latch block. No checks are performed
393 // here.
394 inline void SetLatchBlockImpl(BasicBlock* latch) { loop_latch_ = latch; }
395 // Sets |merge| as the loop merge block. No checks are performed here.
396 inline void SetMergeBlockImpl(BasicBlock* merge) { loop_merge_ = merge; }
397
398 // Each differnt loop |condition| affects how we calculate the number of
399 // iterations using the |condition_value|, |init_value|, and |step_values| of
400 // the induction variable. This method will return the number of iterations in
401 // a loop with those values for a given |condition|.
402 int64_t GetIterations(SpvOp condition, int64_t condition_value,
403 int64_t init_value, int64_t step_value) const;
404
405 // This is to allow for loops to be removed mid iteration without invalidating
406 // the iterators.
407 bool loop_is_marked_for_removal_;
408
409 // This is only to allow LoopDescriptor::dummy_top_loop_ to add top level
410 // loops as child.
411 friend class LoopDescriptor;
412 friend class LoopUtils;
413};
414
415// Loop descriptions class for a given function.
416// For a given function, the class builds loop nests information.
417// The analysis expects a structured control flow.
418class LoopDescriptor {
419 public:
420 // Iterator interface (depth first postorder traversal).
421 using iterator = PostOrderTreeDFIterator<Loop>;
422 using const_iterator = PostOrderTreeDFIterator<const Loop>;
423
424 using pre_iterator = TreeDFIterator<Loop>;
425 using const_pre_iterator = TreeDFIterator<const Loop>;
426
427 // Creates a loop object for all loops found in |f|.
428 LoopDescriptor(IRContext* context, const Function* f);
429
430 // Disable copy constructor, to avoid double-free on destruction.
431 LoopDescriptor(const LoopDescriptor&) = delete;
432 // Move constructor.
433 LoopDescriptor(LoopDescriptor&& other) : dummy_top_loop_(nullptr) {
434 // We need to take ownership of the Loop objects in the other
435 // LoopDescriptor, to avoid double-free.
436 loops_ = std::move(other.loops_);
437 other.loops_.clear();
438 basic_block_to_loop_ = std::move(other.basic_block_to_loop_);
439 other.basic_block_to_loop_.clear();
440 dummy_top_loop_ = std::move(other.dummy_top_loop_);
441 }
442
443 // Destructor
444 ~LoopDescriptor();
445
446 // Returns the number of loops found in the function.
447 inline size_t NumLoops() const { return loops_.size(); }
448
449 // Returns the loop at a particular |index|. The |index| must be in bounds,
450 // check with NumLoops before calling.
451 inline Loop& GetLoopByIndex(size_t index) const {
452 assert(loops_.size() > index &&
453 "Index out of range (larger than loop count)");
454 return *loops_[index];
455 }
456
457 // Returns the loops in |this| in the order their headers appear in the
458 // binary.
459 std::vector<Loop*> GetLoopsInBinaryLayoutOrder();
460
461 // Returns the inner most loop that contains the basic block id |block_id|.
462 inline Loop* operator[](uint32_t block_id) const {
463 return FindLoopForBasicBlock(block_id);
464 }
465
466 // Returns the inner most loop that contains the basic block |bb|.
467 inline Loop* operator[](const BasicBlock* bb) const {
468 return (*this)[bb->id()];
469 }
470
471 // Iterators for post order depth first traversal of the loops.
472 // Inner most loops will be visited first.
473 inline iterator begin() { return iterator::begin(&dummy_top_loop_); }
474 inline iterator end() { return iterator::end(&dummy_top_loop_); }
475 inline const_iterator begin() const { return cbegin(); }
476 inline const_iterator end() const { return cend(); }
477 inline const_iterator cbegin() const {
478 return const_iterator::begin(&dummy_top_loop_);
479 }
480 inline const_iterator cend() const {
481 return const_iterator::end(&dummy_top_loop_);
482 }
483
484 // Iterators for pre-order depth first traversal of the loops.
485 // Inner most loops will be visited first.
486 inline pre_iterator pre_begin() { return ++pre_iterator(&dummy_top_loop_); }
487 inline pre_iterator pre_end() { return pre_iterator(); }
488 inline const_pre_iterator pre_begin() const { return pre_cbegin(); }
489 inline const_pre_iterator pre_end() const { return pre_cend(); }
490 inline const_pre_iterator pre_cbegin() const {
491 return ++const_pre_iterator(&dummy_top_loop_);
492 }
493 inline const_pre_iterator pre_cend() const { return const_pre_iterator(); }
494
495 // Returns the inner most loop that contains the basic block |bb|.
496 inline void SetBasicBlockToLoop(uint32_t bb_id, Loop* loop) {
497 basic_block_to_loop_[bb_id] = loop;
498 }
499
500 // Mark the loop |loop_to_add| as needing to be added when the user calls
501 // PostModificationCleanup. |parent| may be null.
502 inline void AddLoop(std::unique_ptr<Loop>&& loop_to_add, Loop* parent) {
503 loops_to_add_.emplace_back(std::make_pair(parent, std::move(loop_to_add)));
504 }
505
506 // Checks all loops in |this| and will create pre-headers for all loops
507 // that don't have one. Returns |true| if any blocks were created.
508 bool CreatePreHeaderBlocksIfMissing();
509
510 // Should be called to preserve the LoopAnalysis after loops have been marked
511 // for addition with AddLoop or MarkLoopForRemoval.
512 void PostModificationCleanup();
513
514 // Removes the basic block id |bb_id| from the block to loop mapping.
515 inline void ForgetBasicBlock(uint32_t bb_id) {
516 basic_block_to_loop_.erase(bb_id);
517 }
518
519 // Adds the loop |new_loop| and all its nested loops to the descriptor set.
520 // The object takes ownership of all the loops.
521 Loop* AddLoopNest(std::unique_ptr<Loop> new_loop);
522
523 // Remove the loop |loop|.
524 void RemoveLoop(Loop* loop);
525
526 void SetAsTopLoop(Loop* loop) {
527 assert(std::find(dummy_top_loop_.begin(), dummy_top_loop_.end(), loop) ==
528 dummy_top_loop_.end() &&
529 "already registered");
530 dummy_top_loop_.nested_loops_.push_back(loop);
531 }
532
533 Loop* GetDummyRootLoop() { return &dummy_top_loop_; }
534 const Loop* GetDummyRootLoop() const { return &dummy_top_loop_; }
535
536 private:
537 // TODO(dneto): This should be a vector of unique_ptr. But VisualStudio 2013
538 // is unable to compile it.
539 using LoopContainerType = std::vector<Loop*>;
540
541 using LoopsToAddContainerType =
542 std::vector<std::pair<Loop*, std::unique_ptr<Loop>>>;
543
544 // Creates loop descriptors for the function |f|.
545 void PopulateList(IRContext* context, const Function* f);
546
547 // Returns the inner most loop that contains the basic block id |block_id|.
548 inline Loop* FindLoopForBasicBlock(uint32_t block_id) const {
549 std::unordered_map<uint32_t, Loop*>::const_iterator it =
550 basic_block_to_loop_.find(block_id);
551 return it != basic_block_to_loop_.end() ? it->second : nullptr;
552 }
553
554 // Erase all the loop information.
555 void ClearLoops();
556
557 // A list of all the loops in the function. This variable owns the Loop
558 // objects.
559 LoopContainerType loops_;
560
561 // Dummy root: this "loop" is only there to help iterators creation.
562 Loop dummy_top_loop_;
563
564 std::unordered_map<uint32_t, Loop*> basic_block_to_loop_;
565
566 // List of the loops marked for addition when PostModificationCleanup is
567 // called.
568 LoopsToAddContainerType loops_to_add_;
569};
570
571} // namespace opt
572} // namespace spvtools
573
574#endif // SOURCE_OPT_LOOP_DESCRIPTOR_H_
575