Support SCoPs with multiple exit edges

Regions that have multiple exit edges are very common. A simple if condition
yields e.g. such a region:

        if
      /   \
  then     else
      \   /
      after

Region: if -> after

This regions contains the bbs 'if', 'then', 'else', but not 'after'. It has
two exit edges 'then' -> 'after' and 'else' -> 'after'.

Previously we scheduled the RegionSimplify pass to translate such regions into
simple regions. With this patch, we now support them natively.

Contributed-by: Star Tan <tanmx_star@yeah.net>
llvm-svn: 179159

3 files changed, 26 insertions, 5 deletions

diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index d67f2d1730a..f0bbf3d7b6a 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -554,9 +554,9 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock()))
     INVALID(Other, "Region containing entry block of function is invalid!");
 
-  // Only a simple region is allowed.
-  if (!R.isSimple())
-    INVALID(SimpleRegion, "Region not simple: " << R.getNameStr());
+  // Only regions that have a single entry are allowed.
+  if (!R.getEnteringBlock())
+    INVALID(SimpleRegion, "Region has multiple entries: " << R.getNameStr());
 
   if (!isValidExit(Context))
     return false;
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
index e3e5621693e..664638c00f6 100644
--- a/polly/lib/CodeGen/CodeGeneration.cpp
+++ b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -34,6 +34,7 @@
 #include "polly/CodeGen/PTXGenerator.h"
 #include "polly/CodeGen/Utils.h"
 #include "polly/Support/GICHelper.h"
+#include "polly/Support/ScopHelper.h"
 
 #include "llvm/IR/Module.h"
 #include "llvm/ADT/SetVector.h"
@@ -983,7 +984,16 @@ public:
   bool runOnScop(Scop &S) {
     ParallelLoops.clear();
 
-    assert(S.getRegion().isSimple() && "Only simple regions are supported");
+    Region &R = S.getRegion();
+
+    assert (!R.isTopLevelRegion() && "Top level regions are not supported");
+    assert (R.getEnteringBlock() && "Only support regions with a single entry");
+
+    if (!R.getExitingBlock()) {
+      BasicBlock *newExit = createSingleExitEdge(&R, this);
+      for (Region::const_iterator RI = R.begin(), RE = R.end(); RI != RE; ++RI)
+        (*RI)->replaceExitRecursive(newExit);
+    }
 
     BasicBlock *StartBlock = executeScopConditionally(S, this);
 
diff --git a/polly/lib/CodeGen/IslCodeGeneration.cpp b/polly/lib/CodeGen/IslCodeGeneration.cpp
index 6db09258a62..6e0d225ce16 100644
--- a/polly/lib/CodeGen/IslCodeGeneration.cpp
+++ b/polly/lib/CodeGen/IslCodeGeneration.cpp
@@ -30,6 +30,7 @@
 #include "polly/CodeGen/LoopGenerators.h"
 #include "polly/CodeGen/Utils.h"
 #include "polly/Support/GICHelper.h"
+#include "polly/Support/ScopHelper.h"
 
 #include "llvm/IR/Module.h"
 #include "llvm/Analysis/LoopInfo.h"
@@ -1024,7 +1025,17 @@ public:
 
   bool runOnScop(Scop &S) {
     IslAstInfo &AstInfo = getAnalysis<IslAstInfo>();
-    assert(S.getRegion().isSimple() && "Only simple regions are supported");
+
+    Region &R = S.getRegion();
+
+    assert (!R.isTopLevelRegion() && "Top level regions are not supported");
+    assert (R.getEnteringBlock() && "Only support regions with a single entry");
+
+    if (!R.getExitingBlock()) {
+      BasicBlock *newExit = createSingleExitEdge(&R, this);
+      for (Region::const_iterator RI = R.begin(), RE = R.end(); RI != RE; ++RI)
+        (*RI)->replaceExitRecursive(newExit);
+    }
 
     BasicBlock *StartBlock = executeScopConditionally(S, this);
     isl_ast_node *Ast = AstInfo.getAst();