Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/IR/CFG.h
Line
Count
Source (jump to first uncovered line)
1
//===- CFG.h ----------------------------------------------------*- 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
/// \file
9
///
10
/// This file provides various utilities for inspecting and working with the
11
/// control flow graph in LLVM IR. This includes generic facilities for
12
/// iterating successors and predecessors of basic blocks, the successors of
13
/// specific terminator instructions, etc. It also defines specializations of
14
/// GraphTraits that allow Function and BasicBlock graphs to be treated as
15
/// proper graphs for generic algorithms.
16
///
17
//===----------------------------------------------------------------------===//
18
19
#ifndef LLVM_IR_CFG_H
20
#define LLVM_IR_CFG_H
21
22
#include "llvm/ADT/GraphTraits.h"
23
#include "llvm/ADT/iterator.h"
24
#include "llvm/ADT/iterator_range.h"
25
#include "llvm/IR/BasicBlock.h"
26
#include "llvm/IR/Function.h"
27
#include "llvm/IR/InstrTypes.h"
28
#include "llvm/IR/Value.h"
29
#include "llvm/Support/Casting.h"
30
#include "llvm/Support/type_traits.h"
31
#include <cassert>
32
#include <cstddef>
33
#include <iterator>
34
35
namespace llvm {
36
37
//===----------------------------------------------------------------------===//
38
// BasicBlock pred_iterator definition
39
//===----------------------------------------------------------------------===//
40
41
template <class Ptr, class USE_iterator> // Predecessor Iterator
42
class PredIterator : public std::iterator<std::forward_iterator_tag,
43
                                          Ptr, ptrdiff_t, Ptr*, Ptr*> {
44
  using super =
45
      std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
46
  using Self = PredIterator<Ptr, USE_iterator>;
47
  USE_iterator It;
48
49
1.10G
  inline void advancePastNonTerminators() {
50
1.10G
    // Loop to ignore non-terminator uses (for example BlockAddresses).
51
1.10G
    while (!It.atEnd()) {
52
720M
      if (auto *Inst = dyn_cast<Instruction>(*It))
53
720M
        if (Inst->isTerminator())
54
720M
          break;
55
9.23k
56
9.23k
      ++It;
57
9.23k
    }
58
1.10G
  }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::advancePastNonTerminators()
Line
Count
Source
49
503M
  inline void advancePastNonTerminators() {
50
503M
    // Loop to ignore non-terminator uses (for example BlockAddresses).
51
503M
    while (!It.atEnd()) {
52
314M
      if (auto *Inst = dyn_cast<Instruction>(*It))
53
314M
        if (Inst->isTerminator())
54
314M
          break;
55
4.96k
56
4.96k
      ++It;
57
4.96k
    }
58
503M
  }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::advancePastNonTerminators()
Line
Count
Source
49
603M
  inline void advancePastNonTerminators() {
50
603M
    // Loop to ignore non-terminator uses (for example BlockAddresses).
51
603M
    while (!It.atEnd()) {
52
406M
      if (auto *Inst = dyn_cast<Instruction>(*It))
53
406M
        if (Inst->isTerminator())
54
406M
          break;
55
4.26k
56
4.26k
      ++It;
57
4.26k
    }
58
603M
  }
59
60
public:
61
  using pointer = typename super::pointer;
62
  using reference = typename super::reference;
63
64
  PredIterator() = default;
65
536M
  explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
66
536M
    advancePastNonTerminators();
67
536M
  }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::PredIterator(llvm::BasicBlock*)
Line
Count
Source
65
206M
  explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
66
206M
    advancePastNonTerminators();
67
206M
  }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::PredIterator(llvm::BasicBlock const*)
Line
Count
Source
65
330M
  explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
66
330M
    advancePastNonTerminators();
67
330M
  }
68
535M
  inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::PredIterator(llvm::BasicBlock*, bool)
Line
Count
Source
68
204M
  inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::PredIterator(llvm::BasicBlock const*, bool)
Line
Count
Source
68
330M
  inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
69
70
1.12G
  inline bool operator==(const Self& x) const { return It == x.It; }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::operator==(llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> > const&) const
Line
Count
Source
70
601M
  inline bool operator==(const Self& x) const { return It == x.It; }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::operator==(llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> > const&) const
Line
Count
Source
70
524M
  inline bool operator==(const Self& x) const { return It == x.It; }
71
617M
  inline bool operator!=(const Self& x) const { return !operator==(x); }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::operator!=(llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> > const&) const
