include/llvm/Analysis/RegionIterator.h - llvm-project/llvm - Git at Google

 //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // 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/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/IR/CFG.h"
 #include <cassert>
 #include <iterator>
 #include <type_traits>

 namespace llvm {

 class BasicBlock;

 //===----------------------------------------------------------------------===//
 /// 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 NodeRef, class BlockT, class RegionT> class RNSuccIterator {
 public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
   using reference = value_type &;

 private:
   using BlockTraits = GraphTraits<BlockT *>;
   using SuccIterTy = typename BlockTraits::ChildIteratorType;

   // 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.
   };

   static_assert(std::is_pointer<NodeRef>::value,
                 "FIXME: Currently RNSuccIterator only supports NodeRef as "
                 "pointers due to the use of pointer-specific data structures "
                 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
                 "it to support non-pointer types");

   // Use two bit to represent the mode iterator.
   PointerIntPair<NodeRef, 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);
   }

   NodeRef 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.
   NodeRef getISucc(BlockT *BB) const {
     NodeRef 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:
   using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;

   /// Create begin iterator of a RegionNode.
   inline RNSuccIterator(NodeRef 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();
   }

   /// Create an end iterator.
   inline RNSuccIterator(NodeRef 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 value_type 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;
   }
 };

 //===----------------------------------------------------------------------===//
 /// 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 NodeRef, class BlockT, class RegionT>
 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
   using BlockTraits = GraphTraits<BlockT *>;
   using SuccIterTy = typename BlockTraits::ChildIteratorType;

   NodeRef Node;
   SuccIterTy Itor;

 public:
   using iterator_category = std::forward_iterator_tag;
   using value_type = NodeRef;
   using difference_type = std::ptrdiff_t;
   using pointer = value_type *;
   using reference = value_type &;

   using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;

   /// 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(NodeRef 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;
   }

   /// Create an end iterator
   inline RNSuccIterator(NodeRef 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 value_type 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;
   }
 };

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

 template <class NodeRef, class BlockT, class RegionT>
 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
   return RNSuccIterator<NodeRef, 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 *> {                                    \
     using NodeRef = NodeT *;                                                   \
     using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>;        \
     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     static inline ChildIteratorType child_begin(NodeRef N) {                   \
       return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
     }                                                                          \
     static inline ChildIteratorType child_end(NodeRef N) {                     \
       return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
     }                                                                          \
   };                                                                           \
   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
     using NodeRef = NodeT *;                                                   \
     using ChildIteratorType =                                                  \
         RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;                      \
     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     static inline ChildIteratorType child_begin(NodeRef N) {                   \
       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
     }                                                                          \
     static inline ChildIteratorType child_end(NodeRef N) {                     \
       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true);        \
     }                                                                          \
   }

 #define RegionGraphTraits(RegionT, NodeT)                                      \
   template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> {    \
     using nodes_iterator = df_iterator<NodeRef>;                               \
     static NodeRef 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 *>> {                                  \
     using nodes_iterator =                                                     \
         df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,          \
                     GraphTraits<FlatIt<NodeRef>>>;                             \
     static NodeRef 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*>> {
   using nodes_iterator =
       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
                   GraphTraits<FlatIt<NodeRef>>>;

   static NodeRef 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 *> {
   using nodes_iterator =
       df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
                   GraphTraits<FlatIt<NodeRef>>>;

   static NodeRef 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 // LLVM_ANALYSIS_REGIONITERATOR_H
	//===- RegionIterator.h - Iterators to iteratate over Regions ---- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	// 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/DepthFirstIterator.h"
	#include "llvm/ADT/GraphTraits.h"
	#include "llvm/ADT/PointerIntPair.h"
	#include "llvm/Analysis/RegionInfo.h"
	#include "llvm/IR/CFG.h"
	#include <cassert>
	#include <iterator>
	#include <type_traits>

	namespace llvm {

	class BasicBlock;

	//===----------------------------------------------------------------------===//
	/// 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 NodeRef, class BlockT, class RegionT> class RNSuccIterator {
	public:
	using iterator_category = std::forward_iterator_tag;
	using value_type = NodeRef;
	using difference_type = std::ptrdiff_t;
	using pointer = value_type *;
	using reference = value_type &;

	private:
	using BlockTraits = GraphTraits<BlockT *>;
	using SuccIterTy = typename BlockTraits::ChildIteratorType;

	// 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.
	};

	static_assert(std::is_pointer<NodeRef>::value,
	"FIXME: Currently RNSuccIterator only supports NodeRef as "
	"pointers due to the use of pointer-specific data structures "
	"(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
	"it to support non-pointer types");

	// Use two bit to represent the mode iterator.
	PointerIntPair<NodeRef, 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);
	}

	NodeRef 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.
	NodeRef getISucc(BlockT *BB) const {
	NodeRef 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:
	using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;

	/// Create begin iterator of a RegionNode.
	inline RNSuccIterator(NodeRef 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();
	}

	/// Create an end iterator.
	inline RNSuccIterator(NodeRef 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 value_type 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;
	}
	};

	//===----------------------------------------------------------------------===//
	/// 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 NodeRef, class BlockT, class RegionT>
	class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
	using BlockTraits = GraphTraits<BlockT *>;
	using SuccIterTy = typename BlockTraits::ChildIteratorType;

	NodeRef Node;
	SuccIterTy Itor;

	public:
	using iterator_category = std::forward_iterator_tag;
	using value_type = NodeRef;
	using difference_type = std::ptrdiff_t;
	using pointer = value_type *;
	using reference = value_type &;

	using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;

	/// 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(NodeRef 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;
	}

	/// Create an end iterator
	inline RNSuccIterator(NodeRef 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 value_type 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;
	}
	};

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

	template <class NodeRef, class BlockT, class RegionT>
	inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
	return RNSuccIterator<NodeRef, 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 *> { \
	using NodeRef = NodeT *; \
	using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>; \
	static NodeRef getEntryNode(NodeRef N) { return N; } \
	static inline ChildIteratorType child_begin(NodeRef N) { \
	return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \
	} \
	static inline ChildIteratorType child_end(NodeRef N) { \
	return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \
	} \
	}; \
	template <> struct GraphTraits<FlatIt<NodeT *>> { \
	using NodeRef = NodeT *; \
	using ChildIteratorType = \
	RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>; \
	static NodeRef getEntryNode(NodeRef N) { return N; } \
	static inline ChildIteratorType child_begin(NodeRef N) { \
	return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \
	} \
	static inline ChildIteratorType child_end(NodeRef N) { \
	return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \
	} \
	}

	#define RegionGraphTraits(RegionT, NodeT) \
	template <> struct GraphTraits<RegionT > : public GraphTraits<NodeT > { \
	using nodes_iterator = df_iterator<NodeRef>; \
	static NodeRef 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 *>> { \
	using nodes_iterator = \
	df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, \
	GraphTraits<FlatIt<NodeRef>>>; \
	static NodeRef 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*>> {
	using nodes_iterator =
	df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
	GraphTraits<FlatIt<NodeRef>>>;

	static NodeRef 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 *> {
	using nodes_iterator =
	df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
	GraphTraits<FlatIt<NodeRef>>>;

	static NodeRef 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 // LLVM_ANALYSIS_REGIONITERATOR_H