[rustc.git] / src / llvm / include / llvm / Analysis / RegionIterator.h

//===- RegionIterator.h - Iterators to iteratate over Regions ---*- 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 the iterators to iterate over the elements of a Region.
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_REGIONITERATOR_H
#define LLVM_ANALYSIS_REGIONITERATOR_H

#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/IR/CFG.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {
//===----------------------------------------------------------------------===//
/// @brief Hierarchical RegionNode successor iterator.
///
/// This iterator iterates over all successors of a RegionNode.
///
/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
/// the parent Region.  Furthermore for BasicBlocks that start a subregion, a
/// RegionNode representing the subregion is returned.
///
/// For a subregion RegionNode there is just one successor. The RegionNode
/// representing the exit of the subregion.
template<class NodeType, class BlockT, class RegionT>
class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
                                           NodeType, ptrdiff_t> {
  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;

  typedef GraphTraits<BlockT*> BlockTraits;
  typedef typename BlockTraits::ChildIteratorType SuccIterTy;

  // The iterator works in two modes, bb mode or region mode.
  enum ItMode {
    // In BB mode it returns all successors of this BasicBlock as its
    // successors.
    ItBB,
    // In region mode there is only one successor, thats the regionnode mapping
    // to the exit block of the regionnode
    ItRgBegin, // At the beginning of the regionnode successor.
    ItRgEnd    // At the end of the regionnode successor.
  };

  // Use two bit to represent the mode iterator.
  PointerIntPair<NodeType*, 2, ItMode> Node;

  // The block successor iterator.
  SuccIterTy BItor;

  // advanceRegionSucc - A region node has only one successor. It reaches end
  // once we advance it.
  void advanceRegionSucc() {
    assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
    Node.setInt(ItRgEnd);
  }

  NodeType* getNode() const{ return Node.getPointer(); }

  // isRegionMode - Is the current iterator in region mode?
  bool isRegionMode() const { return Node.getInt() != ItBB; }

  // Get the immediate successor. This function may return a Basic Block
  // RegionNode or a subregion RegionNode.
  NodeType* getISucc(BlockT* BB) const {
    NodeType *succ;
    succ = getNode()->getParent()->getNode(BB);
    assert(succ && "BB not in Region or entered subregion!");
    return succ;
  }

  // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
  inline BlockT* getRegionSucc() const {
    assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
    return getNode()->template getNodeAs<RegionT>()->getExit();
  }

  // isExit - Is this the exit BB of the Region?
  inline bool isExit(BlockT* BB) const {
    return getNode()->getParent()->getExit() == BB;
  }
public:
  typedef RNSuccIterator<NodeType, BlockT, RegionT> Self;

  typedef typename super::pointer pointer;

  /// @brief Create begin iterator of a RegionNode.
  inline RNSuccIterator(NodeType* node)
    : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
      BItor(BlockTraits::child_begin(node->getEntry())) {

    // Skip the exit block
    if (!isRegionMode())
      while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
        ++BItor;

    if (isRegionMode() && isExit(getRegionSucc()))
      advanceRegionSucc();
  }

  /// @brief Create an end iterator.
  inline RNSuccIterator(NodeType* node, bool)
    : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
      BItor(BlockTraits::child_end(node->getEntry())) {}

  inline bool operator==(const Self& x) const {
    assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
    if (isRegionMode())
      return Node.getInt() == x.Node.getInt();
    else
      return BItor == x.BItor;
  }

  inline bool operator!=(const Self& x) const { return !operator==(x); }

  inline pointer operator*() const {
    BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
    assert(!isExit(BB) && "Iterator out of range!");
    return getISucc(BB);
  }

  inline Self& operator++() {
    if(isRegionMode()) {
      // The Region only has 1 successor.
      advanceRegionSucc();
    } else {
      // Skip the exit.
      do
        ++BItor;
      while (BItor != BlockTraits::child_end(getNode()->getEntry())
          && isExit(*BItor));
    }
    return *this;
  }

  inline Self operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
  }

  inline const Self &operator=(const Self &I) {
    if (this != &I) {
      assert(getNode()->getParent() == I.getNode()->getParent()
             && "Cannot assign iterators of two different regions!");
      Node = I.Node;
      BItor = I.BItor;
    }
    return *this;
  }
};


