RegionInfo: Add getMaxRegionExit()

getMaxRegionExit returns the exit of the maximal refined region starting
at a specific basic block.

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

2 files changed, 45 insertions, 0 deletions

diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
index a54509f5e8..7a2670f2c0 100644
--- a/include/llvm/Analysis/RegionInfo.h
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -572,6 +572,12 @@ public:
   /// region containing BB.
   Region *operator[](BasicBlock *BB) const;
 
+  /// @brief Return the exit of the maximal refined region, that starts at a
+  /// BasicBlock.
+  ///
+  /// @param BB The BasicBlock the refined region starts.
+  BasicBlock *getMaxRegionExit(BasicBlock *BB) const;
+
   /// @brief Find the smallest region that contains two regions.
   ///
   /// @param A The first region.
diff --git a/lib/Analysis/RegionInfo.cpp b/lib/Analysis/RegionInfo.cpp
index 0ea92cb012..ac660e72f0 100644
--- a/lib/Analysis/RegionInfo.cpp
+++ b/lib/Analysis/RegionInfo.cpp
@@ -651,6 +651,45 @@ Region *RegionInfo::operator[](BasicBlock *BB) const {
   return getRegionFor(BB);
 }
 
+
+BasicBlock *RegionInfo::getMaxRegionExit(BasicBlock *BB) const {
+  BasicBlock *Exit = NULL;
+
+  while (true) {
+    // Get largest region that starts at BB.
+    Region *R = getRegionFor(BB);
+    while (R && R->getParent() && R->getParent()->getEntry() == BB)
+      R = R->getParent();
+
+    // Get the single exit of BB.
+    if (R && R->getEntry() == BB)
+      Exit = R->getExit();
+    else if (++succ_begin(BB) == succ_end(BB))
+      Exit = *succ_begin(BB);
+    else // No single exit exists.
+      return Exit;
+
+    // Get largest region that starts at Exit.
+    Region *ExitR = getRegionFor(Exit);
+    while (ExitR && ExitR->getParent()
+           && ExitR->getParent()->getEntry() == Exit)
+      ExitR = ExitR->getParent();
+
+    for (pred_iterator PI = pred_begin(Exit), PE = pred_end(Exit); PI != PE;
+         ++PI)
+      if (!R->contains(*PI) && !ExitR->contains(*PI))
+        break;
+
+    // This stops infinite cycles.
+    if (DT->dominates(Exit, BB))
+      break;
+
+    BB = Exit;
+  }
+
+  return Exit;
+}
+
 Region*
 RegionInfo::getCommonRegion(Region *A, Region *B) const {
   assert (A && B && "One of the Regions is NULL");