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