1 //===- CFG.h ----------------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
18 //===----------------------------------------------------------------------===//
23 #include "llvm/ADT/GraphTraits.h"
24 #include "llvm/ADT/iterator.h"
25 #include "llvm/ADT/iterator_range.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"
31 #include "llvm/Support/type_traits.h"
38 //===----------------------------------------------------------------------===//
39 // BasicBlock pred_iterator definition
40 //===----------------------------------------------------------------------===//
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*> {
46 std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
47 using Self = PredIterator<Ptr, USE_iterator>;
50 inline void advancePastNonTerminators() {
51 // Loop to ignore non-terminator uses (for example BlockAddresses).
53 if (auto *Inst = dyn_cast<Instruction>(*It))
54 if (Inst->isTerminator())
62 using pointer = typename super::pointer;
63 using reference = typename super::reference;
65 PredIterator() = default;
66 explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
67 advancePastNonTerminators();
69 inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
71 inline bool operator==(const Self& x) const { return It == x.It; }
72 inline bool operator!=(const Self& x) const { return !operator==(x); }
74 inline reference operator*() const {
75 assert(!It.atEnd() && "pred_iterator out of range!");
76 return cast<Instruction>(*It)->getParent();
78 inline pointer *operator->() const { return &operator*(); }
80 inline Self& operator++() { // Preincrement
81 assert(!It.atEnd() && "pred_iterator out of range!");
82 ++It; advancePastNonTerminators();
86 inline Self operator++(int) { // Postincrement
87 Self tmp = *this; ++*this; return tmp;
90 /// getOperandNo - Return the operand number in the predecessor's
91 /// terminator of the successor.
92 unsigned getOperandNo() const {
93 return It.getOperandNo();
96 /// getUse - Return the operand Use in the predecessor's terminator
103 using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
104 using const_pred_iterator =
105 PredIterator<const BasicBlock, Value::const_user_iterator>;
106 using pred_range = iterator_range<pred_iterator>;
107 using pred_const_range = iterator_range<const_pred_iterator>;
109 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
110 inline const_pred_iterator pred_begin(const BasicBlock *BB) {
111 return const_pred_iterator(BB);
113 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
114 inline const_pred_iterator pred_end(const BasicBlock *BB) {
115 return const_pred_iterator(BB, true);
117 inline bool pred_empty(const BasicBlock *BB) {
118 return pred_begin(BB) == pred_end(BB);
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));
125 inline pred_range predecessors(BasicBlock *BB) {
126 return pred_range(pred_begin(BB), pred_end(BB));
128 inline pred_const_range predecessors(const BasicBlock *BB) {
129 return pred_const_range(pred_begin(BB), pred_end(BB));
132 //===----------------------------------------------------------------------===//
133 // Instruction and BasicBlock succ_iterator helpers
134 //===----------------------------------------------------------------------===//
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 *> {
142 using difference_type = int;
143 using pointer = BlockT *;
144 using reference = BlockT *;
149 using Self = SuccIterator<InstructionT, BlockT>;
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());
157 /// Proxy object to allow write access in operator[]
158 class SuccessorProxy {
162 explicit SuccessorProxy(const Self &It) : It(It) {}
164 SuccessorProxy(const SuccessorProxy &) = default;
166 SuccessorProxy &operator=(SuccessorProxy RHS) {
167 *this = reference(RHS);
171 SuccessorProxy &operator=(reference RHS) {
172 It.Inst->setSuccessor(It.Idx, RHS);
176 operator reference() const { return *It; }
181 explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
183 inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
185 Idx = Inst->getNumSuccessors();
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
191 // Defining SuccIterator for incomplete and malformed CFGs is especially
192 // useful for debugging.
196 /// This is used to interface between code that wants to
197 /// operate on terminator instructions directly.
198 int getSuccessorIndex() const { return Idx; }
200 inline bool operator==(const Self &x) const { return Idx == x.Idx; }
202 inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
204 // We use the basic block pointer directly for operator->.
205 inline BlockT *operator->() const { return operator*(); }
207 inline bool operator<(const Self &RHS) const {
208 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
209 return Idx < RHS.Idx;
212 int operator-(const Self &RHS) const {
213 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
214 return Idx - RHS.Idx;
217 inline Self &operator+=(int RHS) {
218 int NewIdx = Idx + RHS;
219 assert(index_is_valid(NewIdx) && "Iterator index out of bound");
224 inline Self &operator-=(int RHS) { return operator+=(-RHS); }
226 // Specially implement the [] operation using a proxy object to support
228 inline SuccessorProxy operator[](int Offset) {
231 return SuccessorProxy(TmpIt);
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();
241 template <typename T, typename U> struct isPodLike<SuccIterator<T, U>> {
242 static const bool value = isPodLike<T>::value;
245 using succ_iterator = SuccIterator<Instruction, BasicBlock>;
246 using succ_const_iterator = SuccIterator<const Instruction, const BasicBlock>;
247 using succ_range = iterator_range<succ_iterator>;
248 using succ_const_range = iterator_range<succ_const_iterator>;
250 inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
251 inline succ_const_iterator succ_begin(const Instruction *I) {
252 return succ_const_iterator(I);
254 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
255 inline succ_const_iterator succ_end(const Instruction *I) {
256 return succ_const_iterator(I, true);
258 inline bool succ_empty(const Instruction *I) {
259 return succ_begin(I) == succ_end(I);
261 inline unsigned succ_size(const Instruction *I) {
262 return std::distance(succ_begin(I), succ_end(I));
264 inline succ_range successors(Instruction *I) {
265 return succ_range(succ_begin(I), succ_end(I));
267 inline succ_const_range successors(const Instruction *I) {
268 return succ_const_range(succ_begin(I), succ_end(I));
271 inline succ_iterator succ_begin(BasicBlock *BB) {
272 return succ_iterator(BB->getTerminator());
274 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
275 return succ_const_iterator(BB->getTerminator());
277 inline succ_iterator succ_end(BasicBlock *BB) {
278 return succ_iterator(BB->getTerminator(), true);
280 inline succ_const_iterator succ_end(const BasicBlock *BB) {
281 return succ_const_iterator(BB->getTerminator(), true);
283 inline bool succ_empty(const BasicBlock *BB) {
284 return succ_begin(BB) == succ_end(BB);
286 inline unsigned succ_size(const BasicBlock *BB) {
287 return std::distance(succ_begin(BB), succ_end(BB));
289 inline succ_range successors(BasicBlock *BB) {
290 return succ_range(succ_begin(BB), succ_end(BB));
292 inline succ_const_range successors(const BasicBlock *BB) {
293 return succ_const_range(succ_begin(BB), succ_end(BB));
296 //===--------------------------------------------------------------------===//
297 // GraphTraits specializations for basic block graphs (CFGs)
298 //===--------------------------------------------------------------------===//
300 // Provide specializations of GraphTraits to be able to treat a function as a
301 // graph of basic blocks...
303 template <> struct GraphTraits<BasicBlock*> {
304 using NodeRef = BasicBlock *;
305 using ChildIteratorType = succ_iterator;
307 static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
308 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
309 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
312 template <> struct GraphTraits<const BasicBlock*> {
313 using NodeRef = const BasicBlock *;
314 using ChildIteratorType = succ_const_iterator;
316 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
318 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
319 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
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.
327 template <> struct GraphTraits<Inverse<BasicBlock*>> {
328 using NodeRef = BasicBlock *;
329 using ChildIteratorType = pred_iterator;
331 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
332 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
333 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
336 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
337 using NodeRef = const BasicBlock *;
338 using ChildIteratorType = const_pred_iterator;
340 static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
341 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
342 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
345 //===--------------------------------------------------------------------===//
346 // GraphTraits specializations for function basic block graphs (CFGs)
347 //===--------------------------------------------------------------------===//
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.
353 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
354 static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
356 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
357 using nodes_iterator = pointer_iterator<Function::iterator>;
359 static nodes_iterator nodes_begin(Function *F) {
360 return nodes_iterator(F->begin());
363 static nodes_iterator nodes_end(Function *F) {
364 return nodes_iterator(F->end());
367 static size_t size(Function *F) { return F->size(); }
369 template <> struct GraphTraits<const Function*> :
370 public GraphTraits<const BasicBlock*> {
371 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
373 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
374 using nodes_iterator = pointer_iterator<Function::const_iterator>;
376 static nodes_iterator nodes_begin(const Function *F) {
377 return nodes_iterator(F->begin());
380 static nodes_iterator nodes_end(const Function *F) {
381 return nodes_iterator(F->end());
384 static size_t size(const Function *F) { return F->size(); }
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.
392 template <> struct GraphTraits<Inverse<Function*>> :
393 public GraphTraits<Inverse<BasicBlock*>> {
394 static NodeRef getEntryNode(Inverse<Function *> G) {
395 return &G.Graph->getEntryBlock();
398 template <> struct GraphTraits<Inverse<const Function*>> :
399 public GraphTraits<Inverse<const BasicBlock*>> {
400 static NodeRef getEntryNode(Inverse<const Function *> G) {
401 return &G.Graph->getEntryBlock();
405 } // end namespace llvm
407 #endif // LLVM_IR_CFG_H