#ifndef LLVM_ANALYSIS_REGION_ITERATOR_H
#define LLVM_ANALYSIS_REGION_ITERATOR_H
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/raw_ostream.h"
namespace llvm {
template<class NodeType>
class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
NodeType, ptrdiff_t>
{
typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
enum ItMode{
ItBB,
ItRgBegin, ItRgEnd };
PointerIntPair<NodeType*, 2, enum ItMode> Node;
succ_iterator BItor;
void advanceRegionSucc() {
assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
Node.setInt(ItRgEnd);
}
NodeType* getNode() const{ return Node.getPointer(); }
bool isRegionMode() const { return Node.getInt() != ItBB; }
RegionNode* getISucc(BasicBlock* BB) const {
RegionNode *succ;
succ = getNode()->getParent()->getNode(BB);
assert(succ && "BB not in Region or entered subregion!");
return succ;
}
inline BasicBlock* getRegionSucc() const {
assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
return getNode()->template getNodeAs<Region>()->getExit();
}
inline bool isExit(BasicBlock* BB) const {
return getNode()->getParent()->getExit() == BB;
}
public:
typedef RNSuccIterator<NodeType> Self;
typedef typename super::pointer pointer;
inline RNSuccIterator(NodeType* node)
: Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
BItor(succ_begin(node->getEntry())) {
if (!isRegionMode())
while (succ_end(node->getEntry()) != BItor && isExit(*BItor))
++BItor;
if (isRegionMode() && isExit(getRegionSucc()))
advanceRegionSucc();
}
inline RNSuccIterator(NodeType* node, bool)
: Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
BItor(succ_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 {
BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor;
assert(!isExit(BB) && "Iterator out of range!");
return getISucc(BB);
}
inline Self& operator++() {
if(isRegionMode()) {
advanceRegionSucc();
} else {
do
++BItor;
while (BItor != succ_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;
}
};
template<class NodeType>
class RNSuccIterator<FlatIt<NodeType> >
: public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t>
{
typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
NodeType* Node;
succ_iterator Itor;
public:
typedef RNSuccIterator<FlatIt<NodeType> > Self;
typedef typename super::pointer pointer;
inline RNSuccIterator(NodeType* node) : Node(node),
Itor(succ_begin(node->getEntry())) {
assert(!Node->isSubRegion()
&& "Subregion node not allowed in flat iterating mode!");
assert(Node->getParent() && "A BB node must have a parent!");
while (succ_end(Node->getEntry()) != Itor
&& Node->getParent()->getExit() == *Itor)
++Itor;
}
inline RNSuccIterator(NodeType* node, bool) : Node(node),
Itor(succ_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 {
BasicBlock* BB = *Itor;
Region* Parent = Node->getParent();
assert(Parent->getExit() != BB && "iterator out of range!");
return Parent->getBBNode(BB);
}
inline Self& operator++() {
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>
inline RNSuccIterator<NodeType> succ_begin(NodeType* Node) {
return RNSuccIterator<NodeType>(Node);
}
template<class NodeType>
inline RNSuccIterator<NodeType> succ_end(NodeType* Node) {
return RNSuccIterator<NodeType>(Node, true);
}
#define RegionNodeGraphTraits(NodeT) \
template<> struct GraphTraits<NodeT*> { \
typedef NodeT NodeType; \
typedef RNSuccIterator<NodeType> ChildIteratorType; \
static NodeType *getEntryNode(NodeType* N) { return N; } \
static inline ChildIteratorType child_begin(NodeType *N) { \
return RNSuccIterator<NodeType>(N); \
} \
static inline ChildIteratorType child_end(NodeType *N) { \
return RNSuccIterator<NodeType>(N, true); \
} \
}; \
template<> struct GraphTraits<FlatIt<NodeT*> > { \
typedef NodeT NodeType; \
typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \
static NodeType *getEntryNode(NodeType* N) { return N; } \
static inline ChildIteratorType child_begin(NodeType *N) { \
return RNSuccIterator<FlatIt<NodeType> >(N); \
} \
static inline ChildIteratorType child_end(NodeType *N) { \
return RNSuccIterator<FlatIt<NodeType> >(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);
RegionNodeGraphTraits(const RegionNode);
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));
}
};
}
#endif