CFG.h revision 0aef12a7a96968a80c38144dfc0a7ae6a9152db9
1//===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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 "Support/GraphTraits.h" 19#include "llvm/Function.h" 20#include "llvm/InstrTypes.h" 21#include "Support/iterator" 22 23namespace llvm { 24 25//===--------------------------------------------------------------------===// 26// BasicBlock pred_iterator definition 27//===--------------------------------------------------------------------===// 28 29template <class _Ptr, class _USE_iterator> // Predecessor Iterator 30class PredIterator : public bidirectional_iterator<_Ptr, ptrdiff_t> { 31 typedef bidirectional_iterator<_Ptr, ptrdiff_t> super; 32 _Ptr *BB; 33 _USE_iterator It; 34public: 35 typedef PredIterator<_Ptr,_USE_iterator> _Self; 36 typedef typename super::pointer pointer; 37 38 inline void advancePastConstants() { 39 // Loop to ignore non terminator uses (for example PHI nodes)... 40 while (It != BB->use_end() && !isa<TerminatorInst>(*It)) 41 ++It; 42 } 43 44 inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) { 45 advancePastConstants(); 46 } 47 inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {} 48 49 inline bool operator==(const _Self& x) const { return It == x.It; } 50 inline bool operator!=(const _Self& x) const { return !operator==(x); } 51 52 inline pointer operator*() const { 53 assert(It != BB->use_end() && "pred_iterator out of range!"); 54 return cast<TerminatorInst>(*It)->getParent(); 55 } 56 inline pointer *operator->() const { return &(operator*()); } 57 58 inline _Self& operator++() { // Preincrement 59 assert(It != BB->use_end() && "pred_iterator out of range!"); 60 ++It; advancePastConstants(); 61 return *this; 62 } 63 64 inline _Self operator++(int) { // Postincrement 65 _Self tmp = *this; ++*this; return tmp; 66 } 67 68 inline _Self& operator--() { --It; return *this; } // Predecrement 69 inline _Self operator--(int) { // Postdecrement 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 } 110 111 inline const _Self &operator=(const _Self &I) { 112 assert(Term == I.Term &&"Cannot assign iterators to two different blocks!"); 113 idx = I.idx; 114 return *this; 115 } 116 117 /// getSuccessorIndex - This is used to interface between code that wants to 118 /// operate on terminator instructions directly. 119 unsigned getSuccessorIndex() const { return idx; } 120 121 inline bool operator==(const _Self& x) const { return idx == x.idx; } 122 inline bool operator!=(const _Self& x) const { return !operator==(x); } 123 124 inline pointer operator*() const { return Term->getSuccessor(idx); } 125 inline pointer operator->() const { return operator*(); } 126 127 inline _Self& operator++() { ++idx; return *this; } // Preincrement 128 inline _Self operator++(int) { // Postincrement 129 _Self tmp = *this; ++*this; return tmp; 130 } 131 132 inline _Self& operator--() { --idx; return *this; } // Predecrement 133 inline _Self operator--(int) { // Postdecrement 134 _Self tmp = *this; --*this; return tmp; 135 } 136}; 137 138typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator; 139typedef SuccIterator<const TerminatorInst*, 140 const BasicBlock> succ_const_iterator; 141 142inline succ_iterator succ_begin(BasicBlock *BB) { 143 return succ_iterator(BB->getTerminator()); 144} 145inline succ_const_iterator succ_begin(const BasicBlock *BB) { 146 return succ_const_iterator(BB->getTerminator()); 147} 148inline succ_iterator succ_end(BasicBlock *BB) { 149 return succ_iterator(BB->getTerminator(), true); 150} 151inline succ_const_iterator succ_end(const BasicBlock *BB) { 152 return succ_const_iterator(BB->getTerminator(), true); 153} 154 155 156 157//===--------------------------------------------------------------------===// 158// GraphTraits specializations for basic block graphs (CFGs) 159//===--------------------------------------------------------------------===// 160 161// Provide specializations of GraphTraits to be able to treat a function as a 162// graph of basic blocks... 163 164template <> struct GraphTraits<BasicBlock*> { 165 typedef BasicBlock NodeType; 166 typedef succ_iterator ChildIteratorType; 167 168 static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 169 static inline ChildIteratorType child_begin(NodeType *N) { 170 return succ_begin(N); 171 } 172 static inline ChildIteratorType child_end(NodeType *N) { 173 return succ_end(N); 174 } 175}; 176 177template <> struct GraphTraits<const BasicBlock*> { 178 typedef const BasicBlock NodeType; 179 typedef succ_const_iterator ChildIteratorType; 180 181 static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 182 183 static inline ChildIteratorType child_begin(NodeType *N) { 184 return succ_begin(N); 185 } 186 static inline ChildIteratorType child_end(NodeType *N) { 187 return succ_end(N); 188 } 189}; 190 191// Provide specializations of GraphTraits to be able to treat a function as a 192// graph of basic blocks... and to walk it in inverse order. Inverse order for 193// a function is considered to be when traversing the predecessor edges of a BB 194// instead of the successor edges. 195// 196template <> struct GraphTraits<Inverse<BasicBlock*> > { 197 typedef BasicBlock NodeType; 198 typedef pred_iterator ChildIteratorType; 199 static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 200 static inline ChildIteratorType child_begin(NodeType *N) { 201 return pred_begin(N); 202 } 203 static inline ChildIteratorType child_end(NodeType *N) { 204 return pred_end(N); 205 } 206}; 207 208template <> struct GraphTraits<Inverse<const BasicBlock*> > { 209 typedef const BasicBlock NodeType; 210 typedef pred_const_iterator ChildIteratorType; 211 static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 212 return G.Graph; 213 } 214 static inline ChildIteratorType child_begin(NodeType *N) { 215 return pred_begin(N); 216 } 217 static inline ChildIteratorType child_end(NodeType *N) { 218 return pred_end(N); 219 } 220}; 221 222 223 224//===--------------------------------------------------------------------===// 225// GraphTraits specializations for function basic block graphs (CFGs) 226//===--------------------------------------------------------------------===// 227 228// Provide specializations of GraphTraits to be able to treat a function as a 229// graph of basic blocks... these are the same as the basic block iterators, 230// except that the root node is implicitly the first node of the function. 231// 232template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 233 static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); } 234 235 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 236 typedef Function::iterator nodes_iterator; 237 static nodes_iterator nodes_begin(Function *F) { return F->begin(); } 238 static nodes_iterator nodes_end (Function *F) { return F->end(); } 239}; 240template <> struct GraphTraits<const Function*> : 241 public GraphTraits<const BasicBlock*> { 242 static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();} 243 244 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 245 typedef Function::const_iterator nodes_iterator; 246 static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } 247 static nodes_iterator nodes_end (const Function *F) { return F->end(); } 248}; 249 250 251// Provide specializations of GraphTraits to be able to treat a function as a 252// graph of basic blocks... and to walk it in inverse order. Inverse order for 253// a function is considered to be when traversing the predecessor edges of a BB 254// instead of the successor edges. 255// 256template <> struct GraphTraits<Inverse<Function*> > : 257 public GraphTraits<Inverse<BasicBlock*> > { 258 static NodeType *getEntryNode(Inverse<Function*> G) { 259 return &G.Graph->getEntryBlock(); 260 } 261}; 262template <> struct GraphTraits<Inverse<const Function*> > : 263 public GraphTraits<Inverse<const BasicBlock*> > { 264 static NodeType *getEntryNode(Inverse<const Function *> G) { 265 return &G.Graph->getEntryBlock(); 266 } 267}; 268 269} // End llvm namespace 270 271#endif 272