2 files changed, 94 insertions, 5 deletions

diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp
index d1c569f1682..2178558685a 100644
--- a/polly/lib/CodeGen/BlockGenerators.cpp
+++ b/polly/lib/CodeGen/BlockGenerators.cpp
@@ -1027,6 +1027,50 @@ BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
   return BBCopyIDom;
 }
 
+// This is to determine whether an llvm::Value (defined in @p BB) is usable when
+// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
+// does not work in cases where the exit block has edges from outside the
+// region. In that case the llvm::Value would never be usable in in the exit
+// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
+// for the subregion's exiting edges only. We need to determine whether an
+// llvm::Value is usable in there. We do this by checking whether it dominates
+// all exiting blocks individually.
+static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
+                                      BasicBlock *BB) {
+  for (auto ExitingBB : predecessors(R->getExit())) {
+    // Check for non-subregion incoming edges.
+    if (!R->contains(ExitingBB))
+      continue;
+
+    if (!DT.dominates(BB, ExitingBB))
+      return false;
+  }
+
+  return true;
+}
+
+// Find the direct dominator of the subregion's exit block if the subregion was
+// simplified.
+static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
+  BasicBlock *Common = nullptr;
+  for (auto ExitingBB : predecessors(R->getExit())) {
+    // Check for non-subregion incoming edges.
+    if (!R->contains(ExitingBB))
+      continue;
+
+    // First exiting edge.
+    if (!Common) {
+      Common = ExitingBB;
+      continue;
+    }
+
+    Common = DT.findNearestCommonDominator(Common, ExitingBB);
+  }
+
+  assert(Common && R->contains(Common));
+  return Common;
+}
+
 void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                isl_id_to_ast_expr *IdToAstExp) {
   assert(Stmt.isRegionStmt() &&
@@ -1119,7 +1163,7 @@ void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
         Blocks.push_back(*SI);
 
     // Remember value in case it is visible after this subregion.
-    if (DT.dominates(BB, ExitBB))
+    if (isDominatingSubregionExit(DT, R, BB))
       ValueMap.insert(RegionMap.begin(), RegionMap.end());
   }
 
@@ -1129,10 +1173,10 @@ void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
   BlockMap[R->getExit()] = ExitBBCopy;
 
-  if (ExitBB == R->getExit())
-    repairDominance(ExitBB, ExitBBCopy);
-  else
-    DT.changeImmediateDominator(ExitBBCopy, BlockMap.lookup(ExitBB));
+  BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R));
+  assert(ExitDomBBCopy && "Common exit dominator must be within region; at "
+                          "least the entry node must match");
+  DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
 
   // As the block generator doesn't handle control flow we need to add the
   // region control flow by hand after all blocks have been copied.
diff --git a/polly/test/Isl/CodeGen/region_exiting-domtree.ll b/polly/test/Isl/CodeGen/region_exiting-domtree.ll
new file mode 100644
index 00000000000..cef52062dc8
--- /dev/null
+++ b/polly/test/Isl/CodeGen/region_exiting-domtree.ll
@@ -0,0 +1,45 @@
+; RUN: opt %loadPolly -polly-codegen -verify-dom-info -analyze < %s
+
+; Verify that the DominatorTree is preserved correctly for the inserted
+; %polly.stmt.exit.exit block, which serves as new exit block for the generated
+; subregion. In particulat, it must be dominated by %polly.stmt.subregion.enter,
+; the generated subregion's entry block.
+
+define void @func(i32 %n, i32* noalias nonnull %A) {
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [0, %entry], [%i.inc, %loop.inc]
+  %i.cmp = icmp slt i32 %i, %n
+  br i1 %i.cmp, label %body, label %return
+
+body:
+  %skipcond = icmp slt i32 %i, 5
+  br i1 %skipcond, label %subregion.enter, label %subregion.skip
+
+subregion.skip:
+  br label %exit
+
+subregion.enter:
+  %sqr = mul i32 %i, %i
+  %cond = icmp eq i32 %sqr, 0
+  store i32 %i, i32* %A
+  br i1 %cond, label %subregion.true, label %subregion.false
+
+subregion.true:
+  br label %exit
+
+subregion.false:
+  br label %exit
+
+exit:
+  br label %loop.inc
+
+loop.inc:
+  %i.inc = add nuw nsw i32 %i, 1
+  br label %loop
+
+return:
+  ret void
+}