llvm.org GIT mirror llvm / release_23 include / llvm / Support / CFG.h
release_23

Tree @release_23 (Download .tar.gz)

CFG.h @release_23

4848689
63b3afa
6fbcc26
 
7ed47a1
 
63b3afa
6fbcc26
428039a
2fbfdcf
428039a
 
 
 
4848689
 
428039a
551ccae
2fbfdcf
cc179d3
551ccae
cc179d3
d0fde30
 
cc179d3
 
 
 
 
a266197
 
cc179d3
 
 
fe8041a
63b3afa
280a6e6
 
 
6ad5a31
 
63b3afa
3ef437d
280a6e6
cc179d3
3ef437d
63b3afa
cc179d3
 
63b3afa
 
3ef437d
280a6e6
cc179d3
 
63b3afa
cc179d3
3ef437d
280a6e6
63b3afa
cc179d3
63b3afa
cc179d3
63b3afa
cc179d3
 
 
 
63b3afa
cc179d3
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3b96359
 
 
cc179d3
3b96359
cc179d3
3b96359
fe8041a
cc179d3
63b3afa
3b96359
cc179d3
 
3b96359
cc179d3
 
 
5554a1d
 
 
 
8f1717f
5554a1d
b977ef2
 
 
33e0a75
63b3afa
cc179d3
 
63b3afa
280a6e6
cc179d3
63b3afa
cc179d3
 
63b3afa
cc179d3
63b3afa
cc179d3
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
428039a
 
 
 
 
63b3afa
428039a
 
 
 
cc179d3
428039a
 
63b3afa
cc179d3
428039a
63b3afa
cc179d3
428039a
 
 
 
 
cc179d3
428039a
 
 
63b3afa
cc179d3
428039a
63b3afa
cc179d3
428039a
 
 
63b3afa
428039a
2fbfdcf
428039a
 
 
 
cc179d3
428039a
63b3afa
cc179d3
428039a
63b3afa
cc179d3
428039a
 
 
 
 
cc179d3
428039a
63b3afa
428039a
63b3afa
cc179d3
428039a
63b3afa
cc179d3
428039a
 
 
 
 
 
2fbfdcf
428039a
 
63b3afa
428039a
2fbfdcf
428039a
2fbfdcf
02a3be0
f77b570
 
 
 
 
428039a
2fbfdcf
428039a
02a3be0
f77b570
 
 
 
 
428039a
 
 
63b3afa
428039a
2fbfdcf
428039a
 
2fbfdcf
428039a
2fbfdcf
02a3be0
2fbfdcf
428039a
2fbfdcf
428039a
2fbfdcf
02a3be0
428039a
 
 
d0fde30
 
428039a
//===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines specializations of GraphTraits that allow Function and
// BasicBlock graphs to be treated as proper graphs for generic algorithms.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_CFG_H
#define LLVM_SUPPORT_CFG_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/Function.h"
#include "llvm/InstrTypes.h"
#include "llvm/ADT/iterator"

namespace llvm {

//===--------------------------------------------------------------------===//
// BasicBlock pred_iterator definition
//===--------------------------------------------------------------------===//

template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
class PredIterator : public forward_iterator<_Ptr, ptrdiff_t> {
  typedef forward_iterator<_Ptr, ptrdiff_t> super;
  _USE_iterator It;
public:
  typedef PredIterator<_Ptr,_USE_iterator> _Self;
  typedef typename super::pointer pointer;

  inline void advancePastNonTerminators() {
    // Loop to ignore non terminator uses (for example PHI nodes)...
    while (!It.atEnd() && !isa<TerminatorInst>(*It))
      ++It;
  }

  inline PredIterator(_Ptr *bb) : It(bb->use_begin()) {
    advancePastNonTerminators();
  }
  inline PredIterator(_Ptr *bb, bool) : It(bb->use_end()) {}

  inline bool operator==(const _Self& x) const { return It == x.It; }
  inline bool operator!=(const _Self& x) const { return !operator==(x); }

  inline pointer operator*() const {
    assert(!It.atEnd() && "pred_iterator out of range!");
    return cast<TerminatorInst>(*It)->getParent();
  }
  inline pointer *operator->() const { return &(operator*()); }

  inline _Self& operator++() {   // Preincrement
    assert(!It.atEnd() && "pred_iterator out of range!");
    ++It; advancePastNonTerminators();
    return *this;
  }

  inline _Self operator++(int) { // Postincrement
    _Self tmp = *this; ++*this; return tmp;
  }
};

typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
typedef PredIterator<const BasicBlock,
                     Value::use_const_iterator> pred_const_iterator;

inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  return pred_const_iterator(BB);
}
inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
inline pred_const_iterator pred_end(const BasicBlock *BB) {
  return pred_const_iterator(BB, true);
}



//===--------------------------------------------------------------------===//
// BasicBlock succ_iterator definition
//===--------------------------------------------------------------------===//

template <class Term_, class BB_>           // Successor Iterator
class SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> {
  const Term_ Term;
  unsigned idx;
  typedef bidirectional_iterator<BB_, ptrdiff_t> super;
public:
  typedef SuccIterator<Term_, BB_> _Self;
  typedef typename super::pointer pointer;
  // TODO: This can be random access iterator, need operator+ and stuff tho

