Fix DomTree preservation for generated subregions.

The generated dedicated subregion exit block was assumed to have the same
dominance relation as the original exit block. This is incorrect if the exit
block receives other edges than only from the subregion, which results in that
e.g. the subregion's entry block does not dominate the exit block.

llvm-svn: 261865

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
+}