CFG.h revision fe8041ae397ebbcc311469aa39dfb79f8191b412 
1//===-- llvm/Support/CFG.h - Process LLVM structures as graphs ---*- C++ -*--=//
2//
3// This file defines specializations of GraphTraits that allow Function and
4// BasicBlock graphs to be treated as proper graphs for generic algorithms.
5//
6//===----------------------------------------------------------------------===//
7
8#ifndef LLVM_CFG_H
9#define LLVM_CFG_H
10
11#include "Support/GraphTraits.h"
12#include "llvm/Function.h"
13#include "llvm/BasicBlock.h"
14#include "llvm/InstrTypes.h"
15#include "Support/iterator"
16
17//===--------------------------------------------------------------------===//
18// BasicBlock pred_iterator definition
19//===--------------------------------------------------------------------===//
20
21template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
22class PredIterator : public bidirectional_iterator<_Ptr, ptrdiff_t> {
23  typedef bidirectional_iterator<_Ptr, ptrdiff_t> super;
24  _Ptr *BB;
25  _USE_iterator It;
26public:
27  typedef PredIterator<_Ptr,_USE_iterator> _Self;
28  typedef typename super::pointer pointer;
29
30  inline void advancePastConstants() {
31    // TODO: This is bad
32    // Loop to ignore constant pool references
33    while (It != BB->use_end() && !isa<TerminatorInst>(*It))
34      ++It;
35  }
36
37  inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
38    advancePastConstants();
39  }
40  inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
41
42  inline bool operator==(const _Self& x) const { return It == x.It; }
43  inline bool operator!=(const _Self& x) const { return !operator==(x); }
44
45  inline pointer operator*() const {
46    assert(It != BB->use_end() && "pred_iterator out of range!");
47    return cast<Instruction>(*It)->getParent();
48  }
49  inline pointer *operator->() const { return &(operator*()); }
50
51  inline _Self& operator++() {   // Preincrement
52    assert(It != BB->use_end() && "pred_iterator out of range!");
53    ++It; advancePastConstants();
54    return *this;
55  }
56
57  inline _Self operator++(int) { // Postincrement
58    _Self tmp = *this; ++*this; return tmp;
59  }
60
61  inline _Self& operator--() { --It; return *this; }  // Predecrement
62  inline _Self operator--(int) { // Postdecrement
63    _Self tmp = *this; --*this; return tmp;
64  }
65};
66
67typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
68typedef PredIterator<const BasicBlock,
69                     Value::use_const_iterator> pred_const_iterator;
70
71inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
72inline pred_const_iterator pred_begin(const BasicBlock *BB) {
73  return pred_const_iterator(BB);
74}
75inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
76inline pred_const_iterator pred_end(const BasicBlock *BB) {
77  return pred_const_iterator(BB, true);
78}
79
80
81
82//===--------------------------------------------------------------------===//
83// BasicBlock succ_iterator definition
84//===--------------------------------------------------------------------===//
85
86template <class _Term, class _BB>           // Successor Iterator
87class SuccIterator : public bidirectional_iterator<_BB, ptrdiff_t> {
88  const _Term Term;
89  unsigned idx;
90  typedef bidirectional_iterator<_BB, ptrdiff_t> super;
91public:
92  typedef SuccIterator<_Term, _BB> _Self;
93  typedef typename super::pointer pointer;
94  // TODO: This can be random access iterator, need operator+ and stuff tho
95
96  inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
97    assert(T && "getTerminator returned null!");
98  }
99  inline SuccIterator(_Term T, bool)                       // end iterator
100    : Term(T), idx(Term->getNumSuccessors()) {
101    assert(T && "getTerminator returned null!");
102  }
103
104  inline bool operator==(const _Self& x) const { return idx == x.idx; }
105  inline bool operator!=(const _Self& x) const { return !operator==(x); }
106
107  inline pointer operator*() const { return Term->getSuccessor(idx); }
108  inline pointer operator->() const { return operator*(); }
109
110  inline _Self& operator++() { ++idx; return *this; } // Preincrement
111  inline _Self operator++(int) { // Postincrement
112    _Self tmp = *this; ++*this; return tmp;
113  }
114
115  inline _Self& operator--() { --idx; return *this; }  // Predecrement
116  inline _Self operator--(int) { // Postdecrement
117    _Self tmp = *this; --*this; return tmp;
118  }
119};
120
121typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
122typedef SuccIterator<const TerminatorInst*,
123                     const BasicBlock> succ_const_iterator;
124
125inline succ_iterator succ_begin(BasicBlock *BB) {
126  return succ_iterator(BB->getTerminator());
127}
128inline succ_const_iterator succ_begin(const BasicBlock *BB) {
129  return succ_const_iterator(BB->getTerminator());
130}
131inline succ_iterator succ_end(BasicBlock *BB) {
132  return succ_iterator(BB->getTerminator(), true);
133}
134inline succ_const_iterator succ_end(const BasicBlock *BB) {
135  return succ_const_iterator(BB->getTerminator(), true);
136}
137
138
139
140//===--------------------------------------------------------------------===//
141// GraphTraits specializations for basic block graphs (CFGs)
142//===--------------------------------------------------------------------===//
143
144// Provide specializations of GraphTraits to be able to treat a function as a
145// graph of basic blocks...
146
147template <> struct GraphTraits<BasicBlock*> {
148  typedef BasicBlock NodeType;
149  typedef succ_iterator ChildIteratorType;
150
151  static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
152  static inline ChildIteratorType child_begin(NodeType *N) {
153    return succ_begin(N);
154  }
155  static inline ChildIteratorType child_end(NodeType *N) {
156    return succ_end(N);
157  }
158};
159
160template <> struct GraphTraits<const BasicBlock*> {
161  typedef const BasicBlock NodeType;
162  typedef succ_const_iterator ChildIteratorType;
163
164  static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
165
166  static inline ChildIteratorType child_begin(NodeType *N) {
167    return succ_begin(N);
168  }
169  static inline ChildIteratorType child_end(NodeType *N) {
170    return succ_end(N);
171  }
172};
173
174// Provide specializations of GraphTraits to be able to treat a function as a
175// graph of basic blocks... and to walk it in inverse order.  Inverse order for
176// a function is considered to be when traversing the predecessor edges of a BB
177// instead of the successor edges.
178//
179template <> struct GraphTraits<Inverse<BasicBlock*> > {
180  typedef BasicBlock NodeType;
181  typedef pred_iterator ChildIteratorType;
182  static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
183  static inline ChildIteratorType child_begin(NodeType *N) {
184    return pred_begin(N);
185  }
186  static inline ChildIteratorType child_end(NodeType *N) {
187    return pred_end(N);
188  }
189};
190
191template <> struct GraphTraits<Inverse<const BasicBlock*> > {
192  typedef const BasicBlock NodeType;
193  typedef pred_const_iterator ChildIteratorType;
194  static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
195    return G.Graph;
196  }
197  static inline ChildIteratorType child_begin(NodeType *N) {
198    return pred_begin(N);
199  }
200  static inline ChildIteratorType child_end(NodeType *N) {
201    return pred_end(N);
202  }
203};
204
205
206
207//===--------------------------------------------------------------------===//
208// GraphTraits specializations for function basic block graphs (CFGs)
209//===--------------------------------------------------------------------===//
210
211// Provide specializations of GraphTraits to be able to treat a function as a
212// graph of basic blocks... these are the same as the basic block iterators,
213// except that the root node is implicitly the first node of the function.
214//
215template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
216  static NodeType *getEntryNode(Function *F) { return &F->getEntryNode(); }
217};
218template <> struct GraphTraits<const Function*> :
219  public GraphTraits<const BasicBlock*> {
220  static NodeType *getEntryNode(const Function *F) { return &F->getEntryNode();}
221};
222
223
224// Provide specializations of GraphTraits to be able to treat a function as a
225// graph of basic blocks... and to walk it in inverse order.  Inverse order for
226// a function is considered to be when traversing the predecessor edges of a BB
227// instead of the successor edges.
228//
229template <> struct GraphTraits<Inverse<Function*> > :
230  public GraphTraits<Inverse<BasicBlock*> > {
231  static NodeType *getEntryNode(Inverse<Function*> G) {
232    return &G.Graph->getEntryNode();
233  }
234};
235template <> struct GraphTraits<Inverse<const Function*> > :
236  public GraphTraits<Inverse<const BasicBlock*> > {
237  static NodeType *getEntryNode(Inverse<const Function *> G) {
238    return &G.Graph->getEntryNode();
239  }
240};
241
242#endif
243