Add new RegionInfo pass.

The RegionInfo pass detects single entry single exit regions in a function,
where a region is defined as any subgraph that is connected to the remaining
graph at only two spots.
Furthermore an hierarchical region tree is built.
Use it by calling "opt -regions analyze" or "opt -view-regions".

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109089 91177308-0d34-0410-b5e6-96231b3b80d8

32 files changed, 2707 insertions, 0 deletions

diff --git a/docs/Passes.html b/docs/Passes.html
index fb3bc94..12a936a 100644
--- a/docs/Passes.html
+++ b/docs/Passes.html
@@ -120,6 +120,7 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "  <p>\n" if !
 <tr><td><a href="#print-used-types">-print-used-types</a></td><td>Find Used Types</td></tr>
 <tr><td><a href="#profile-estimator">-profile-estimator</a></td><td>Estimate profiling information</td></tr>
 <tr><td><a href="#profile-loader">-profile-loader</a></td><td>Load profile information from llvmprof.out</td></tr>
+<tr><td><a href="#regions">-regions</a></td><td>Detect single entry single exit regions in a function</td></tr>
 <tr><td><a href="#profile-verifier">-profile-verifier</a></td><td>Verify profiling information</td></tr>
 <tr><td><a href="#scalar-evolution">-scalar-evolution</a></td><td>Scalar Evolution Analysis</td></tr>
 <tr><td><a href="#scev-aa">-scev-aa</a></td><td>ScalarEvolution-based Alias Analysis</td></tr>
@@ -771,6 +772,17 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "  <p>\n" if !
 <div class="doc_text">
   <p>Pass that checks profiling information for plausibility.</p>
 </div>
+<div class="doc_subsection">
+  <a name="regions">-regions: Detect single entry single exit regions in a function</a>
+</div>
+<div class="doc_text">
+  <p>
+  The <code>RegionInfo</code> pass detects single entry single exit regions in a
+  function, where a region is defined as any subgraph that is connected to the
+  remaining graph at only two spots. Furthermore, an hierarchical region tree is
+  built.
+  </p>
+</div>
 
 <!-------------------------------------------------------------------------- -->
 <div class="doc_subsection">
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index ce3f7a6..38bba77 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -154,6 +154,13 @@ namespace llvm {
   // print debug info intrinsics in human readable form
   FunctionPass *createDbgInfoPrinterPass();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createRegionInfoPass - This pass finds all single entry single exit regions
+  // in a function and builds the region hierarchy.
+  //
+  FunctionPass *createRegionInfoPass();
+
   // Print module-level debug info metadata in human-readable form.
   ModulePass *createModuleDebugInfoPrinterPass();
 }
diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
new file mode 100644
index 0000000..c4ac1eb
--- /dev/null
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -0,0 +1,601 @@
+//===- RegionInfo.h - SESE region 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 papers 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 magnitude
+// of dominance tree calculation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_REGION_INFO_H
+#define LLVM_ANALYSIS_REGION_INFO_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+class Region;
+class RegionInfo;
+class raw_ostream;
+
+/// @brief Marker class to iterate over the elements of a Region in flat mode.
+///
+/// The class is used to either iterate in Flat mode or by not using it to not
+/// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
+/// and the iteration returns every BasicBlock.  If the Flat mode is not
+/// selected for SubRegions just one RegionNode containing the subregion is
+/// returned.
+template <class GraphType>
+class FlatIt {};
+
+/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a
+/// Region.
+class RegionNode {
+  // DO NOT IMPLEMENT
+  RegionNode(const RegionNode &);
+  // DO NOT IMPLEMENT
+  const RegionNode &operator=(const RegionNode &);
+
+  /// This is the entry basic block that starts this region node.  If this is a
+  /// BasicBlock RegionNode, then entry is just the basic block, that this
+  /// RegionNode represents.  Otherwise it is the entry of this (Sub)RegionNode.
+  ///
+  /// In the BBtoRegionNode map of the parent of this node, BB will always map
+  /// to this node no matter which kind of node this one is.
+  ///
+  /// The node can hold either a Region or a BasicBlock.
+  /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
+  /// RegionNode.
+  PointerIntPair<BasicBlock*, 1, bool> entry;
+
+protected:
+  /// @brief The parent Region of this RegionNode.
+  /// @see getParent()
+  Region* parent;
+
+public:
+  /// @brief Create a RegionNode.
+  ///
+  /// @param Parent      The parent of this RegionNode.
+  /// @param Entry       The entry BasicBlock of the RegionNode.  If this
+  ///                    RegionNode represents a BasicBlock, this is the
+  ///                    BasicBlock itself.  If it represents a subregion, this
+  ///                    is the entry BasicBlock of the subregion.
+  /// @param isSubRegion If this RegionNode represents a SubRegion.
+  inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0)
+    : entry(Entry, isSubRegion), parent(Parent) {}
+
+  /// @brief Get the parent Region of this RegionNode.
+  ///
+  /// The parent Region is the Region this RegionNode belongs to. If for
+  /// example a BasicBlock is element of two Regions, there exist two
+  /// RegionNodes for this BasicBlock. Each with the getParent() function
+  /// pointing to the Region this RegionNode belongs to.
+  ///
+  /// @return Get the parent Region of this RegionNode.
+  inline Region* getParent() const { return parent; }
+
+  /// @brief Get the entry BasicBlock of this RegionNode.
+  ///
+  /// If this RegionNode represents a BasicBlock this is just the BasicBlock
+  /// itself, otherwise we return the entry BasicBlock of the Subregion
+  ///
+  /// @return The entry BasicBlock of this RegionNode.
+  inline BasicBlock* getEntry() const { return entry.getPointer(); }
+
+  /// @brief Get the content of this RegionNode.
+  ///
+  /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
+  /// check the type of the content with the isSubRegion() function call.
+  ///
+  /// @return The content of this RegionNode.
+  template<class T>
+  inline T* getNodeAs() const;
+
+  /// @brief Is this RegionNode a subregion?
+  ///
+  /// @return True if it contains a subregion. False if it contains a
+  ///         BasicBlock.
+  inline bool isSubRegion() const {
+    return entry.getInt();
+  }
+};
+
+/// Print a RegionNode.
+inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node);
+
+template<>
+inline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const {
+  assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
+  return getEntry();
+}
+
+template<>
+inline Region* RegionNode::getNodeAs<Region>() const {
+  assert(isSubRegion() && "This is not a subregion RegionNode!");
+  return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
+}
+
+//===----------------------------------------------------------------------===//
+/// @brief A single entry single exit Region.
+///
+/// A Region is a connected subgraph of a control flow graph that has exactly
+/// two connections to the remaining graph. It can be used to analyze or
+/// optimize parts of the control flow graph.
+///
+/// A <em> simple Region </em> is connected to the remaing graph by just two
+/// edges. One edge entering the Region and another one leaving the Region.
+///
+/// An <em> extended Region </em> (or just Region) is a subgraph that can be
+/// transform into a simple Region. The transformation is done by adding
+/// BasicBlocks that merge several entry or exit edges so that after the merge
+/// just one entry and one exit edge exists.
+///
+/// The \e Entry of a Region is the first BasicBlock that is passed after
+/// entering the Region. It is an element of the Region. The entry BasicBlock
+/// dominates all BasicBlocks in the Region.
+///
+/// The \e Exit of a Region is the first BasicBlock that is passed after
+/// leaving the Region. It is not an element of the Region. The exit BasicBlock,
+/// postdominates all BasicBlocks in the Region.
+///
+/// A <em> canonical Region </em> cannot be constructed by combining smaller
+/// Regions.
+///
+/// Region A is the \e parent of Region B, if B is completely contained in A.
+///
+/// Two canonical Regions either do not intersect at all or one is
+/// the parent of the other.
+///
+/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
+/// Regions in the control flow graph and E is the \e parent relation of these
+/// Regions.
+///
+/// Example:
+///
+/// \verbatim
+/// A simple control flow graph, that contains two regions.
+///
+///        1
+///       / |
+///      2   |
+///     / \   3
+///    4   5  |
+///    |   |  |
+///    6   7  8
+///     \  | /
+///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
+///        9        Region B: 2 -> 9 {2,4,5,6,7}
+/// \endverbatim
+///
+/// You can obtain more examples by either calling
+///
+/// <tt> "opt -regions -analyze anyprogram.ll" </tt>
+/// or
+/// <tt> "opt -view-regions-only anyprogram.ll" </tt>
+///
+/// on any LLVM file you are interested in.
+///
+/// The first call returns a textual representation of the program structure
+/// tree, the second one creates a graphical representation using graphviz.
+class Region : public RegionNode {
+  friend class RegionInfo;
+  // DO NOT IMPLEMENT
+  Region(const Region &);
+  // DO NOT IMPLEMENT
+  const Region &operator=(const Region &);
+
+  // Information necessary to manage this Region.
+  RegionInfo* RI;
+  DominatorTree *DT;
+
+  // The exit BasicBlock of this region.
+  // (The entry BasicBlock is part of RegionNode)
+  BasicBlock *exit;
+
+  typedef std::vector<Region*> RegionSet;
+
+  // The subregions of this region.
+  RegionSet children;
+
+  typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT;
+
+  // Save the BasicBlock RegionNodes that are element of this Region.
+  mutable BBNodeMapT BBNodeMap;
+
+  /// verifyBBInRegion - Check if a BB is in this Region. This check also works
+  /// if the region is incorrectly built. (EXPENSIVE!)
+  void verifyBBInRegion(BasicBlock* BB) const;
+
+  /// verifyWalk - Walk over all the BBs of the region starting from BB and
+  /// verify that all reachable basic blocks are elements of the region.
+  /// (EXPENSIVE!)
+  void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const;
+
+  /// verifyRegionNest - Verify if the region and its children are valid
+  /// regions (EXPENSIVE!)
+  void verifyRegionNest() const;
+
+public:
+  /// @brief Create a new region.
+  ///
+  /// @param Entry  The entry basic block of the region.
+  /// @param Exit   The exit basic block of the region.
+  /// @param RI     The region info object that is managing this region.
+  /// @param DT     The dominator tree of the current function.
+  /// @param Parent The surrounding region or NULL if this is a top level
+  ///               region.
+  Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI,
+         DominatorTree *DT, Region *Parent = 0);
+
+  /// Delete the Region and all its subregions.
+  ~Region();
+
+  /// @brief Get the entry BasicBlock of the Region.
+  /// @return The entry BasicBlock of the region.
+  BasicBlock *getEntry() const { return RegionNode::getEntry(); }
+
+  /// @brief Get the exit BasicBlock of the Region.
+  /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
+  ///         Region.
+  BasicBlock *getExit() const { return exit; }
+
+  /// @brief Get the parent of the Region.
+  /// @return The parent of the Region or NULL if this is a top level
+  ///         Region.
+  Region *getParent() const { return RegionNode::getParent(); }
+
+  /// @brief Get the RegionNode representing the current Region.
+  /// @return The RegionNode representing the current Region.
+  RegionNode* getNode() const {
+    return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this));
+  }
+
+  /// @brief Get the nesting level of this Region.
+  ///
+  /// An toplevel Region has depth 0.
+  ///
+  /// @return The depth of the region.
+  unsigned getDepth() const;
+
+  /// @brief Is this a simple region?
+  ///
+  /// A region is simple if it has exactly one exit and one entry edge.
+  ///
+  /// @return True if the Region is simple.
+  bool isSimple() const;
+
+  /// @brief Returns the name of the Region.
+  /// @return The Name of the Region.
+  std::string getNameStr() const {
+    std::string exitName;
+
+    if (getExit())
+      exitName = getExit()->getNameStr();
+    else
+      exitName = "<Function Return>";
+
+    return getEntry()->getNameStr() + " => " + exitName;
+  }
+
+  /// @brief Return the RegionInfo object, that belongs to this Region.
+  RegionInfo *getRegionInfo() const {
+    return RI;
+  }
+
+  /// @brief Print the region.
+  ///
+  /// @param OS The output stream the Region is printed to.
+  /// @param printTree Print also the tree of subregions.
+  /// @param level The indentation level used for printing.
+  void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const;
+
+  /// @brief Print the region to stderr.
+  void dump() const;
+
+  /// @brief Check if the region contains a BasicBlock.
+  ///
+  /// @param BB The BasicBlock that might be contained in this Region.
+  /// @return True if the block is contained in the region otherwise false.
+  bool contains(const BasicBlock *BB) const;
+
+  /// @brief Check if the region contains another region.
+  ///
+  /// @param SubRegion The region that might be contained in this Region.
+  /// @return True if SubRegion is contained in the region otherwise false.
+  bool contains(const Region *SubRegion) const {
+    // Toplevel Region.
+    if (!getExit())
+      return true;
+
+    return contains(SubRegion->getEntry())
+      && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit());
+  }
+
+  /// @brief Check if the region contains an Instruction.
+  ///
+  /// @param Inst The Instruction that might be contained in this region.
+  /// @return True if the Instruction is contained in the region otherwise false.
+  bool contains(const Instruction *Inst) const {
+    return contains(Inst->getParent());
+  }
+
+  /// @brief Get the subregion that starts at a BasicBlock
+  ///
+  /// @param BB The BasicBlock the subregion should start.
+  /// @return The Subregion if available, otherwise NULL.
+  Region* getSubRegionNode(BasicBlock *BB) const;
+
+  /// @brief Get the RegionNode for a BasicBlock
+  ///
+  /// @param BB The BasicBlock at which the RegionNode should start.
+  /// @return If available, the RegionNode that represents the subregion
+  ///         starting at BB. If no subregion starts at BB, the RegionNode
+  ///         representing BB.
+  RegionNode* getNode(BasicBlock *BB) const;
+
+  /// @brief Get the BasicBlock RegionNode for a BasicBlock
+  ///
+  /// @param BB The BasicBlock for which the RegionNode is requested.
+  /// @return The RegionNode representing the BB.
+  RegionNode* getBBNode(BasicBlock *BB) const;
+
+  /// @brief Add a new subregion to this Region.
+  ///
+  /// @param SubRegion The new subregion that will be added.
+  void addSubRegion(Region *SubRegion);
+
+  /// @brief Remove a subregion from this Region.
+  ///
+  /// The subregion is not deleted, as it will probably be inserted into another
+  /// region.
+  /// @param SubRegion The SubRegion that will be removed.
+  Region *removeSubRegion(Region *SubRegion);
+
+  /// @brief Move all direct child nodes of this Region to another Region.
+  ///
+  /// @param To The Region the child nodes will be transfered to.
+  void transferChildrenTo(Region *To);
+
+  /// @brief Verify if the region is a correct region.
+  ///
+  /// Check if this is a correctly build Region. This is an expensive check, as
+  /// the complete CFG of the Region will be walked.
+  void verifyRegion() const;
+
+  /// @brief Clear the cache for BB RegionNodes.
+  ///
+  /// After calling this function the BasicBlock RegionNodes will be stored at
+  /// different memory locations. RegionNodes obtained before this function is
+  /// called are therefore not comparable to RegionNodes abtained afterwords.
+  void clearNodeCache();
+
+  /// @name Subregion Iterators
+  ///
+  /// These iterators iterator over all subregions of this Region.
+  //@{
+  typedef RegionSet::iterator iterator;
+  typedef RegionSet::const_iterator const_iterator;
+
+  iterator begin() { return children.begin(); }
+  iterator end() { return children.end(); }
+
+  const_iterator begin() const { return children.begin(); }
+  const_iterator end() const { return children.end(); }
+  //@}
+
+  /// @name BasicBlock Iterators
+  ///
+  /// These iterators iterate over all BasicBlock RegionNodes that are
+  /// contained in this Region. The iterator also iterates over BasicBlocks
+  /// that are elements of a subregion of this Region. It is therefore called a
+  /// flat iterator.
+  //@{
+  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
+                      GraphTraits<FlatIt<RegionNode*> > > block_iterator;
+
+  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
+                      false, GraphTraits<FlatIt<const RegionNode*> > >
+            const_block_iterator;
+
+  block_iterator block_begin();
+  block_iterator block_end();
+
+  const_block_iterator block_begin() const;
+  const_block_iterator block_end() const;
+  //@}
+
+  /// @name Element Iterators
+  ///
+  /// These iterators iterate over all BasicBlock and subregion RegionNodes that
+  /// are direct children of this Region. It does not iterate over any
+  /// RegionNodes that are also element of a subregion of this Region.
+  //@{
+  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
+                      GraphTraits<RegionNode*> > element_iterator;
+
+  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
+                      false, GraphTraits<const RegionNode*> >
+            const_element_iterator;
+
+  element_iterator element_begin();
+  element_iterator element_end();
+
+  const_element_iterator element_begin() const;
+  const_element_iterator element_end() const;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
+/// @brief Analysis that detects all canonical Regions.
+///
+/// The RegionInfo pass detects all canonical regions in a function. The Regions
+/// are connected using the parent relation. This builds a Program Structure
+/// Tree.
+class RegionInfo : public FunctionPass {
+  typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap;
+  typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
+  typedef SmallPtrSet<Region*, 4> RegionSet;
+
+  // DO NOT IMPLEMENT
+  RegionInfo(const RegionInfo &);
+  // DO NOT IMPLEMENT
+  const RegionInfo &operator=(const RegionInfo &);
+
+  DominatorTree *DT;
+  PostDominatorTree *PDT;
+  DominanceFrontier *DF;
+
+  /// The top level region.
+  Region *TopLevelRegion;
+
+  /// Map every BB to the smallest region, that contains BB.
+  BBtoRegionMap BBtoRegion;
+
+  // isCommonDomFrontier - Returns true if BB is in the dominance frontier of
+  // entry, because it was inherited from exit. In the other case there is an
+  // edge going from entry to BB without passing exit.
+  bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry,
+                           BasicBlock* exit) const;
+
+  // isRegion - Check if entry and exit surround a valid region, based on
+  // dominance tree and dominance frontier.
+  bool isRegion(BasicBlock* entry, BasicBlock* exit) const;
+
+  // insertShortCut - Saves a shortcut pointing from entry to exit.
+  // This function may extend this shortcut if possible.
+  void insertShortCut(BasicBlock* entry, BasicBlock* exit,
+                      BBtoBBMap* ShortCut) const;
+
+  // getNextPostDom - Returns the next BB that postdominates N, while skipping
+  // all post dominators that cannot finish a canonical region.
+  DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const;
+
+  // isTrivialRegion - A region is trivial, if it contains only one BB.
+  bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const;
+
+  // createRegion - Creates a single entry single exit region.
+  Region *createRegion(BasicBlock *entry, BasicBlock *exit);
+
+  // findRegionsWithEntry - Detect all regions starting with bb 'entry'.
+  void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut);
+
+  // scanForRegions - Detects regions in F.
+  void scanForRegions(Function &F, BBtoBBMap *ShortCut);
+
+  // getTopMostParent - Get the top most parent with the same entry block.
+  Region *getTopMostParent(Region *region);
+
+  // buildRegionsTree - build the region hierarchy after all region detected.
+  void buildRegionsTree(DomTreeNode *N, Region *region);
+
+  // Calculate - detecte all regions in function and build the region tree.
+  void Calculate(Function& F);
+
+  void releaseMemory();
+
+  // updateStatistics - Update statistic about created regions.
+  void updateStatistics(Region *R);
+
+  // isSimple - Check if a region is a simple region with exactly one entry
+  // edge and exactly one exit edge.
+  bool isSimple(Region* R) const;
+
+public:
+  static char ID;
+  explicit RegionInfo();
+
+  ~RegionInfo();
+
+  /// @name FunctionPass interface
+  //@{
+  virtual bool runOnFunction(Function &F);
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+  virtual void print(raw_ostream &OS, const Module *) const;
+  virtual void verifyAnalysis() const;
+  //@}
+
+  /// @brief Get the smallest region that contains a BasicBlock.
+  ///
+  /// @param BB The basic block.
+  /// @return The smallest region, that contains BB or NULL, if there is no
+  /// region containing BB.
+  Region *getRegionFor(BasicBlock *BB) const;
+
+  /// @brief A shortcut for getRegionFor().
+  ///
+  /// @param BB The basic block.
+  /// @return The smallest region, that contains BB or NULL, if there is no
+  /// region containing BB.
+  Region *operator[](BasicBlock *BB) const;
+
+  /// @brief Find the smallest region that contains two regions.
+  ///
+  /// @param A The first region.
+  /// @param B The second region.
+  /// @return The smallest region containing A and B.
+  Region *getCommonRegion(Region* A, Region *B) const;
+
+  /// @brief Find the smallest region that contains two basic blocks.
+  ///
+  /// @param A The first basic block.
+  /// @param B The second basic block.
+  /// @return The smallest region that contains A and B.
+  Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const {
+    return getCommonRegion(getRegionFor(A), getRegionFor(B));
+  }
+
+  /// @brief Find the smallest region that contains a set of regions.
+  ///
+  /// @param Regions A vector of regions.
+  /// @return The smallest region that contains all regions in Regions.
+  Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const;
+
+  /// @brief Find the smallest region that contains a set of basic blocks.
+  ///
+  /// @param BBs A vector of basic blocks.
+  /// @return The smallest region that contains all basic blocks in BBS.
+  Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const;
+
+  Region *getTopLevelRegion() const {
+    return TopLevelRegion;
+  }
+
+  /// @brief Clear the Node Cache for all Regions.
+  ///
+  /// @see Region::clearNodeCache()
+  void clearNodeCache() {
+    if (TopLevelRegion)
+      TopLevelRegion->clearNodeCache();
+  }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) {
+  if (Node.isSubRegion())
+    return OS << Node.getNodeAs<Region>()->getNameStr();
+  else
+    return OS << Node.getNodeAs<BasicBlock>()->getNameStr();
+}
+} // End llvm namespace
+#endif
+
diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h
new file mode 100644
index 0000000..ced5b52
--- /dev/null
+++ b/include/llvm/Analysis/RegionIterator.h
@@ -0,0 +1,342 @@
+//===- 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_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 {
+//===----------------------------------------------------------------------===//
+/// @brief Hierachical 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 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.
+  };
+
+  // Use two bit to represent the mode iterator.
+  PointerIntPair<NodeType*, 2, enum ItMode> Node;
+
+  // The block successor iterator.
+  succ_iterator 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.
+  RegionNode* getISucc(BasicBlock* BB) const {
+    RegionNode *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 BasicBlock* getRegionSucc() const {
+    assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
+    return getNode()->template getNodeAs<Region>()->getExit();
+  }
+
+  // isExit - Is this the exit BB of the Region?
+  inline bool isExit(BasicBlock* BB) const {
+    return getNode()->getParent()->getExit() == BB;
+  }
+public:
+  typedef RNSuccIterator<NodeType> Self;
+
+  typedef typename super::pointer pointer;
+
+  /// @brief Create begin iterator of a RegionNode.
+  inline RNSuccIterator(NodeType* node)
+    : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
+    BItor(succ_begin(node->getEntry())) {
+
+
+    // Skip the exit block
+    if (!isRegionMode())
+      while (succ_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(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()) {
+      // The Region only has 1 successor.
+      advanceRegionSucc();
+    } else {
+      // Skip the exit.
+      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;
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+/// @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 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;
+
+  /// @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(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!");
+
+      // Skip the exit block of the iterating region.
+      while (succ_end(Node->getEntry()) != Itor
+          && Node->getParent()->getExit() == *Itor)
+        ++Itor;
+  }
+  /// @brief Create an end iterator
+  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;
+
+    // Get the iterating region.
+    Region* 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>
+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 can either be region node or const region node, otherwise child_begin
+// and child_end 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->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));
+  }
+};
+
+} // End namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/RegionPrinter.h b/include/llvm/Analysis/RegionPrinter.h
new file mode 100644
index 0000000..758748a
--- /dev/null
+++ b/include/llvm/Analysis/RegionPrinter.h
@@ -0,0 +1,26 @@
+//===-- RegionPrinter.h - Region printer external interface -----*- 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 external functions that can be called to explicitly
+// instantiate the region printer.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_REGIONPRINTER_H
+#define LLVM_ANALYSIS_REGIONPRINTER_H
+
+namespace llvm {
+  class FunctionPass;
+  FunctionPass *createRegionViewerPass();
+  FunctionPass *createRegionOnlyViewerPass();
+  FunctionPass *createRegionPrinterPass();
+  FunctionPass *createRegionOnlyPrinterPass();
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index 876703b..4f3a019 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -22,6 +22,7 @@
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/PointerTracking.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/RegionPrinter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/Lint.h"
 #include "llvm/Assembly/PrintModulePass.h"
@@ -106,6 +107,11 @@ namespace {
       (void) llvm::createPostDomOnlyViewerPass();
       (void) llvm::createPostDomViewerPass();
       (void) llvm::createReassociatePass();
+      (void) llvm::createRegionInfoPass();
+      (void) llvm::createRegionOnlyPrinterPass();
+      (void) llvm::createRegionOnlyViewerPass();
+      (void) llvm::createRegionPrinterPass();
+      (void) llvm::createRegionViewerPass();
       (void) llvm::createSCCPPass();
       (void) llvm::createScalarReplAggregatesPass();
       (void) llvm::createSimplifyLibCallsPass();
diff --git a/include/llvm/Support/GraphWriter.h b/include/llvm/Support/GraphWriter.h
index 559f004..f653f97 100644
--- a/include/llvm/Support/GraphWriter.h
+++ b/include/llvm/Support/GraphWriter.h
@@ -271,6 +271,12 @@ public:
       O << "[" << Attrs << "]";
     O << ";\n";
   }
+
+  /// getOStream - Get the raw output stream into the graph file. Useful to
+  /// write fancy things using addCustomGraphFeatures().
+  raw_ostream &getOStream() {
+    return O;
+  }
 };
 
 template<typename GraphType>
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index d9b670d..587f413 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -38,6 +38,8 @@ add_llvm_library(LLVMAnalysis
   ProfileInfoLoader.cpp
   ProfileInfoLoaderPass.cpp
   ProfileVerifierPass.cpp
+  RegionInfo.cpp
+  RegionPrinter.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp
   ScalarEvolutionExpander.cpp
diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp
new file mode 100644
index 0000000..589cc47
--- /dev/null
+++ b/lib/Analysis/RegionInfo.cpp
@@ -0,0 +1,637 @@
+//===- RegionInfo.cpp - SESE region detection analysis --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Detects single entry single exit regions in the control flow graph.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/RegionInfo.h"
+#include "llvm/Analysis/RegionIterator.h"
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "region"
+#include "llvm/Support/Debug.h"
+
+#include <set>
+#include <algorithm>
+
+using namespace llvm;
+
+// Always verify if expensive checking is enabled.
+#ifdef XDEBUG
+bool VerifyRegionInfo = true;
+#else
+bool VerifyRegionInfo = false;
+#endif
+
+static cl::opt<bool,true>
+VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo),
+                cl::desc("Verify region info (time consuming)"));
+
+STATISTIC(numRegions,       "The # of regions");
+STATISTIC(numSimpleRegions, "The # of simple regions");
+
+//===----------------------------------------------------------------------===//
+/// PrintStyle - Print region in difference ways.
+enum PrintStyle { PrintNone, PrintBB, PrintRN  };
+
+cl::opt<enum PrintStyle> printStyle("print-region-style", cl::Hidden,
+  cl::desc("style of printing regions"),
+  cl::values(
+    clEnumValN(PrintNone, "none",  "print no details"),
+    clEnumValN(PrintBB, "bb",  "print regions in detail with block_iterator"),
+    clEnumValN(PrintRN, "rn",  "print regions in detail with element_iterator"),
+    clEnumValEnd));
+//===----------------------------------------------------------------------===//
+/// Region Implementation
+Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo,
+               DominatorTree *dt, Region *Parent)
+               : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}
+
+Region::~Region() {
+  // Only clean the cache for this Region. Caches of child Regions will be
+  // cleaned when the child Regions are deleted.
+  BBNodeMap.clear();
+
+  for (iterator I = begin(), E = end(); I != E; ++I)
+    delete *I;
+}
+
+bool Region::contains(const BasicBlock *B) const {
+  BasicBlock *BB = const_cast<BasicBlock*>(B);
+
+  assert(DT->getNode(BB) && "BB not part of the dominance tree");
+
+  BasicBlock *entry = getEntry(), *exit = getExit();
+
+  // Toplevel region.
+  if (!exit)
+    return true;
+
+  return (DT->dominates(entry, BB)
+    && !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
+}
+
+bool Region::isSimple() const {
+  bool isSimple = true;
+  bool found = false;
+
+  BasicBlock *entry = getEntry(), *exit = getExit();
+
+  // TopLevelRegion
+  if (!exit)
+    return false;
+
+  for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
+       ++PI)
+    if (!contains(*PI)) {
+      if (found) {
+        isSimple = false;
+        break;
+      }
+      found = true;
+    }
+
+  found = false;
+
+  for (pred_iterator PI = pred_begin(exit), PE = pred_end(exit); PI != PE;
+       ++PI)
+    if (contains(*PI)) {
+      if (found) {
+        isSimple = false;
+        break;
+      }
+      found = true;
+    }
+
+  return isSimple;
+}
+
+void Region::verifyBBInRegion(BasicBlock *BB) const {
+  if (!contains(BB))
+    llvm_unreachable("Broken region found!");
+
+  BasicBlock *entry = getEntry(), *exit = getExit();
+
+  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+    if (!contains(*SI) && exit != *SI)
+      llvm_unreachable("Broken region found!");
+
+  if (entry != BB)
+    for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); SI != SE; ++SI)
+      if (!contains(*SI))
+        llvm_unreachable("Broken region found!");
+}
+
+void Region::verifyWalk(BasicBlock *BB, std::set<BasicBlock*> *visited) const {
+  BasicBlock *exit = getExit();
+
+  visited->insert(BB);
+
+  verifyBBInRegion(BB);
+
+  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
+    if (*SI != exit && visited->find(*SI) == visited->end())
+        verifyWalk(*SI, visited);
+}
+
+void Region::verifyRegion() const {
+  // Only do verification when user wants to, otherwise this expensive
+  // check will be invoked by PassManager.
+  if (!VerifyRegionInfo) return;
+
+  std::set<BasicBlock*> visited;
+  verifyWalk(getEntry(), &visited);
+}
+
+void Region::verifyRegionNest() const {
+  for (Region::const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
+    (*RI)->verifyRegionNest();
+
+  verifyRegion();
+}
+
+Region::block_iterator Region::block_begin() {
+  return GraphTraits<FlatIt<Region*> >::nodes_begin(this);
+}
+
+Region::block_iterator Region::block_end() {
+  return GraphTraits<FlatIt<Region*> >::nodes_end(this);
+}
+
+Region::const_block_iterator Region::block_begin() const {
+  return GraphTraits<FlatIt<const Region*> >::nodes_begin(this);
+}
+
+Region::const_block_iterator Region::block_end() const {
+  return GraphTraits<FlatIt<const Region*> >::nodes_end(this);
+}
+
+Region::element_iterator Region::element_begin() {
+  return GraphTraits<Region*>::nodes_begin(this);
+}
+
+Region::element_iterator Region::element_end() {
+  return GraphTraits<Region*>::nodes_end(this);
+}
+
+Region::const_element_iterator Region::element_begin() const {
+  return GraphTraits<const Region*>::nodes_begin(this);
+}
+
+Region::const_element_iterator Region::element_end() const {
+  return GraphTraits<const Region*>::nodes_end(this);
+}
+
+Region* Region::getSubRegionNode(BasicBlock *BB) const {
+  Region *R = RI->getRegionFor(BB);
+
+  if (!R || R == this)
+    return 0;
+
+  // If we pass the BB out of this region, that means our code is broken.
+  assert(contains(R) && "BB not in current region!");
+
+  while (contains(R->getParent()) && R->getParent() != this)
+    R = R->getParent();
+
+  if (R->getEntry() != BB)
+    return 0;
+
+  return R;
+}
+
+RegionNode* Region::getBBNode(BasicBlock *BB) const {
+  assert(contains(BB) && "Can get BB node out of this region!");
+
+  BBNodeMapT::const_iterator at = BBNodeMap.find(BB);
+
+  if (at != BBNodeMap.end())
+    return at->second;
+
+  RegionNode *NewNode = new RegionNode(const_cast<Region*>(this), BB);
+  BBNodeMap.insert(std::make_pair(BB, NewNode));
+  return NewNode;
+}
+
+RegionNode* Region::getNode(BasicBlock *BB) const {
+  assert(contains(BB) && "Can get BB node out of this region!");
+  if (Region* Child = getSubRegionNode(BB))
+    return Child->getNode();
+
+  return getBBNode(BB);
+}
+
+void Region::transferChildrenTo(Region *To) {
+  for (iterator I = begin(), E = end(); I != E; ++I) {
+    (*I)->parent = To;
+    To->children.push_back(*I);
+  }
+  children.clear();
+}
+
+void Region::addSubRegion(Region *SubRegion) {
+  assert(SubRegion->parent == 0 && "SubRegion already has a parent!");
+  SubRegion->parent = this;
+  // Set up the region node.
+  assert(std::find(children.begin(), children.end(), SubRegion) == children.end()
+         && "Node already exist!");
+  children.push_back(SubRegion);
+}
+
+
+Region *Region::removeSubRegion(Region *Child) {
+  assert(Child->parent == this && "Child is not a child of this region!");
+  Child->parent = 0;
+  RegionSet::iterator I = std::find(children.begin(), children.end(), Child);
+  assert(I != children.end() && "Region does not exit. Unable to remove.");
+  children.erase(children.begin()+(I-begin()));
+  return Child;
+}
+
+unsigned Region::getDepth() const {
+  unsigned Depth = 0;
+
+  for (Region *R = parent; R != 0; R = R->parent)
+    ++Depth;
+
+  return Depth;
+}
+
+void Region::print(raw_ostream &OS, bool print_tree, unsigned level) const {
+  if (print_tree)
+    OS.indent(level*2) << "[" << level << "] " << getNameStr();
+  else
+    OS.indent(level*2) << getNameStr();
+
+  OS << "\n";
+
+
+  if (printStyle != PrintNone) {
+    OS.indent(level*2) << "{\n";
+    OS.indent(level*2 + 2);
+
+    if (printStyle == PrintBB) {
+      for (const_block_iterator I = block_begin(), E = block_end(); I!=E; ++I)
+        OS << **I << ", "; // TODO: remove the last ","
+    } else if (printStyle == PrintRN) {
+      for (const_element_iterator I = element_begin(), E = element_end(); I!=E; ++I)
+        OS << **I << ", "; // TODO: remove the last ",
+    }
+
+    OS << "\n";
+  }
+
+  if (print_tree)
+    for (const_iterator RI = begin(), RE = end(); RI != RE; ++RI)
+      (*RI)->print(OS, print_tree, level+1);
+
+  if (printStyle != PrintNone)
+    OS.indent(level*2) << "} \n";
+}
+
+void Region::dump() const {
+  print(dbgs(), true, getDepth());
+}
+
+void Region::clearNodeCache() {
+  BBNodeMap.clear();
+  for (Region::iterator RI = begin(), RE = end(); RI != RE; ++RI)
+    (*RI)->clearNodeCache();
+}
+
+//===----------------------------------------------------------------------===//
+// RegionInfo implementation
+//
+
+bool RegionInfo::isCommonDomFrontier(BasicBlock *BB, BasicBlock *entry,
+                                     BasicBlock *exit) const {
+  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
+    if (DT->dominates(entry, *PI) && !DT->dominates(exit, *PI))
+      return false;
+
+  return true;
+}
+
+bool RegionInfo::isRegion(BasicBlock *entry, BasicBlock *exit) const {
+  assert(entry && exit && "entry and exit must not be null!");
+  typedef DominanceFrontier::DomSetType DST;
+
+  DST *entrySuccs = &(*DF->find(entry)).second;
+
+  // Exit is the header of a loop that contains the entry. In this case,
+  // the dominance frontier must only contain the exit.
+  if (!DT->dominates(entry, exit)) {
+    for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
+         SI != SE; ++SI)
+      if (*SI != exit && *SI != entry)
+        return false;
+
+    return true;
+  }
+
+  DST *exitSuccs = &(*DF->find(exit)).second;
+
+  // Do not allow edges leaving the region.
+  for (DST::iterator SI = entrySuccs->begin(), SE = entrySuccs->end();
+       SI != SE; ++SI) {
+    if (*SI == exit || *SI == entry)
+      continue;
+    if (exitSuccs->find(*SI) == exitSuccs->end())
+      return false;
+    if (!isCommonDomFrontier(*SI, entry, exit))
+      return false;
+  }
+
+  // Do not allow edges pointing into the region.
+  for (DST::iterator SI = exitSuccs->begin(), SE = exitSuccs->end();
+       SI != SE; ++SI)
+    if (DT->dominates(entry, *SI) && *SI != entry && *SI != exit)
+      return false;
+
+
+  return true;
+}
+
+void RegionInfo::insertShortCut(BasicBlock *entry, BasicBlock *exit,
+                             BBtoBBMap *ShortCut) const {
+  assert(entry && exit && "entry and exit must not be null!");
+
+  BBtoBBMap::iterator e = ShortCut->find(exit);
+
+  if (e == ShortCut->end())
+    // No further region at exit available.
+    (*ShortCut)[entry] = exit;
+  else {
+    // We found a region e that starts at exit. Therefore (entry, e->second)
+    // is also a region, that is larger than (entry, exit). Insert the
+    // larger one.
+    BasicBlock *BB = e->second;
+    (*ShortCut)[entry] = BB;
+  }
+}
+
+DomTreeNode* RegionInfo::getNextPostDom(DomTreeNode* N,
+                                        BBtoBBMap *ShortCut) const {
+  BBtoBBMap::iterator e = ShortCut->find(N->getBlock());
+
+  if (e == ShortCut->end())
+    return N->getIDom();
+
+  return PDT->getNode(e->second)->getIDom();
+}
+
+bool RegionInfo::isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const {
+  assert(entry && exit && "entry and exit must not be null!");
+
+  unsigned num_successors = succ_end(entry) - succ_begin(entry);
+
+  if (num_successors <= 1 && exit == *(succ_begin(entry)))
+    return true;
+
+  return false;
+}
+
+void RegionInfo::updateStatistics(Region *R) {
+  ++numRegions;
+
+  // TODO: Slow. Should only be enabled if -stats is used.
+  if (R->isSimple()) ++numSimpleRegions;
+}
+
+Region *RegionInfo::createRegion(BasicBlock *entry, BasicBlock *exit) {
+  assert(entry && exit && "entry and exit must not be null!");
+
+  if (isTrivialRegion(entry, exit))
+    return 0;
+
+  Region *region = new Region(entry, exit, this, DT);
+  BBtoRegion.insert(std::make_pair(entry, region));
+
+ #ifdef XDEBUG
+    region->verifyRegion();
+ #else
+    DEBUG(region->verifyRegion());
+ #endif
+
+  updateStatistics(region);
+  return region;
+}
+
+void RegionInfo::findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut) {
+  assert(entry);
+
+  DomTreeNode *N = PDT->getNode(entry);
+
+  if (!N)
+    return;
+
+  Region *lastRegion= 0;
+  BasicBlock *lastExit = entry;
+
+  // As only a BasicBlock that postdominates entry can finish a region, walk the
+  // post dominance tree upwards.
+  while ((N = getNextPostDom(N, ShortCut))) {
+    BasicBlock *exit = N->getBlock();
+
+    if (!exit)
+      break;
+
+    if (isRegion(entry, exit)) {
+      Region *newRegion = createRegion(entry, exit);
+
+      if (lastRegion)
+        newRegion->addSubRegion(lastRegion);
+
+      lastRegion = newRegion;
+      lastExit = exit;
+    }
+
+    // This can never be a region, so stop the search.
+    if (!DT->dominates(entry, exit))
+      break;
+  }
+
+  // Tried to create regions from entry to lastExit.  Next time take a
+  // shortcut from entry to lastExit.
+  if (lastExit != entry)
+    insertShortCut(entry, lastExit, ShortCut);
+}
+
+void RegionInfo::scanForRegions(Function &F, BBtoBBMap *ShortCut) {
+  BasicBlock *entry = &(F.getEntryBlock());
+  DomTreeNode *N = DT->getNode(entry);
+
+  // Iterate over the dominance tree in post order to start with the small
+  // regions from the bottom of the dominance tree.  If the small regions are
+  // detected first, detection of bigger regions is faster, as we can jump
+  // over the small regions.
+  for (po_iterator<DomTreeNode*> FI = po_begin(N), FE = po_end(N); FI != FE;
+    ++FI) {
+    findRegionsWithEntry((*FI)->getBlock(), ShortCut);
+  }
+}
+
+Region *RegionInfo::getTopMostParent(Region *region) {
+  while (region->parent)
+    region = region->getParent();
+
+  return region;
+}
+
+void RegionInfo::buildRegionsTree(DomTreeNode *N, Region *region) {
+  BasicBlock *BB = N->getBlock();
+
+  // Passed region exit
+  while (BB == region->getExit())
+    region = region->getParent();
+
+  BBtoRegionMap::iterator it = BBtoRegion.find(BB);
+
+  // This basic block is a start block of a region. It is already in the
+  // BBtoRegion relation. Only the child basic blocks have to be updated.
+  if (it != BBtoRegion.end()) {
+    Region *newRegion = it->second;;
+    region->addSubRegion(getTopMostParent(newRegion));
+    region = newRegion;
+  } else {
+    BBtoRegion[BB] = region;
+  }
+
+  for (DomTreeNode::iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI)
+    buildRegionsTree(*CI, region);
+}
+
+void RegionInfo::releaseMemory() {
+  BBtoRegion.clear();
+  if (TopLevelRegion)
+    delete TopLevelRegion;
+  TopLevelRegion = 0;
+}
+
+RegionInfo::RegionInfo() : FunctionPass(&ID) {
+  TopLevelRegion = 0;
+}
+
+RegionInfo::~RegionInfo() {
+  releaseMemory();
+}
+
+void RegionInfo::Calculate(Function &F) {
+  // ShortCut a function where for every BB the exit of the largest region
+  // starting with BB is stored. These regions can be threated as single BBS.
+  // This improves performance on linear CFGs.
+  BBtoBBMap ShortCut;
+
+  scanForRegions(F, &ShortCut);
+  BasicBlock *BB = &F.getEntryBlock();
+  buildRegionsTree(DT->getNode(BB), TopLevelRegion);
+}
+
+bool RegionInfo::runOnFunction(Function &F) {
+  releaseMemory();
+
+  DT = &getAnalysis<DominatorTree>();
+  PDT = &getAnalysis<PostDominatorTree>();
+  DF = &getAnalysis<DominanceFrontier>();
+
+  TopLevelRegion = new Region(&F.getEntryBlock(), 0, this, DT, 0);
+  updateStatistics(TopLevelRegion);
+
+  Calculate(F);
+
+  return false;
+}
+
+void RegionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequiredTransitive<DominatorTree>();
+  AU.addRequired<PostDominatorTree>();
+  AU.addRequired<DominanceFrontier>();
+}
+
+void RegionInfo::print(raw_ostream &OS, const Module *) const {
+  OS << "Region tree:\n";
+  TopLevelRegion->print(OS, true, 0);
+  OS << "End region tree\n";
+}
+
+void RegionInfo::verifyAnalysis() const {
+  // Only do verification when user wants to, otherwise this expensive check
+  // will be invoked by PMDataManager::verifyPreservedAnalysis when
+  // a regionpass (marked PreservedAll) finish.
+  if (!VerifyRegionInfo) return;
+
+  TopLevelRegion->verifyRegionNest();
+}
+
+// Region pass manager support.
+Region *RegionInfo::getRegionFor(BasicBlock *BB) const {
+  BBtoRegionMap::const_iterator I=
+    BBtoRegion.find(BB);
+  return I != BBtoRegion.end() ? I->second : 0;
+}
+
+Region *RegionInfo::operator[](BasicBlock *BB) const {
+  return getRegionFor(BB);
+}
+
+Region*
+RegionInfo::getCommonRegion(Region *A, Region *B) const {
+  assert (A && B && "One of the Regions is NULL");
+
+  if (A->contains(B)) return A;
+
+  while (!B->contains(A))
+    B = B->getParent();
+
+  return B;
+}
+
+Region*
+RegionInfo::getCommonRegion(SmallVectorImpl<Region*> &Regions) const {
+  Region* ret = Regions.back();
+  Regions.pop_back();
+
+  for (SmallVectorImpl<Region*>::const_iterator I = Regions.begin(),
+       E = Regions.end(); I != E; ++I)
+      ret = getCommonRegion(ret, *I);
+
+  return ret;
+}
+
+Region*
+RegionInfo::getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const {
+  Region* ret = getRegionFor(BBs.back());
+  BBs.pop_back();
+
+  for (SmallVectorImpl<BasicBlock*>::const_iterator I = BBs.begin(),
+       E = BBs.end(); I != E; ++I)
+      ret = getCommonRegion(ret, getRegionFor(*I));
+
+  return ret;
+}
+
+char RegionInfo::ID = 0;
+INITIALIZE_PASS(RegionInfo, "regions",
+                "Detect single entry single exit regions", true, true);
+
+// Create methods available outside of this file, to use them
+// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
+// the link time optimization.
+
+namespace llvm {
+  FunctionPass *createRegionInfoPass() {
+    return new RegionInfo();
+  }
+}
+
diff --git a/lib/Analysis/RegionPrinter.cpp b/lib/Analysis/RegionPrinter.cpp
new file mode 100644
index 0000000..c657143
--- /dev/null
+++ b/lib/Analysis/RegionPrinter.cpp
@@ -0,0 +1,182 @@
+//===- RegionPrinter.cpp - Print regions tree pass ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Print out the region tree of a function using dotty/graphviz.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/RegionInfo.h"
+#include "llvm/Analysis/RegionIterator.h"
+#include "llvm/Analysis/RegionPrinter.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/DOTGraphTraitsPass.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+/// onlySimpleRegion - Show only the simple regions in the RegionViewer.
+static cl::opt<bool>
+onlySimpleRegions("only-simple-regions",
+                  cl::desc("Show only simple regions in the graphviz viewer"),
+                  cl::Hidden,
+                  cl::init(false));
+
+namespace llvm {
+template<>
+struct DOTGraphTraits<RegionNode*> : public DefaultDOTGraphTraits {
+
+  DOTGraphTraits (bool isSimple=false)
+    : DefaultDOTGraphTraits(isSimple) {}
+
+  std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
+
+    if (!Node->isSubRegion()) {
+      BasicBlock *BB = Node->getNodeAs<BasicBlock>();
+
+      if (isSimple())
+        return DOTGraphTraits<const Function*>
+          ::getSimpleNodeLabel(BB, BB->getParent());
+      else
+        return DOTGraphTraits<const Function*>
+          ::getCompleteNodeLabel(BB, BB->getParent());
+    }
+
+    return "Not implemented";
+  }
+};
+
+template<>
+struct DOTGraphTraits<RegionInfo*> : public DOTGraphTraits<RegionNode*> {
+
+  DOTGraphTraits (bool isSimple=false)
+    : DOTGraphTraits<RegionNode*>(isSimple) {}
+
+  static std::string getGraphName(RegionInfo *DT) {
+    return "Region Graph";
+  }
+
+  std::string getNodeLabel(RegionNode *Node, RegionInfo *G) {
+    return DOTGraphTraits<RegionNode*>::getNodeLabel(Node,
+                                                     G->getTopLevelRegion());
+  }
+
+  // Print the cluster of the subregions. This groups the single basic blocks
+  // and adds a different background color for each group.
+  static void printRegionCluster(const Region *R, GraphWriter<RegionInfo*> &GW,
+                                 unsigned depth = 0) {
+    raw_ostream &O = GW.getOStream();
+    O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void*>(R)
+      << " {\n";
+    O.indent(2 * (depth + 1)) << "label = \"\";\n";
+
+    if (!onlySimpleRegions || R->isSimple()) {
+      O.indent(2 * (depth + 1)) << "style = filled;\n";
+      O.indent(2 * (depth + 1)) << "color = "
+        << ((R->getDepth() * 2 % 12) + 1) << "\n";
+
+    } else {
+      O.indent(2 * (depth + 1)) << "style = solid;\n";
+      O.indent(2 * (depth + 1)) << "color = "
+        << ((R->getDepth() * 2 % 12) + 2) << "\n";
+    }
+
+    for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI)
+      printRegionCluster(*RI, GW, depth + 1);
+
+    RegionInfo *RI = R->getRegionInfo();
+
+    for (Region::const_block_iterator BI = R->block_begin(),
+         BE = R->block_end(); BI != BE; ++BI) {
+      BasicBlock *BB = (*BI)->getNodeAs<BasicBlock>();
+      if (RI->getRegionFor(BB) == R)
+        O.indent(2 * (depth + 1)) << "Node"
+          << static_cast<const void*>(RI->getTopLevelRegion()->getBBNode(BB))
+          << ";\n";
+    }
+
+    O.indent(2 * depth) << "}\n";
+  }
+
+  static void addCustomGraphFeatures(const RegionInfo* RI,
+                                     GraphWriter<RegionInfo*> &GW) {
+    raw_ostream &O = GW.getOStream();
+    O << "\tcolorscheme = \"paired12\"\n";
+    printRegionCluster(RI->getTopLevelRegion(), GW, 4);
+  }
+};
+} //end namespace llvm
+
+namespace {
+
+struct RegionViewer
+  : public DOTGraphTraitsViewer<RegionInfo, false> {
+  static char ID;
+  RegionViewer() : DOTGraphTraitsViewer<RegionInfo, false>("reg", &ID){}
+};
+
+char RegionViewer::ID = 0;
+INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function",
+                true, true);
+
+struct RegionOnlyViewer
+  : public DOTGraphTraitsViewer<RegionInfo, true> {
+  static char ID;
+  RegionOnlyViewer() : DOTGraphTraitsViewer<RegionInfo, true>("regonly", &ID){}
+};
+
+char RegionOnlyViewer::ID = 0;
+INITIALIZE_PASS(RegionOnlyViewer, "view-regions-only",
+                "View regions of function (with no function bodies)",
+                true, true);
+
+struct RegionPrinter
+  : public DOTGraphTraitsPrinter<RegionInfo, false> {
+  static char ID;
+  RegionPrinter() :
+    DOTGraphTraitsPrinter<RegionInfo, false>("reg", &ID) {}
+};
+} //end anonymous namespace
+
+char RegionPrinter::ID = 0;
+INITIALIZE_PASS(RegionPrinter, "dot-regions",
+                "Print regions of function to 'dot' file", true, true);
+
+struct RegionOnlyPrinter
+  : public DOTGraphTraitsPrinter<RegionInfo, true> {
+  static char ID;
+  RegionOnlyPrinter() :
+    DOTGraphTraitsPrinter<RegionInfo, true>("reg", &ID) {}
+};
+
+char RegionOnlyPrinter::ID = 0;
+INITIALIZE_PASS(RegionOnlyPrinter, "dot-regions-only",
+                "Print regions of function to 'dot' file "
+                "(with no function bodies)",
+                true, true);
+
+FunctionPass* llvm::createRegionViewerPass() {
+  return new RegionViewer();
+}
+
+FunctionPass* llvm::createRegionOnlyViewerPass() {
+  return new RegionOnlyViewer();
+}
+
+FunctionPass* llvm::createRegionPrinterPass() {
+  return new RegionPrinter();
+}
+
+FunctionPass* llvm::createRegionOnlyPrinterPass() {
+  return new RegionOnlyPrinter();
+}
+
diff --git a/test/Analysis/RegionInfo/block_sort.ll b/test/Analysis/RegionInfo/block_sort.ll
new file mode 100644
index 0000000..faec45a
--- /dev/null
+++ b/test/Analysis/RegionInfo/block_sort.ll
@@ -0,0 +1,42 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats -analyze < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @BZ2_blockSort() nounwind {
+start:
+  br label %while
+
+while:
+  br label %while.body134.i.i
+
+while.body134.i.i:
+  br i1 1, label %end, label %w
+
+w:
+  br label %if.end140.i.i
+
+if.end140.i.i:
+  br i1 1, label %while.end186.i.i, label %if.end183.i.i
+
+if.end183.i.i:
+  br label %while.body134.i.i
+
+while.end186.i.i:
+  br label %while
+
+end:
+  ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] start => <Function Return>
+; CHECK: [1] while => end
+
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: start, while, while.body134.i.i, end, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
+; BBIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
+
+; RNIT: start, while => end, end,
+; RNIT: while, while.body134.i.i, w, if.end140.i.i, while.end186.i.i, if.end183.i.i,
diff --git a/test/Analysis/RegionInfo/cond_loop.ll b/test/Analysis/RegionInfo/cond_loop.ll
new file mode 100644
index 0000000..2ce57c3
--- /dev/null
+++ b/test/Analysis/RegionInfo/cond_loop.ll
@@ -0,0 +1,33 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+5:
+        br label %"0"
+
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	ret void
+3:
+	br i1 1, label %"1", label %"4"
+4:
+        br label %"0"
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 5 => <Function Return>
+; CHECK: [1] 0 => 2
+
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 5, 0, 1, 2, 3, 4,
+; BBIT: 0, 1, 3, 4,
+
+; RNIT: 5, 0 => 2, 2,
+; RNIT: 0, 1, 3, 4,
diff --git a/test/Analysis/RegionInfo/condition_complicated.ll b/test/Analysis/RegionInfo/condition_complicated.ll
new file mode 100644
index 0000000..7ca5c7c
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_complicated.ll
@@ -0,0 +1,60 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+end165:
+  br i1 1, label %false239, label %true181
+
+true181:
+  br i1 1, label %then187, label %else232
+
+then187:
+  br label %end265
+
+else232:
+  br i1 1, label %false239, label %then245
+
+false239:
+  br i1 1, label %then245, label %else259
+
+then245:
+  br i1 1, label %then251, label %end253
+
+then251:
+  br label %end253
+
+end253:
+  br label %end265
+
+else259:
+  br label %end265
+
+end265:
+  br i1 1, label %then291, label %end298
+
+then291:
+  br label %end298
+
+end298:
+  ret i8 1
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] end165 => <Function Return>
+; CHECK-NEXT: [1] end165 => end265
+; CHECK-NEXT: [2] then245 => end253
+; CHECK-NEXT: [1] end265 => end298
+
+; STAT: 4 region - The # of regions
+
+; BBIT: end165, false239, then245, then251, end253, end265, then291, end298, else259, true181, then187, else232,
+; BBIT: end165, false239, then245, then251, end253, else259, true181, then187, else232,
+; BBIT: then245, then251,
+; BBIT: end265, then291,
+
+; RNIT: end165 => end265, end265 => end298, end298,
+; RNIT: end165, false239, then245 => end253, end253, else259, true181, then187, else232,
+; RNIT: then245, then251,
+; RNIT: end265, then291,
diff --git a/test/Analysis/RegionInfo/condition_complicated_2.ll b/test/Analysis/RegionInfo/condition_complicated_2.ll
new file mode 100644
index 0000000..5fa940a
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_complicated_2.ll
@@ -0,0 +1,44 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc void @compress() nounwind {
+end33:
+  br i1 1, label %end124, label %lor.lhs.false95
+
+lor.lhs.false95:
+  br i1 1, label %then107, label %end172
+
+then107:
+  br i1 1, label %end124, label %then113
+
+then113:
+  br label %end124
+
+end124:
+  br label %exit
+
+end172:
+  br label %exit
+
+
+exit:
+  unreachable
+
+
+}
+; CHECK-NOT: =>
+; CHECK: [0] end33 => <Function Return>
+; CHECK-NEXT:      [1] end33 => exit
+; CHECK-NEXT:   [2] then107 => end124
+
+; STAT: 3 region - The # of regions
+
+; BBIT: end33, end124, exit, lor.lhs.false95, then107, then113, end172,
+; BBIT: end33, end124, lor.lhs.false95, then107, then113, end172,
+; BBIT: then107, then113,
+
+; RNIT: end33 => exit, exit,
+; RNIT: end33, end124, lor.lhs.false95, then107 => end124, end172,
+; RNIT: then107, then113,
diff --git a/test/Analysis/RegionInfo/condition_forward_edge.ll b/test/Analysis/RegionInfo/condition_forward_edge.ll
new file mode 100644
index 0000000..098c9b6
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_forward_edge.ll
@@ -0,0 +1,26 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"3"
+3:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 3
+
+; STAT: 2 region - The # of regions
+
+; BBIT: 0, 1, 2, 3,
+; BBIT: 1, 2,
+
+; RNIT: 0, 1 => 3, 3,
+; RNIT: 1, 2,
diff --git a/test/Analysis/RegionInfo/condition_same_exit.ll b/test/Analysis/RegionInfo/condition_same_exit.ll
new file mode 100644
index 0000000..1b88596
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_same_exit.ll
@@ -0,0 +1,31 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br i1 1, label %"1", label %"4"
+
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"4"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 0 => 4
+; CHECK-NEXT:   [2] 1 => 4
+; STAT: 3 region - The # of regions
+
+; BBIT: 0, 1, 2, 4, 3,
+; BBIT: 0, 1, 2, 3,
+; BBIT: 1, 2, 3,
+
+; RNIT: 0 => 4, 4,
+; RNIT: 0, 1 => 4,
+; RNIT: 1, 2, 3,
diff --git a/test/Analysis/RegionInfo/condition_simple.ll b/test/Analysis/RegionInfo/condition_simple.ll
new file mode 100644
index 0000000..19b154b
--- /dev/null
+++ b/test/Analysis/RegionInfo/condition_simple.ll
@@ -0,0 +1,28 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"4"
+3:
+	br label %"4"
+4:
+	ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 4
+; STAT: 2 region - The # of regions
+
+; BBIT: 0, 1, 2, 4, 3,
+; BBIT: 1, 2, 3,
+
+; RNIT: 0, 1 => 4, 4,
+; RNIT: 1, 2, 3,
diff --git a/test/Analysis/RegionInfo/dg.exp b/test/Analysis/RegionInfo/dg.exp
new file mode 100644
index 0000000..f200589
--- /dev/null
+++ b/test/Analysis/RegionInfo/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm.exp
+
+RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]]
diff --git a/test/Analysis/RegionInfo/exit_in_condition.ll b/test/Analysis/RegionInfo/exit_in_condition.ll
new file mode 100644
index 0000000..3b152d2
--- /dev/null
+++ b/test/Analysis/RegionInfo/exit_in_condition.ll
@@ -0,0 +1,38 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %body.i, label %if.end
+
+body.i:
+  br i1 1, label %end, label %if.end
+
+if.end:
+  br label %if.then64
+
+if.then64:
+  br label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, outer, body, body.i, end, if.end, if.then64,
+; BBIT: outer, body, body.i, if.end, if.then64,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer, body, body.i, if.end, if.then64,
diff --git a/test/Analysis/RegionInfo/infinite_loop.ll b/test/Analysis/RegionInfo/infinite_loop.ll
new file mode 100644
index 0000000..59cead4
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop.ll
@@ -0,0 +1,20 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"2"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 4
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
diff --git a/test/Analysis/RegionInfo/infinite_loop_2.ll b/test/Analysis/RegionInfo/infinite_loop_2.ll
new file mode 100644
index 0000000..80c69b7
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_2.ll
@@ -0,0 +1,36 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"1"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+        br label %"2"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK: [1] 1 => 3
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4,
+; BBIT: 1, 2, 5, 11, 6, 12,
+
+; RNIT: 0, 1 => 3, 3, 4,
+; RNIT: 1, 2, 5, 11, 6, 12,
diff --git a/test/Analysis/RegionInfo/infinite_loop_3.ll b/test/Analysis/RegionInfo/infinite_loop_3.ll
new file mode 100644
index 0000000..74ceafb
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_3.ll
@@ -0,0 +1,52 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"7"
+7:
+	br i1 1, label %"1", label %"8"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+        br label %"2"
+8:
+	br label %"9"
+9:
+	br i1 1, label %"13", label %"14"
+13:
+        br label %"10"
+14:
+        br label %"10"
+10:
+        br label %"8"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 3
+; CHECK-NEXT: [1] 7 => 1
+; STAT: 3 region - The # of regions
+; STAT: 2 region - The # of simple regions
+
+; BBIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14,
+; BBIT: 7, 8, 9, 13, 10, 14,
+; BBIT: 1, 2, 5, 11, 6, 12,
+
+; RNIT: 0, 7 => 1, 1 => 3, 3, 4,
+; RNIT: 7, 8, 9, 13, 10, 14,
+; RNIT: 1, 2, 5, 11, 6, 12,
diff --git a/test/Analysis/RegionInfo/infinite_loop_4.ll b/test/Analysis/RegionInfo/infinite_loop_4.ll
new file mode 100644
index 0000000..fd56af1
--- /dev/null
+++ b/test/Analysis/RegionInfo/infinite_loop_4.ll
@@ -0,0 +1,48 @@
+; RUN: opt -regions -analyze < %s 
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+	br label %"7"
+7:
+	br i1 1, label %"1", label %"8"
+1:
+	br i1 1, label %"2", label %"3"
+2:
+	br label %"5"
+5:
+	br i1 1, label %"11", label %"12"
+11:
+        br label %"6"
+12:
+        br label %"6"
+6:
+	br i1 1, label %"2", label %"10"
+8:
+	br label %"9"
+9:
+	br i1 1, label %"13", label %"14"
+13:
+        br label %"10"
+14:
+        br label %"10"
+10:
+        br label %"8"
+3:
+	br label %"4"
+4:
+	ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 7 => 3
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4,
+; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
+
+; RNIT: 0, 7 => 3, 3, 4,
+; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12,
diff --git a/test/Analysis/RegionInfo/loop_with_condition.ll b/test/Analysis/RegionInfo/loop_with_condition.ll
new file mode 100644
index 0000000..d1d6898
--- /dev/null
+++ b/test/Analysis/RegionInfo/loop_with_condition.ll
@@ -0,0 +1,46 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition() nounwind {
+0:
+        br label %"1"
+1:
+	br i1 1, label %"6", label %"2"
+2:
+	br i1 1, label %"3", label %"4"
+3:
+	br label %"5"
+4:
+	br label %"5"
+5:
+        br label %"8"
+8:
+        br i1 1, label %"7", label %"9"
+9:
+        br label %"2"
+7:
+        br label %"6"
+6:
+	ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 6
+; CHECK-NEXT:   [2] 2 => 7
+; CHECK-NEXT:     [3] 2 => 5
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 6, 2, 3, 5, 8, 7, 9, 4,
+; BBIT: 1, 2, 3, 5, 8, 7, 9, 4,
+; BBIT: 2, 3, 5, 8, 9, 4,
+; BBIT: 2, 3, 4,
+
+; RNIT: 0, 1 => 6, 6,
+; RNIT: 1, 2 => 7, 7,
+; RNIT: 2 => 5, 5, 8, 9,
+; RNIT: 2, 3, 4,
diff --git a/test/Analysis/RegionInfo/loops_1.ll b/test/Analysis/RegionInfo/loops_1.ll
new file mode 100644
index 0000000..d4bf3cc
--- /dev/null
+++ b/test/Analysis/RegionInfo/loops_1.ll
@@ -0,0 +1,40 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @loops_1() nounwind {
+entry:
+  br i1 1, label %outer , label %a
+
+a:
+  br label %body
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %land, label %if
+
+land:
+  br i1 1, label %exit, label %end
+
+exit:
+  br i1 1, label %if, label %end
+
+if:
+  br label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] entry => end
+; STAT: 2 region - The # of regions
+
+; BBIT: entry, outer, body, land, exit, if, end, a,
+; BBIT: entry, outer, body, land, exit, if, a,
+
+; RNIT: entry => end, end,
+; RNIT: entry, outer, body, land, exit, if, a,
diff --git a/test/Analysis/RegionInfo/loops_2.ll b/test/Analysis/RegionInfo/loops_2.ll
new file mode 100644
index 0000000..07aa7c3
--- /dev/null
+++ b/test/Analysis/RegionInfo/loops_2.ll
@@ -0,0 +1,49 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @meread_() nounwind {
+entry:
+  br label %bb23
+
+bb23:
+  br label %bb.i
+
+bb.i:                                             ; preds = %bb.i, %bb54
+  br label %pflini_.exit
+
+pflini_.exit:                                     ; preds = %bb.i
+  br label %bb58thread-split
+
+bb58thread-split:                                 ; preds = %bb64, %bb61, %pflini_.exit
+  br label %bb58
+
+bb58:                                             ; preds = %bb60, %bb58thread-split
+  br i1 1, label %bb59, label %bb23
+
+bb59:                                             ; preds = %bb58
+  switch i32 1, label %bb60 [
+    i32 1, label %l98
+  ]
+
+bb60:                                             ; preds = %bb59
+  br i1 1, label %bb61, label %bb58
+
+bb61:                                             ; preds = %bb60
+  br label %bb58thread-split
+
+l98:                                   ; preds = %bb69, %bb59
+  ret void
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK: [1] bb23 => l98
+; STAT: 2 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61, l98,
+; BBIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61,
+
+; RNIT: entry, bb23 => l98, l98,
+; RNIT: bb23, bb.i, pflini_.exit, bb58thread-split, bb58, bb59, bb60, bb61,
diff --git a/test/Analysis/RegionInfo/mix_1.ll b/test/Analysis/RegionInfo/mix_1.ll
new file mode 100644
index 0000000..829c157
--- /dev/null
+++ b/test/Analysis/RegionInfo/mix_1.ll
@@ -0,0 +1,69 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @a_linear_impl_fig_1() nounwind {
+0:
+
+	br i1 1, label %"1", label %"15"
+1:
+ 	switch i32 0, label %"2" [ i32 0, label %"3"
+                                  i32 1, label %"7"]
+2:
+	br label %"4"
+3:
+	br label %"5"
+4:
+	br label %"6"
+5:
+	br label %"6"
+6:
+	br label %"7"
+7:
+	br label %"15"
+15:
+	br label %"8"
+8:
+	br label %"16"
+16:
+        br label %"9"
+9:
+	br i1 1, label %"10", label %"11"
+11:
+	br i1 1, label %"13", label %"12"
+13:
+	br label %"14"
+12:
+	br label %"14"
+14:
+	br label %"8"
+10:
+        br label %"17"
+17:
+        br label %"18"
+18:
+        ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 0 => 15
+; CHECK-NEXT:  [2] 1 => 7
+; CHECK-NEXT: [1] 8 => 10
+; CHECK-NEXT:  [2] 11 => 14
+; STAT: 5 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 4, 6, 7, 15, 8, 16, 9, 10, 17, 18, 11, 13, 14, 12, 3, 5,
+; BBIT: 0, 1, 2, 4, 6, 7, 3, 5,
+; BBIT: 1, 2, 4, 6, 3, 5,
+; BBIT: 8, 16, 9, 11, 13, 14, 12,
+; BBIT: 11, 13, 12,
+
+; RNIT: 0 => 15, 15, 8 => 10, 10, 17, 18,
+; RNIT: 0, 1 => 7, 7,
+; RNIT: 1, 2, 4, 6, 3, 5,
+; RNIT: 8, 16, 9, 11 => 14, 14,
+; RNIT: 11, 13, 12,
diff --git a/test/Analysis/RegionInfo/multiple_exiting_edge.ll b/test/Analysis/RegionInfo/multiple_exiting_edge.ll
new file mode 100644
index 0000000..7bc0e46
--- /dev/null
+++ b/test/Analysis/RegionInfo/multiple_exiting_edge.ll
@@ -0,0 +1,38 @@
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @normal_condition_0() nounwind {
+bb38:                                             ; preds = %bb34, %bb34, %bb37
+  switch i32 undef, label %bb42 [
+    i32 67, label %bb42
+    i32 90, label %bb41
+  ]
+bb41:                                             ; preds = %bb38
+  br label %bb42
+bb42:                                             ; preds = %bb38, %bb38, %bb41
+  ret void
+}
+
+; BBIT: bb38, bb42, bb41,
+; BBIT: bb38, bb41,
+
+; RNIT: bb38 => bb42, bb42,
+; RNIT: bb38, bb41,
+
+define void @normal_condition_1() nounwind {
+bb38:                                             ; preds = %bb34, %bb34, %bb37
+  switch i32 undef, label %bb41 [
+    i32 67, label %bb42
+    i32 90, label %bb42
+  ]
+bb41:                                             ; preds = %bb38
+  br label %bb42
+bb42:                                             ; preds = %bb38, %bb38, %bb41
+  ret void
+}
+
+; BBIT: bb38, bb41, bb42,
+; BBIT: bb38, bb41,
+
+; RNIT: bb38 => bb42, bb42,
+; RNIT: bb38, bb41,
diff --git a/test/Analysis/RegionInfo/nested_loops.ll b/test/Analysis/RegionInfo/nested_loops.ll
new file mode 100644
index 0000000..9d8c455
--- /dev/null
+++ b/test/Analysis/RegionInfo/nested_loops.ll
@@ -0,0 +1,33 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %exit172, label %end
+
+exit172:
+  br i1 1, label %end, label %outer
+
+end:
+  ret i8 1
+}
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+
+; STAT: 2 region - The # of regions
+
+; BBIT: entry, outer, body, exit172, end,
+; BBIT: outer, body, exit172,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer, body, exit172,
diff --git a/test/Analysis/RegionInfo/next.ll b/test/Analysis/RegionInfo/next.ll
new file mode 100644
index 0000000..d986387
--- /dev/null
+++ b/test/Analysis/RegionInfo/next.ll
@@ -0,0 +1,49 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @MAIN__() nounwind {
+entry:
+  br label %__label_002001.outer
+
+__label_002001.outer:                             ; preds = %bb236, %bb92
+  br label %__label_002001
+
+__label_002001:                                   ; preds = %bb229, %__label_002001.outer
+  br i1  1, label %bb93, label %__label_000020
+
+bb93:                                             ; preds = %__label_002001
+  br i1  1, label %__label_000020, label %bb197
+
+bb197:                                            ; preds = %bb193
+  br i1  1, label %bb229, label %bb224
+
+bb224:                                            ; preds = %bb223, %bb227
+  br i1  1, label %bb229, label %bb224
+
+bb229:                                            ; preds = %bb227, %bb223
+  br i1  1, label %__label_002001, label %__label_002001.outer
+
+__label_000020:                                   ; preds = %__label_002001, %bb194
+  ret void
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT:  [1] __label_002001.outer => __label_000020
+; CHECK-NEXT;      [2] bb197 => bb229
+; CHECK-NEXT;            [3] bb224 => bb229
+
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, __label_002001.outer, __label_002001, bb93, __label_000020, bb197, bb229, bb224,
+; BBIT: __label_002001.outer, __label_002001, bb93, bb197, bb229, bb224,
+; BBIT: bb197, bb224,
+; BBIT: bb224,
+
+; RNIT: entry, __label_002001.outer => __label_000020, __label_000020,
+; RNIT: __label_002001.outer, __label_002001, bb93, bb197 => bb229, bb229,
+; RNIT: bb197, bb224 => bb229,
+; RNIT: bb224,
diff --git a/test/Analysis/RegionInfo/paper.ll b/test/Analysis/RegionInfo/paper.ll
new file mode 100644
index 0000000..00b544b
--- /dev/null
+++ b/test/Analysis/RegionInfo/paper.ll
@@ -0,0 +1,55 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define void @a_linear_impl_fig_1() nounwind {
+0:
+        br label %"1"
+1:
+	br label %"2"
+2:
+	br label %"3"
+3:
+	br i1 1, label %"13", label %"4"
+4:
+	br i1 1, label %"5", label %"1"
+5:
+	br i1 1, label %"8", label %"6"
+6:
+	br i1 1, label %"7", label %"4"
+7:
+	ret void
+8:
+	br i1 1, label %"9", label %"1"
+9:
+	br label %"10"
+10:
+	br i1 1, label %"12", label %"11"
+11:
+	br i1 1, label %"9", label %"8"
+13:
+	br i1 1, label %"2", label %"1"
+12:
+ 	switch i32 0, label %"1" [ i32 0, label %"9"
+                                  i32 1, label %"8"]
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] 0 => <Function Return>
+; CHECK-NEXT: [1] 1 => 7
+; CHECK-NEXT:   [2] 1 => 4
+; CHECK-NEXT:   [2] 8 => 1
+
+; STAT: 4 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: 0, 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6, 7,
+; BBIT: 1, 2, 3, 13, 4, 5, 8, 9, 10, 12, 11, 6,
+; BBIT: 1, 2, 3, 13,
+; BBIT: 8, 9, 10, 12, 11,
+
+; RNIT: 0, 1 => 7, 7,
+; RNIT: 1 => 4, 4, 5, 8 => 1, 6,
+; RNIT: 1, 2, 3, 13,
+; RNIT: 8, 9, 10, 12, 11,
diff --git a/test/Analysis/RegionInfo/two_loops_same_header.ll b/test/Analysis/RegionInfo/two_loops_same_header.ll
new file mode 100644
index 0000000..a97182b
--- /dev/null
+++ b/test/Analysis/RegionInfo/two_loops_same_header.ll
@@ -0,0 +1,46 @@
+; RUN: opt -regions -analyze < %s | FileCheck %s
+; RUN: opt -regions -stats < %s |& FileCheck -check-prefix=STAT %s
+; RUN: opt -regions -print-region-style=bb  -analyze < %s |& FileCheck -check-prefix=BBIT %s
+; RUN: opt -regions -print-region-style=rn  -analyze < %s |& FileCheck -check-prefix=RNIT %s
+
+define internal fastcc zeroext i8 @handle_compress() nounwind {
+entry:
+  br label %outer
+
+outer:
+  br label %body
+
+body:
+  br i1 1, label %else, label %true77
+
+true77:
+  br i1 1, label %then83, label %else
+
+then83:
+  br label %outer
+
+else:
+  br label %else106
+
+else106:
+  br i1 1, label %end, label %outer
+
+end:
+  ret i8 1
+}
+
+; CHECK-NOT: =>
+; CHECK: [0] entry => <Function Return>
+; CHECK-NEXT: [1] outer => end
+; CHECK-NEXT:   [2] outer => else
+
+; STAT: 3 region - The # of regions
+; STAT: 1 region - The # of simple regions
+
+; BBIT: entry, outer, body, else, else106, end, true77, then83,
+; BBIT: outer, body, else, else106, true77, then83,
+; BBIT: outer, body, true77, then83,
+
+; RNIT: entry, outer => end, end,
+; RNIT: outer => else, else, else106,
+; RNIT: outer, body, true77, then83,