Coverage Report

Created: 2019-02-21 13:17

/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
// 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:
58
    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 {
65
    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
74
  static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
75
76
  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
84
  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:
115
  LoopBlocksDFS(Loop *Container) :
116
861k
    L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
117
861k
    PostBlocks.reserve(Container->getNumBlocks());
118
861k
  }
119
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.
126
  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
127
128
  /// Iterate over the cached postorder blocks.
129
111
  POIterator beginPostorder() const {
130
111
    assert(isComplete() && "bad loop DFS");
131
111
    return PostBlocks.begin();
132
111
  }
133
111
  POIterator endPostorder() const { return PostBlocks.end(); }
134
135
  /// Reverse iterate over the cached postorder blocks.
136
854k
  RPOIterator beginRPO() const {
137
854k
    assert(isComplete() && "bad loop DFS");
138
854k
    return PostBlocks.rbegin();
139
854k
  }
140
854k
  RPOIterator endRPO() const { return PostBlocks.rend(); }
141
142
  /// Return true if this block has been preorder visited.
143
  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
144
145
  /// Return true if this block has a postorder number.
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.
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.
160
  unsigned getRPO(BasicBlock *BB) const {
161
    return 1 + PostBlocks.size() - getPostorder(BB);
162
  }
163
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:
177
766k
  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
178
179
  /// Traverse the loop blocks and store the DFS result.
180
765k
  void perform(LoopInfo *LI) {
181
765k
    DFS.perform(LI);
182
765k
  }
183
184
  /// Reverse iterate over the cached postorder blocks.
185
765k
  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
186
766k
  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:
193
1.71M
  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:
210
  LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
211
857k
    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.
216
857k
  POTIterator begin() {
217
857k
    assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
218
857k
    assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
219
857k
    return po_ext_begin(DFS.L->getHeader(), *this);
220
857k
  }
221
857k
  POTIterator end() {
222
857k
    // po_ext_end interface requires a basic block, but ignores its value.
223
857k
    return po_ext_end(DFS.L->getHeader(), *this);
224
857k
  }
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.
231
6.66M
  bool visitPreorder(BasicBlock *BB) {
232
6.66M
    if (!DFS.L->contains(LI->getLoopFor(BB)))
233
1.16M
      return false;
234
5.50M
235
5.50M
    return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
236
5.50M
  }
237
238
  /// Called by po_iterator each time it advances, indicating a block's
239
  /// postorder.
240
3.38M
  void finishPostorder(BasicBlock *BB) {
241
3.38M
    assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
242
3.38M
    DFS.PostBlocks.push_back(BB);
243
3.38M
    DFS.PostNumbers[BB] = DFS.PostBlocks.size();
244
3.38M
  }
245
};
246
247
inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
248
6.66M
    Optional<BasicBlock *> From, BasicBlock *To) {
249
6.66M
  return LBT.visitPreorder(To);
250
6.66M
}
251
252
inline void po_iterator_storage<LoopBlocksTraversal, true>::
253
3.38M
finishPostorder(BasicBlock *BB) {
254
3.38M
  LBT.finishPostorder(BB);
255
3.38M
}
256
257
} // End namespace llvm
258
259
#endif