RegionInfo.h

//===- RegionInfo.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.
//
//===----------------------------------------------------------------------===//
//
// Calculate a program structure tree built out of single entry single exit
// regions.
// The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
// Koehler - 2009".
// The algorithm to calculate these data structures however is completely
// different, as it takes advantage of existing information already available
// in (Post)dominace tree and dominance frontier passes. This leads to a simpler
// and in practice hopefully better performing algorithm. The runtime of the
// algorithms described in the paper above are both linear in graph size,
// O(V+E), whereas this algorithm is not, as the dominance frontier information
// itself is not, but in practice runtime seems to be in the order of dominance
// tree calculation.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_REGION_INFO_H
#define LLVM_ANALYSIS_REGION_INFO_H

#include "llvm/ADT/PointerUnion.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {

class Region;
class RegionInfo;

// FlatIt - This class is used as a little marker class
template <class GraphType>
struct FlatIt {
  const GraphType &Graph;

  inline FlatIt(const GraphType &G) : Graph(G) {}
};

//forward declaration of the region node iterator
template<class> class RNSuccIterator;

class RegionNode {
protected:
  Region* parent;

  BasicBlock* BB;

  PointerUnion<const Region*, BasicBlock*> SubclassData;

  inline RegionNode(Region* r, BasicBlock* entry, BasicBlock* exit)
    : parent(r), BB(entry), SubclassData(exit) {}

public:
  inline RegionNode(Region* r, BasicBlock *bb)
    : parent(r), BB(bb), SubclassData(r){}

  virtual ~RegionNode() {}

  inline Region* getParent() const { return parent; }

  inline const Region* getItRegion() const {
    assert(!isRegionNode() && "this is not a BB node!");
    return SubclassData.get<const Region*>();
  }

  inline void setItRegion(const Region* R) {
    assert(!isRegionNode() && "this is not a BB node!");
    SubclassData = R;
  }

  inline void propItRegionTo(RegionNode *Node) const {
    Node->setItRegion(getItRegion());
  }

  inline BasicBlock* getBB() const { return BB; }

  template<class T>
  inline T* getNodeAs() const;

  inline bool isRegionNode() const {
    // This is only a region node if SubclassData holds the exit BB of this
    // region.
    return SubclassData.is<BasicBlock*>();
  }
};

//===----------------------------------------------------------------------===//
// RegionNode implementation
//

template<>
inline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const {
  assert(!isRegionNode() && "this is not a BB node!");
  return BB;
}

template<>
inline Region* RegionNode::getNodeAs<Region>() const {
  assert(isRegionNode() && "this is not a region node!");
  return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
}

//===----------------------------------------------------------------------===//
template<class BaseIt>
class RegionSetIt : public std::iterator<std::forward_iterator_tag,
                                         Region, ptrdiff_t>
{
  typedef std::iterator<std::forward_iterator_tag, Region, ptrdiff_t> super;

  BaseIt I, E;

public:
  typedef RegionSetIt _Self;
  typedef super::pointer pointer;

  inline RegionSetIt(BaseIt& i, BaseIt& e) : I(i), E(e) {
    while( I!= E && !I->second->isRegionNode())
      ++I;//skip bb nodes
  }
  //end iterator
  inline RegionSetIt(BaseIt& e) : I(e), E(e) {}

  inline bool operator==(const _Self& x) const {
    return I == x.I && E == x.E;
  }

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

  inline pointer operator*() const {
    assert(I != E && "RegionSetIt not dereferencable!");
    assert(I->second->isRegionNode() && "expect a region node!");
    return I->second->template getNodeAs<Region>();
  }

  inline pointer operator->() const {
    assert(I != E && "RegionSetIt not dereferencable!");
    assert(I->second->isRegionNode() && "expect a region node!");
    return I->second->template getNodeAs<Region>();
  }

  inline _Self& operator++() {   // Preincrement
    ++I;
    while( I!= E && !I->second->isRegionNode())
      ++I;//skip bb nodes

    return *this;
  }

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

  inline const _Self &operator=(const _Self &X) {
    if (this != &X) {
      assert(E == X.E &&"Cannot assign iterators to two different Regionset!");
      E = X.E;
      I = X.I;
    }
    return *this;
  }
};

//===----------------------------------------------------------------------===//
// make Region class derived from RegionNode so that:
// - we can keep the "parent" field synchronous
// - we dont need to free the old region node and create the new one
//    when transfering region from parentA to parentB
// - we do not need to keep a set for child region, and another set child
//    regionnode
class Region : private RegionNode {
  friend class RegionInfo;

  RegionInfo* RI;
  DominatorTree *DT;
  PostDominatorTree *PDT;

  typedef std::map<BasicBlock*, RegionNode*> NodeMapT;
  typedef std::map<BasicBlock*, RegionNode*>::iterator nodemap_iterator;
  std::map<BasicBlock*, RegionNode*> RNodeMap;

  RegionNode* getNode() {
    return static_cast<RegionNode*>(this);
  }

  const RegionNode* getNode() const {
      return static_cast<const RegionNode* const>(this);
  }

  bool contains(const Region *other) const {
    return DT->dominates(getEntry(), other->getEntry())
      && PDT->dominates(getExit(), other->getExit());
  }

  //===--------------------------------------------------------------------===//

  void verifyBBInRegion(BasicBlock* BB) const;

  void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const;

