1 //===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // This file defines iterators to visit the basic blocks within a loop.
9 //
10 // These iterators currently visit blocks within subloops as well.
11 // Unfortunately we have no efficient way of summarizing loop exits which would
12 // allow skipping subloops during traversal.
13 //
14 // If you want to visit all blocks in a loop and don't need an ordered traveral,
15 // use Loop::block_begin() instead.
16 //
17 // This is intentionally designed to work with ill-formed loops in which the
18 // backedge has been deleted. The only prerequisite is that all blocks
19 // contained within the loop according to the most recent LoopInfo analysis are
20 // reachable from the loop header.
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
24 #define LLVM_ANALYSIS_LOOPITERATOR_H
25 
26 #include "llvm/ADT/PostOrderIterator.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 
29 namespace llvm {
30 
31 class LoopBlocksTraversal;
32 
33 // A traits type that is intended to be used in graph algorithms. The graph
34 // traits starts at the loop header, and traverses the BasicBlocks that are in
35 // the loop body, but not the loop header. Since the loop header is skipped,
36 // the back edges are excluded.
37 //
38 // TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
39 //       LoopBodyTraits, so that insertEdge doesn't have to be specialized.
40 struct LoopBodyTraits {
41   using NodeRef = std::pair<const Loop *, BasicBlock *>;
42 
43   // This wraps a const Loop * into the iterator, so we know which edges to
44   // filter out.
45   class WrappedSuccIterator
46       : public iterator_adaptor_base<
47             WrappedSuccIterator, succ_iterator,
48             typename std::iterator_traits<succ_iterator>::iterator_category,
49             NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
50     using BaseT = iterator_adaptor_base<
51         WrappedSuccIterator, succ_iterator,
52         typename std::iterator_traits<succ_iterator>::iterator_category,
53         NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
54 
55     const Loop *L;
56 
57   public:
WrappedSuccIteratorLoopBodyTraits58     WrappedSuccIterator(succ_iterator Begin, const Loop *L)
59         : BaseT(Begin), L(L) {}
60 
61     NodeRef operator*() const { return {L, *I}; }
62   };
63 
64   struct LoopBodyFilter {
operatorLoopBodyTraits::LoopBodyFilter65     bool operator()(NodeRef N) const {
66       const Loop *L = N.first;
67       return N.second != L->getHeader() && L->contains(N.second);
68     }
69   };
70 
71   using ChildIteratorType =
72       filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
73 
getEntryNodeLoopBodyTraits74   static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
75 
child_beginLoopBodyTraits76   static ChildIteratorType child_begin(NodeRef Node) {
77     return make_filter_range(make_range<WrappedSuccIterator>(
78                                  {succ_begin(Node.second), Node.first},
79                                  {succ_end(Node.second), Node.first}),
80                              LoopBodyFilter{})
81         .begin();
82   }
83 
child_endLoopBodyTraits84   static ChildIteratorType child_end(NodeRef Node) {
85     return make_filter_range(make_range<WrappedSuccIterator>(
86                                  {succ_begin(Node.second), Node.first},
87                                  {succ_end(Node.second), Node.first}),
88                              LoopBodyFilter{})
89         .end();
90   }
91 };
92 
93 /// Store the result of a depth first search within basic blocks contained by a
94 /// single loop.
95 ///
96 /// TODO: This could be generalized for any CFG region, or the entire CFG.
97 class LoopBlocksDFS {
98 public:
99   /// Postorder list iterators.
100   typedef std::vector<BasicBlock*>::const_iterator POIterator;
101   typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
102 
103   friend class LoopBlocksTraversal;
104 
105 private:
106   Loop *L;
107 
108   /// Map each block to its postorder number. A block is only mapped after it is
109   /// preorder visited by DFS. It's postorder number is initially zero and set
110   /// to nonzero after it is finished by postorder traversal.
111   DenseMap<BasicBlock*, unsigned> PostNumbers;
112   std::vector<BasicBlock*> PostBlocks;
113 
114 public:
LoopBlocksDFS(Loop * Container)115   LoopBlocksDFS(Loop *Container) :
116     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
117     PostBlocks.reserve(Container->getNumBlocks());
118   }
119 
getLoop()120   Loop *getLoop() const { return L; }
121 
122   /// Traverse the loop blocks and store the DFS result.
123   void perform(LoopInfo *LI);
124 
125   /// Return true if postorder numbers are assigned to all loop blocks.
isComplete()126   bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
127 
128   /// Iterate over the cached postorder blocks.
beginPostorder()129   POIterator beginPostorder() const {
130     assert(isComplete() && "bad loop DFS");
131     return PostBlocks.begin();
132   }
endPostorder()133   POIterator endPostorder() const { return PostBlocks.end(); }
134 
135   /// Reverse iterate over the cached postorder blocks.
beginRPO()136   RPOIterator beginRPO() const {
137     assert(isComplete() && "bad loop DFS");
138     return PostBlocks.rbegin();
139   }
endRPO()140   RPOIterator endRPO() const { return PostBlocks.rend(); }
141 
142   /// Return true if this block has been preorder visited.
hasPreorder(BasicBlock * BB)143   bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
144 
145   /// Return true if this block has a postorder number.
hasPostorder(BasicBlock * BB)146   bool hasPostorder(BasicBlock *BB) const {
147     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
148     return I != PostNumbers.end() && I->second;
149   }
150 
151   /// Get a block's postorder number.
getPostorder(BasicBlock * BB)152   unsigned getPostorder(BasicBlock *BB) const {
153     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
154     assert(I != PostNumbers.end() && "block not visited by DFS");
155     assert(I->second && "block not finished by DFS");
156     return I->second;
157   }
158 
159   /// Get a block's reverse postorder number.
getRPO(BasicBlock * BB)160   unsigned getRPO(BasicBlock *BB) const {
161     return 1 + PostBlocks.size() - getPostorder(BB);
162   }
163 
clear()164   void clear() {
165     PostNumbers.clear();
166     PostBlocks.clear();
167   }
168 };
169 
170 /// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
171 /// interface for the DFS reverse post-order traversal of blocks in a loop body.
172 class LoopBlocksRPO {
173 private:
174   LoopBlocksDFS DFS;
175 
176 public:
LoopBlocksRPO(Loop * Container)177   LoopBlocksRPO(Loop *Container) : DFS(Container) {}
178 
179   /// Traverse the loop blocks and store the DFS result.
perform(LoopInfo * LI)180   void perform(LoopInfo *LI) {
181     DFS.perform(LI);
182   }
183 
184   /// Reverse iterate over the cached postorder blocks.
begin()185   LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
end()186   LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
187 };
188 
189 /// Specialize po_iterator_storage to record postorder numbers.
190 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
191   LoopBlocksTraversal &LBT;
192 public:
po_iterator_storage(LoopBlocksTraversal & lbs)193   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
194   // These functions are defined below.
195   bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
196   void finishPostorder(BasicBlock *BB);
197 };
198 
199 /// Traverse the blocks in a loop using a depth-first search.
200 class LoopBlocksTraversal {
201 public:
202   /// Graph traversal iterator.
203   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
204 
205 private:
206   LoopBlocksDFS &DFS;
207   LoopInfo *LI;
208 
209 public:
LoopBlocksTraversal(LoopBlocksDFS & Storage,LoopInfo * LInfo)210   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
211     DFS(Storage), LI(LInfo) {}
212 
213   /// Postorder traversal over the graph. This only needs to be done once.
214   /// po_iterator "automatically" calls back to visitPreorder and
215   /// finishPostorder to record the DFS result.
begin()216   POTIterator begin() {
217     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
218     assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
219     return po_ext_begin(DFS.L->getHeader(), *this);
220   }
end()221   POTIterator end() {
222     // po_ext_end interface requires a basic block, but ignores its value.
223     return po_ext_end(DFS.L->getHeader(), *this);
224   }
225 
226   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
227   /// is contained in the loop and has not been visited, then mark it preorder
228   /// visited and return true.
229   ///
230   /// TODO: If anyone is interested, we could record preorder numbers here.
visitPreorder(BasicBlock * BB)231   bool visitPreorder(BasicBlock *BB) {
232     if (!DFS.L->contains(LI->getLoopFor(BB)))
233       return false;
234 
235     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
236   }
237 
238   /// Called by po_iterator each time it advances, indicating a block's
239   /// postorder.
finishPostorder(BasicBlock * BB)240   void finishPostorder(BasicBlock *BB) {
241     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
242     DFS.PostBlocks.push_back(BB);
243     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
244   }
245 };
246 
insertEdge(Optional<BasicBlock * > From,BasicBlock * To)247 inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
248     Optional<BasicBlock *> From, BasicBlock *To) {
249   return LBT.visitPreorder(To);
250 }
251 
252 inline void po_iterator_storage<LoopBlocksTraversal, true>::
finishPostorder(BasicBlock * BB)253 finishPostorder(BasicBlock *BB) {
254   LBT.finishPostorder(BB);
255 }
256 
257 } // End namespace llvm
258 
259 #endif
260