BlockGenerator: Be less agressive with deleting dead instructions

We now only delete trivially dead instructions in the BB we copy (copyBB), but
not in any other BB.  Only for copyBB we know that there will _never_ be any
future uses of instructions that have no use after copyBB has been generated.
Other instructions in the AST that have been generated by IslNodeBuilder may
look dead at the moment, but may possibly still be referenced by GlobalMaps. If
we delete them now, later uses would break surprisingly.

We do not have a test case that breaks due to us deleting too many instructions.
This issue was found by inspection.

llvm-svn: 248688

3 files changed, 46 insertions, 8 deletions

diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp
index 58c60acb99f..606478b7ea5 100644
--- a/polly/lib/CodeGen/BlockGenerators.cpp
+++ b/polly/lib/CodeGen/BlockGenerators.cpp
@@ -285,6 +285,28 @@ void BlockGenerator::copyInstruction(ScopStmt &Stmt, const Instruction *Inst,
   copyInstScalar(Stmt, Inst, BBMap, LTS);
 }
 
+/// @brief Remove trivially dead instructions from BB
+///
+/// This function drops trivially dead instructions from a basic block. It
+/// on purpose does _not_ recurse into other BBs even if the deletion of
+/// instructions in this basic block can make instructions in other basic blocks
+/// triviall dead.
+static void simplifyInstsInBlockOnly(BasicBlock *BB) {
+  auto BI = --BB->end(), BE = BB->begin();
+  bool Exit = false;
+  while (!Exit) {
+    auto ToRemove = BI;
+    if (BI != BE)
+      BI--;
+    else
+      Exit = true;
+
+    if (!isInstructionTriviallyDead(ToRemove))
+      continue;
+    ToRemove->eraseFromParent();
+  }
+}
+
 void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                               isl_id_to_ast_expr *NewAccesses) {
   assert(Stmt.isBlockStmt() &&
@@ -296,7 +318,13 @@ void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
   copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
 
   auto CopyBB = Builder.GetInsertBlock();
-  SimplifyInstructionsInBlock(CopyBB, nullptr);
+  // Delete trivially dead instructions in CopyBB, but not in any other BB.
+  // Only for copyBB we know that there will _never_ be any future uses of
+  // instructions that have no use after copyBB has finished. Other instructions
+  // in the AST that have been generated by IslNodeBuilder may look dead at
+  // the moment, but may possibly still be referenced by GlobalMaps. If we
+  // delete them now, later uses would break surprisingly.
+  simplifyInstsInBlockOnly(CopyBB);
   Builder.SetInsertPoint(CopyBB->getTerminator());
 }
 
@@ -1090,8 +1118,14 @@ void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
     LTS[L] = SE.getUnknown(LoopPHI);
   }
 
+  // Delete trivially dead instructions in CopyBB, but not in any other BB.
+  // Only for copyBB we know that there will _never_ be any future uses of
+  // instructions that have no use after copyBB has finished. Other instructions
+  // in the AST that have been generated by IslNodeBuilder may look dead at
+  // the moment, but may possibly still be referenced by GlobalMaps. If we
+  // delete them now, later uses would break surprisingly.
   for (auto *BB : SeenBlocks)
-    SimplifyInstructionsInBlock(BlockMap[BB], nullptr);
+    simplifyInstsInBlockOnly(BlockMap[BB]);
 
   // Reset the old insert point for the build.
   Builder.SetInsertPoint(ExitBBCopy->begin());
diff --git a/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll b/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
index aaf98a6fc58..ad465eda931 100644
--- a/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
@@ -40,4 +40,5 @@ for.end:                                          ; preds = %for.cond
 }
 
 ; CHECK: %polly.access.cast.A = bitcast [100 x i32] addrspace(5)* %A to i32 addrspace(5)*
-; CHECK: %tmp2_p_scalar_ = load i32, i32 addrspace(5)* %polly.access.cast.A, align 4, !alias.scope !0, !noalias !2
+; CHECK: %polly.access.A = getelementptr i32, i32 addrspace(5)* %polly.access.cast.A, i64 0
+; CHECK: %tmp2_p_scalar_ = load i32, i32 addrspace(5)* %polly.access.A, align 4, !alias.scope !0, !noalias !2
diff --git a/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll b/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll
index 45094436367..61913cb09ef 100644
--- a/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll
+++ b/polly/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll
@@ -13,9 +13,12 @@ loop:
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
-; CHECK-NEXT:    store float 3.000000e+00, float* %merge.phiops
-; CHECK-NEXT:    store float 3.000000e+00, float* %val1.s2a
-; CHECK-NEXT:    store float 3.000000e+00, float* %val2.s2a
+; CHECK-NEXT: %p_val0 = fadd float 1.000000e+00, 2.000000e+00
+; CHECK-NEXT: %p_val1 = fadd float 1.000000e+00, 2.000000e+00
+; CHECK-NEXT: %p_val2 = fadd float 1.000000e+00, 2.000000e+00
+; CHECK-NEXT: store float %p_val0, float* %merge.phiops
+; CHECK-NEXT: store float %p_val1, float* %val1.s2a
+; CHECK-NEXT: store float %p_val2, float* %val2.s2a
 
 ; FIXME -> The last two writes are not really needed and can be dropped if the
 ;          incoming block of the PHI and the value that is used share the same
@@ -25,13 +28,13 @@ branch1:
   br i1 %cond1, label %branch2, label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch1:
-; CHECK-NEXT:    store float 3.000000e+00, float* %merge.phiops
+; CHECK-NEXT:    store float %p_val1, float* %merge.phiops
 
 branch2:
   br label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch2:
-; CHECK-NEXT:    store float 3.000000e+00, float* %merge.phiops
+; CHECK-NEXT:    store float %p_val2, float* %merge.phiops
 
 backedge:
   %merge = phi float [%val0, %loop], [%val1, %branch1], [%val2, %branch2]