//===----------------------------------------------------------------------===//
/// @brief Flat RegionNode iterator.
///
/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
/// are contained in the Region and its subregions. This is close to a virtual
/// control flow graph of the Region.
template<class NodeType, class BlockT, class RegionT>
class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
  : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
  typedef GraphTraits<BlockT*> BlockTraits;
  typedef typename BlockTraits::ChildIteratorType SuccIterTy;

  NodeType* Node;
  SuccIterTy Itor;

public:
  typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
  typedef typename super::pointer pointer;

  /// @brief Create the iterator from a RegionNode.
  ///
  /// Note that the incoming node must be a bb node, otherwise it will trigger
  /// an assertion when we try to get a BasicBlock.
  inline RNSuccIterator(NodeType* node) :
    Node(node),
    Itor(BlockTraits::child_begin(node->getEntry())) {
      assert(!Node->isSubRegion()
             && "Subregion node not allowed in flat iterating mode!");
      assert(Node->getParent() && "A BB node must have a parent!");

      // Skip the exit block of the iterating region.
      while (BlockTraits::child_end(Node->getEntry()) != Itor
          && Node->getParent()->getExit() == *Itor)
        ++Itor;
  }

  /// @brief Create an end iterator
  inline RNSuccIterator(NodeType* node, bool) :
    Node(node),
    Itor(BlockTraits::child_end(node->getEntry())) {
      assert(!Node->isSubRegion()
             && "Subregion node not allowed in flat iterating mode!");
  }

  inline bool operator==(const Self& x) const {
    assert(Node->getParent() == x.Node->getParent()
           && "Cannot compare iterators of different regions!");

    return Itor == x.Itor && Node == x.Node;
  }

  inline bool operator!=(const Self& x) const { return !operator==(x); }

  inline pointer operator*() const {
    BlockT *BB = *Itor;

    // Get the iterating region.
    RegionT *Parent = Node->getParent();

    // The only case that the successor reaches out of the region is it reaches
    // the exit of the region.
    assert(Parent->getExit() != BB && "iterator out of range!");

    return Parent->getBBNode(BB);
  }

  inline Self& operator++() {
    // Skip the exit block of the iterating region.
    do
      ++Itor;
    while (Itor != succ_end(Node->getEntry())
        && Node->getParent()->getExit() == *Itor);

    return *this;
  }

  inline Self operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
  }

  inline const Self &operator=(const Self &I) {
    if (this != &I) {
      assert(Node->getParent() == I.Node->getParent()
             && "Cannot assign iterators to two different regions!");
      Node = I.Node;
      Itor = I.Itor;
    }
    return *this;
  }
};

template<class NodeType, class BlockT, class RegionT>
inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
  return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
}

template<class NodeType, class BlockT, class RegionT>
inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
  return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
}

//===--------------------------------------------------------------------===//
// RegionNode GraphTraits specialization so the bbs in the region can be
// iterate by generic graph iterators.
//
// NodeT can either be region node or const region node, otherwise child_begin
// and child_end fail.

#define RegionNodeGraphTraits(NodeT, BlockT, RegionT)   \
  template<> struct GraphTraits<NodeT*> {      \
  typedef NodeT NodeType; \
  typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType;  \
  static NodeType *getEntryNode(NodeType* N) { return N; } \
  static inline ChildIteratorType child_begin(NodeType *N) { \
    return RNSuccIterator<NodeType, BlockT, RegionT>(N);             \
  } \
  static inline ChildIteratorType child_end(NodeType *N) { \
    return RNSuccIterator<NodeType, BlockT, RegionT>(N, true);     \
  } \
}; \
template<> struct GraphTraits<FlatIt<NodeT*>> {  \
  typedef NodeT NodeType; \
  typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType;    \
  static NodeType *getEntryNode(NodeType* N) { return N; } \
  static inline ChildIteratorType child_begin(NodeType *N) { \
    return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
  } \
  static inline ChildIteratorType child_end(NodeType *N) { \
    return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
  } \
}

