LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

CFG.h

Go to the documentation of this file.
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