1 //===- 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_IR_CFG_H 16 #define LLVM_IR_CFG_H 17 18 #include "llvm/ADT/GraphTraits.h" 19 #include "llvm/ADT/iterator_range.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/InstrTypes.h" 22 23 namespace llvm { 24 25 //===----------------------------------------------------------------------===// 26 // BasicBlock pred_iterator definition 27 //===----------------------------------------------------------------------===// 28 29 template <class Ptr, class USE_iterator> // Predecessor Iterator 30 class PredIterator : public std::iterator<std::forward_iterator_tag, 31 Ptr, ptrdiff_t, Ptr*, Ptr*> { 32 typedef std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, 33 Ptr*> super; 34 typedef PredIterator<Ptr, USE_iterator> Self; 35 USE_iterator It; 36 37 inline void advancePastNonTerminators() { 38 // Loop to ignore non-terminator uses (for example BlockAddresses). 39 while (!It.atEnd() && !isa<TerminatorInst>(*It)) 40 ++It; 41 } 42 43 public: 44 typedef typename super::pointer pointer; 45 typedef typename super::reference reference; 46 47 PredIterator() {} 48 explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) { 49 advancePastNonTerminators(); 50 } 51 inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {} 52 53 inline bool operator==(const Self& x) const { return It == x.It; } 54 inline bool operator!=(const Self& x) const { return !operator==(x); } 55 56 inline reference operator*() const { 57 assert(!It.atEnd() && "pred_iterator out of range!"); 58 return cast<TerminatorInst>(*It)->getParent(); 59 } 60 inline pointer *operator->() const { return &operator*(); } 61 62 inline Self& operator++() { // Preincrement 63 assert(!It.atEnd() && "pred_iterator out of range!"); 64 ++It; advancePastNonTerminators(); 65 return *this; 66 } 67 68 inline Self operator++(int) { // Postincrement 69 Self tmp = *this; ++*this; return tmp; 70 } 71 72 /// getOperandNo - Return the operand number in the predecessor's 73 /// terminator of the successor. 74 unsigned getOperandNo() const { 75 return It.getOperandNo(); 76 } 77 78 /// getUse - Return the operand Use in the predecessor's terminator 79 /// of the successor. 80 Use &getUse() const { 81 return It.getUse(); 82 } 83 }; 84 85 typedef PredIterator<BasicBlock, Value::user_iterator> pred_iterator; 86 typedef PredIterator<const BasicBlock, 87 Value::const_user_iterator> const_pred_iterator; 88 typedef llvm::iterator_range<pred_iterator> pred_range; 89 typedef llvm::iterator_range<const_pred_iterator> pred_const_range; 90 91 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } 92 inline const_pred_iterator pred_begin(const BasicBlock *BB) { 93 return const_pred_iterator(BB); 94 } 95 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} 96 inline const_pred_iterator pred_end(const BasicBlock *BB) { 97 return const_pred_iterator(BB, true); 98 } 99 inline bool pred_empty(const BasicBlock *BB) { 100 return pred_begin(BB) == pred_end(BB); 101 } 102 inline pred_range predecessors(BasicBlock *BB) { 103 return pred_range(pred_begin(BB), pred_end(BB)); 104 } 105 inline pred_const_range predecessors(const BasicBlock *BB) { 106 return pred_const_range(pred_begin(BB), pred_end(BB)); 107 } 108 109 //===----------------------------------------------------------------------===// 110 // BasicBlock succ_iterator helpers 111 //===----------------------------------------------------------------------===// 112 113 typedef TerminatorInst::SuccIterator<TerminatorInst *, BasicBlock> 114 succ_iterator; 115 typedef TerminatorInst::SuccIterator<const TerminatorInst *, const BasicBlock> 116 succ_const_iterator; 117 typedef llvm::iterator_range<succ_iterator> succ_range; 118 typedef llvm::iterator_range<succ_const_iterator> succ_const_range; 119 120 inline succ_iterator succ_begin(BasicBlock *BB) { 121 return succ_iterator(BB->getTerminator()); 122 } 123 inline succ_const_iterator succ_begin(const BasicBlock *BB) { 124 return succ_const_iterator(BB->getTerminator()); 125 } 126 inline succ_iterator succ_end(BasicBlock *BB) { 127 return succ_iterator(BB->getTerminator(), true); 128 } 129 inline succ_const_iterator succ_end(const BasicBlock *BB) { 130 return succ_const_iterator(BB->getTerminator(), true); 131 } 132 inline bool succ_empty(const BasicBlock *BB) { 133 return succ_begin(BB) == succ_end(BB); 134 } 135 inline succ_range successors(BasicBlock *BB) { 136 return succ_range(succ_begin(BB), succ_end(BB)); 137 } 138 inline succ_const_range successors(const BasicBlock *BB) { 139 return succ_const_range(succ_begin(BB), succ_end(BB)); 140 } 141 142 template <typename T, typename U> 143 struct isPodLike<TerminatorInst::SuccIterator<T, U>> { 144 static const bool value = isPodLike<T>::value; 145 }; 146 147 148 149 //===--------------------------------------------------------------------===// 150 // GraphTraits specializations for basic block graphs (CFGs) 151 //===--------------------------------------------------------------------===// 152 153 // Provide specializations of GraphTraits to be able to treat a function as a 154 // graph of basic blocks... 155 156 template <> struct GraphTraits<BasicBlock*> { 157 typedef BasicBlock NodeType; 158 typedef succ_iterator ChildIteratorType; 159 160 static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 161 static inline ChildIteratorType child_begin(NodeType *N) { 162 return succ_begin(N); 163 } 164 static inline ChildIteratorType child_end(NodeType *N) { 165 return succ_end(N); 166 } 167 }; 168 169 template <> struct GraphTraits<const BasicBlock*> { 170 typedef const BasicBlock NodeType; 171 typedef succ_const_iterator ChildIteratorType; 172 173 static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 174 175 static inline ChildIteratorType child_begin(NodeType *N) { 176 return succ_begin(N); 177 } 178 static inline ChildIteratorType child_end(NodeType *N) { 179 return succ_end(N); 180 } 181 }; 182 183 // Provide specializations of GraphTraits to be able to treat a function as a 184 // graph of basic blocks... and to walk it in inverse order. Inverse order for 185 // a function is considered to be when traversing the predecessor edges of a BB 186 // instead of the successor edges. 187 // 188 template <> struct GraphTraits<Inverse<BasicBlock*> > { 189 typedef BasicBlock NodeType; 190 typedef pred_iterator ChildIteratorType; 191 static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 192 static inline ChildIteratorType child_begin(NodeType *N) { 193 return pred_begin(N); 194 } 195 static inline ChildIteratorType child_end(NodeType *N) { 196 return pred_end(N); 197 } 198 }; 199 200 template <> struct GraphTraits<Inverse<const BasicBlock*> > { 201 typedef const BasicBlock NodeType; 202 typedef const_pred_iterator ChildIteratorType; 203 static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 204 return G.Graph; 205 } 206 static inline ChildIteratorType child_begin(NodeType *N) { 207 return pred_begin(N); 208 } 209 static inline ChildIteratorType child_end(NodeType *N) { 210 return pred_end(N); 211 } 212 }; 213 214 215 216 //===--------------------------------------------------------------------===// 217 // GraphTraits specializations for function basic block graphs (CFGs) 218 //===--------------------------------------------------------------------===// 219 220 // Provide specializations of GraphTraits to be able to treat a function as a 221 // graph of basic blocks... these are the same as the basic block iterators, 222 // except that the root node is implicitly the first node of the function. 223 // 224 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 225 static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); } 226 227 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 228 typedef Function::iterator nodes_iterator; 229 static nodes_iterator nodes_begin(Function *F) { return F->begin(); } 230 static nodes_iterator nodes_end (Function *F) { return F->end(); } 231 static size_t size (Function *F) { return F->size(); } 232 }; 233 template <> struct GraphTraits<const Function*> : 234 public GraphTraits<const BasicBlock*> { 235 static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();} 236 237 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 238 typedef Function::const_iterator nodes_iterator; 239 static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } 240 static nodes_iterator nodes_end (const Function *F) { return F->end(); } 241 static size_t size (const Function *F) { return F->size(); } 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 // 250 template <> struct GraphTraits<Inverse<Function*> > : 251 public GraphTraits<Inverse<BasicBlock*> > { 252 static NodeType *getEntryNode(Inverse<Function*> G) { 253 return &G.Graph->getEntryBlock(); 254 } 255 }; 256 template <> 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