Line
Count
Source
71
100M
  inline bool operator!=(const Self& x) const { return !operator==(x); }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::operator!=(llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> > const&) const
Line
Count
Source
71
516M
  inline bool operator!=(const Self& x) const { return !operator==(x); }
72
73
537M
  inline reference operator*() const {
74
537M
    assert(!It.atEnd() && "pred_iterator out of range!");
75
537M
    return cast<Instruction>(*It)->getParent();
76
537M
  }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::operator*() const
Line
Count
Source
73
303M
  inline reference operator*() const {
74
303M
    assert(!It.atEnd() && "pred_iterator out of range!");
75
303M
    return cast<Instruction>(*It)->getParent();
76
303M
  }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::operator*() const
Line
Count
Source
73
234M
  inline reference operator*() const {
74
234M
    assert(!It.atEnd() && "pred_iterator out of range!");
75
234M
    return cast<Instruction>(*It)->getParent();
76
234M
  }
77
  inline pointer *operator->() const { return &operator*(); }
78
79
569M
  inline Self& operator++() {   // Preincrement
80
569M
    assert(!It.atEnd() && "pred_iterator out of range!");
81
569M
    ++It; advancePastNonTerminators();
82
569M
    return *this;
83
569M
  }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::operator++()
Line
Count
Source
79
272M
  inline Self& operator++() {   // Preincrement
80
272M
    assert(!It.atEnd() && "pred_iterator out of range!");
81
272M
    ++It; advancePastNonTerminators();
82
272M
    return *this;
83
272M
  }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::operator++()
Line
Count
Source
79
297M
  inline Self& operator++() {   // Preincrement
80
297M
    assert(!It.atEnd() && "pred_iterator out of range!");
81
297M
    ++It; advancePastNonTerminators();
82
297M
    return *this;
83
297M
  }
84
85
33.3k
  inline Self operator++(int) { // Postincrement
86
33.3k
    Self tmp = *this; ++*this; return tmp;
87
33.3k
  }
llvm::PredIterator<llvm::BasicBlock, llvm::Value::user_iterator_impl<llvm::User> >::operator++(int)
Line
Count
Source
85
33.0k
  inline Self operator++(int) { // Postincrement
86
33.0k
    Self tmp = *this; ++*this; return tmp;
87
33.0k
  }
llvm::PredIterator<llvm::BasicBlock const, llvm::Value::user_iterator_impl<llvm::User const> >::operator++(int)
Line
Count
Source
85
350
  inline Self operator++(int) { // Postincrement
86
350
    Self tmp = *this; ++*this; return tmp;
87
350
  }
88
89
  /// getOperandNo - Return the operand number in the predecessor's
90
  /// terminator of the successor.
91
  unsigned getOperandNo() const {
92
    return It.getOperandNo();
93
  }
94
95
  /// getUse - Return the operand Use in the predecessor's terminator
96
  /// of the successor.
97
135
  Use &getUse() const {
98
135
    return It.getUse();
99
135
  }
100
};
101
102
using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
103
using const_pred_iterator =
104
    PredIterator<const BasicBlock, Value::const_user_iterator>;
105
using pred_range = iterator_range<pred_iterator>;
106
using pred_const_range = iterator_range<const_pred_iterator>;
107
108
206M
inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
109
330M
inline const_pred_iterator pred_begin(const BasicBlock *BB) {
110
330M
  return const_pred_iterator(BB);
111
330M
}
112
204M
inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
113
330M
inline const_pred_iterator pred_end(const BasicBlock *BB) {
114
330M
  return const_pred_iterator(BB, true);
115
330M
}
116
51.1M
inline bool pred_empty(const BasicBlock *BB) {
117
51.1M
  return pred_begin(BB) == pred_end(BB);
118
51.1M
}
119
/// Get the number of predecessors of \p BB. This is a linear time operation.
120
/// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
121
26.2M
inline unsigned pred_size(const BasicBlock *BB) {
122
26.2M
  return std::distance(pred_begin(BB), pred_end(BB));
123
26.2M
}
124
33.5M
inline pred_range predecessors(BasicBlock *BB) {
125
33.5M
  return pred_range(pred_begin(BB), pred_end(BB));
126
33.5M
}
127
284k
inline pred_const_range predecessors(const BasicBlock *BB) {
128
284k
  return pred_const_range(pred_begin(BB), pred_end(BB));
129
284k
}
130
131
//===----------------------------------------------------------------------===//
132
// Instruction and BasicBlock succ_iterator helpers
133
//===----------------------------------------------------------------------===//
134
135
template <class InstructionT, class BlockT>
136
class SuccIterator
137
    : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
