LLVM  9.0.0svn
CFG.h
Go to the documentation of this file.
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"
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"
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*>;
47  USE_iterator It;
48 
49  inline void advancePastNonTerminators() {
50  // Loop to ignore non-terminator uses (for example BlockAddresses).
51  while (!It.atEnd()) {
52  if (auto *Inst = dyn_cast<Instruction>(*It))
53  if (Inst->isTerminator())
54  break;
55 
56  ++It;
57  }
58  }
59 
60 public:
61  using pointer = typename super::pointer;
62  using reference = typename super::reference;
63 
64  PredIterator() = default;
65  explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
66  advancePastNonTerminators();
67  }
68  inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
69 
70  inline bool operator==(const Self& x) const { return It == x.It; }
71  inline bool operator!=(const Self& x) const { return !operator==(x); }
72 
73  inline reference operator*() const {
74  assert(!It.atEnd() && "pred_iterator out of range!");
75  return cast<Instruction>(*It)->getParent();
76  }
77  inline pointer *operator->() const { return &operator*(); }
78 
79  inline Self& operator++() { // Preincrement
80  assert(!It.atEnd() && "pred_iterator out of range!");
81  ++It; advancePastNonTerminators();
82  return *this;
83  }
84 
85  inline Self operator++(int) { // Postincrement
86  Self tmp = *this; ++*this; return tmp;
87  }
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  Use &getUse() const {
98  return It.getUse();
99  }
100 };
101 
103 using const_pred_iterator =
107 
110  return const_pred_iterator(BB);
111 }
112 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
114  return const_pred_iterator(BB, true);
115 }
116 inline bool pred_empty(const BasicBlock *BB) {
117  return pred_begin(BB) == pred_end(BB);
118 }
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 inline unsigned pred_size(const BasicBlock *BB) {
122  return std::distance(pred_begin(BB), pred_end(BB));
123 }
125  return pred_range(pred_begin(BB), pred_end(BB));
126 }
128  return pred_const_range(pred_begin(BB), pred_end(BB));
129 }
130 
131 //===----------------------------------------------------------------------===//
132 // Instruction and BasicBlock succ_iterator helpers
133 //===----------------------------------------------------------------------===//
134 
135 template <class InstructionT, class BlockT>
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;
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  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
181  // end iterator
182  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
183  if (Inst)
184  Idx = Inst->getNumSuccessors();
185  else
186  // Inst == NULL happens, if a basic block is not fully constructed and
187  // consequently getTerminator() returns NULL. In this case we construct
188  // a SuccIterator which describes a basic block that has zero
189  // successors.
190  // Defining SuccIterator for incomplete and malformed CFGs is especially
191  // useful for debugging.
192  Idx = 0;
193  }
194 
195  /// This is used to interface between code that wants to
196  /// operate on terminator instructions directly.
197  int getSuccessorIndex() const { return Idx; }
198 
199  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
200 
201  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
202 
203  // We use the basic block pointer directly for operator->.
204  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  int operator-(const Self &RHS) const {
212  assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
213  return Idx - RHS.Idx;
214  }
215 
216  inline Self &operator+=(int RHS) {
217  int NewIdx = Idx + RHS;
218  assert(index_is_valid(NewIdx) && "Iterator index out of bound");
219  Idx = NewIdx;
220  return *this;
221  }
222 
223  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 
244 
247  return succ_const_iterator(I);
248 }
249 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
251  return succ_const_iterator(I, true);
252 }
253 inline bool succ_empty(const Instruction *I) {
254  return succ_begin(I) == succ_end(I);
255 }
256 inline unsigned succ_size(const Instruction *I) {
257  return std::distance(succ_begin(I), succ_end(I));
258 }
260  return succ_range(succ_begin(I), succ_end(I));
261 }
263  return succ_const_range(succ_begin(I), succ_end(I));
264 }
265 
267  return succ_iterator(BB->getTerminator());
268 }
270  return succ_const_iterator(BB->getTerminator());
271 }
273  return succ_iterator(BB->getTerminator(), true);
274 }
276  return succ_const_iterator(BB->getTerminator(), true);
277 }
278 inline bool succ_empty(const BasicBlock *BB) {
279  return succ_begin(BB) == succ_end(BB);
280 }
281 inline unsigned succ_size(const BasicBlock *BB) {
282  return std::distance(succ_begin(BB), succ_end(BB));
283 }
285  return succ_range(succ_begin(BB), succ_end(BB));
286 }
288  return succ_const_range(succ_begin(BB), succ_end(BB));
289 }
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 *;
301 
302  static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
305 };
306 
307 template <> struct GraphTraits<const BasicBlock*> {
308  using NodeRef = const BasicBlock *;
310 
311  static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
312 
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 *;
325 
329 };
330 
331 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
332  using NodeRef = const BasicBlock *;
334 
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  static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
350 
351  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
353 
355  return nodes_iterator(F->begin());
356  }
357 
359  return nodes_iterator(F->end());
360  }
361 
362  static size_t size(Function *F) { return F->size(); }
363 };
364 template <> struct GraphTraits<const Function*> :
366  static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
367 
368  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
370 
372  return nodes_iterator(F->begin());
373  }
374 
376  return nodes_iterator(F->end());
377  }
378 
379  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*>> :
390  return &G.Graph->getEntryBlock();
391  }
392 };
393 template <> struct GraphTraits<Inverse<const Function*>> :
396  return &G.Graph->getEntryBlock();
397  }
398 };
399 
400 } // end namespace llvm
401 
402 #endif // LLVM_IR_CFG_H
size_t size() const
Definition: Function.h:685
std::string & operator+=(std::string &buffer, StringRef string)
Definition: StringRef.h:888
static NodeRef getEntryNode(const BasicBlock *BB)
Definition: CFG.h:311
BlockT * pointer
Definition: CFG.h:142
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator_range< succ_iterator > succ_range
Definition: CFG.h:242
static NodeRef getEntryNode(Inverse< BasicBlock *> G)
Definition: CFG.h:326
int operator-(const Self &RHS) const
Definition: CFG.h:211
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
Definition: CFG.h:102
iterator end()
Definition: Function.h:682
static NodeRef getEntryNode(BasicBlock *BB)
Definition: CFG.h:302
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:313
int getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly...
Definition: CFG.h:197
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:328
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:137
SuccIterator< const Instruction, const BasicBlock > succ_const_iterator
Definition: CFG.h:241
static NodeRef getEntryNode(Inverse< const Function *> G)
Definition: CFG.h:395
SuccIterator(InstructionT *Inst)
Definition: CFG.h:180
PredIterator(Ptr *bb, bool)
Definition: CFG.h:68
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:337
iterator_range< const_pred_iterator > pred_const_range
Definition: CFG.h:106
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
SuccIterator(InstructionT *Inst, bool)
Definition: CFG.h:182
pointer * operator->() const
Definition: CFG.h:77
bool operator==(const Self &x) const
Definition: CFG.h:199
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:102
reference operator*() const
Definition: CFG.h:73
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:336
BlockT * operator*() const
Definition: CFG.h:201
iterator begin()
Definition: Function.h:680
iterator_range< succ_const_iterator > succ_const_range
Definition: CFG.h:243
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:314
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:67
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:303
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
Use & getUse() const
getUse - Return the operand Use in the predecessor&#39;s terminator of the successor. ...
Definition: CFG.h:97
static nodes_iterator nodes_begin(const Function *F)
Definition: CFG.h:371
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
typename super::reference reference
Definition: CFG.h:62
typename BasicBlock *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
static NodeRef getEntryNode(Inverse< Function *> G)
Definition: CFG.h:389
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Self & operator++()
Definition: CFG.h:79
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:112
iterator_range< pred_iterator > pred_range
Definition: CFG.h:105
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:304
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
static NodeRef getEntryNode(Inverse< const BasicBlock *> G)
Definition: CFG.h:335
bool succ_empty(const Instruction *I)
Definition: CFG.h:253
unsigned getOperandNo() const
getOperandNo - Return the operand number in the predecessor&#39;s terminator of the successor.
Definition: CFG.h:91
static nodes_iterator nodes_end(const Function *F)
Definition: CFG.h:375
BlockT * getSource()
Get the source BlockT of this iterator.
Definition: CFG.h:234
Self & operator-=(int RHS)
Definition: CFG.h:223
const GraphType & Graph
Definition: GraphTraits.h:96
bool operator<(const Self &RHS) const
Definition: CFG.h:206
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
int difference_type
Definition: CFG.h:141
static NodeRef getEntryNode(Function *F)
Definition: CFG.h:349
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
A range adaptor for a pair of iterators.
PredIterator(Ptr *bb)
Definition: CFG.h:65
static size_t size(const Function *F)
Definition: CFG.h:379
static NodeRef getEntryNode(const Function *F)
Definition: CFG.h:366
unsigned succ_size(const Instruction *I)
Definition: CFG.h:256
Self & operator+=(int RHS)
Definition: CFG.h:216
BlockT * operator->() const
Definition: CFG.h:204
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:327
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:240
PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator
Definition: CFG.h:104
BlockT * reference
Definition: CFG.h:143
typename super::pointer pointer
Definition: CFG.h:61
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:121
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static nodes_iterator nodes_end(Function *F)
Definition: CFG.h:358
bool operator!=(const Self &x) const
Definition: CFG.h:71
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PredIterator()=default
aarch64 promote const
bool operator==(const Self &x) const
Definition: CFG.h:70
static nodes_iterator nodes_begin(Function *F)
Definition: CFG.h:354
succ_range successors(Instruction *I)
Definition: CFG.h:259
Self operator++(int)
Definition: CFG.h:85
static size_t size(Function *F)
Definition: CFG.h:362
SuccessorProxy operator[](int Offset)
Definition: CFG.h:227