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