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 23namespace llvm { 24 25//===----------------------------------------------------------------------===// 26// BasicBlock pred_iterator definition 27//===----------------------------------------------------------------------===// 28 29template <class Ptr, class USE_iterator> // Predecessor Iterator 30class 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 43public: 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 85typedef PredIterator<BasicBlock, Value::user_iterator> pred_iterator; 86typedef PredIterator<const BasicBlock, 87 Value::const_user_iterator> const_pred_iterator; 88typedef llvm::iterator_range<pred_iterator> pred_range; 89typedef llvm::iterator_range<const_pred_iterator> pred_const_range; 90 91inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } 92inline const_pred_iterator pred_begin(const BasicBlock *BB) { 93 return const_pred_iterator(BB); 94} 95inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} 96inline const_pred_iterator pred_end(const BasicBlock *BB) { 97 return const_pred_iterator(BB, true); 98} 99inline bool pred_empty(const BasicBlock *BB) { 100 return pred_begin(BB) == pred_end(BB); 101} 102inline pred_range predecessors(BasicBlock *BB) { 103 return pred_range(pred_begin(BB), pred_end(BB)); 104} 105inline 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 113typedef TerminatorInst::SuccIterator<TerminatorInst *, BasicBlock> 114 succ_iterator; 115typedef TerminatorInst::SuccIterator<const TerminatorInst *, const BasicBlock> 116 succ_const_iterator; 117typedef llvm::iterator_range<succ_iterator> succ_range; 118typedef llvm::iterator_range<succ_const_iterator> succ_const_range; 119 120inline succ_iterator succ_begin(BasicBlock *BB) { 121 return succ_iterator(BB->getTerminator()); 122} 123inline succ_const_iterator succ_begin(const BasicBlock *BB) { 124 return succ_const_iterator(BB->getTerminator()); 125} 126inline succ_iterator succ_end(BasicBlock *BB) { 127 return succ_iterator(BB->getTerminator(), true); 128} 129inline succ_const_iterator succ_end(const BasicBlock *BB) { 130 return succ_const_iterator(BB->getTerminator(), true); 131} 132inline bool succ_empty(const BasicBlock *BB) { 133 return succ_begin(BB) == succ_end(BB); 134} 135inline succ_range successors(BasicBlock *BB) { 136 return succ_range(succ_begin(BB), succ_end(BB)); 137} 138inline succ_const_range successors(const BasicBlock *BB) { 139 return succ_const_range(succ_begin(BB), succ_end(BB)); 140} 141 142template <typename T, typename U> 143struct 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 156template <> 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 169template <> 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// 188template <> 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 200template <> 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// 224template <> 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}; 233template <> 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// 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