39 // A class to represent and manipulate a loop in structured control flow.
40 class Loop {
42   using ChildrenList = std::vector<Loop*>;
49   explicit Loop(IRContext* context)  in Loop()  function
59   Loop(IRContext* context, DominatorAnalysis* analysis, BasicBlock* header,
70   // Returns the header (first basic block of the loop). This block contains the
77   // loop.
80            "The loop is not structured");  in UpdateLoopMergeInst()
91   // These functions return nullptr if the loop is not structured (i.e. if it
96   // Sets |latch| as the loop unique block branching back to the header.
98   //  - |latch| must be in the loop;
102   // Sets |continue_block| as the continue block of the loop. This should be the
106   // Returns the basic block which marks the end of the loop.
107   // These functions return nullptr if the loop is not structured.
110   // Sets |merge| as the loop merge block. A merge block must have the following
112   //  - |merge| must not be in the loop;
113   //  - all its predecessors must be in the loop.
115   // If the loop has an OpLoopMerge in its header, this instruction is also
119   // Returns the loop pre-header, nullptr means that the loop predecessor does
122   //   - Dominates the loop header;
123   //   - Has only the loop header as successor.
126   // Returns the loop pre-header.
128   // Sets |preheader| as the loop preheader block. A preheader block must have
130   //  - |merge| must not be in the loop;
131   //  - have an unconditional branch to the loop header.
134   // Returns the loop pre-header, if there is no suitable preheader it will be
138   // Returns true if this loop contains any nested loops.
142   // loop and has at least one predecessor in the loop.
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.
156   // Returns the depth of this loop in the loop nest.
157   // The outer-most loop has a depth of 1.
160     for (const Loop* loop = GetParent(); loop; loop = loop->GetParent()) lvl++;  in GetDepth()  local
167   // Adds |nested| as a nested loop of this loop. Automatically register |this|
169   inline void AddNestedLoop(Loop* nested) {  in AddNestedLoop()
170     assert(!nested->GetParent() && "The loop has another parent.");  in AddNestedLoop()
175   inline Loop* GetParent() { return parent_; }  in GetParent()
176   inline const Loop* GetParent() const { return parent_; }  in GetParent()
180   // Returns true if this loop is itself nested within another loop.
183   // Returns the set of all basic blocks contained within the loop. Will be all
185   // loop merge block.
190   // Returns true if the basic block |bb| is inside this loop.
195   // Returns true if the basic block id |bb_id| is inside this loop.
200   // Returns true if the instruction |inst| is inside this loop.
203   // Adds the Basic Block |bb| to this loop and its parents.
206   // Adds the Basic Block with |id| to this loop and its parents.
208     for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {  in AddBasicBlock()  local
209       loop->loop_basic_blocks_.insert(id);  in AddBasicBlock()
213   // Removes the Basic Block id |bb_id| from this loop and its parents.
217     for (Loop* loop = this; loop != nullptr; loop = loop->parent_) {  in RemoveBasicBlock()  local
218       loop->loop_basic_blocks_.erase(bb_id);  in RemoveBasicBlock()
222   // Removes all the basic blocks from the set of basic blocks within the loop.
227   // Adds the Basic Block |bb| this loop and its parents.
230            "Basic block does not belong to the loop");  in AddBasicBlockToLoop()
235   // Returns the list of induction variables within the loop.
239   // used by the loop condition within the loop. This only works if the loop is
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
253   // Returns the value of the OpLoopMerge control operand as a bool. Loop
264   // within the loop body.
267   // Remove the child loop form this loop.
268   inline void RemoveChildLoop(Loop* loop) {  in RemoveChildLoop()  argument
270         std::find(nested_loops_.begin(), nested_loops_.end(), loop));  in RemoveChildLoop()
271     loop->SetParent(nullptr);  in RemoveChildLoop()
274   // Mark this loop to be removed later by a call to
278   // Returns whether or not this loop has been marked for removal.
283     for (const Loop* child : nested_loops_) {  in AreAllChildrenMarkedForRemoval()
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.
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; }  in SetParent()
299   // Returns true is the instruction is invariant and safe to move wrt loop
303   // loop
312   // Takes in a phi instruction |induction| and the loop |header| and returns
313   // the step operation of the loop.
316   // Returns true if we can deduce the number of loop iterations in the step
321   // Returns true if we can deduce the number of loop iterations in the
326   // Creates the list of the loop's basic block in structured order and store
335   // Given the loop |condition|, |initial_value|, |step_value|, the trip count
337   // condition value for the residual loop.
344   // Returns the condition instruction for entry into the loop
348   // Returns the context associated this loop.
352   // which is also dominated by the loop continue block. This block is the latch
359   // The block which marks the start of the loop.
362   // The block which begins the body of the loop.
365   // The block which marks the end of the loop.
368   // The block immediately before the loop header.
371   // The block containing the backedge to the loop header.
374   // A parent of a loop is the loop which contains it as a nested child loop.
375   Loop* parent_;
377   // Nested child loops of this loop.
380   // A set of all the basic blocks which comprise the loop structure. Will be
384   // Check that |bb| is inside the loop using domination property.
389   // Returns the loop preheader if it exists, returns nullptr otherwise.
392   // Sets |latch| as the loop unique latch block. No checks are performed
395   // Sets |merge| as the loop merge block. No checks are performed here.
398   // Each differnt loop |condition| affects how we calculate the number of
401   // a loop with those values for a given |condition|.
415 // Loop descriptions class for a given function.
416 // For a given function, the class builds loop nests information.
421   using iterator = PostOrderTreeDFIterator<Loop>;
422   using const_iterator = PostOrderTreeDFIterator<const Loop>;
424   using pre_iterator = TreeDFIterator<Loop>;
425   using const_pre_iterator = TreeDFIterator<const Loop>;
427   // Creates a loop object for all loops found in |f|.
434     // We need to take ownership of the Loop objects in the other  in LoopDescriptor()
449   // Returns the loop at a particular |index|. The |index| must be in bounds,
451   inline Loop& GetLoopByIndex(size_t index) const {  in GetLoopByIndex()
453            "Index out of range (larger than loop count)");  in GetLoopByIndex()
459   std::vector<Loop*> GetLoopsInBinaryLayoutOrder();
461   // Returns the inner most loop that contains the basic block id |block_id|.
462   inline Loop* operator[](uint32_t block_id) const {
466   // Returns the inner most loop that contains the basic block |bb|.
467   inline Loop* operator[](const BasicBlock* bb) const {
495   // Returns the inner most loop that contains the basic block |bb|.
496   inline void SetBasicBlockToLoop(uint32_t bb_id, Loop* loop) {  in SetBasicBlockToLoop()  argument
497     basic_block_to_loop_[bb_id] = loop;  in SetBasicBlockToLoop()
500   // Mark the loop |loop_to_add| as needing to be added when the user calls
502   inline void AddLoop(Loop* loop_to_add, Loop* parent) {  in AddLoop()
514   // Removes the basic block id |bb_id| from the block to loop mapping.
519   // Adds the loop |new_loop| and all its nested loops to the descriptor set.
521   Loop* AddLoopNest(std::unique_ptr<Loop> new_loop);
523   // Remove the loop |loop|.
524   void RemoveLoop(Loop* loop);
526   void SetAsTopLoop(Loop* loop) {  in SetAsTopLoop()  argument
527     assert(std::find(dummy_top_loop_.begin(), dummy_top_loop_.end(), loop) ==  in SetAsTopLoop()
530     dummy_top_loop_.nested_loops_.push_back(loop);  in SetAsTopLoop()
533   Loop* GetDummyRootLoop() { return &dummy_top_loop_; }  in GetDummyRootLoop()
534   const Loop* GetDummyRootLoop() const { return &dummy_top_loop_; }  in GetDummyRootLoop()
539   using LoopContainerType = std::vector<Loop*>;
540   using LoopsToAddContainerType = std::vector<std::pair<Loop*, Loop*>>;
542   // Creates loop descriptors for the function |f|.
545   // Returns the inner most loop that contains the basic block id |block_id|.
546   inline Loop* FindLoopForBasicBlock(uint32_t block_id) const {  in FindLoopForBasicBlock()
547     std::unordered_map<uint32_t, Loop*>::const_iterator it =  in FindLoopForBasicBlock()
552   // Erase all the loop information.
555   // A list of all the loops in the function.  This variable owns the Loop
559   // Dummy root: this "loop" is only there to help iterators creation.
560   Loop dummy_top_loop_;
562   std::unordered_map<uint32_t, Loop*> basic_block_to_loop_;