LLVM  8.0.0svn
CFG.h
Go to the documentation of this file.
1 //===- CFG.h ----------------------------------------------------*- 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 /// \file
10 ///
11 /// This file provides various utilities for inspecting and working with the
12 /// control flow graph in LLVM IR. This includes generic facilities for
13 /// iterating successors and predecessors of basic blocks, the successors of
14 /// specific terminator instructions, etc. It also defines specializations of
15 /// GraphTraits that allow Function and BasicBlock graphs to be treated as
16 /// proper graphs for generic algorithms.
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_IR_CFG_H
21 #define LLVM_IR_CFG_H
22 
23 #include "llvm/ADT/GraphTraits.h"
24 #include "llvm/ADT/iterator.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/InstrTypes.h"
29 #include "llvm/IR/Value.h"
30 #include "llvm/Support/Casting.h"
32 #include <cassert>
33 #include <cstddef>
34 #include <iterator>
35 
36 namespace llvm {
37 
38 //===----------------------------------------------------------------------===//
39 // BasicBlock pred_iterator definition
40 //===----------------------------------------------------------------------===//
41 
42 template <class Ptr, class USE_iterator> // Predecessor Iterator
43 class PredIterator : public std::iterator<std::forward_iterator_tag,
44  Ptr, ptrdiff_t, Ptr*, Ptr*> {
45  using super =
46  std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
48  USE_iterator It;
49 
50  inline void advancePastNonTerminators() {
51  // Loop to ignore non-terminator uses (for example BlockAddresses).
52  while (!It.atEnd()) {
53  if (auto *Inst = dyn_cast<Instruction>(*It))
54  if (Inst->isTerminator())
55  break;
56 
57  ++It;
58  }
59  }
60 
61 public:
62  using pointer = typename super::pointer;
63  using reference = typename super::reference;
64 
65  PredIterator() = default;
66  explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
67  advancePastNonTerminators();
68  }
69  inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
70 
71  inline bool operator==(const Self& x) const { return It == x.It; }
72  inline bool operator!=(const Self& x) const { return !operator==(x); }
73 
74  inline reference operator*() const {
75  assert(!It.atEnd() && "pred_iterator out of range!");
76  return cast<Instruction>(*It)->getParent();
77  }
78  inline pointer *operator->() const { return &operator*(); }
79 
80  inline Self& operator++() { // Preincrement
81  assert(!It.atEnd() && "pred_iterator out of range!");
82  ++It; advancePastNonTerminators();
83  return *this;
84  }
85 
86  inline Self operator++(int) { // Postincrement
87  Self tmp = *this; ++*this; return tmp;
88  }
89 
90  /// getOperandNo - Return the operand number in the predecessor's
91  /// terminator of the successor.
92  unsigned getOperandNo() const {
93  return It.getOperandNo();
94  }
95 
96  /// getUse - Return the operand Use in the predecessor's terminator
97  /// of the successor.
98  Use &getUse() const {
99  return It.getUse();
100  }
101 };
102 
104 using const_pred_iterator =
108 
111  return const_pred_iterator(BB);
112 }
113 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
115  return const_pred_iterator(BB, true);
116 }
117 inline bool pred_empty(const BasicBlock *BB) {
118  return pred_begin(BB) == pred_end(BB);
119 }
120 inline unsigned pred_size(const BasicBlock *BB) {
121  return std::distance(pred_begin(BB), pred_end(BB));
122 }
124  return pred_range(pred_begin(BB), pred_end(BB));
125 }
127  return pred_const_range(pred_begin(BB), pred_end(BB));
128 }
129 
130 //===----------------------------------------------------------------------===//
131 // Instruction and BasicBlock succ_iterator helpers
132 //===----------------------------------------------------------------------===//
133 
134 template <class InstructionT, class BlockT>
136  : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
137  std::random_access_iterator_tag, BlockT, int,
138  BlockT *, BlockT *> {
139 public:
140  using difference_type = int;
141  using pointer = BlockT *;
142  using reference = BlockT *;
143 
144 private:
145  InstructionT *Inst;
146  int Idx;
148 
149  inline bool index_is_valid(int Idx) {
150  // Note that we specially support the index of zero being valid even in the
151  // face of a null instruction.
152  return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
153  }
154 
155  /// Proxy object to allow write access in operator[]
156  class SuccessorProxy {
157  Self It;
158 
159  public:
160  explicit SuccessorProxy(const Self &It) : It(It) {}
161 
162  SuccessorProxy(const SuccessorProxy &) = default;
163 
164  SuccessorProxy &operator=(SuccessorProxy RHS) {
165  *this = reference(RHS);
166  return *this;
167  }
168 
169  SuccessorProxy &operator=(reference RHS) {
170  It.Inst->setSuccessor(It.Idx, RHS);
171  return *this;
172  }
173 
174  operator reference() const { return *It; }
175  };
176 
177 public:
178  // begin iterator
179  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
180  // end iterator
181  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
182  if (Inst)
183  Idx = Inst->getNumSuccessors();
184  else
185  // Inst == NULL happens, if a basic block is not fully constructed and
186  // consequently getTerminator() returns NULL. In this case we construct
187  // a SuccIterator which describes a basic block that has zero
188  // successors.
189  // Defining SuccIterator for incomplete and malformed CFGs is especially
190  // useful for debugging.
191  Idx = 0;
192  }
193 
194  /// This is used to interface between code that wants to
195  /// operate on terminator instructions directly.
196  int getSuccessorIndex() const { return Idx; }
197 
198  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
199 
200  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
201 
202  // We use the basic block pointer directly for operator->.
203  inline BlockT *operator->() const { return operator*(); }
204 
205  inline bool operator<(const Self &RHS) const {
206  assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
207  return Idx < RHS.Idx;
208  }
209 
210  int operator-(const Self &RHS) const {
211  assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
212  return Idx - RHS.Idx;
213  }
214 
215  inline Self &operator+=(int RHS) {
216  int NewIdx = Idx + RHS;
217  assert(index_is_valid(NewIdx) && "Iterator index out of bound");
218  Idx = NewIdx;
219  return *this;
220  }
221 
222  inline Self &operator-=(int RHS) { return operator+=(-RHS); }
223 
224  // Specially implement the [] operation using a proxy object to support
225  // assignment.
226  inline SuccessorProxy operator[](int Offset) {
227  Self TmpIt = *this;
228  TmpIt += Offset;
229  return SuccessorProxy(TmpIt);
230  }
231 
232  /// Get the source BlockT of this iterator.
233  inline BlockT *getSource() {
234  assert(Inst && "Source not available, if basic block was malformed");
235  return Inst->getParent();
236  }
237 };
238 
239 template <typename T, typename U> struct isPodLike<SuccIterator<T, U>> {
240  static const bool value = isPodLike<T>::value;
241 };
242 
247 
250  return succ_const_iterator(I);
251 }
252 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
254  return succ_const_iterator(I, true);
255 }
256 inline bool succ_empty(const Instruction *I) {
257  return succ_begin(I) == succ_end(I);
258 }
259 inline unsigned succ_size(const Instruction *I) {
260  return std::distance(succ_begin(I), succ_end(I));
261 }
263  return succ_range(succ_begin(I), succ_end(I));
264 }
266  return succ_const_range(succ_begin(I), succ_end(I));
267 }
268 
270  return succ_iterator(BB->getTerminator());
271 }
273  return succ_const_iterator(BB->getTerminator());
274 }
276  return succ_iterator(BB->getTerminator(), true);
277 }
279  return succ_const_iterator(BB->getTerminator(), true);
280 }
281 inline bool succ_empty(const BasicBlock *BB) {
282  return succ_begin(BB) == succ_end(BB);
283 }
284 inline unsigned succ_size(const BasicBlock *BB) {
285  return std::distance(succ_begin(BB), succ_end(BB));
286 }
288  return succ_range(succ_begin(BB), succ_end(BB));
289 }
291  return succ_const_range(succ_begin(BB), succ_end(BB));
292 }
293 
294 //===--------------------------------------------------------------------===//
295 // GraphTraits specializations for basic block graphs (CFGs)
296 //===--------------------------------------------------------------------===//
297 
298 // Provide specializations of GraphTraits to be able to treat a function as a
299 // graph of basic blocks...
300 
301 template <> struct GraphTraits<BasicBlock*> {
302  using NodeRef = BasicBlock *;
304 
305  static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
308 };
309 
310 template <> struct GraphTraits<const BasicBlock*> {
311  using NodeRef = const BasicBlock *;
313 
314  static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
315 
318 };
319 
320 // Provide specializations of GraphTraits to be able to treat a function as a
321 // graph of basic blocks... and to walk it in inverse order. Inverse order for
322 // a function is considered to be when traversing the predecessor edges of a BB
323 // instead of the successor edges.
324 //
325 template <> struct GraphTraits<Inverse<BasicBlock*>> {
326  using NodeRef = BasicBlock *;
328 
332 };
333 
334 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
335  using NodeRef = const BasicBlock *;
337 
341 };
342 
343 //===--------------------------------------------------------------------===//
344 // GraphTraits specializations for function basic block graphs (CFGs)
345 //===--------------------------------------------------------------------===//
346 
347 // Provide specializations of GraphTraits to be able to treat a function as a
348 // graph of basic blocks... these are the same as the basic block iterators,
349 // except that the root node is implicitly the first node of the function.
350 //
351 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
352  static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
353 
354  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
356 
358  return nodes_iterator(F->begin());
359  }
360 
362  return nodes_iterator(F->end());
363  }
364 
365  static size_t size(Function *F) { return F->size(); }
366 };
367 template <> struct GraphTraits<const Function*> :
369  static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
370 
371  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
373 
375  return nodes_iterator(F->begin());
376  }
377 
379  return nodes_iterator(F->end());
380  }
381 
382  static size_t size(const Function *F) { return F->size(); }
383 };
384 
385 // Provide specializations of GraphTraits to be able to treat a function as a
386 // graph of basic blocks... and to walk it in inverse order. Inverse order for
387 // a function is considered to be when traversing the predecessor edges of a BB
388 // instead of the successor edges.
389 //
390 template <> struct GraphTraits<Inverse<Function*>> :
393  return &G.Graph->getEntryBlock();
394  }
395 };
396 template <> struct GraphTraits<Inverse<const Function*>> :
399  return &G.Graph->getEntryBlock();
400  }
401 };
402 
403 } // end namespace llvm
404 
405 #endif // LLVM_IR_CFG_H
size_t size() const
Definition: Function.h:661
std::string & operator+=(std::string &buffer, StringRef string)
Definition: StringRef.h:921
static NodeRef getEntryNode(const BasicBlock *BB)
Definition: CFG.h:314
BlockT * pointer
Definition: CFG.h:141
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator_range< succ_iterator > succ_range
Definition: CFG.h:245
static NodeRef getEntryNode(Inverse< BasicBlock *> G)
Definition: CFG.h:329
int operator-(const Self &RHS) const
Definition: CFG.h:210
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
Definition: CFG.h:103
iterator end()
Definition: Function.h:658
static NodeRef getEntryNode(BasicBlock *BB)
Definition: CFG.h:305
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:316
int getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: CFG.h:196
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:331
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
SuccIterator< const Instruction, const BasicBlock > succ_const_iterator
Definition: CFG.h:244
static NodeRef getEntryNode(Inverse< const Function *> G)
Definition: CFG.h:398
SuccIterator(InstructionT *Inst)
Definition: CFG.h:179
PredIterator(Ptr *bb, bool)
Definition: CFG.h:69
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:340
iterator_range< const_pred_iterator > pred_const_range
Definition: CFG.h:107
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
SuccIterator(InstructionT *Inst, bool)
Definition: CFG.h:181
pointer * operator->() const
Definition: CFG.h:78
bool operator==(const Self &x) const
Definition: CFG.h:198
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
reference operator*() const
Definition: CFG.h:74
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:339
BlockT * operator*() const
Definition: CFG.h:200
iterator begin()
Definition: Function.h:656
iterator_range< succ_const_iterator > succ_const_range
Definition: CFG.h:246
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:317
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:306
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
Use & getUse() const
getUse - Return the operand Use in the predecessor&#39;s terminator of the successor. ...
Definition: CFG.h:98
static nodes_iterator nodes_begin(const Function *F)
Definition: CFG.h:374
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
typename super::reference reference
Definition: CFG.h:63
typename BasicBlock *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:79
static NodeRef getEntryNode(Inverse< Function *> G)
Definition: CFG.h:392
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Self & operator++()
Definition: CFG.h:80
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
iterator_range< pred_iterator > pred_range
Definition: CFG.h:106
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:307
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:117
static NodeRef getEntryNode(Inverse< const BasicBlock *> G)
Definition: CFG.h:338
bool succ_empty(const Instruction *I)
Definition: CFG.h:256
unsigned getOperandNo() const
getOperandNo - Return the operand number in the predecessor&#39;s terminator of the successor.
Definition: CFG.h:92
static nodes_iterator nodes_end(const Function *F)
Definition: CFG.h:378
BlockT * getSource()
Get the source BlockT of this iterator.
Definition: CFG.h:233
Self & operator-=(int RHS)
Definition: CFG.h:222
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
Definition: ArrayRef.h:530
const GraphType & Graph
Definition: GraphTraits.h:97
bool operator<(const Self &RHS) const
Definition: CFG.h:205
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
int difference_type
Definition: CFG.h:140
static NodeRef getEntryNode(Function *F)
Definition: CFG.h:352
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:123
A range adaptor for a pair of iterators.
PredIterator(Ptr *bb)
Definition: CFG.h:66
static size_t size(const Function *F)
Definition: CFG.h:382
static NodeRef getEntryNode(const Function *F)
Definition: CFG.h:369
unsigned succ_size(const Instruction *I)
Definition: CFG.h:259
Self & operator+=(int RHS)
Definition: CFG.h:215
BlockT * operator->() const
Definition: CFG.h:203
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:330
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:243
PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator
Definition: CFG.h:105
BlockT * reference
Definition: CFG.h:142
typename super::pointer pointer
Definition: CFG.h:62
unsigned pred_size(const BasicBlock *BB)
Definition: CFG.h:120
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static nodes_iterator nodes_end(Function *F)
Definition: CFG.h:361
bool operator!=(const Self &x) const
Definition: CFG.h:72
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PredIterator()=default
aarch64 promote const
bool operator==(const Self &x) const
Definition: CFG.h:71
static nodes_iterator nodes_begin(Function *F)
Definition: CFG.h:357
succ_range successors(Instruction *I)
Definition: CFG.h:262
Self operator++(int)
Definition: CFG.h:86
static size_t size(Function *F)
Definition: CFG.h:365
SuccessorProxy operator[](int Offset)
Definition: CFG.h:226