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