138
                                  std::random_access_iterator_tag, BlockT, int,
139
                                  BlockT *, BlockT *> {
140
public:
141
  using difference_type = int;
142
  using pointer = BlockT *;
143
  using reference = BlockT *;
144
145
private:
146
  InstructionT *Inst;
147
  int Idx;
148
  using Self = SuccIterator<InstructionT, BlockT>;
149
150
  inline bool index_is_valid(int Idx) {
151
    // Note that we specially support the index of zero being valid even in the
152
    // face of a null instruction.
153
    return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
154
  }
155
156
  /// Proxy object to allow write access in operator[]
157
  class SuccessorProxy {
158
    Self It;
159
160
  public:
161
    explicit SuccessorProxy(const Self &It) : It(It) {}
162
163
    SuccessorProxy(const SuccessorProxy &) = default;
164
165
    SuccessorProxy &operator=(SuccessorProxy RHS) {
166
      *this = reference(RHS);
167
      return *this;
168
    }
169
170
    SuccessorProxy &operator=(reference RHS) {
171
      It.Inst->setSuccessor(It.Idx, RHS);
172
      return *this;
173
    }
174
175
    operator reference() const { return *It; }
176
  };
177
178
public:
179
  // begin iterator
180
617M
  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::SuccIterator(llvm::Instruction const*)
Line
Count
Source
180
221M
  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::SuccIterator(llvm::Instruction*)
Line
Count
Source
180
395M
  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
181
  // end iterator
182
821M
  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
183
821M
    if (Inst)
184
821M
      Idx = Inst->getNumSuccessors();
185
101
    else
186
101
      // Inst == NULL happens, if a basic block is not fully constructed and
187
101
      // consequently getTerminator() returns NULL. In this case we construct
188
101
      // a SuccIterator which describes a basic block that has zero
189
101
      // successors.
190
101
      // Defining SuccIterator for incomplete and malformed CFGs is especially
191
101
      // useful for debugging.
192
101
      Idx = 0;
193
821M
  }
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::SuccIterator(llvm::Instruction const*, bool)
Line
Count
Source
182
323M
  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
183
323M
    if (Inst)
184
323M
      Idx = Inst->getNumSuccessors();
185
0
    else
186
0
      // Inst == NULL happens, if a basic block is not fully constructed and
187
0
      // consequently getTerminator() returns NULL. In this case we construct
188
0
      // a SuccIterator which describes a basic block that has zero
189
0
      // successors.
190
0
      // Defining SuccIterator for incomplete and malformed CFGs is especially
191
0
      // useful for debugging.
192
0
      Idx = 0;
193
323M
  }
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::SuccIterator(llvm::Instruction*, bool)
Line
Count
Source
182
497M
  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
183
497M
    if (Inst)
184
497M
      Idx = Inst->getNumSuccessors();
185
101
    else
186
101
      // Inst == NULL happens, if a basic block is not fully constructed and
187
101
      // consequently getTerminator() returns NULL. In this case we construct
188
101
      // a SuccIterator which describes a basic block that has zero
189
101
      // successors.
190
101
      // Defining SuccIterator for incomplete and malformed CFGs is especially
191
101
      // useful for debugging.
192
101
      Idx = 0;
193
497M
  }
194
195
  /// This is used to interface between code that wants to
196
  /// operate on terminator instructions directly.
197
52.6M
  int getSuccessorIndex() const { return Idx; }
Unexecuted instantiation: llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::getSuccessorIndex() const
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::getSuccessorIndex() const
Line
Count
Source
197
52.6M
  int getSuccessorIndex() const { return Idx; }
198
199
1.36G
  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::operator==(llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const> const&) const
Line
Count
Source
199
436M
  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::operator==(llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock> const&) const
Line
Count
Source
199
926M
  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
200
201
827M
  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::operator*() const
Line
Count
Source
201
545M
  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::operator*() const
Line
Count
Source
201
281M
  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
202
203
  // We use the basic block pointer directly for operator->.
204
0
  inline BlockT *operator->() const { return operator*(); }
205
206
  inline bool operator<(const Self &RHS) const {
207
    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
208
    return Idx < RHS.Idx;
209
  }
