LLVM API Documentation
00001 //===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines specializations of GraphTraits that allow Function and 00011 // BasicBlock graphs to be treated as proper graphs for generic algorithms. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_SUPPORT_CFG_H 00016 #define LLVM_SUPPORT_CFG_H 00017 00018 #include "llvm/ADT/GraphTraits.h" 00019 #include "llvm/Function.h" 00020 #include "llvm/InstrTypes.h" 00021 #include "llvm/ADT/iterator" 00022 00023 namespace llvm { 00024 00025 //===--------------------------------------------------------------------===// 00026 // BasicBlock pred_iterator definition 00027 //===--------------------------------------------------------------------===// 00028 00029 template <class _Ptr, class _USE_iterator> // Predecessor Iterator 00030 class PredIterator : public forward_iterator<_Ptr, ptrdiff_t> { 00031 typedef forward_iterator<_Ptr, ptrdiff_t> super; 00032 _Ptr *BB; 00033 _USE_iterator It; 00034 public: 00035 typedef PredIterator<_Ptr,_USE_iterator> _Self; 00036 typedef typename super::pointer pointer; 00037 00038 inline void advancePastNonTerminators() { 00039 // Loop to ignore non terminator uses (for example PHI nodes)... 00040 while (It != BB->use_end() && !isa<TerminatorInst>(*It)) 00041 ++It; 00042 } 00043 00044 inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) { 00045 advancePastNonTerminators(); 00046 } 00047 inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {} 00048 00049 inline bool operator==(const _Self& x) const { return It == x.It; } 00050 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00051 00052 inline pointer operator*() const { 00053 assert(It != BB->use_end() && "pred_iterator out of range!"); 00054 return cast<TerminatorInst>(*It)->getParent(); 00055 } 00056 inline pointer *operator->() const { return &(operator*()); } 00057 00058 inline _Self& operator++() { // Preincrement 00059 assert(It != BB->use_end() && "pred_iterator out of range!"); 00060 ++It; advancePastNonTerminators(); 00061 return *this; 00062 } 00063 00064 inline _Self operator++(int) { // Postincrement 00065 _Self tmp = *this; ++*this; return tmp; 00066 } 00067 }; 00068 00069 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator; 00070 typedef PredIterator<const BasicBlock, 00071 Value::use_const_iterator> pred_const_iterator; 00072 00073 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } 00074 inline pred_const_iterator pred_begin(const BasicBlock *BB) { 00075 return pred_const_iterator(BB); 00076 } 00077 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} 00078 inline pred_const_iterator pred_end(const BasicBlock *BB) { 00079 return pred_const_iterator(BB, true); 00080 } 00081 00082 00083 00084 //===--------------------------------------------------------------------===// 00085 // BasicBlock succ_iterator definition 00086 //===--------------------------------------------------------------------===// 00087 00088 template <class Term_, class BB_> // Successor Iterator 00089 class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> { 00090 const Term_ Term; 00091 unsigned idx; 00092 typedef bidirectional_iterator<BB_, ptrdiff_t> super; 00093 public: 00094 typedef SuccIterator<Term_, BB_> _Self; 00095 typedef typename super::pointer pointer; 00096 // TODO: This can be random access iterator, need operator+ and stuff tho 00097 00098 inline SuccIterator(Term_ T) : Term(T), idx(0) { // begin iterator 00099 assert(T && "getTerminator returned null!"); 00100 } 00101 inline SuccIterator(Term_ T, bool) // end iterator 00102 : Term(T), idx(Term->getNumSuccessors()) { 00103 assert(T && "getTerminator returned null!"); 00104 } 00105 00106 inline const _Self &operator=(const _Self &I) { 00107 assert(Term == I.Term &&"Cannot assign iterators to two different blocks!"); 00108 idx = I.idx; 00109 return *this; 00110 } 00111 00112 /// getSuccessorIndex - This is used to interface between code that wants to 00113 /// operate on terminator instructions directly. 00114 unsigned getSuccessorIndex() const { return idx; } 00115 00116 inline bool operator==(const _Self& x) const { return idx == x.idx; } 00117 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00118 00119 inline pointer operator*() const { return Term->getSuccessor(idx); } 00120 inline pointer operator->() const { return operator*(); } 00121 00122 inline _Self& operator++() { ++idx; return *this; } // Preincrement 00123 inline _Self operator++(int) { // Postincrement 00124 _Self tmp = *this; ++*this; return tmp; 00125 } 00126 00127 inline _Self& operator--() { --idx; return *this; } // Predecrement 00128 inline _Self operator--(int) { // Postdecrement 00129 _Self tmp = *this; --*this; return tmp; 00130 } 00131 }; 00132 00133 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator; 00134 typedef SuccIterator<const TerminatorInst*, 00135 const BasicBlock> succ_const_iterator; 00136 00137 inline succ_iterator succ_begin(BasicBlock *BB) { 00138 return succ_iterator(BB->getTerminator()); 00139 } 00140 inline succ_const_iterator succ_begin(const BasicBlock *BB) { 00141 return succ_const_iterator(BB->getTerminator()); 00142 } 00143 inline succ_iterator succ_end(BasicBlock *BB) { 00144 return succ_iterator(BB->getTerminator(), true); 00145 } 00146 inline succ_const_iterator succ_end(const BasicBlock *BB) { 00147 return succ_const_iterator(BB->getTerminator(), true); 00148 } 00149 00150 00151 00152 //===--------------------------------------------------------------------===// 00153 // GraphTraits specializations for basic block graphs (CFGs) 00154 //===--------------------------------------------------------------------===// 00155 00156 // Provide specializations of GraphTraits to be able to treat a function as a 00157 // graph of basic blocks... 00158 00159 template <> struct GraphTraits<BasicBlock*> { 00160 typedef BasicBlock NodeType; 00161 typedef succ_iterator ChildIteratorType; 00162 00163 static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 00164 static inline ChildIteratorType child_begin(NodeType *N) { 00165 return succ_begin(N); 00166 } 00167 static inline ChildIteratorType child_end(NodeType *N) { 00168 return succ_end(N); 00169 } 00170 }; 00171 00172 template <> struct GraphTraits<const BasicBlock*> { 00173 typedef const BasicBlock NodeType; 00174 typedef succ_const_iterator ChildIteratorType; 00175 00176 static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 00177 00178 static inline ChildIteratorType child_begin(NodeType *N) { 00179 return succ_begin(N); 00180 } 00181 static inline ChildIteratorType child_end(NodeType *N) { 00182 return succ_end(N); 00183 } 00184 }; 00185 00186 // Provide specializations of GraphTraits to be able to treat a function as a 00187 // graph of basic blocks... and to walk it in inverse order. Inverse order for 00188 // a function is considered to be when traversing the predecessor edges of a BB 00189 // instead of the successor edges. 00190 // 00191 template <> struct GraphTraits<Inverse<BasicBlock*> > { 00192 typedef BasicBlock NodeType; 00193 typedef pred_iterator ChildIteratorType; 00194 static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 00195 static inline ChildIteratorType child_begin(NodeType *N) { 00196 return pred_begin(N); 00197 } 00198 static inline ChildIteratorType child_end(NodeType *N) { 00199 return pred_end(N); 00200 } 00201 }; 00202 00203 template <> struct GraphTraits<Inverse<const BasicBlock*> > { 00204 typedef const BasicBlock NodeType; 00205 typedef pred_const_iterator ChildIteratorType; 00206 static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 00207 return G.Graph; 00208 } 00209 static inline ChildIteratorType child_begin(NodeType *N) { 00210 return pred_begin(N); 00211 } 00212 static inline ChildIteratorType child_end(NodeType *N) { 00213 return pred_end(N); 00214 } 00215 }; 00216 00217 00218 00219 //===--------------------------------------------------------------------===// 00220 // GraphTraits specializations for function basic block graphs (CFGs) 00221 //===--------------------------------------------------------------------===// 00222 00223 // Provide specializations of GraphTraits to be able to treat a function as a 00224 // graph of basic blocks... these are the same as the basic block iterators, 00225 // except that the root node is implicitly the first node of the function. 00226 // 00227 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 00228 static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); } 00229 00230 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00231 typedef Function::iterator nodes_iterator; 00232 static nodes_iterator nodes_begin(Function *F) { return F->begin(); } 00233 static nodes_iterator nodes_end (Function *F) { return F->end(); } 00234 }; 00235 template <> struct GraphTraits<const Function*> : 00236 public GraphTraits<const BasicBlock*> { 00237 static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();} 00238 00239 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00240 typedef Function::const_iterator nodes_iterator; 00241 static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } 00242 static nodes_iterator nodes_end (const Function *F) { return F->end(); } 00243 }; 00244 00245 00246 // Provide specializations of GraphTraits to be able to treat a function as a 00247 // graph of basic blocks... and to walk it in inverse order. Inverse order for 00248 // a function is considered to be when traversing the predecessor edges of a BB 00249 // instead of the successor edges. 00250 // 00251 template <> struct GraphTraits<Inverse<Function*> > : 00252 public GraphTraits<Inverse<BasicBlock*> > { 00253 static NodeType *getEntryNode(Inverse<Function*> G) { 00254 return &G.Graph->getEntryBlock(); 00255 } 00256 }; 00257 template <> struct GraphTraits<Inverse<const Function*> > : 00258 public GraphTraits<Inverse<const BasicBlock*> > { 00259 static NodeType *getEntryNode(Inverse<const Function *> G) { 00260 return &G.Graph->getEntryBlock(); 00261 } 00262 }; 00263 00264 } // End llvm namespace 00265 00266 #endif