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