210
211
129M
  int operator-(const Self &RHS) const {
212
129M
    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
213
129M
    return Idx - RHS.Idx;
214
129M
  }
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::operator-(llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const> const&) const
Line
Count
Source
211
11.0M
  int operator-(const Self &RHS) const {
212
11.0M
    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
213
11.0M
    return Idx - RHS.Idx;
214
11.0M
  }
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::operator-(llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock> const&) const
Line
Count
Source
211
118M
  int operator-(const Self &RHS) const {
212
118M
    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
213
118M
    return Idx - RHS.Idx;
214
118M
  }
215
216
883M
  inline Self &operator+=(int RHS) {
217
883M
    int NewIdx = Idx + RHS;
218
883M
    assert(index_is_valid(NewIdx) && "Iterator index out of bound");
219
883M
    Idx = NewIdx;
220
883M
    return *this;
221
883M
  }
llvm::SuccIterator<llvm::Instruction, llvm::BasicBlock>::operator+=(int)
Line
Count
Source
216
657M
  inline Self &operator+=(int RHS) {
217
657M
    int NewIdx = Idx + RHS;
218
657M
    assert(index_is_valid(NewIdx) && "Iterator index out of bound");
219
657M
    Idx = NewIdx;
220
657M
    return *this;
221
657M
  }
llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const>::operator+=(int)
Line
Count
Source
216
225M
  inline Self &operator+=(int RHS) {
217
225M
    int NewIdx = Idx + RHS;
218
225M
    assert(index_is_valid(NewIdx) && "Iterator index out of bound");
219
225M
    Idx = NewIdx;
220
225M
    return *this;
221
225M
  }
222
223
229M
  inline Self &operator-=(int RHS) { return operator+=(-RHS); }
224
225
  // Specially implement the [] operation using a proxy object to support
226
  // assignment.
227
  inline SuccessorProxy operator[](int Offset) {
228
    Self TmpIt = *this;
229
    TmpIt += Offset;
230
    return SuccessorProxy(TmpIt);
231
  }
232
233
  /// Get the source BlockT of this iterator.
234
  inline BlockT *getSource() {
235
    assert(Inst && "Source not available, if basic block was malformed");
236
    return Inst->getParent();
237
  }
