CFG.h revision 2fbfdcffd3e0cf41422aaa6c526c37cb02b81341
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 <iterator> 16 17//===--------------------------------------------------------------------===// 18// BasicBlock pred_iterator definition 19//===--------------------------------------------------------------------===// 20 21template <class _Ptr, class _USE_iterator> // Predecessor Iterator 22class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> { 23 _Ptr *BB; 24 _USE_iterator It; 25public: 26 typedef PredIterator<_Ptr,_USE_iterator> _Self; 27 28 inline void advancePastConstants() { 29 // TODO: This is bad 30 // Loop to ignore constant pool references 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<Instruction>(*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 std::bidirectional_iterator<_BB, ptrdiff_t> { 86 const _Term Term; 87 unsigned idx; 88public: 89 typedef SuccIterator<_Term, _BB> _Self; 90 // TODO: This can be random access iterator, need operator+ and stuff tho 91 92 inline SuccIterator(_Term T) : Term(T), idx(0) { // begin iterator 93 assert(T && "getTerminator returned null!"); 94 } 95 inline SuccIterator(_Term T, bool) // end iterator 96 : Term(T), idx(Term->getNumSuccessors()) { 97 assert(T && "getTerminator returned null!"); 98 } 99 100 inline bool operator==(const _Self& x) const { return idx == x.idx; } 101 inline bool operator!=(const _Self& x) const { return !operator==(x); } 102 103 inline pointer operator*() const { return Term->getSuccessor(idx); } 104 inline pointer operator->() const { return operator*(); } 105 106 inline _Self& operator++() { ++idx; return *this; } // Preincrement 107 inline _Self operator++(int) { // Postincrement 108 _Self tmp = *this; ++*this; return tmp; 109 } 110 111 inline _Self& operator--() { --idx; return *this; } // Predecrement 112 inline _Self operator--(int) { // Postdecrement 113 _Self tmp = *this; --*this; return tmp; 114 } 115}; 116 117typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator; 118typedef SuccIterator<const TerminatorInst*, 119 const BasicBlock> succ_const_iterator; 120 121inline succ_iterator succ_begin(BasicBlock *BB) { 122 return succ_iterator(BB->getTerminator()); 123} 124inline succ_const_iterator succ_begin(const BasicBlock *BB) { 125 return succ_const_iterator(BB->getTerminator()); 126} 127inline succ_iterator succ_end(BasicBlock *BB) { 128 return succ_iterator(BB->getTerminator(), true); 129} 130inline succ_const_iterator succ_end(const BasicBlock *BB) { 131 return succ_const_iterator(BB->getTerminator(), true); 132} 133 134 135 136//===--------------------------------------------------------------------===// 137// GraphTraits specializations for basic block graphs (CFGs) 138//===--------------------------------------------------------------------===// 139 140// Provide specializations of GraphTraits to be able to treat a function as a 141// graph of basic blocks... 142 143template <> struct GraphTraits<BasicBlock*> { 144 typedef BasicBlock NodeType; 145 typedef succ_iterator ChildIteratorType; 146 147 static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 148 static inline ChildIteratorType child_begin(NodeType *N) { 149 return succ_begin(N); 150 } 151 static inline ChildIteratorType child_end(NodeType *N) { 152 return succ_end(N); 153 } 154}; 155 156template <> struct GraphTraits<const BasicBlock*> { 157 typedef const BasicBlock NodeType; 158 typedef succ_const_iterator ChildIteratorType; 159 160 static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 161 162 static inline ChildIteratorType child_begin(NodeType *N) { 163 return succ_begin(N); 164 } 165 static inline ChildIteratorType child_end(NodeType *N) { 166 return succ_end(N); 167 } 168}; 169 170// Provide specializations of GraphTraits to be able to treat a function as a 171// graph of basic blocks... and to walk it in inverse order. Inverse order for 172// a function is considered to be when traversing the predecessor edges of a BB 173// instead of the successor edges. 174// 175template <> struct GraphTraits<Inverse<BasicBlock*> > { 176 typedef BasicBlock NodeType; 177 typedef pred_iterator ChildIteratorType; 178 static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 179 static inline ChildIteratorType child_begin(NodeType *N) { 180 return pred_begin(N); 181 } 182 static inline ChildIteratorType child_end(NodeType *N) { 183 return pred_end(N); 184 } 185}; 186 187template <> struct GraphTraits<Inverse<const BasicBlock*> > { 188 typedef const BasicBlock NodeType; 189 typedef pred_const_iterator ChildIteratorType; 190 static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 191 return G.Graph; 192 } 193 static inline ChildIteratorType child_begin(NodeType *N) { 194 return pred_begin(N); 195 } 196 static inline ChildIteratorType child_end(NodeType *N) { 197 return pred_end(N); 198 } 199}; 200 201 202 203//===--------------------------------------------------------------------===// 204// GraphTraits specializations for function basic block graphs (CFGs) 205//===--------------------------------------------------------------------===// 206 207// Provide specializations of GraphTraits to be able to treat a function as a 208// graph of basic blocks... these are the same as the basic block iterators, 209// except that the root node is implicitly the first node of the function. 210// 211template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 212 static NodeType *getEntryNode(Function *F) { return F->getEntryNode(); } 213}; 214template <> struct GraphTraits<const Function*> : 215 public GraphTraits<const BasicBlock*> { 216 static NodeType *getEntryNode(const Function *F) { return F->getEntryNode(); } 217}; 218 219 220// Provide specializations of GraphTraits to be able to treat a function as a 221// graph of basic blocks... and to walk it in inverse order. Inverse order for 222// a function is considered to be when traversing the predecessor edges of a BB 223// instead of the successor edges. 224// 225template <> struct GraphTraits<Inverse<Function*> > : 226 public GraphTraits<Inverse<BasicBlock*> > { 227 static NodeType *getEntryNode(Inverse<Function*> G) { 228 return G.Graph->front(); 229 } 230}; 231template <> struct GraphTraits<Inverse<const Function*> > : 232 public GraphTraits<Inverse<const BasicBlock*> > { 233 static NodeType *getEntryNode(Inverse<const Function *> G) { 234 return G.Graph->front(); 235 } 236}; 237 238#endif 239