RegionIterator.h

//===- RegionIterator.h - SESE region detection analysis -----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// this files define the iterators that allow users iterate BBs in region.
//
//===----------------------------------------------------------------------===//
#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;
  // 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.
  };

  PointerIntPair<NodeType*, 2, enum ItMode> Node;

  succ_iterator BItor;

  void advanceRegionSucc() {
    assert(Node.getInt() == ItRgBegin && "cant advance region succ!");
    Node.setInt(ItRgEnd);
  }

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

  bool isRegionMode() const { return Node.getInt() != ItBB; }

  RegionNode* getISucc(BasicBlock* BB) const {
    RegionNode* succ = getNode()->getParent()->getChildNode(BB);
    assert(succ && "bb not in region or enter sub region!");
    return succ;
  }

  inline BasicBlock* getRegionSucc() const {
    assert(Node.getInt() == ItRgBegin && "cant get region succ!");
    return getNode()->template getNodeAs<Region>()->getExit();
  }

  inline bool reachExit(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->isRegionNode()?ItRgBegin:ItBB),
    BItor(node->getBB()->getTerminator()) {
    // Skip the exit block
    if (!isRegionMode() && reachExit(*BItor))
      ++BItor;
    else if (isRegionMode() &&  reachExit(getRegionSucc()))

      advanceRegionSucc();
  }

  inline RNSuccIterator(NodeType* node, bool)
    : Node(node, node->isRegionNode()?ItRgEnd:ItBB),
    BItor(node->getBB()->getTerminator(), true) {}

  inline bool operator==(const _Self& x) const {
    assert(isRegionMode() == x.isRegionMode() && "broken iterator!");
    //preform difference comparison on difference mode, because we only
    //increase one kind of iterator on each mode
    return isRegionMode() ?
      (Node.getInt() == x.Node.getInt()) : (BItor == x.BItor);
  }

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

  inline pointer operator*() const {
    BasicBlock* BB = isRegionMode()?getRegionSucc():*BItor;

    // the only case that the successor reach out of the region
    // is it reach the exit of the region, or it reach end
    assert(!reachExit(BB) && "iterator out of range!");
    return getISucc(BB);
  }

  inline _Self& operator++() {   // Preincrement
    if(isRegionMode())
      advanceRegionSucc();
    else {
      //increase the Itor
      ++BItor;
      //and skip the exit
      if (BItor.index_is_valid(BItor.getSuccessorIndex()) &&
        reachExit(*BItor))
        ++BItor;
    }
    return *this;
  }

  inline _Self operator++(int) { // Postincrement
    _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 to 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;

  RegionNode* getBBNode(BasicBlock* BB) const {
    RegionNode* ret = Node->getItRegion()->getBBNode(BB);
    Node->propItRegionTo(ret);
    return ret;
  }

public:
  typedef RNSuccIterator<FlatIt<NodeType> > _Self;
  typedef typename super::pointer pointer;

  inline RNSuccIterator(NodeType* node) : Node(node),
    Itor(node->template getNodeAs<BasicBlock>()->getTerminator()) {
      assert(!Node->isRegionNode() &&
        "unexpect a region node in flat iterating mode!");
      // Skip the exit block of the iterating region.
      if (Node->getItRegion()->getExit() == *Itor) ++Itor;
  }
  inline RNSuccIterator(NodeType* node, bool) : Node(node),
    // Create the end iterator.
    Itor(node->template getNodeAs<BasicBlock>()->getTerminator(), true) {}

  inline bool operator==(const _Self& x) const {
    assert(Node->getItRegion() == x.Node->getItRegion() &&
      "cant compare iterators of different regions!");
    return Itor == x.Itor;
  }
  inline bool operator!=(const _Self& x) const { return !operator==(x); }

  inline pointer operator*() const {
    BasicBlock* BB = *Itor;
    // The only case that the successor reach out of the region is it reach the
    // exit of the region.
    assert(Node->getItRegion()->getExit()!=BB && "iterator out of range!");

    return getBBNode(BB);
  }

  inline _Self& operator++() { // Preincrement
    ++Itor;

    if (Itor.index_is_valid(Itor.getSuccessorIndex())
        && Node->getItRegion()->getExit() == *Itor)
      ++Itor;
    return *this;
  }

  inline _Self operator++(int) { // Postincrement
    _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);
}

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

#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->getGraphEntry(); \
  } \
  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->getFlatGraphEntry(); \
  } \
  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);

//TODO: preds

} // End namespace llvm

#endif

---