  inline SuccIterator(Term_ T) : Term(T), idx(0) {         // begin iterator
    assert(T && "getTerminator returned null!");
  }
  inline SuccIterator(Term_ T, bool)                       // end iterator
    : Term(T), idx(Term->getNumSuccessors()) {
    assert(T && "getTerminator returned null!");
  }

  inline const _Self &operator=(const _Self &I) {
    assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
    idx = I.idx;
    return *this;
  }

  /// getSuccessorIndex - This is used to interface between code that wants to
  /// operate on terminator instructions directly.
  unsigned getSuccessorIndex() const { return idx; }

  inline bool operator==(const _Self& x) const { return idx == x.idx; }
  inline bool operator!=(const _Self& x) const { return !operator==(x); }

  inline pointer operator*() const { return Term->getSuccessor(idx); }
  inline pointer operator->() const { return operator*(); }

  inline _Self& operator++() { ++idx; return *this; } // Preincrement
  inline _Self operator++(int) { // Postincrement
    _Self tmp = *this; ++*this; return tmp;
  }

  inline _Self& operator--() { --idx; return *this; }  // Predecrement
  inline _Self operator--(int) { // Postdecrement
    _Self tmp = *this; --*this; return tmp;
  }
};

typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
typedef SuccIterator<const TerminatorInst*,
                     const BasicBlock> succ_const_iterator;

inline succ_iterator succ_begin(BasicBlock *BB) {
  return succ_iterator(BB->getTerminator());
}
inline succ_const_iterator succ_begin(const BasicBlock *BB) {
  return succ_const_iterator(BB->getTerminator());
}
inline succ_iterator succ_end(BasicBlock *BB) {
  return succ_iterator(BB->getTerminator(), true);
}
inline succ_const_iterator succ_end(const BasicBlock *BB) {
  return succ_const_iterator(BB->getTerminator(), true);
}



//===--------------------------------------------------------------------===//
// GraphTraits specializations for basic block graphs (CFGs)
//===--------------------------------------------------------------------===//

// Provide specializations of GraphTraits to be able to treat a function as a
// graph of basic blocks...

template <> struct GraphTraits<BasicBlock*> {
  typedef BasicBlock NodeType;
  typedef succ_iterator ChildIteratorType;

  static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return succ_begin(N);
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return succ_end(N);
  }
};

template <> struct GraphTraits<const BasicBlock*> {
  typedef const BasicBlock NodeType;
  typedef succ_const_iterator ChildIteratorType;

  static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }

  static inline ChildIteratorType child_begin(NodeType *N) {
    return succ_begin(N);
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return succ_end(N);
  }
};

// Provide specializations of GraphTraits to be able to treat a function as a
// graph of basic blocks... and to walk it in inverse order.  Inverse order for
// a function is considered to be when traversing the predecessor edges of a BB
// instead of the successor edges.
//
template <> struct GraphTraits<Inverse<BasicBlock*> > {
  typedef BasicBlock NodeType;
  typedef pred_iterator ChildIteratorType;
  static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return pred_begin(N);
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return pred_end(N);
  }
};

template <> struct GraphTraits<Inverse<const BasicBlock*> > {
  typedef const BasicBlock NodeType;
  typedef pred_const_iterator ChildIteratorType;
  static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
    return G.Graph;
  }
  static inline ChildIteratorType child_begin(NodeType *N) {
    return pred_begin(N);
  }
  static inline ChildIteratorType child_end(NodeType *N) {
    return pred_end(N);
  }
};



//===--------------------------------------------------------------------===//
// GraphTraits specializations for function basic block graphs (CFGs)
//===--------------------------------------------------------------------===//

// Provide specializations of GraphTraits to be able to treat a function as a
// graph of basic blocks... these are the same as the basic block iterators,
// except that the root node is implicitly the first node of the function.
//
template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
  static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }

  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
  typedef Function::iterator nodes_iterator;
  static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
  static nodes_iterator nodes_end  (Function *F) { return F->end(); }
};
template <> struct GraphTraits<const Function*> :
  public GraphTraits<const BasicBlock*> {
  static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}

  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
  typedef Function::const_iterator nodes_iterator;
  static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
  static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
};


// Provide specializations of GraphTraits to be able to treat a function as a
// graph of basic blocks... and to walk it in inverse order.  Inverse order for
// a function is considered to be when traversing the predecessor edges of a BB
// instead of the successor edges.
//
template <> struct GraphTraits<Inverse<Function*> > :
  public GraphTraits<Inverse<BasicBlock*> > {
  static NodeType *getEntryNode(Inverse<Function*> G) {
    return &G.Graph->getEntryBlock();
  }
};
template <> struct GraphTraits<Inverse<const Function*> > :
  public GraphTraits<Inverse<const BasicBlock*> > {
  static NodeType *getEntryNode(Inverse<const Function *> G) {
    return &G.Graph->getEntryBlock();
  }
};

} // End llvm namespace

#endif