#define RegionGraphTraits(RegionT, NodeT) \
template<> struct GraphTraits<RegionT*> \
  : public GraphTraits<NodeT*> { \
  typedef df_iterator<NodeType*> nodes_iterator; \
  static NodeType *getEntryNode(RegionT* R) { \
    return R->getNode(R->getEntry()); \
  } \
  static nodes_iterator nodes_begin(RegionT* R) { \
    return nodes_iterator::begin(getEntryNode(R)); \
  } \
  static nodes_iterator nodes_end(RegionT* R) { \
    return nodes_iterator::end(getEntryNode(R)); \
  } \
}; \
template<> struct GraphTraits<FlatIt<RegionT*> > \
  : public GraphTraits<FlatIt<NodeT*> > { \
  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \
  GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \
  static NodeType *getEntryNode(RegionT* R) { \
    return R->getBBNode(R->getEntry()); \
  } \
  static nodes_iterator nodes_begin(RegionT* R) { \
    return nodes_iterator::begin(getEntryNode(R)); \
  } \
  static nodes_iterator nodes_end(RegionT* R) { \
    return nodes_iterator::end(getEntryNode(R)); \
  } \
}

RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);

RegionGraphTraits(Region, RegionNode);
RegionGraphTraits(const Region, const RegionNode);

template <> struct GraphTraits<RegionInfo*>
  : public GraphTraits<FlatIt<RegionNode*> > {
  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;

  static NodeType *getEntryNode(RegionInfo *RI) {
    return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
  }
  static nodes_iterator nodes_begin(RegionInfo* RI) {
    return nodes_iterator::begin(getEntryNode(RI));
  }
  static nodes_iterator nodes_end(RegionInfo *RI) {
    return nodes_iterator::end(getEntryNode(RI));
  }
};

template <> struct GraphTraits<RegionInfoPass*>
  : public GraphTraits<RegionInfo *> {
  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;

  static NodeType *getEntryNode(RegionInfoPass *RI) {
    return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
  }
  static nodes_iterator nodes_begin(RegionInfoPass* RI) {
    return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
  }
  static nodes_iterator nodes_end(RegionInfoPass *RI) {
    return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
  }
};

} // End namespace llvm

#endif
Commit	Line	Data
223e47cc LB	1	//===- RegionIterator.h - Iterators to iteratate over Regions ---- C++ --===//
	2	//
	3	// The LLVM Compiler Infrastructure
	4	//
	5	// This file is distributed under the University of Illinois Open Source
	6	// License. See LICENSE.TXT for details.
	7	//
	8	//===----------------------------------------------------------------------===//
	9	// This file defines the iterators to iterate over the elements of a Region.
	10	//===----------------------------------------------------------------------===//
