Support SCoPs with multiple entry edges.

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

  if
 /   \
then  else
 \   /
for_region

This for_region contains two entry edges 'then' -> 'for_region' and 'else' -> 'for_region'.

Previously we scheduled the RegionSimplify pass to translate such regions into
simple regions. With this patch, we now support them natively when the region is
in -loop-simplify form, which means the entry block should not be a loop header.

Contributed by:  Star Tan <tanmx_star@yeah.net>

llvm-svn: 179586

1 files changed, 27 insertions, 0 deletions

diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index 904492a2814..118bd64c080 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/ScopHelper.h"
+#include "polly/ScopInfo.h"
 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
@@ -86,6 +87,32 @@ BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
   return SplitBlockPredecessors(BB, Preds, ".region", P);
 }
 
+void polly::simplifyRegion(Scop *S, Pass *P){
+  Region *R = &S->getRegion();
+
+  // Create single entry edge if the region has multiple entry edges.
+  if (!R->getEnteringBlock()){
+    BasicBlock *OldEntry = R->getEntry();
+    BasicBlock *NewEntry = SplitBlock (OldEntry, OldEntry->begin(), P);
+
+    for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
+      if ((*SI)->getBasicBlock() == OldEntry) {
+        (*SI)->setBasicBlock(NewEntry);
+        break;
+      }
+
+    R->replaceEntryRecursive(NewEntry);
+  }
+
+  // Create single exit edge if the region has multiple exit edges.
+  if (!R->getExitingBlock()) {
+    BasicBlock *NewExit = createSingleExitEdge(R, P);
+
+    for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI)
+      (*RI)->replaceExitRecursive(NewExit);
+  }
+}
+
 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   // Find first non-alloca instruction. Every basic block has a non-alloc
   // instruction, as every well formed basic block has a terminator.