LLVM  6.0.0svn
LoopIterator.h
Go to the documentation of this file.
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 
28 #include "llvm/Analysis/LoopInfo.h"
29 
30 namespace llvm {
31 
32 class 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.
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.
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> {
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 =
74 
75  static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
76 
78  return make_filter_range(make_range<WrappedSuccIterator>(
79  {succ_begin(Node.second), Node.first},
80  {succ_end(Node.second), Node.first}),
82  .begin();
83  }
84 
86  return make_filter_range(make_range<WrappedSuccIterator>(
87  {succ_begin(Node.second), Node.first},
88  {succ_end(Node.second), Node.first}),
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.
99 public:
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 
106 private:
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.
113  std::vector<BasicBlock*> PostBlocks;
114 
115 public:
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 {
149  return I != PostNumbers.end() && I->second;
150  }
151 
152  /// Get a block's postorder number.
153  unsigned getPostorder(BasicBlock *BB) const {
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.
173  LoopBlocksTraversal &LBT;
174 public:
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.
183 public:
184  /// Graph traversal iterator.
186 
187 private:
189  LoopInfo *LI;
190 
191 public:
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.
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.
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 
231  return LBT.visitPreorder(To);
232 }
233 
236  LBT.finishPostorder(BB);
237 }
238 
239 } // End namespace llvm
240 
241 #endif
bool hasPostorder(BasicBlock *BB) const
Return true if this block has a postorder number.
Definition: LoopIterator.h:147
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:243
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:234
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Loop * getLoop() const
Definition: LoopIterator.h:121
LoopBlocksDFS(Loop *Container)
Definition: LoopIterator.h:116
TerminatorInst::SuccIterator< TerminatorInst *, BasicBlock > succ_iterator
Definition: CFG.h:122
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:127
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:176
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:182
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:130
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:585
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:198
bool hasPreorder(BasicBlock *BB) const
Return true if this block has been preorder visited.
Definition: LoopIterator.h:144
void finishPostorder(NodeRef BB)
RPOIterator endRPO() const
Definition: LoopIterator.h:141
BlockT * getHeader() const
Definition: LoopInfo.h:103
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
static ChildIteratorType child_end(NodeRef Node)
Definition: LoopIterator.h:85
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:131
po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator
Graph traversal iterator.
Definition: LoopIterator.h:185
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:42
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:288
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
WrappedSuccIterator(succ_iterator Begin, const Loop *L)
Definition: LoopIterator.h:59
Default po_iterator_storage implementation with an internal set object.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:102
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:91
bool insertEdge(Optional< NodeRef > From, NodeRef To)
static NodeRef getEntryNode(const Loop &G)
Definition: LoopIterator.h:75
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:632
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
unsigned getRPO(BasicBlock *BB) const
Get a block&#39;s reverse postorder number.
Definition: LoopIterator.h:161
static ChildIteratorType child_begin(NodeRef Node)
Definition: LoopIterator.h:77
bool visitPreorder(BasicBlock *BB)
Called by po_iterator upon reaching a block via a CFG edge.
Definition: LoopIterator.h:213
const DataFlowGraph & G
Definition: RDFGraph.cpp:206
const size_t N
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:98
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
POIterator endPostorder() const
Definition: LoopIterator.h:134
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:149
Basic Alias true
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:360
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
iterator end()
Definition: DenseMap.h:73
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:101
LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo)
Definition: LoopIterator.h:192
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:350
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:126
void finishPostorder(BasicBlock *BB)
Called by po_iterator each time it advances, indicating a block&#39;s postorder.
Definition: LoopIterator.h:222
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:137
unsigned getPostorder(BasicBlock *BB) const
Get a block&#39;s postorder number.
Definition: LoopIterator.h:153
bool operator()(NodeRef N) const
Definition: LoopIterator.h:66