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/// Store the result of a depth first search within basic blocks contained by a
35/// single loop.
36///
37/// TODO: This could be generalized for any CFG region, or the entire CFG.
38class LoopBlocksDFS {
39public:
40  /// Postorder list iterators.
41  typedef std::vector<BasicBlock*>::const_iterator POIterator;
42  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
43
44  friend class LoopBlocksTraversal;
45
46private:
47  Loop *L;
48
49  /// Map each block to its postorder number. A block is only mapped after it is
50  /// preorder visited by DFS. It's postorder number is initially zero and set
51  /// to nonzero after it is finished by postorder traversal.
52  DenseMap<BasicBlock*, unsigned> PostNumbers;
53  std::vector<BasicBlock*> PostBlocks;
54
55public:
56  LoopBlocksDFS(Loop *Container) :
57    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
58    PostBlocks.reserve(Container->getNumBlocks());
59  }
60
61  Loop *getLoop() const { return L; }
62
63  /// Traverse the loop blocks and store the DFS result.
64  void perform(LoopInfo *LI);
65
66  /// Return true if postorder numbers are assigned to all loop blocks.
67  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
68
69  /// Iterate over the cached postorder blocks.
70  POIterator beginPostorder() const {
71    assert(isComplete() && "bad loop DFS");
72    return PostBlocks.begin();
73  }
74  POIterator endPostorder() const { return PostBlocks.end(); }
75
76  /// Reverse iterate over the cached postorder blocks.
77  RPOIterator beginRPO() const {
78    assert(isComplete() && "bad loop DFS");
79    return PostBlocks.rbegin();
80  }
81  RPOIterator endRPO() const { return PostBlocks.rend(); }
82
83  /// Return true if this block has been preorder visited.
84  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
85
86  /// Return true if this block has a postorder number.
87  bool hasPostorder(BasicBlock *BB) const {
88    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
89    return I != PostNumbers.end() && I->second;
90  }
91
92  /// Get a block's postorder number.
93  unsigned getPostorder(BasicBlock *BB) const {
94    DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
95    assert(I != PostNumbers.end() && "block not visited by DFS");
96    assert(I->second && "block not finished by DFS");
97    return I->second;
98  }
99
100  /// Get a block's reverse postorder number.
101  unsigned getRPO(BasicBlock *BB) const {
102    return 1 + PostBlocks.size() - getPostorder(BB);
103  }
104
105  void clear() {
106    PostNumbers.clear();
107    PostBlocks.clear();
108  }
109};
110
111/// Specialize po_iterator_storage to record postorder numbers.
112template<> class po_iterator_storage<LoopBlocksTraversal, true> {
113  LoopBlocksTraversal &LBT;
114public:
115  po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
116  // These functions are defined below.
117  bool insertEdge(BasicBlock *From, BasicBlock *To);
118  void finishPostorder(BasicBlock *BB);
119};
120
121/// Traverse the blocks in a loop using a depth-first search.
122class LoopBlocksTraversal {
123public:
124  /// Graph traversal iterator.
125  typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
126
127private:
128  LoopBlocksDFS &DFS;
129  LoopInfo *LI;
130
131public:
132  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
133    DFS(Storage), LI(LInfo) {}
134
135  /// Postorder traversal over the graph. This only needs to be done once.
136  /// po_iterator "automatically" calls back to visitPreorder and
137  /// finishPostorder to record the DFS result.
138  POTIterator begin() {
139    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
140    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
141    return po_ext_begin(DFS.L->getHeader(), *this);
142  }
143  POTIterator end() {
144    // po_ext_end interface requires a basic block, but ignores its value.
145    return po_ext_end(DFS.L->getHeader(), *this);
146  }
147
148  /// Called by po_iterator upon reaching a block via a CFG edge. If this block
149  /// is contained in the loop and has not been visited, then mark it preorder
150  /// visited and return true.
151  ///
152  /// TODO: If anyone is interested, we could record preorder numbers here.
153  bool visitPreorder(BasicBlock *BB) {
154    if (!DFS.L->contains(LI->getLoopFor(BB)))
155      return false;
156
157    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
158  }
159
160  /// Called by po_iterator each time it advances, indicating a block's
161  /// postorder.
162  void finishPostorder(BasicBlock *BB) {
163    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
164    DFS.PostBlocks.push_back(BB);
165    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
166  }
167};
168
169inline bool po_iterator_storage<LoopBlocksTraversal, true>::
170insertEdge(BasicBlock *From, BasicBlock *To) {
171  return LBT.visitPreorder(To);
172}
173
174inline void po_iterator_storage<LoopBlocksTraversal, true>::
175finishPostorder(BasicBlock *BB) {
176  LBT.finishPostorder(BB);
177}
178
179} // End namespace llvm
180
181#endif
182