238
};
239
240
using succ_iterator = SuccIterator<Instruction, BasicBlock>;
241
using succ_const_iterator = SuccIterator<const Instruction, const BasicBlock>;
242
using succ_range = iterator_range<succ_iterator>;
243
using succ_const_range = iterator_range<succ_const_iterator>;
244
245
31.8M
inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
246
2.69M
inline succ_const_iterator succ_begin(const Instruction *I) {
247
2.69M
  return succ_const_iterator(I);
248
2.69M
}
249
31.8M
inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
250
2.69M
inline succ_const_iterator succ_end(const Instruction *I) {
251
2.69M
  return succ_const_iterator(I, true);
252
2.69M
}
253
0
inline bool succ_empty(const Instruction *I) {
254
0
  return succ_begin(I) == succ_end(I);
255
0
}
256
0
inline unsigned succ_size(const Instruction *I) {
257
0
  return std::distance(succ_begin(I), succ_end(I));
258
0
}
259
31.8M
inline succ_range successors(Instruction *I) {
260
31.8M
  return succ_range(succ_begin(I), succ_end(I));
261
31.8M
}
262
2.69M
inline succ_const_range successors(const Instruction *I) {
263
2.69M
  return succ_const_range(succ_begin(I), succ_end(I));
264
2.69M
}
265
266
363M
inline succ_iterator succ_begin(BasicBlock *BB) {
267
363M
  return succ_iterator(BB->getTerminator());
268
363M
}
269
219M
inline succ_const_iterator succ_begin(const BasicBlock *BB) {
270
219M
  return succ_const_iterator(BB->getTerminator());
271
219M
}
272
465M
inline succ_iterator succ_end(BasicBlock *BB) {
273
465M
  return succ_iterator(BB->getTerminator(), true);
274
465M
}
275
321M
inline succ_const_iterator succ_end(const BasicBlock *BB) {
276
321M
  return succ_const_iterator(BB->getTerminator(), true);
277
321M
}
278
4.69M
inline bool succ_empty(const BasicBlock *BB) {
279
4.69M
  return succ_begin(BB) == succ_end(BB);
280
4.69M
}
281
9.98M
inline unsigned succ_size(const BasicBlock *BB) {
282
9.98M
  return std::distance(succ_begin(BB), succ_end(BB));
283
9.98M
}
284
64.8M
inline succ_range successors(BasicBlock *BB) {
285
64.8M
  return succ_range(succ_begin(BB), succ_end(BB));
286
64.8M
}
287
28.0M
inline succ_const_range successors(const BasicBlock *BB) {
288
28.0M
  return succ_const_range(succ_begin(BB), succ_end(BB));
289
28.0M
}
290
291
//===--------------------------------------------------------------------===//
292
// GraphTraits specializations for basic block graphs (CFGs)
293
//===--------------------------------------------------------------------===//
294
295
// Provide specializations of GraphTraits to be able to treat a function as a
296
// graph of basic blocks...
297
298
template <> struct GraphTraits<BasicBlock*> {
299
  using NodeRef = BasicBlock *;
300
  using ChildIteratorType = succ_iterator;
301
302
11.7M
  static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
303
265M
  static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
304
366M
  static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
305
};
306
307
template <> struct GraphTraits<const BasicBlock*> {
308
  using NodeRef = const BasicBlock *;
309
  using ChildIteratorType = succ_const_iterator;
310
311
5.34M
  static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
312
313
66.5M
  static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
314
131M
  static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
315
};
316
317
// Provide specializations of GraphTraits to be able to treat a function as a
318
// graph of basic blocks... and to walk it in inverse order.  Inverse order for
319
// a function is considered to be when traversing the predecessor edges of a BB
320
// instead of the successor edges.
321
//
322
template <> struct GraphTraits<Inverse<BasicBlock*>> {
323
  using NodeRef = BasicBlock *;
324
  using ChildIteratorType = pred_iterator;
325
326
971
  static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
327
105M
  static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
328
105M
  static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
329
};
330
331
template <> struct GraphTraits<Inverse<const BasicBlock*>> {
332
  using NodeRef = const BasicBlock *;
333
  using ChildIteratorType = const_pred_iterator;
334
335
319
  static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
336
330
  static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
337
676
  static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
338
};
339
340
//===--------------------------------------------------------------------===//
341
// GraphTraits specializations for function basic block graphs (CFGs)
342
//===--------------------------------------------------------------------===//
343
344
// Provide specializations of GraphTraits to be able to treat a function as a
345
// graph of basic blocks... these are the same as the basic block iterators,
346
// except that the root node is implicitly the first node of the function.
347
//
348
template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
349
12.1M
  static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
350
351
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
352
  using nodes_iterator = pointer_iterator<Function::iterator>;
353
354
606k
  static nodes_iterator nodes_begin(Function *F) {
355
606k
    return nodes_iterator(F->begin());
356
606k
  }
357
358
606k
  static nodes_iterator nodes_end(Function *F) {
359
606k
    return nodes_iterator(F->end());
360
606k
  }
361
362
0
  static size_t size(Function *F) { return F->size(); }
363
};
364
template <> struct GraphTraits<const Function*> :
365
  public GraphTraits<const BasicBlock*> {
366
3.04M
  static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
367
368
  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
369
  using nodes_iterator = pointer_iterator<Function::const_iterator>;
370
371
3
  static nodes_iterator nodes_begin(const Function *F) {
372
3
    return nodes_iterator(F->begin());
373
3
  }
374
375
3
  static nodes_iterator nodes_end(const Function *F) {
376
3
    return nodes_iterator(F->end());
377
3
  }
378
379
0
  static size_t size(const Function *F) { return F->size(); }
380
};
381
382
// Provide specializations of GraphTraits to be able to treat a function as a
383
// graph of basic blocks... and to walk it in inverse order.  Inverse order for
384
// a function is considered to be when traversing the predecessor edges of a BB
385
// instead of the successor edges.
386
//
387
template <> struct GraphTraits<Inverse<Function*>> :
388
  public GraphTraits<Inverse<BasicBlock*>> {
389
0
  static NodeRef getEntryNode(Inverse<Function *> G) {
390
0
    return &G.Graph->getEntryBlock();
391
0
  }
392
};
393
template <> struct GraphTraits<Inverse<const Function*>> :
394
  public GraphTraits<Inverse<const BasicBlock*>> {
395
0
  static NodeRef getEntryNode(Inverse<const Function *> G) {
396
0
    return &G.Graph->getEntryBlock();
397
0
  }
398
};
399
400
} // end namespace llvm
401
402
#endif // LLVM_IR_CFG_H