LLVM API Documentation

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 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