[Polly] BlockGenerator: Generate synthesisable instructions only on-demand

[grosser]

Summary

Instructions which we can synthesis from a SCEV expression are not generated
directly, but only when they are used as an operand of another instruction. This
avoids generating unnecessary instruction and works more reliably than first
inserting them and then deleting them later on.

Suggested-by: Johannes Doerfert <[e-mail]>

[jdoerfert]

LGTM.

polly/trunk/lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::copyInstruction(ScopStmt &Stmt, const Instruction *Inst,
   // Terminator instructions control the control flow. They are explicitly
   // expressed in the clast and do not need to be copied.
   if (Inst->isTerminator())
     return;
 
   Loop *L = getLoopForInst(Inst);
   if ((Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
       canSynthesize(Inst, &LI, &SE, &Stmt.getParent()->getRegion())) {
-    Value *NewValue = getNewValue(Stmt, Inst, BBMap, LTS, L);
-    BBMap[Inst] = NewValue;
+    // Synthesizable statements will be generated on-demand.
     return;
   }
 
   if (const LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
     Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
     // Compute NewLoad before its insertion in BBMap to make the insertion
     // deterministic.
     BBMap[Load] = NewLoad;
void BlockGenerator::copyInstruction(ScopStmt &Stmt, const Instruction *Inst,
   // Skip some special intrinsics for which we do not adjust the semantics to
   // the new schedule. All others are handled like every other instruction.
   if (isIgnoredIntrinsic(Inst))
     return;
 
   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() &&
          "Only block statements can be copied by the block generator");
 
   ValueMapT BBMap;
 
   BasicBlock *BB = Stmt.getBasicBlock();
   copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
-
-  auto CopyBB = Builder.GetInsertBlock();
-  // 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());
 }
 
 BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
   BasicBlock *CopyBB =
       SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI);
   CopyBB->setName("polly.stmt." + BB->getName());
   return CopyBB;
 }
for (BasicBlock *BB : SeenBlocks) {
 
     for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
       if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
         LoopPHI->addIncoming(NullVal, PredBBCopy);
 
     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)
