include/llvm/Support/CFG.h

   1 //===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 "Support/GraphTraits.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/InstrTypes.h"
  22 #include "Support/iterator"
  23
  24 namespace llvm {
  25
  26 //===--------------------------------------------------------------------===//
  27 // BasicBlock pred_iterator definition
  28 //===--------------------------------------------------------------------===//
  29
  30 template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
  31 class PredIterator : public bidirectional_iterator<_Ptr, ptrdiff_t> {
  32   typedef bidirectional_iterator<_Ptr, ptrdiff_t> super;
  33   _Ptr *BB;
  34   _USE_iterator It;
  35 public:
  36   typedef PredIterator<_Ptr,_USE_iterator> _Self;
  37   typedef typename super::pointer pointer;
  38
  39   inline void advancePastConstants() {
  40     // Loop to ignore non terminator uses (for example PHI nodes)...
  41     while (It != BB->use_end() && !isa<TerminatorInst>(*It))
  42       ++It;
  43   }
  44
  45   inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
  46     advancePastConstants();
  47   }
  48   inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
  49
  50   inline bool operator==(const _Self& x) const { return It == x.It; }
  51   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  52
  53   inline pointer operator*() const {
  54     assert(It != BB->use_end() && "pred_iterator out of range!");
  55     return cast<TerminatorInst>(*It)->getParent();
  56   }
  57   inline pointer *operator->() const { return &(operator*()); }
  58
  59   inline _Self& operator++() {   // Preincrement
  60     assert(It != BB->use_end() && "pred_iterator out of range!");
  61     ++It; advancePastConstants();
  62     return *this;
  63   }
  64
  65   inline _Self operator++(int) { // Postincrement
  66     _Self tmp = *this; ++*this; return tmp;
  67   }
  68
  69   inline _Self& operator--() { --It; return *this; }  // Predecrement
  70   inline _Self operator--(int) { // Postdecrement
  71     _Self tmp = *this; --*this; return tmp;
  72   }
  73 };
  74
  75 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
  76 typedef PredIterator<const BasicBlock,
  77                      Value::use_const_iterator> pred_const_iterator;
  78
  79 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
  80 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  81   return pred_const_iterator(BB);
  82 }
  83 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
  84 inline pred_const_iterator pred_end(const BasicBlock *BB) {
  85   return pred_const_iterator(BB, true);
  86 }
  87
  88
  89
  90 //===--------------------------------------------------------------------===//
  91 // BasicBlock succ_iterator definition
  92 //===--------------------------------------------------------------------===//
  93
  94 template <class _Term, class _BB>           // Successor Iterator
  95 class SuccIterator : public bidirectional_iterator<_BB, ptrdiff_t> {
  96   const _Term Term;
  97   unsigned idx;
  98   typedef bidirectional_iterator<_BB, ptrdiff_t> super;
  99 public:
 100   typedef SuccIterator<_Term, _BB> _Self;
 101   typedef typename super::pointer pointer;
 102   // TODO: This can be random access iterator, need operator+ and stuff tho
 103
 104   inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
 105     assert(T && "getTerminator returned null!");
 106   }
 107   inline SuccIterator(_Term T, bool)                       // end iterator
 108     : Term(T), idx(Term->getNumSuccessors()) {
 109     assert(T && "getTerminator returned null!");
 110   }
 111
 112   inline const _Self &operator=(const _Self &I) {
 113     assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
 114     idx = I.idx;
 115     return *this;
 116   }
 117
 118   /// getSuccessorIndex - This is used to interface between code that wants to
 119   /// operate on terminator instructions directly.
 120   unsigned getSuccessorIndex() const { return idx; }
 121
 122   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 123   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 124
 125   inline pointer operator*() const { return Term->getSuccessor(idx); }
 126   inline pointer operator->() const { return operator*(); }
 127
 128   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 129   inline _Self operator++(int) { // Postincrement
 130     _Self tmp = *this; ++*this; return tmp;
 131   }
 132
 133   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 134   inline _Self operator--(int) { // Postdecrement
 135     _Self tmp = *this; --*this; return tmp;
 136   }
 137 };
 138
 139 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
 140 typedef SuccIterator<const TerminatorInst*,
 141                      const BasicBlock> succ_const_iterator;
 142
 143 inline succ_iterator succ_begin(BasicBlock *BB) {
 144   return succ_iterator(BB->getTerminator());
 145 }
 146 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 147   return succ_const_iterator(BB->getTerminator());
 148 }
 149 inline succ_iterator succ_end(BasicBlock *BB) {
 150   return succ_iterator(BB->getTerminator(), true);
 151 }
 152 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 153   return succ_const_iterator(BB->getTerminator(), true);
 154 }
 155
 156
 157
 158 //===--------------------------------------------------------------------===//
 159 // GraphTraits specializations for basic block graphs (CFGs)
 160 //===--------------------------------------------------------------------===//
 161
 162 // Provide specializations of GraphTraits to be able to treat a function as a
 163 // graph of basic blocks...
 164
 165 template <> struct GraphTraits<BasicBlock*> {
 166   typedef BasicBlock NodeType;
 167   typedef succ_iterator ChildIteratorType;
 168
 169   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 170   static inline ChildIteratorType child_begin(NodeType *N) {
 171     return succ_begin(N);
 172   }
 173   static inline ChildIteratorType child_end(NodeType *N) {
 174     return succ_end(N);
 175   }
 176 };
 177
 178 template <> struct GraphTraits<const BasicBlock*> {
 179   typedef const BasicBlock NodeType;
 180   typedef succ_const_iterator ChildIteratorType;
 181
 182   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 183
 184   static inline ChildIteratorType child_begin(NodeType *N) {
 185     return succ_begin(N);
 186   }
 187   static inline ChildIteratorType child_end(NodeType *N) {
 188     return succ_end(N);
 189   }
 190 };
 191
 192 // Provide specializations of GraphTraits to be able to treat a function as a
 193 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 194 // a function is considered to be when traversing the predecessor edges of a BB
 195 // instead of the successor edges.
 196 //
 197 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 198   typedef BasicBlock NodeType;
 199   typedef pred_iterator ChildIteratorType;
 200   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 201   static inline ChildIteratorType child_begin(NodeType *N) {
 202     return pred_begin(N);
 203   }
 204   static inline ChildIteratorType child_end(NodeType *N) {
 205     return pred_end(N);
 206   }
 207 };
 208
 209 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 210   typedef const BasicBlock NodeType;
 211   typedef pred_const_iterator ChildIteratorType;
 212   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 213     return G.Graph;
 214   }
 215   static inline ChildIteratorType child_begin(NodeType *N) {
 216     return pred_begin(N);
 217   }
 218   static inline ChildIteratorType child_end(NodeType *N) {
 219     return pred_end(N);
 220   }
 221 };
 222
 223
 224
 225 //===--------------------------------------------------------------------===//
 226 // GraphTraits specializations for function basic block graphs (CFGs)
 227 //===--------------------------------------------------------------------===//
 228
 229 // Provide specializations of GraphTraits to be able to treat a function as a
 230 // graph of basic blocks... these are the same as the basic block iterators,
 231 // except that the root node is implicitly the first node of the function.
 232 //
 233 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
 234   static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
 235
 236   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 237   typedef Function::iterator nodes_iterator;
 238   static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
 239   static nodes_iterator nodes_end  (Function *F) { return F->end(); }
 240 };
 241 template <> struct GraphTraits<const Function*> :
 242   public GraphTraits<const BasicBlock*> {
 243   static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
 244
 245   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 246   typedef Function::const_iterator nodes_iterator;
 247   static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
 248   static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
 249 };
 250
 251
 252 // Provide specializations of GraphTraits to be able to treat a function as a
 253 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 254 // a function is considered to be when traversing the predecessor edges of a BB
 255 // instead of the successor edges.
 256 //
 257 template <> struct GraphTraits<Inverse<Function*> > :
 258   public GraphTraits<Inverse<BasicBlock*> > {
 259   static NodeType *getEntryNode(Inverse<Function*> G) {
 260     return &G.Graph->getEntryBlock();
 261   }
 262 };
 263 template <> struct GraphTraits<Inverse<const Function*> > :
 264   public GraphTraits<Inverse<const BasicBlock*> > {
 265   static NodeType *getEntryNode(Inverse<const Function *> G) {
 266     return &G.Graph->getEntryBlock();
 267   }
 268 };
 269
 270 //===--------------------------------------------------------------------===//
 271 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
 272 //===--------------------------------------------------------------------===//
 273
 274 // Provide specializations of GraphTraits to be able to treat a
 275 // MachineFunction as a graph of MachineBasicBlocks...
 276 //
 277
 278 template <> struct GraphTraits<MachineBasicBlock *> {
 279   typedef MachineBasicBlock NodeType;
 280   typedef MachineBasicBlock::succ_iterator ChildIteratorType;
 281
 282   static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
 283   static inline ChildIteratorType child_begin(NodeType *N) {
 284     return N->succ_begin();
 285   }
 286   static inline ChildIteratorType child_end(NodeType *N) {
 287     return N->succ_end();
 288   }
 289 };
 290
 291 template <> struct GraphTraits<const MachineBasicBlock *> {
 292   typedef const MachineBasicBlock NodeType;
 293   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
 294
 295   static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
 296   static inline ChildIteratorType child_begin(NodeType *N) {
 297     return N->succ_begin();
 298   }
 299   static inline ChildIteratorType child_end(NodeType *N) {
 300     return N->succ_end();
 301   }
 302 };
 303
 304 // Provide specializations of GraphTraits to be able to treat a
 305 // MachineFunction as a graph of MachineBasicBlocks... and to walk it
 306 // in inverse order.  Inverse order for a function is considered
 307 // to be when traversing the predecessor edges of a MBB
 308 // instead of the successor edges.
 309 //
 310 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
 311   typedef MachineBasicBlock NodeType;
 312   typedef MachineBasicBlock::pred_iterator ChildIteratorType;
 313   static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
 314     return G.Graph;
 315   }
 316   static inline ChildIteratorType child_begin(NodeType *N) {
 317     return N->pred_begin();
 318   }
 319   static inline ChildIteratorType child_end(NodeType *N) {
 320     return N->pred_end();
 321   }
 322 };
 323
 324 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
 325   typedef const MachineBasicBlock NodeType;
 326   typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
 327   static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
 328     return G.Graph;
 329   }
 330   static inline ChildIteratorType child_begin(NodeType *N) {
 331     return N->pred_begin();
 332   }
 333   static inline ChildIteratorType child_end(NodeType *N) {
 334     return N->pred_end();
 335   }
 336 };
 337
 338
 339 //===--------------------------------------------------------------------===//
 340 // GraphTraits specializations for MachineFunction bb graphs (machine-CFGs)
 341 //===--------------------------------------------------------------------===//
 342
 343 // Provide specializations of GraphTraits to be able to treat a
 344 // MachineFunction as a graph of MachineBasicBlocks... these are the
 345 // same as the MachineBasicBlock iterators, except that the root node
 346 // is implicitly the first node of the MachineFunction.
 347 //
 348 template <> struct GraphTraits<MachineFunction*> :
 349   public GraphTraits<MachineBasicBlock*> {
 350   static NodeType *getEntryNode(MachineFunction *F) {
 351     return &F->front();
 352   }
 353   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 354   typedef MachineFunction::iterator nodes_iterator;
 355   static nodes_iterator nodes_begin(MachineFunction *F) { return F->begin(); }
 356   static nodes_iterator nodes_end  (MachineFunction *F) { return F->end(); }
 357 };
 358 template <> struct GraphTraits<const MachineFunction*> :
 359   public GraphTraits<const MachineBasicBlock*> {
 360   static NodeType *getEntryNode(const MachineFunction *F) {
 361     return &F->front();
 362   }
 363   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 364   typedef MachineFunction::const_iterator nodes_iterator;
 365   static nodes_iterator nodes_begin(const MachineFunction *F) {
 366     return F->begin();
 367   }
 368   static nodes_iterator nodes_end  (const MachineFunction *F) {
 369     return F->end();
 370   }
 371 };
 372
 373
 374 // Provide specializations of GraphTraits to be able to treat a
 375 // MachineFunction as a graph of MachineBasicBlocks... and to walk it
 376 // in inverse order.  Inverse order for a MachineFunction is considered
 377 // to be when traversing the predecessor edges of a MBB instead of the
 378 // successor edges.
 379 //
 380 template <> struct GraphTraits<Inverse<MachineFunction*> > :
 381   public GraphTraits<Inverse<MachineBasicBlock*> > {
 382   static NodeType *getEntryNode(Inverse<MachineFunction*> G) {
 383     return &G.Graph->front();
 384   }
 385 };
 386 template <> struct GraphTraits<Inverse<const MachineFunction*> > :
 387   public GraphTraits<Inverse<const MachineBasicBlock*> > {
 388   static NodeType *getEntryNode(Inverse<const MachineFunction *> G) {
 389     return &G.Graph->front();
 390   }
 391 };
 392
 393 } // End llvm namespace
 394
 395 #endif