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 bidirectional_iterator<_Ptr, ptrdiff_t> { 00031 typedef bidirectional_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 advancePastConstants() { 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 advancePastConstants(); 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; advancePastConstants(); 00061 return *this; 00062 } 00063 00064 inline _Self operator++(int) { // Postincrement 00065 _Self tmp = *this; ++*this; return tmp; 00066 } 00067 00068 inline _Self& operator--() { --It; return *this; } // Predecrement 00069 inline _Self operator--(int) { // Postdecrement 00070 _Self tmp = *this; --*this; return tmp; 00071 } 00072 }; 00073 00074 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator; 00075 typedef PredIterator<const BasicBlock, 00076 Value::use_const_iterator> pred_const_iterator; 00077 00078 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } 00079 inline pred_const_iterator pred_begin(const BasicBlock *BB) { 00080 return pred_const_iterator(BB); 00081 } 00082 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} 00083 inline pred_const_iterator pred_end(const BasicBlock *BB) { 00084 return pred_const_iterator(BB, true); 00085 } 00086 00087 00088 00089 //===--------------------------------------------------------------------===// 00090 // BasicBlock succ_iterator definition 00091 //===--------------------------------------------------------------------===// 00092 00093 template <class Term_, class BB_> // Successor Iterator 00094 class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> { 00095 const Term_ Term; 00096 unsigned idx; 00097 typedef bidirectional_iterator<BB_, ptrdiff_t> super; 00098 public: 00099 typedef SuccIterator<Term_, BB_> _Self; 00100 typedef typename super::pointer pointer; 00101 // TODO: This can be random access iterator, need operator+ and stuff tho 00102 00103 inline SuccIterator(Term_ T) : Term(T), idx(0) { // begin iterator 00104 assert(T && "getTerminator returned null!"); 00105 } 00106 inline SuccIterator(Term_ T, bool) // end iterator 00107 : Term(T), idx(Term->getNumSuccessors()) { 00108 assert(T && "getTerminator returned null!"); 00109 } 00110 00111 inline const _Self &operator=(const _Self &I) { 00112 assert(Term == I.Term &&"Cannot assign iterators to two different blocks!"); 00113 idx = I.idx; 00114 return *this; 00115 } 00116 00117 /// getSuccessorIndex - This is used to interface between code that wants to 00118 /// operate on terminator instructions directly. 00119 unsigned getSuccessorIndex() const { return idx; } 00120 00121 inline bool operator==(const _Self& x) const { return idx == x.idx; } 00122 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00123 00124 inline pointer operator*() const { return Term->getSuccessor(idx); } 00125 inline pointer operator->() const { return operator*(); } 00126 00127 inline _Self& operator++() { ++idx; return *this; } // Preincrement 00128 inline _Self operator++(int) { // Postincrement 00129 _Self tmp = *this; ++*this; return tmp; 00130 } 00131 00132 inline _Self& operator--() { --idx; return *this; } // Predecrement 00133 inline _Self operator--(int) { // Postdecrement 00134 _Self tmp = *this; --*this; return tmp; 00135 } 00136 }; 00137 00138 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator; 00139 typedef SuccIterator<const TerminatorInst*, 00140 const BasicBlock> succ_const_iterator; 00141 00142 inline succ_iterator succ_begin(BasicBlock *BB) { 00143 return succ_iterator(BB->getTerminator()); 00144 } 00145 inline succ_const_iterator succ_begin(const BasicBlock *BB) { 00146 return succ_const_iterator(BB->getTerminator()); 00147 } 00148 inline succ_iterator succ_end(BasicBlock *BB) { 00149 return succ_iterator(BB->getTerminator(), true); 00150 } 00151 inline succ_const_iterator succ_end(const BasicBlock *BB) { 00152 return succ_const_iterator(BB->getTerminator(), true); 00153 } 00154 00155 00156 00157 //===--------------------------------------------------------------------===// 00158 // GraphTraits specializations for basic block graphs (CFGs) 00159 //===--------------------------------------------------------------------===// 00160 00161 // Provide specializations of GraphTraits to be able to treat a function as a 00162 // graph of basic blocks... 00163 00164 template <> struct GraphTraits<BasicBlock*> { 00165 typedef BasicBlock NodeType; 00166 typedef succ_iterator ChildIteratorType; 00167 00168 static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 00169 static inline ChildIteratorType child_begin(NodeType *N) { 00170 return succ_begin(N); 00171 } 00172 static inline ChildIteratorType child_end(NodeType *N) { 00173 return succ_end(N); 00174 } 00175 }; 00176 00177 template <> struct GraphTraits<const BasicBlock*> { 00178 typedef const BasicBlock NodeType; 00179 typedef succ_const_iterator ChildIteratorType; 00180 00181 static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 00182 00183 static inline ChildIteratorType child_begin(NodeType *N) { 00184 return succ_begin(N); 00185 } 00186 static inline ChildIteratorType child_end(NodeType *N) { 00187 return succ_end(N); 00188 } 00189 }; 00190 00191 // Provide specializations of GraphTraits to be able to treat a function as a 00192 // graph of basic blocks... and to walk it in inverse order. Inverse order for 00193 // a function is considered to be when traversing the predecessor edges of a BB 00194 // instead of the successor edges. 00195 // 00196 template <> struct GraphTraits<Inverse<BasicBlock*> > { 00197 typedef BasicBlock NodeType; 00198 typedef pred_iterator ChildIteratorType; 00199 static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 00200 static inline ChildIteratorType child_begin(NodeType *N) { 00201 return pred_begin(N); 00202 } 00203 static inline ChildIteratorType child_end(NodeType *N) { 00204 return pred_end(N); 00205 } 00206 }; 00207 00208 template <> struct GraphTraits<Inverse<const BasicBlock*> > { 00209 typedef const BasicBlock NodeType; 00210 typedef pred_const_iterator ChildIteratorType; 00211 static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 00212 return G.Graph; 00213 } 00214 static inline ChildIteratorType child_begin(NodeType *N) { 00215 return pred_begin(N); 00216 } 00217 static inline ChildIteratorType child_end(NodeType *N) { 00218 return pred_end(N); 00219 } 00220 }; 00221 00222 00223 00224 //===--------------------------------------------------------------------===// 00225 // GraphTraits specializations for function basic block graphs (CFGs) 00226 //===--------------------------------------------------------------------===// 00227 00228 // Provide specializations of GraphTraits to be able to treat a function as a 00229 // graph of basic blocks... these are the same as the basic block iterators, 00230 // except that the root node is implicitly the first node of the function. 00231 // 00232 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 00233 static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); } 00234 00235 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00236 typedef Function::iterator nodes_iterator; 00237 static nodes_iterator nodes_begin(Function *F) { return F->begin(); } 00238 static nodes_iterator nodes_end (Function *F) { return F->end(); } 00239 }; 00240 template <> struct GraphTraits<const Function*> : 00241 public GraphTraits<const BasicBlock*> { 00242 static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();} 00243 00244 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00245 typedef Function::const_iterator nodes_iterator; 00246 static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } 00247 static nodes_iterator nodes_end (const Function *F) { return F->end(); } 00248 }; 00249 00250 00251 // Provide specializations of GraphTraits to be able to treat a function as a 00252 // graph of basic blocks... and to walk it in inverse order. Inverse order for 00253 // a function is considered to be when traversing the predecessor edges of a BB 00254 // instead of the successor edges. 00255 // 00256 template <> struct GraphTraits<Inverse<Function*> > : 00257 public GraphTraits<Inverse<BasicBlock*> > { 00258 static NodeType *getEntryNode(Inverse<Function*> G) { 00259 return &G.Graph->getEntryBlock(); 00260 } 00261 }; 00262 template <> struct GraphTraits<Inverse<const Function*> > : 00263 public GraphTraits<Inverse<const BasicBlock*> > { 00264 static NodeType *getEntryNode(Inverse<const Function *> G) { 00265 return &G.Graph->getEntryBlock(); 00266 } 00267 }; 00268 00269 } // End llvm namespace 00270 00271 #endif