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 /// Get the number of predecessors of \p BB. This is a linear time operation.
121 /// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
122 inline unsigned pred_size(const BasicBlock *BB) {
123  return std::distance(pred_begin(BB), pred_end(BB));
124 }
126  return pred_range(pred_begin(BB), pred_end(BB));
127 }
129  return pred_const_range(pred_begin(BB), pred_end(BB));
130 }
131 
132 //===----------------------------------------------------------------------===//
133 // Instruction and BasicBlock succ_iterator helpers
134 //===----------------------------------------------------------------------===//
135 
136 template <class InstructionT, class BlockT>
138  : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
139  std::random_access_iterator_tag, BlockT, int,
140  BlockT *, BlockT *> {
141 public:
142  using difference_type = int;
143  using pointer = BlockT *;
144  using reference = BlockT *;
145 
146 private:
147  InstructionT *Inst;
148  int Idx;
150 
151  inline bool index_is_valid(int Idx) {
152  // Note that we specially support the index of zero being valid even in the
153  // face of a null instruction.
154  return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
155  }
156 
157  /// Proxy object to allow write access in operator[]
158  class SuccessorProxy {
159  Self It;
160 
161  public:
162  explicit SuccessorProxy(const Self &It) : It(It) {}
163 
164  SuccessorProxy(const SuccessorProxy &) = default;
165 
166  SuccessorProxy &operator=(SuccessorProxy RHS) {
167  *this = reference(RHS);
168  return *this;
169  }
170 
171  SuccessorProxy &operator=(reference RHS) {
172  It.Inst->setSuccessor(It.Idx, RHS);
173  return *this;
174  }
175 
176  operator reference() const { return *It; }
177  };
178 
179 public:
180  // begin iterator
181  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
182  // end iterator
183  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
184  if (Inst)
185  Idx = Inst->getNumSuccessors();
186  else
187  // Inst == NULL happens, if a basic block is not fully constructed and
188  // consequently getTerminator() returns NULL. In this case we construct
189  // a SuccIterator which describes a basic block that has zero
190  // successors.
191  // Defining SuccIterator for incomplete and malformed CFGs is especially
192  // useful for debugging.
193  Idx = 0;
194  }
195 
196  /// This is used to interface between code that wants to
197  /// operate on terminator instructions directly.
198  int getSuccessorIndex() const { return Idx; }
199 
200  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
201 
202  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
203 
204  // We use the basic block pointer directly for operator->.
205  inline BlockT *operator->() const { return operator*(); }
206 
207  inline bool operator<(const Self &RHS) const {
208  assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
209  return Idx < RHS.Idx;
210  }
211 
212  int operator-(const Self &RHS) const {
213  assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
214  return Idx - RHS.Idx;
215  }
216 
217  inline Self &operator+=(int RHS) {
218  int NewIdx = Idx + RHS;
219  assert(index_is_valid(NewIdx) && "Iterator index out of bound");
220  Idx = NewIdx;
221  return *this;
222  }
223 
224  inline Self &operator-=(int RHS) { return operator+=(-RHS); }
225 
226  // Specially implement the [] operation using a proxy object to support
227  // assignment.
228  inline SuccessorProxy operator[](int Offset) {
229  Self TmpIt = *this;
230  TmpIt += Offset;
231  return SuccessorProxy(TmpIt);
232  }
233 
234  /// Get the source BlockT of this iterator.
235  inline BlockT *getSource() {
236  assert(Inst && "Source not available, if basic block was malformed");
237  return Inst->getParent();
238  }
239 };
240 
241 template <typename T, typename U> struct isPodLike<SuccIterator<T, U>> {
242  static const bool value = isPodLike<T>::value;
243 };
244 
249 
252  return succ_const_iterator(I);
253 }
254 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
256  return succ_const_iterator(I, true);
257 }
258 inline bool succ_empty(const Instruction *I) {
259  return succ_begin(I) == succ_end(I);
260 }
261 inline unsigned succ_size(const Instruction *I) {
262  return std::distance(succ_begin(I), succ_end(I));
263 }
265  return succ_range(succ_begin(I), succ_end(I));
266 }
268  return succ_const_range(succ_begin(I), succ_end(I));
269 }
270 
272  return succ_iterator(BB->getTerminator());
273 }
275  return succ_const_iterator(BB->getTerminator());
276 }
278  return succ_iterator(BB->getTerminator(), true);
279 }
281  return succ_const_iterator(BB->getTerminator(), true);
282 }
283 inline bool succ_empty(const BasicBlock *BB) {
284  return succ_begin(BB) == succ_end(BB);
285 }
286 inline unsigned succ_size(const BasicBlock *BB) {
287  return std::distance(succ_begin(BB), succ_end(BB));
288 }
290  return succ_range(succ_begin(BB), succ_end(BB));
291 }
293  return succ_const_range(succ_begin(BB), succ_end(BB));
294 }
295 
296 //===--------------------------------------------------------------------===//
297 // GraphTraits specializations for basic block graphs (CFGs)
298 //===--------------------------------------------------------------------===//
299 
300 // Provide specializations of GraphTraits to be able to treat a function as a
301 // graph of basic blocks...
302 
303 template <> struct GraphTraits<BasicBlock*> {
304  using NodeRef = BasicBlock *;
306 
307  static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
310 };
311 
312 template <> struct GraphTraits<const BasicBlock*> {
313  using NodeRef = const BasicBlock *;
315 
316  static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
317 
320 };
321 
322 // Provide specializations of GraphTraits to be able to treat a function as a
323 // graph of basic blocks... and to walk it in inverse order. Inverse order for
324 // a function is considered to be when traversing the predecessor edges of a BB
325 // instead of the successor edges.
326 //
327 template <> struct GraphTraits<Inverse<BasicBlock*>> {
328  using NodeRef = BasicBlock *;
330 
334 };
335 
336 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
337  using NodeRef = const BasicBlock *;
339 
343 };
344 
345 //===--------------------------------------------------------------------===//
346 // GraphTraits specializations for function basic block graphs (CFGs)
347 //===--------------------------------------------------------------------===//
348 
349 // Provide specializations of GraphTraits to be able to treat a function as a
350 // graph of basic blocks... these are the same as the basic block iterators,
351 // except that the root node is implicitly the first node of the function.
352 //
353 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
354  static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
355 
356  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
358 
360  return nodes_iterator(F->begin());
361  }
362 
364  return nodes_iterator(F->end());
365  }
366 
367  static size_t size(Function *F) { return F->size(); }
368 };
369 template <> struct GraphTraits<const Function*> :
371  static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
372 
373  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
375 
377  return nodes_iterator(F->begin());
378  }
379 
381  return nodes_iterator(F->end());
382  }
383 
384  static size_t size(const Function *F) { return F->size(); }
385 };
386 
387 // Provide specializations of GraphTraits to be able to treat a function as a
388 // graph of basic blocks... and to walk it in inverse order. Inverse order for
389 // a function is considered to be when traversing the predecessor edges of a BB
390 // instead of the successor edges.
391 //
392 template <> struct GraphTraits<Inverse<Function*>> :
395  return &G.Graph->getEntryBlock();
396  }
397 };
398 template <> struct GraphTraits<Inverse<const Function*>> :
401  return &G.Graph->getEntryBlock();
402  }
403 };
404 
405 } // end namespace llvm
406 
407 #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:316
BlockT * pointer
Definition: CFG.h:143
This class represents lattice values for constants.
Definition: AllocatorList.h:24
iterator_range< succ_iterator > succ_range
Definition: CFG.h:247
static NodeRef getEntryNode(Inverse< BasicBlock *> G)
Definition: CFG.h:331
int operator-(const Self &RHS) const
Definition: CFG.h:212
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:307
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:318
int getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: CFG.h:198
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:333
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:246
static NodeRef getEntryNode(Inverse< const Function *> G)
Definition: CFG.h:400
SuccIterator(InstructionT *Inst)
Definition: CFG.h:181
PredIterator(Ptr *bb, bool)
Definition: CFG.h:69
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:342
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:183
pointer * operator->() const
Definition: CFG.h:78
bool operator==(const Self &x) const
Definition: CFG.h:200
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:341
BlockT * operator*() const
Definition: CFG.h:202
iterator begin()
Definition: Function.h:656
iterator_range< succ_const_iterator > succ_const_range
Definition: CFG.h:248
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:319
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:308
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:376
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:394
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:309
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:117
static NodeRef getEntryNode(Inverse< const BasicBlock *> G)
Definition: CFG.h:340
bool succ_empty(const Instruction *I)
Definition: CFG.h:258
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:380
BlockT * getSource()
Get the source BlockT of this iterator.
Definition: CFG.h:235
Self & operator-=(int RHS)
Definition: CFG.h:224
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:207
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
int difference_type
Definition: CFG.h:142
static NodeRef getEntryNode(Function *F)
Definition: CFG.h:354
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
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:384
static NodeRef getEntryNode(const Function *F)
Definition: CFG.h:371
unsigned succ_size(const Instruction *I)
Definition: CFG.h:261
Self & operator+=(int RHS)
Definition: CFG.h:217
BlockT * operator->() const
Definition: CFG.h:205
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:332
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:245
PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator
Definition: CFG.h:105
BlockT * reference
Definition: CFG.h:144
typename super::pointer pointer
Definition: CFG.h:62
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:122
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static nodes_iterator nodes_end(Function *F)
Definition: CFG.h:363
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:359
succ_range successors(Instruction *I)
Definition: CFG.h:264
Self operator++(int)
Definition: CFG.h:86
static size_t size(Function *F)
Definition: CFG.h:367
SuccessorProxy operator[](int Offset)
Definition: CFG.h:228