  void verifyRegionNest() const;

public:
  Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI,
         DominatorTree *DT, PostDominatorTree *PDT,
         Region *Parent = 0);

  ~Region();

  bool contains(BasicBlock *BB) const;

  BasicBlock *getEntry() const { return BB; }

  BasicBlock *getExit() const { return SubclassData.get<BasicBlock*>(); }

  using RegionNode::getParent;

  std::string getName() const {
    return getEntry()->getName().str() + " => " + getExit()->getName().str();
  }

  typedef RegionSetIt<std::map<BasicBlock*, RegionNode*>::iterator> iterator;
  typedef RegionSetIt<std::map<BasicBlock*, RegionNode*>::const_iterator>
    const_iterator;

  iterator begin() {
    std::map<BasicBlock*, RegionNode*>::iterator i = RNodeMap.begin(),
      e = RNodeMap.end();
    return iterator(i, e);
  }

  iterator end() {
    std::map<BasicBlock*, RegionNode*>::iterator e = RNodeMap.end();
    return iterator(e);
  }

  const_iterator begin() const {
    std::map<BasicBlock*, RegionNode*>::const_iterator i = RNodeMap.begin(),
      e = RNodeMap.end();
    return const_iterator(i, e);
  }

  const_iterator end() const {
     std::map<BasicBlock*, RegionNode*>::const_iterator e = RNodeMap.end();
    return const_iterator(e);
  }

  RegionNode* getChildNode(BasicBlock* BB) const {
    // Try to find the node in the map
    NodeMapT::const_iterator at = RNodeMap.find(BB);
    return at != RNodeMap.end() ? at->second : 0;
  }

  RegionNode* getBBNode(BasicBlock* BB) const;

  RegionNode* getGraphEntry() const;
  RegionNode* getFlatGraphEntry() const;

  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
          GraphTraits<FlatIt<RegionNode*> > > block_iterator;

  block_iterator block_begin();
  block_iterator block_end();

  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
          false, GraphTraits<FlatIt<const RegionNode*> > > const_block_iterator;

  const_block_iterator block_begin() const;
  const_block_iterator block_end() const;

  void print(raw_ostream& os, bool printtree = true, unsigned level = 0) const;

  void verifyRegion() const;

  unsigned getRegionDepth() const;

  Region *removeChildRegion(Region *Child);

  void addChildRegion(Region *NewChild);

  void transferChildrenTo(Region *To);
  void transferChildrenTo(RegionInfo *To);

  void removeBlock(BasicBlock *BB);

  void addBlock(BasicBlock *BB);
};


//===----------------------------------------------------------------------===//
inline raw_ostream &operator<<(raw_ostream &o, const RegionNode &Node) {
  if (Node.isRegionNode())
    return o << Node.getNodeAs<Region>()->getName();
  else
    return o << Node.getNodeAs<BasicBlock>()->getNameStr();
}

//===----------------------------------------------------------------------===//
class RegionInfo : public FunctionPass {
  typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap;
  typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
  typedef SmallPtrSet<Region*, 4> RegionSet;

  DominatorTree *DT;
  PostDominatorTree *PDT;
  DominanceFrontier *DF;

  RegionSet topLevelRegions;

  BBtoRegionMap BBtoRegion;


  //===--------------------------------------------------------------------===//

  bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry,
                           BasicBlock* exit) const;

  bool isRegion(BasicBlock* entry, BasicBlock* exit) const;

  void insertShortCut(BasicBlock* entry, BasicBlock* exit,
                      BBtoBBMap* ShortCut) const;

  DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const;

  bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const;

  Region *createRegion(BasicBlock *entry, BasicBlock *exit,
                       BBtoBBMap *ShortCut);

  void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut);

  void scanForRegions(Function &F, BBtoBBMap *ShortCut);

  Region *getTopMostParent(Region *region);

  void buildRegionsTree(DomTreeNode *N, Region *region = 0);

  void Calculate(Function& F);

  void releaseMemory();

  void updateStatistics(Region *R);

  bool isSimple(Region* R) const;

public:
  static char ID;
  explicit RegionInfo();

  ~RegionInfo();

  virtual bool runOnFunction(Function &F);
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  virtual void print(raw_ostream &OS, const Module *) const;
  virtual void verifyAnalysis() const;

  typedef RegionSet::iterator iterator;
  typedef RegionSet::const_iterator const_iterator;

  iterator begin() { return topLevelRegions.begin(); }
  iterator end() { return topLevelRegions.end(); }
  const_iterator begin() const { return topLevelRegions.begin(); }
  const_iterator end() const { return topLevelRegions.end(); }

  Region *getRegionFor(const BasicBlock *BB) const;

  Region *operator[](const BasicBlock *BB) const;

  const Region*
    findSmallestCommonRegion(const Region* A, const Region *B) const;

  const Region* findSmallestCommonRegion(const BasicBlock* A,
                                         const BasicBlock *B) const {
    return findSmallestCommonRegion(getRegionFor(A), getRegionFor(B));
  }

  const Region*
    findSmallestCommonRegion(SmallVectorImpl<Region*> &Regions) const;

  const Region*
    findSmallestCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const;

  void removeRegion(Region *R);

  void changeRegionFor(BasicBlock *BB, Region *R);

  void changeTopLevelRegion(Region *OldRegion, Region *NewRegion);

  void addTopLevelRegion(Region *New) {
    assert(New->getParent() == 0 && "Region already in subregion!");
    topLevelRegions.insert(New);
  }

  void removeBBFromMap(BasicBlock *BB);

};

} // End llvm namespace
#endif

---