CFG.h revision 4bf393a13e779d7a8eac3647df1781068a6dc732 
1//===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- 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//
10// This file defines specializations of GraphTraits that allow Function and
11// BasicBlock graphs to be treated as proper graphs for generic algorithms.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_SUPPORT_CFG_H
16#define LLVM_SUPPORT_CFG_H
17
18#include "llvm/ADT/GraphTraits.h"
19#include "llvm/Function.h"
20#include "llvm/InstrTypes.h"
21#include "llvm/ADT/iterator"
22
23namespace llvm {
24
25//===--------------------------------------------------------------------===//
26// BasicBlock pred_iterator definition
27//===--------------------------------------------------------------------===//
28
29template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
30class PredIterator : public forward_iterator<_Ptr, ptrdiff_t> {
31  typedef forward_iterator<_Ptr, ptrdiff_t> super;
32  _USE_iterator It;
33public:
34  typedef PredIterator<_Ptr,_USE_iterator> _Self;
35  typedef typename super::pointer pointer;
36
37  inline void advancePastNonPreds() {
38    // Loop to ignore non predecessor uses (for example PHI nodes)...
39    while (!It.atEnd()) {
40      if (isa<TerminatorInst>(*It) || isa<BasicBlock>(*It))
41	break;
42      ++It;
43    }
44  }
45
46  inline PredIterator(_Ptr *bb) : It(bb->use_begin()) {
47    advancePastNonPreds();
48  }
49  inline PredIterator(_Ptr *bb, bool) : It(bb->use_end()) {}
50
51  inline bool operator==(const _Self& x) const { return It == x.It; }
52  inline bool operator!=(const _Self& x) const { return !operator==(x); }
53
54  inline pointer operator*() const {
55    assert(!It.atEnd() && "pred_iterator out of range!");
56    if (isa<TerminatorInst>(*It))      // not dyn_cast due to const-correctness
57      return cast<TerminatorInst>(*It)->getParent();
58
59    return cast<_Ptr>(*It);
60  }
61  inline pointer *operator->() const { return &(operator*()); }
62
63  inline _Self& operator++() {   // Preincrement
64    assert(!It.atEnd() && "pred_iterator out of range!");
65    ++It; advancePastNonPreds();
66    return *this;
67  }
68
69  inline _Self operator++(int) { // Postincrement
70    _Self tmp = *this; ++*this; return tmp;
71  }
72};
73
74typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
75typedef PredIterator<const BasicBlock,
76                     Value::use_const_iterator> pred_const_iterator;
77
78inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
79inline pred_const_iterator pred_begin(const BasicBlock *BB) {
80  return pred_const_iterator(BB);
81}
82inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
83inline pred_const_iterator pred_end(const BasicBlock *BB) {
84  return pred_const_iterator(BB, true);
85}
86
87
88
89//===--------------------------------------------------------------------===//
90// BasicBlock succ_iterator definition
91//===--------------------------------------------------------------------===//
92
93template <class Term_, class BB_>           // Successor Iterator
94class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> {
95  const Term_ Term;
96  unsigned idx;
97  typedef bidirectional_iterator<BB_, ptrdiff_t> super;
98public:
99  typedef SuccIterator<Term_, BB_> _Self;
100  typedef typename super::pointer pointer;
101  // TODO: This can be random access iterator, need operator+ and stuff tho
102
103  inline SuccIterator(Term_ T) : Term(T), idx(0) {         // begin iterator
104    assert(T && "getTerminator returned null!");
105  }
106  inline SuccIterator(Term_ T, bool)                       // end iterator
107    : Term(T), idx(Term->getNumSuccessors()) {
108    assert(T && "getTerminator returned null!");
109    if (Term->getParent()->getUnwindDest())
110      ++idx;
111  }
112
113  inline const _Self &operator=(const _Self &I) {
114    assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
115    idx = I.idx;
116    return *this;
117  }
118
119  /// getSuccessorIndex - This is used to interface between code that wants to
120  /// operate on terminator instructions directly.
121  unsigned getSuccessorIndex() const { return idx; }
122
123  inline bool operator==(const _Self& x) const { return idx == x.idx; }
124  inline bool operator!=(const _Self& x) const { return !operator==(x); }
125
126  inline pointer operator*() const {
127    if (idx == Term->getNumSuccessors())
128      return Term->getParent()->getUnwindDest();
129
130    return Term->getSuccessor(idx);
131  }
132  inline pointer operator->() const { return operator*(); }
133
134  inline _Self& operator++() { ++idx; return *this; } // Preincrement
135  inline _Self operator++(int) { // Postincrement
136    _Self tmp = *this; ++*this; return tmp;
137  }
138
139  inline _Self& operator--() { --idx; return *this; }  // Predecrement
140  inline _Self operator--(int) { // Postdecrement
141    _Self tmp = *this; --*this; return tmp;
142  }
143};
144
145typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
146typedef SuccIterator<const TerminatorInst*,
147                     const BasicBlock> succ_const_iterator;
148
149inline succ_iterator succ_begin(BasicBlock *BB) {
150  return succ_iterator(BB->getTerminator());
151}
152inline succ_const_iterator succ_begin(const BasicBlock *BB) {
153  return succ_const_iterator(BB->getTerminator());
154}
155inline succ_iterator succ_end(BasicBlock *BB) {
156  return succ_iterator(BB->getTerminator(), true);
157}
158inline succ_const_iterator succ_end(const BasicBlock *BB) {
159  return succ_const_iterator(BB->getTerminator(), true);
160}
161
162
163
164//===--------------------------------------------------------------------===//
165// GraphTraits specializations for basic block graphs (CFGs)
166//===--------------------------------------------------------------------===//
167
168// Provide specializations of GraphTraits to be able to treat a function as a
169// graph of basic blocks...
170
171template <> struct GraphTraits<BasicBlock*> {
172  typedef BasicBlock NodeType;
173  typedef succ_iterator ChildIteratorType;
174
175  static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
176  static inline ChildIteratorType child_begin(NodeType *N) {
177    return succ_begin(N);
178  }
179  static inline ChildIteratorType child_end(NodeType *N) {
180    return succ_end(N);
181  }
182};
183
184template <> struct GraphTraits<const BasicBlock*> {
185  typedef const BasicBlock NodeType;
186  typedef succ_const_iterator ChildIteratorType;
187
188  static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
189
190  static inline ChildIteratorType child_begin(NodeType *N) {
191    return succ_begin(N);
192  }
193  static inline ChildIteratorType child_end(NodeType *N) {
194    return succ_end(N);
195  }
196};
197
198// Provide specializations of GraphTraits to be able to treat a function as a
199// graph of basic blocks... and to walk it in inverse order.  Inverse order for
200// a function is considered to be when traversing the predecessor edges of a BB
201// instead of the successor edges.
202//
203template <> struct GraphTraits<Inverse<BasicBlock*> > {
204  typedef BasicBlock NodeType;
205  typedef pred_iterator ChildIteratorType;
206  static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
207  static inline ChildIteratorType child_begin(NodeType *N) {
208    return pred_begin(N);
209  }
210  static inline ChildIteratorType child_end(NodeType *N) {
211    return pred_end(N);
212  }
213};
214
215template <> struct GraphTraits<Inverse<const BasicBlock*> > {
216  typedef const BasicBlock NodeType;
217  typedef pred_const_iterator ChildIteratorType;
218  static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
219    return G.Graph;
220  }
221  static inline ChildIteratorType child_begin(NodeType *N) {
222    return pred_begin(N);
223  }
224  static inline ChildIteratorType child_end(NodeType *N) {
225    return pred_end(N);
226  }
227};
228
229
230
231//===--------------------------------------------------------------------===//
232// GraphTraits specializations for function basic block graphs (CFGs)
233//===--------------------------------------------------------------------===//
234
235// Provide specializations of GraphTraits to be able to treat a function as a
236// graph of basic blocks... these are the same as the basic block iterators,
237// except that the root node is implicitly the first node of the function.
238//
239template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
240  static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
241
242  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
243  typedef Function::iterator nodes_iterator;
244  static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
245  static nodes_iterator nodes_end  (Function *F) { return F->end(); }
246};
247template <> struct GraphTraits<const Function*> :
248  public GraphTraits<const BasicBlock*> {
249  static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
250
251  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
252  typedef Function::const_iterator nodes_iterator;
253  static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
254  static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
255};
256
257
258// Provide specializations of GraphTraits to be able to treat a function as a
259// graph of basic blocks... and to walk it in inverse order.  Inverse order for
260// a function is considered to be when traversing the predecessor edges of a BB
261// instead of the successor edges.
262//
263template <> struct GraphTraits<Inverse<Function*> > :
264  public GraphTraits<Inverse<BasicBlock*> > {
265  static NodeType *getEntryNode(Inverse<Function*> G) {
266    return &G.Graph->getEntryBlock();
267  }
268};
269template <> struct GraphTraits<Inverse<const Function*> > :
270  public GraphTraits<Inverse<const BasicBlock*> > {
271  static NodeType *getEntryNode(Inverse<const Function *> G) {
272    return &G.Graph->getEntryBlock();
273  }
274};
275
276} // End llvm namespace
277
278#endif
279