Coverage Report

Created: 2018-07-12 09:57

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopIterator.h
Line
Count
Source
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
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.
41
struct 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.
98
class LoopBlocksDFS {
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.
112
  DenseMap<BasicBlock*, unsigned> PostNumbers;
113
  std::vector<BasicBlock*> PostBlocks;
114
115
public:
116
  LoopBlocksDFS(Loop *Container) :
117
236k
    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
118
236k
    PostBlocks.reserve(Container->getNumBlocks());
119
236k
  }
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
4
  POIterator beginPostorder() const {
131
4
    assert(isComplete() && "bad loop DFS");
132
4
    return PostBlocks.begin();
133
4
  }
134
4
  POIterator endPostorder() const { return PostBlocks.end(); }
135
136
  /// Reverse iterate over the cached postorder blocks.
137
229k
  RPOIterator beginRPO() const {
138
229k
    assert(isComplete() && "bad loop DFS");
139
229k
    return PostBlocks.rbegin();
140
229k
  }
141
229k
  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
/// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
172
/// interface for the DFS reverse post-order traversal of blocks in a loop body.
173
class LoopBlocksRPO {
174
private:
175
  LoopBlocksDFS DFS;
176
177
public:
178
144k
  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
179
180
  /// Traverse the loop blocks and store the DFS result.
181
144k
  void perform(LoopInfo *LI) {
182
144k
    DFS.perform(LI);
183
144k
  }
184
185
  /// Reverse iterate over the cached postorder blocks.
186
144k
  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
187
144k
  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
188
};
189
190
/// Specialize po_iterator_storage to record postorder numbers.
191
template<> class po_iterator_storage<LoopBlocksTraversal, true> {
192
  LoopBlocksTraversal &LBT;
193
public:
194
466k
  po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
195
  // These functions are defined below.
196
  bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
197
  void finishPostorder(BasicBlock *BB);
198
};
199
200
/// Traverse the blocks in a loop using a depth-first search.
201
class LoopBlocksTraversal {
202
public:
203
  /// Graph traversal iterator.
204
  typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
205
206
private:
207
  LoopBlocksDFS &DFS;
208
  LoopInfo *LI;
209
210
public:
211
  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
212
233k
    DFS(Storage), LI(LInfo) {}
213
214
  /// Postorder traversal over the graph. This only needs to be done once.
215
  /// po_iterator "automatically" calls back to visitPreorder and
216
  /// finishPostorder to record the DFS result.
217
233k
  POTIterator begin() {
218
233k
    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
219
233k
    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
220
233k
    return po_ext_begin(DFS.L->getHeader(), *this);
221
233k
  }
222
233k
  POTIterator end() {
223
233k
    // po_ext_end interface requires a basic block, but ignores its value.
224
233k
    return po_ext_end(DFS.L->getHeader(), *this);
225
233k
  }
226
227
  /// Called by po_iterator upon reaching a block via a CFG edge. If this block
228
  /// is contained in the loop and has not been visited, then mark it preorder
229
  /// visited and return true.
230
  ///
231
  /// TODO: If anyone is interested, we could record preorder numbers here.
232
1.08M
  bool visitPreorder(BasicBlock *BB) {
233
1.08M
    if (!DFS.L->contains(LI->getLoopFor(BB)))
234
287k
      return false;
235
801k
236
801k
    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
237
801k
  }
238
239
  /// Called by po_iterator each time it advances, indicating a block's
240
  /// postorder.
241
465k
  void finishPostorder(BasicBlock *BB) {
242
465k
    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
243
465k
    DFS.PostBlocks.push_back(BB);
244
465k
    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
245
465k
  }
246
};
247
248
inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
249
1.08M
    Optional<BasicBlock *> From, BasicBlock *To) {
250
1.08M
  return LBT.visitPreorder(To);
251
1.08M
}
252
253
inline void po_iterator_storage<LoopBlocksTraversal, true>::
254
465k
finishPostorder(BasicBlock *BB) {
255
465k
  LBT.finishPostorder(BB);
256
465k
}
257
258
} // End namespace llvm
259
260
#endif