970d7e83 LB	11	#ifndef LLVM_ANALYSIS_REGIONITERATOR_H
970d7e83 LB	12	#define LLVM_ANALYSIS_REGIONITERATOR_H
223e47cc LB	13
223e47cc LB	14	#include "llvm/ADT/GraphTraits.h"
223e47cc	15	#include "llvm/ADT/PointerIntPair.h"
970d7e83	16	#include "llvm/ADT/SmallPtrSet.h"
223e47cc	17	#include "llvm/Analysis/RegionInfo.h"
1a4d82fc	18	#include "llvm/IR/CFG.h"
223e47cc LB	19	#include "llvm/Support/raw_ostream.h"
	20
	21	namespace llvm {
	22	//===----------------------------------------------------------------------===//
	23	/// @brief Hierarchical RegionNode successor iterator.
	24	///
	25	/// This iterator iterates over all successors of a RegionNode.
	26	///
	27	/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
	28	/// the parent Region. Furthermore for BasicBlocks that start a subregion, a
	29	/// RegionNode representing the subregion is returned.
	30	///
	31	/// For a subregion RegionNode there is just one successor. The RegionNode
	32	/// representing the exit of the subregion.
1a4d82fc	33	template<class NodeType, class BlockT, class RegionT>
223e47cc	34	class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
1a4d82fc	35	NodeType, ptrdiff_t> {
223e47cc	36	typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
1a4d82fc JJ	37
	38	typedef GraphTraits<BlockT*> BlockTraits;
	39	typedef typename BlockTraits::ChildIteratorType SuccIterTy;
	40
223e47cc	41	// The iterator works in two modes, bb mode or region mode.
1a4d82fc	42	enum ItMode {
223e47cc LB	43	// In BB mode it returns all successors of this BasicBlock as its
	44	// successors.
	45	ItBB,
	46	// In region mode there is only one successor, thats the regionnode mapping
	47	// to the exit block of the regionnode
	48	ItRgBegin, // At the beginning of the regionnode successor.
	49	ItRgEnd // At the end of the regionnode successor.
	50	};
	51
	52	// Use two bit to represent the mode iterator.
1a4d82fc	53	PointerIntPair<NodeType*, 2, ItMode> Node;
223e47cc LB	54
223e47cc LB	55	// The block successor iterator.
1a4d82fc	56	SuccIterTy BItor;
223e47cc LB	57
	58	// advanceRegionSucc - A region node has only one successor. It reaches end
	59	// once we advance it.
	60	void advanceRegionSucc() {
	61	assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
	62	Node.setInt(ItRgEnd);
	63	}
	64
	65	NodeType* getNode() const{ return Node.getPointer(); }
	66
	67	// isRegionMode - Is the current iterator in region mode?
	68	bool isRegionMode() const { return Node.getInt() != ItBB; }
	69
	70	// Get the immediate successor. This function may return a Basic Block
	71	// RegionNode or a subregion RegionNode.
1a4d82fc JJ	72	NodeType* getISucc(BlockT* BB) const {
1a4d82fc JJ	73	NodeType *succ;
223e47cc LB	74	succ = getNode()->getParent()->getNode(BB);
	75	assert(succ && "BB not in Region or entered subregion!");
	76	return succ;
	77	}
	78
	79	// getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
1a4d82fc	80	inline BlockT* getRegionSucc() const {
223e47cc	81	assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
1a4d82fc	82	return getNode()->template getNodeAs<RegionT>()->getExit();
223e47cc LB	83	}
	84
	85	// isExit - Is this the exit BB of the Region?
1a4d82fc	86	inline bool isExit(BlockT* BB) const {
223e47cc LB	87	return getNode()->getParent()->getExit() == BB;
	88	}
	89	public:
1a4d82fc	90	typedef RNSuccIterator<NodeType, BlockT, RegionT> Self;
223e47cc LB	91
	92	typedef typename super::pointer pointer;
	93
	94	/// @brief Create begin iterator of a RegionNode.
	95	inline RNSuccIterator(NodeType* node)
	96	: Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
1a4d82fc	97	BItor(BlockTraits::child_begin(node->getEntry())) {
223e47cc LB	98
	99	// Skip the exit block
	100	if (!isRegionMode())
1a4d82fc	101	while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
223e47cc LB	102	++BItor;
	103
	104	if (isRegionMode() && isExit(getRegionSucc()))
	105	advanceRegionSucc();
	106	}
	107
	108	/// @brief Create an end iterator.
	109	inline RNSuccIterator(NodeType* node, bool)
	110	: Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
1a4d82fc	111	BItor(BlockTraits::child_end(node->getEntry())) {}
223e47cc LB	112
	113	inline bool operator==(const Self& x) const {
	114	assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
	115	if (isRegionMode())
	116	return Node.getInt() == x.Node.getInt();
	117	else
	118	return BItor == x.BItor;
	119	}
	120
	121	inline bool operator!=(const Self& x) const { return !operator==(x); }
	122
	123	inline pointer operator*() const {
1a4d82fc	124	BlockT BB = isRegionMode() ? getRegionSucc() : BItor;
223e47cc LB	125	assert(!isExit(BB) && "Iterator out of range!");
	126	return getISucc(BB);
	127	}
	128
	129	inline Self& operator++() {
	130	if(isRegionMode()) {
	131	// The Region only has 1 successor.
	132	advanceRegionSucc();
	133	} else {
	134	// Skip the exit.
	135	do
	136	++BItor;
1a4d82fc	137	while (BItor != BlockTraits::child_end(getNode()->getEntry())
223e47cc LB	138	&& isExit(*BItor));
	139	}
	140	return *this;
	141	}
	142
	143	inline Self operator++(int) {
	144	Self tmp = *this;
	145	++*this;
	146	return tmp;
	147	}
	148
	149	inline const Self &operator=(const Self &I) {
	150	if (this != &I) {
	151	assert(getNode()->getParent() == I.getNode()->getParent()
	152	&& "Cannot assign iterators of two different regions!");
	153	Node = I.Node;
	154	BItor = I.BItor;
	155	}
	156	return *this;
	157	}
	158	};
	159
	160
	161	//===----------------------------------------------------------------------===//
	162	/// @brief Flat RegionNode iterator.
	163	///
	164	/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
	165	/// are contained in the Region and its subregions. This is close to a virtual
	166	/// control flow graph of the Region.
1a4d82fc JJ	167	template<class NodeType, class BlockT, class RegionT>
	168	class RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>
	169	: public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> {
223e47cc	170	typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
1a4d82fc JJ	171	typedef GraphTraits<BlockT*> BlockTraits;
	172	typedef typename BlockTraits::ChildIteratorType SuccIterTy;
	173
223e47cc	174	NodeType* Node;
1a4d82fc	175	SuccIterTy Itor;
223e47cc LB	176
223e47cc LB	177	public:
1a4d82fc	178	typedef RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT> Self;
223e47cc LB	179	typedef typename super::pointer pointer;
	180
	181	/// @brief Create the iterator from a RegionNode.
	182	///
	183	/// Note that the incoming node must be a bb node, otherwise it will trigger
	184	/// an assertion when we try to get a BasicBlock.
1a4d82fc JJ	185	inline RNSuccIterator(NodeType* node) :
	186	Node(node),
	187	Itor(BlockTraits::child_begin(node->getEntry())) {
223e47cc LB	188	assert(!Node->isSubRegion()
	189	&& "Subregion node not allowed in flat iterating mode!");
	190	assert(Node->getParent() && "A BB node must have a parent!");
	191
	192	// Skip the exit block of the iterating region.
1a4d82fc	193	while (BlockTraits::child_end(Node->getEntry()) != Itor
223e47cc LB	194	&& Node->getParent()->getExit() == *Itor)
	195	++Itor;
	196	}
1a4d82fc	197
223e47cc	198	/// @brief Create an end iterator
1a4d82fc JJ	199	inline RNSuccIterator(NodeType* node, bool) :
	200	Node(node),
	201	Itor(BlockTraits::child_end(node->getEntry())) {
223e47cc LB	202	assert(!Node->isSubRegion()
	203	&& "Subregion node not allowed in flat iterating mode!");
	204	}
	205
	206	inline bool operator==(const Self& x) const {
	207	assert(Node->getParent() == x.Node->getParent()
	208	&& "Cannot compare iterators of different regions!");
	209
	210	return Itor == x.Itor && Node == x.Node;
	211	}
	212
	213	inline bool operator!=(const Self& x) const { return !operator==(x); }
	214
	215	inline pointer operator*() const {
1a4d82fc	216	BlockT BB = Itor;
223e47cc LB	217
223e47cc LB	218	// Get the iterating region.
1a4d82fc	219	RegionT *Parent = Node->getParent();
223e47cc LB	220
	221	// The only case that the successor reaches out of the region is it reaches
	222	// the exit of the region.
	223	assert(Parent->getExit() != BB && "iterator out of range!");
	224
	225	return Parent->getBBNode(BB);
	226	}
	227
	228	inline Self& operator++() {
	229	// Skip the exit block of the iterating region.
	230	do
	231	++Itor;
	232	while (Itor != succ_end(Node->getEntry())
	233	&& Node->getParent()->getExit() == *Itor);
	234
	235	return *this;
	236	}
	237
	238	inline Self operator++(int) {
	239	Self tmp = *this;
	240	++*this;
	241	return tmp;
	242	}
	243
	244	inline const Self &operator=(const Self &I) {
	245	if (this != &I) {
	246	assert(Node->getParent() == I.Node->getParent()
	247	&& "Cannot assign iterators to two different regions!");
	248	Node = I.Node;
	249	Itor = I.Itor;
	250	}
	251	return *this;
	252	}
	253	};
	254
1a4d82fc JJ	255	template<class NodeType, class BlockT, class RegionT>
	256	inline RNSuccIterator<NodeType, BlockT, RegionT> succ_begin(NodeType* Node) {
	257	return RNSuccIterator<NodeType, BlockT, RegionT>(Node);
223e47cc LB	258	}
223e47cc LB	259
1a4d82fc JJ	260	template<class NodeType, class BlockT, class RegionT>
	261	inline RNSuccIterator<NodeType, BlockT, RegionT> succ_end(NodeType* Node) {
	262	return RNSuccIterator<NodeType, BlockT, RegionT>(Node, true);
223e47cc LB	263	}
	264
	265	//===--------------------------------------------------------------------===//
	266	// RegionNode GraphTraits specialization so the bbs in the region can be
	267	// iterate by generic graph iterators.
	268	//
	269	// NodeT can either be region node or const region node, otherwise child_begin
	270	// and child_end fail.
	271
1a4d82fc JJ	272	#define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
1a4d82fc JJ	273	template<> struct GraphTraits<NodeT*> { \
223e47cc	274	typedef NodeT NodeType; \
1a4d82fc	275	typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType; \
223e47cc LB	276	static NodeType getEntryNode(NodeType N) { return N; } \
223e47cc LB	277	static inline ChildIteratorType child_begin(NodeType *N) { \
1a4d82fc	278	return RNSuccIterator<NodeType, BlockT, RegionT>(N); \
223e47cc LB	279	} \
223e47cc LB	280	static inline ChildIteratorType child_end(NodeType *N) { \
1a4d82fc	281	return RNSuccIterator<NodeType, BlockT, RegionT>(N, true); \
223e47cc LB	282	} \
223e47cc LB	283	}; \
1a4d82fc	284	template<> struct GraphTraits<FlatIt<NodeT*>> { \
223e47cc	285	typedef NodeT NodeType; \
1a4d82fc	286	typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType; \
223e47cc LB	287	static NodeType getEntryNode(NodeType N) { return N; } \
223e47cc LB	288	static inline ChildIteratorType child_begin(NodeType *N) { \
1a4d82fc	289	return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
223e47cc LB	290	} \
223e47cc LB	291	static inline ChildIteratorType child_end(NodeType *N) { \
1a4d82fc	292	return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
223e47cc LB	293	} \
	294	}
	295
	296	#define RegionGraphTraits(RegionT, NodeT) \
	297	template<> struct GraphTraits<RegionT*> \
	298	: public GraphTraits<NodeT*> { \
	299	typedef df_iterator<NodeType*> nodes_iterator; \
	300	static NodeType getEntryNode(RegionT R) { \
	301	return R->getNode(R->getEntry()); \
	302	} \
	303	static nodes_iterator nodes_begin(RegionT* R) { \
	304	return nodes_iterator::begin(getEntryNode(R)); \
	305	} \
	306	static nodes_iterator nodes_end(RegionT* R) { \
	307	return nodes_iterator::end(getEntryNode(R)); \
	308	} \
	309	}; \
	310	template<> struct GraphTraits<FlatIt<RegionT*> > \
	311	: public GraphTraits<FlatIt<NodeT*> > { \
	312	typedef df_iterator<NodeType, SmallPtrSet<NodeType, 8>, false, \
	313	GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \
	314	static NodeType getEntryNode(RegionT R) { \
	315	return R->getBBNode(R->getEntry()); \
	316	} \
	317	static nodes_iterator nodes_begin(RegionT* R) { \
	318	return nodes_iterator::begin(getEntryNode(R)); \
	319	} \
	320	static nodes_iterator nodes_end(RegionT* R) { \
	321	return nodes_iterator::end(getEntryNode(R)); \
	322	} \
	323	}
	324
1a4d82fc JJ	325	RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
1a4d82fc JJ	326	RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
223e47cc LB	327
	328	RegionGraphTraits(Region, RegionNode);
	329	RegionGraphTraits(const Region, const RegionNode);
	330
	331	template <> struct GraphTraits<RegionInfo*>
	332	: public GraphTraits<FlatIt<RegionNode*> > {
	333	typedef df_iterator<NodeType, SmallPtrSet<NodeType, 8>, false,
	334	GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
	335
	336	static NodeType getEntryNode(RegionInfo RI) {
	337	return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
	338	}
	339	static nodes_iterator nodes_begin(RegionInfo* RI) {
	340	return nodes_iterator::begin(getEntryNode(RI));
	341	}
	342	static nodes_iterator nodes_end(RegionInfo *RI) {
	343	return nodes_iterator::end(getEntryNode(RI));
	344	}
	345	};
	346
1a4d82fc JJ	347	template <> struct GraphTraits<RegionInfoPass*>
	348	: public GraphTraits<RegionInfo *> {
	349	typedef df_iterator<NodeType, SmallPtrSet<NodeType, 8>, false,
	350	GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
	351
	352	static NodeType getEntryNode(RegionInfoPass RI) {
	353	return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
	354	}
	355	static nodes_iterator nodes_begin(RegionInfoPass* RI) {
	356	return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
	357	}
	358	static nodes_iterator nodes_end(RegionInfoPass *RI) {
	359	return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
	360	}
	361	};
	362
223e47cc LB	363	} // End namespace llvm
	364
	365	#endif