-    simplifyInstsInBlockOnly(BlockMap[BB]);
-
   // Reset the old insert point for the build.
   Builder.SetInsertPoint(ExitBBCopy->begin());
 }
 
 void RegionGenerator::generateScalarLoads(ScopStmt &Stmt,
                                           const Instruction *Inst,
                                           ValueMapT &BBMap) {
 

polly/trunk/test/Isl/CodeGen/OpenMP/new_multidim_access.ll

 ; CHECK:    new: [n, m] -> { Stmt_bb4[i0, i1] -> MemRef_A[i0, 43 + i1] };
 
 ; IR: %polly.access.mul.polly.subfunc.arg.A = mul i64 %polly.indvar, %polly.subfunc.arg.m
 ; IR: %6 = add nsw i64 %polly.indvar5, 13
 ; IR: %polly.access.add.polly.subfunc.arg.A = add i64 %polly.access.mul.polly.subfunc.arg.A, %6
 ; IR: %polly.access.polly.subfunc.arg.A = getelementptr float, float* %polly.subfunc.arg.A, i64 %polly.access.add.polly.subfunc.arg.A
 ; IR: %tmp10_p_scalar_ = load float, float* %polly.access.polly.subfunc.arg.A, align 4, !alias.scope !0, !noalias !2, !llvm.mem.parallel_loop_access !3
 
-; IR: %polly.access.mul.polly.subfunc.arg.A9 = mul i64 %polly.indvar, %polly.subfunc.arg.m
+; IR: %polly.access.mul.polly.subfunc.arg.A8 = mul i64 %polly.indvar, %polly.subfunc.arg.m
 ; IR: %7 = add nsw i64 %polly.indvar5, 43
-; IR: %polly.access.add.polly.subfunc.arg.A10 = add i64 %polly.access.mul.polly.subfunc.arg.A9, %7
-; IR: %polly.access.polly.subfunc.arg.A11 = getelementptr float, float* %polly.subfunc.arg.A, i64 %polly.access.add.polly.subfunc.arg.A10
-; IR: store float %p_tmp11, float* %polly.access.polly.subfunc.arg.A11, align 4, !alias.scope !0, !noalias !2, !llvm.mem.parallel_
+; IR: %polly.access.add.polly.subfunc.arg.A9 = add i64 %polly.access.mul.polly.subfunc.arg.A8, %7
+; IR: %polly.access.polly.subfunc.arg.A10 = getelementptr float, float* %polly.subfunc.arg.A, i64 %polly.access.add.polly.subfunc.arg.A9
+; IR: store float %p_tmp11, float* %polly.access.polly.subfunc.arg.A10, align 4, !alias.scope !0, !noalias !2, !llvm.mem.parallel_
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @new_multidim_access(i64 %n, i64 %m, float* %A) {
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb15, %bb
   %i.0 = phi i64 [ 0, %bb ], [ %tmp16, %bb15 ]

polly/trunk/test/Isl/CodeGen/exprModDiv.ll

 ; A[floor(i / 127)]
 ;
 ; Note: without the floor, we would create a map i -> i/127, which only contains
 ;       values of i that are divisible by 127. All other values of i would not
 ;       be mapped to any value. However, to generate correct code we require
 ;       each value of i to indeed be mapped to a value.
 ;
 ; CHECK:  %pexp.p_div_q = udiv i64 %polly.indvar, 127
-; CHECK:  %polly.access.B8 = getelementptr float, float* %B, i64 %pexp.p_div_q
+; CHECK:  %polly.access.B7 = getelementptr float, float* %B, i64 %pexp.p_div_q
 
 ; #define floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 ; A[p + 127 * floord(-p - 1, 127) + 127]
 ; CHECK:  %20 = sub nsw i64 0, %p
 ; CHECK:  %21 = sub nsw i64 %20, 1
 ; CHECK:  %pexp.fdiv_q.0 = sub i64 %21, 127
 ; CHECK:  %pexp.fdiv_q.1 = add i64 %pexp.fdiv_q.0, 1
 ; CHECK:  %pexp.fdiv_q.2 = icmp slt i64 %21, 0
 ; CHECK:  %pexp.fdiv_q.3 = select i1 %pexp.fdiv_q.2, i64 %pexp.fdiv_q.1, i64 %21
 ; CHECK:  %pexp.fdiv_q.4 = sdiv i64 %pexp.fdiv_q.3, 127
 ; CHECK:  %22 = mul nsw i64 127, %pexp.fdiv_q.4
 ; CHECK:  %23 = add nsw i64 %p, %22
 ; CHECK:  %24 = add nsw i64 %23, 127
-; CHECK:  %polly.access.A10 = getelementptr float, float* %A, i64 %24
+; CHECK:  %polly.access.A8 = getelementptr float, float* %A, i64 %24
 
 ; A[p / 127]
 ; CHECK:  %pexp.div = sdiv exact i64 %p, 127
-; CHECK:  %polly.access.B12 = getelementptr float, float* %B, i64 %pexp.div
+; CHECK:  %polly.access.B9 = getelementptr float, float* %B, i64 %pexp.div
 
 ; A[i % 128]
 ; POW2:  %pexp.pdiv_r = urem i64 %polly.indvar, 128
 ; POW2:  %polly.access.A6 = getelementptr float, float* %A, i64 %pexp.pdiv_r
 
 ; A[floor(i / 128)]
 ; POW2:  %pexp.p_div_q = udiv i64 %polly.indvar, 128
-; POW2:  %polly.access.B8 = getelementptr float, float* %B, i64 %pexp.p_div_q
+; POW2:  %polly.access.B7 = getelementptr float, float* %B, i64 %pexp.p_div_q
 
 ; #define floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 ; A[p + 128 * floord(-p - 1, 128) + 128]
 ; POW2:  %20 = sub nsw i64 0, %p
 ; POW2:  %21 = sub nsw i64 %20, 1
 ; POW2:  %polly.fdiv_q.shr = ashr i64 %21, 7
 ; POW2:  %22 = mul nsw i64 128, %polly.fdiv_q.shr
 ; POW2:  %23 = add nsw i64 %p, %22
 ; POW2:  %24 = add nsw i64 %23, 128
-; POW2:  %polly.access.A10 = getelementptr float, float* %A, i64 %24
+; POW2:  %polly.access.A8 = getelementptr float, float* %A, i64 %24
 
 ; A[p / 128]
 ; POW2:  %pexp.div = sdiv exact i64 %p, 128
-; POW2:  %polly.access.B12 = getelementptr float, float* %B, i64 %pexp.div
+; POW2:  %polly.access.B9 = getelementptr float, float* %B, i64 %pexp.div
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @exprModDiv(float* %A, float* %B, float* %C, i64 %N, i64 %p) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry

polly/trunk/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll

 ; RUN: opt %loadPolly -polly-codegen -polly-no-early-exit \
 ; RUN:     -polly-detect-unprofitable -S < %s | FileCheck %s
 
 define void @foo(float* %A, i1 %cond0, i1 %cond1) {
 entry:
   br label %loop
 
 loop:
   %indvar = phi i64 [0, %entry], [%indvar.next, %backedge]
   %val0 = fadd float 1.0, 2.0
   %val1 = fadd float 1.0, 2.0
   %val2 = fadd float 1.0, 2.0
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
+; CHECK-NEXT: %polly.subregion.iv = phi i32 [ 0, %polly.stmt.loop.entry ]
 ; 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