Fix non-affine region dominance of implicitely stored values

[Meinersbur]

Summary

After loop versioning, a dominance check of a non-affine subregion's
exit node causes the dominance check to always fail on any block in the
subregion if it shares the same exit block with the scop. The
subregion's exit block has become polly_merge_new_and_old, which also
receives the control flow of the generated code. This would cause that
any value for implicit stores is assumed to be not from the scop.

We check dominance with the generated exit node instead.

This fixes llvm.org/PR25438

lib/CodeGen/BlockGenerators.cpp

while (!Blocks.empty()) {
     for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
       addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
     IncompletePHINodeMap[BB].clear();
 
     // And continue with new successors inside the region.
     for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
       if (R->contains(*SI) && SeenBlocks.insert(*SI).second)
         Blocks.push_back(*SI);
-
-    // Remember value in case it is visible after this subregion.
-    if (DT.dominates(BB, R->getExit()))
-      ValueMap.insert(RegionMap.begin(), RegionMap.end());
   }
 
   // Now create a new dedicated region exit block and add it to the region map.
   BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                       &*Builder.GetInsertPoint(), &DT, &LI);
   ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
   BlockMap[R->getExit()] = ExitBBCopy;
 
   repairDominance(R->getExit(), ExitBBCopy);
 
+  // Remember value in case it is visible after this subregion. Only values that
+  // dominate the exit node can be visible.
+  for (auto &Pair : RegionMaps)
+    if (DT.properlyDominates(Pair.first, ExitBBCopy))
+      ValueMap.insert(Pair.second.begin(), Pair.second.end());
+
   // 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.
   for (BasicBlock *BB : SeenBlocks) {
 
     BasicBlock *BBCopy = BlockMap[BB];
     TerminatorInst *TI = BB->getTerminator();
     if (isa<UnreachableInst>(TI)) {
       while (!BBCopy->empty())

test/Isl/CodeGen/non-affine-region-implicit-store.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; llvm.org/PR25438
+; After loop versioning, a dominance check of a non-affine subregion's exit node
+; causes the dominance check to always fail any block in the scop. The
+; subregion's exit block has become polly_merge_new_and_old, which also receives
+; the control flow of the generated code. This would cause that any value for
+; implicit stores is assumed to be not from the scop.
+;
+; This checks that the stored value is indeed from the generated code.
+;
+; CHECK-LABEL: polly.stmt.do.body.entry:
+; CHECK:        a.phiops.reload = load i32, i32* %a.phiops
+;
+; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
+; CHECK:         store i32 %a.phiops.reload, i32* %a.s2a
+
+define void @func() {
+entry:
+  br label %while.body
+
+while.body:
+  br label %do.body
+
+do.body:
+  %a = phi i32 [ undef, %while.body ], [ %b, %end_b ]
+  %cond = or i1 undef, undef
+  br i1 %cond, label %end_a, label %if_a
+
+if_a:
+  br label %end_a
+
+end_a:
+  br i1 undef, label %if_b, label %end_b
+
+if_b:
+  br label %end_b
+
+end_b:
+  %b = phi i32 [ undef, %if_b ], [ %a, %end_a ]
+  br i1 false, label %do.body, label %do.end
+
+do.end:
+  br label %return
+
+return:
+  ret void
+}