[DSE] Support looking through memory phis at end of function.

[fhahn]

Summary

Update isWriteAtEndOfFunction to look through MemoryPhis. The reason
MemoryPhis were skipped so far was the known AliasAnalysis issue with it
missing loop-carried dependences.

This problem is already addressed in other parts of the code by skipping
MemoryDefs that may be in difference loops. I think the same logic can
be applied here.

This can have a substantial impact on the number of stores removed in
some cases. For MultiSource/SPEC2006/SPEC2017 with -O3:

Metric: dse.NumFastStores

Program                                       dse.NumFastStores
                                              base              patch   diff
External/S...CINT2017rate/557.xz_r/557.xz_r     14.00             45.00 221.4%
External/S...te/538.imagick_r/538.imagick_r    439.00           1267.00 188.6%
MultiSourc...e/Applications/SIBsim4/SIBsim4      6.00             15.00 150.0%
MultiSourc...Prolangs-C/simulator/simulator      3.00              7.00 133.3%
MultiSource/Applications/siod/siod               3.00              7.00 133.3%
MultiSourc...arks/FreeBench/distray/distray      6.00              9.00  50.0%
MultiSourc...e/Applications/obsequi/Obsequi     22.00             30.00  36.4%
MultiSource/Benchmarks/Ptrdist/bc/bc            23.00             28.00  21.7%
External/S...NT2017rate/502.gcc_r/502.gcc_r   1258.00           1512.00  20.2%
External/S...te/520.omnetpp_r/520.omnetpp_r    954.00           1143.00  19.8%
External/S...rate/510.parest_r/510.parest_r   5961.00           7122.00  19.5%
External/S...C/CINT2006/445.gobmk/445.gobmk     47.00             56.00  19.1%
External/S...00.perlbench_r/500.perlbench_r    241.00            286.00  18.7%
External/S...NT2006/471.omnetpp/471.omnetpp     36.00             42.00  16.7%
External/S...06/400.perlbench/400.perlbench    183.00            210.00  14.8%
MultiSource/Applications/SPASS/SPASS            72.00             81.00  12.5%
External/S...17rate/541.leela_r/541.leela_r     72.00             80.00  11.1%
External/SPEC/CINT2006/403.gcc/403.gcc         585.00            642.00   9.7%
MultiSourc...e/Applications/sqlite3/sqlite3    120.00            131.00   9.2%
MultiSourc...Applications/hexxagon/hexxagon     11.00             12.00   9.1%
External/S.../CFP2006/453.povray/453.povray    566.00            615.00   8.7%
External/S...rate/511.povray_r/511.povray_r    578.00            627.00   8.5%
External/S...FP2006/482.sphinx3/482.sphinx3     12.00             13.00   8.3%
MultiSource/Applications/oggenc/oggenc         130.00            140.00   7.7%
MultiSourc...e/Applications/ClamAV/clamscan    250.00            268.00   7.2%
MultiSourc.../mediabench/jpeg/jpeg-6a/cjpeg     19.00             20.00   5.3%
MultiSourc...ch/consumer-jpeg/consumer-jpeg     19.00             20.00   5.3%
External/S...te/526.blender_r/526.blender_r   3747.00           3928.00   4.8%
MultiSourc...OE-ProxyApps-C++/miniFE/miniFE    104.00            108.00   3.8%
MultiSourc...ch/consumer-lame/consumer-lame     54.00             56.00   3.7%
MultiSource/Benchmarks/Bullet/bullet          1222.00           1264.00   3.4%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4    973.00           1005.00   3.3%
External/S.../CFP2006/447.dealII/447.dealII   2699.00           2780.00   3.0%
External/S...06/483.xalancbmk/483.xalancbmk    788.00            810.00   2.8%
External/S.../CFP2006/450.soplex/450.soplex    180.00            185.00   2.8%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR    338.00            345.00   2.1%
MultiSourc...Benchmarks/7zip/7zip-benchmark    685.00            699.00   2.0%
External/S...FP2017rate/544.nab_r/544.nab_r    158.00            160.00   1.3%
MultiSourc...sumer-typeset/consumer-typeset    772.00            781.00   1.2%
External/S...2017rate/525.x264_r/525.x264_r    410.00            414.00   1.0%
External/S...23.xalancbmk_r/523.xalancbmk_r    998.00           1002.00   0.4%

Compile-time is almost neutral:

https://llvm-compile-time-tracker.com/compare.php?from=b3125ad3d60531a97eea20009cc9629a87755862&to=84007eee59004f43464eda7f5ba8263ed5158df8&stat=instructions

NewPM-O3: +0.03%
NewPM-ReleaseThinLTO: -0.01%
NewPM-ReleaseLTO-g: +0.03%

[fhahn]

Update memcpy.ll test.

[aeubanks]

pardon my ignorance, but could you give an example of something where naively adding all MemoryPhi users misses something but using isGuaranteedLoopIndependent works around that?

[nikic]

llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll

9

Comment is confusing because there is no %l.2.

34

Isn't this exactly the miscompile we want to prevent? The store is to A[iv.2 + 1], which will be read as A[iv.2] on the next iteration?

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

159

Drop TODO

[fhahn]

Update to use isGuaranteedLoopInvariant instead of isGuaranteedLoopIndependent. isGuaranteedLoopIndependent is too loose here because we are not looking for must-alias (as we do for elimination candidates). Instead we must ensure we do not miss any potential reads.

In D132365#3752700, @aeubanks wrote:

pardon my ignorance, but could you give an example of something where naively adding all MemoryPhi users misses something but using isGuaranteedLoopIndependent works around that?

The tests in multiblock-loop-carried-dependence.ll should provide such cases, e.g. @test.1 which was incorrectly optimized by the earlier version of the test.

[fhahn]

llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll

9

thanks, the comment should be updated in 197332a1f80db7cbe2bb43d3f5bd45282245dd28

34

Yeah I missed that in the original version! Updated to use isGuaranteedLoopInvariant

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

159

Thanks, should be removed in the latest version.

[fhahn]

(The shared stats in the description stay effectively the same after the recent update)

[asbirlea]

Thank you for adding this. The diff looks good to me.
The stats and compile-time look very good. Tested for run time performance impact and can't see noticeable improvement.
Overall LGTM from my side (with one inline comment).

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

159

The TODO is unrelated to this patch and should stay.
The store in the %entry block could also be removed. It's writing to an alloca that it's either never used later in this function or overwritten and then used in the call. Either way it's a dead store.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

bool isWriteAtEndOfFunction(MemoryDef *Def) {
     PushMemUses(Def);
     for (unsigned I = 0; I < WorkList.size(); I++) {
       if (WorkList.size() >= MemorySSAScanLimit) {
         LLVM_DEBUG(dbgs() << "  ... hit exploration limit.\n");
         return false;
       }
 
       MemoryAccess *UseAccess = WorkList[I];
-      // Simply adding the users of MemoryPhi to the worklist is not enough,
-      // because we might miss read clobbers in different iterations of a loop,
-      // for example.
-      // TODO: Add support for phi translation to handle the loop case.
-      if (isa<MemoryPhi>(UseAccess))
+      if (isa<MemoryPhi>(UseAccess)) {
+        PushMemUses(cast<MemoryPhi>(UseAccess));
+        continue;
+      }
+      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
+      // AliasAnalysis does not account for loops. Limit elimination to
+      // candidates for which we can guarantee they always store to the same
+      // memory location and not located in different loops.
+      if (!isGuaranteedLoopIndependent(UseInst, Def->getMemoryInst(),
+                                       *MaybeLoc)) {
+        LLVM_DEBUG(dbgs() << "  ... not guaranteed loop independent\n");
         return false;
+      }
 
       // TODO: Checking for aliasing is expensive. Consider reducing the amount
       // of times this is called and/or caching it.
-      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
       if (isReadClobber(*MaybeLoc, UseInst)) {
         LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
         return false;
       }
 
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
         PushMemUses(UseDef);
     }

llvm/test/Transforms/DeadStoreElimination/multiblock-loop-carried-dependence.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 
 ; RUN: opt -dse -S %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64-v256:256:256-v512:512:512"
 
 declare void @use(i32)
 
 ; Test cases with a loop carried dependence in %loop.2, where %l.2 reads the
 ; value stored by the previous iteration. Hence, the store in %loop.2 is not
 ; dead at the end of the function or after the call to lifetime.end().
 
 define void @test.1() {
 ; CHECK-LABEL: @test.1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca [100 x i32], align 4
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop.1:
 ; CHECK-NEXT:    [[IV_1:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ]
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_1]]
 ; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    [[IV_1_NEXT]] = add nsw i64 [[IV_1]], 1
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV_1_NEXT]], 100
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[LOOP_2_PH:%.*]]
 ; CHECK:       loop.2.ph:
 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop.2:
 ; CHECK-NEXT:    [[IV_2:%.*]] = phi i64 [ [[IV_2_NEXT:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_2_PH]] ]
 ; CHECK-NEXT:    [[PTR_IV_2:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[IV_2]]
 ; CHECK-NEXT:    [[L_0:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
 ; CHECK-NEXT:    call void @use(i32 [[L_0]])
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[IV_2]], 1
-; CHECK-NEXT:    [[PTR_IV_2_ADD_1:%.*]] = getelementptr inbounds [100 x i32], [100 x i32]* [[A]], i64 0, i64 [[ADD]]
-; CHECK-NEXT:    store i32 10, i32* [[PTR_IV_2_ADD_1]], align 4
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV_2]], align 4
 ; CHECK-NEXT:    call void @use(i32 [[L_1]])
 ; CHECK-NEXT:    [[IV_2_NEXT]] = add nsw i64 [[IV_2]], 1
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i64 [[IV_2_NEXT]], 100
 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/DeadStoreElimination/multiblock-malloc-free.ll

 
 
 define void @test27() {
 ; CHECK-LABEL: @test27(
 ; CHECK-NEXT:  bb1:
 ; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i64 10)
-; CHECK-NEXT:    store i8 1, i8* [[M]], align 1
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
 ; CHECK-NEXT:    ret void
 ;
 bb1:
   br i1 true, label %bb2, label %bb3
 bb2:

llvm/test/Transforms/DeadStoreElimination/multiblock-memintrinsics.ll

 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
 ; CHECK-NEXT:    call void @readonly_use(i32* [[P]])
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
-; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %P.alloca = alloca [32 x i32]
   %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1

 ; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32], align 4
 ; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
 ; CHECK-NEXT:    call void @readonly_use(i32* [[P]])
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
-; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
-; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX2]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %P.alloca = alloca [32 x i32]
   %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1

llvm/test/Transforms/DeadStoreElimination/phi-translation.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -dse -S %s | FileCheck %s
 
-; TODO: Both the stores in %then and %else can be eliminated by translating %p
+; Both the stores in %then and %else can be eliminated by translating %p
 ; through the phi.
 define void @memoryphi_translate_1(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.1 = alloca i8
else:
   br label %end
 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   store i8 10, i8* %p
   ret void
 }
 
-; TODO: The store in %else can be eliminated by translating %p through the phi.
+; The store in %else can be eliminated by translating %p through the phi.
 ; The store in %then cannot be eliminated, because %a.1 is read before the final
 ; store.
 define i8 @memoryphi_translate_2(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
-; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_1]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1
 ; CHECK-NEXT:    ret i8 [[L]]
 ;
 entry:

 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   %l = load i8, i8* %a.1
   store i8 10, i8* %p
   ret i8 %l
 }
 
-; TODO: The store in %then can be eliminated by translating %p through the phi.
+; The store in %then can be eliminated by translating %p through the phi.
 ; The store in %else cannot be eliminated, because %a.2 is read before the final
 ; store.
 define i8 @memoryphi_translate_3(i1 %c) {
 ; CHECK-LABEL: @memoryphi_translate_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
-; CHECK-NEXT:    store i8 0, i8* [[A_1]], align 1
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    store i8 9, i8* [[A_2]], align 1
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
 ; CHECK-NEXT:    [[L:%.*]] = load i8, i8* [[A_2]], align 1
 ; CHECK-NEXT:    store i8 10, i8* [[P]], align 1

 
 end:
   %p = phi i8* [ %a.1, %then ], [ %a.2, %else ]
   %l = load i8, i8* %p
   store i8 10, i8* %p
   ret i8 %l
 }
 
 ; TODO: The store in %entry can be removed by translating %p through the phi.
 define void @memoryphi_translate_5(i1 %cond) {
 ; CHECK-LABEL: @memoryphi_translate_5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[B:%.*]] = alloca i8, align 1
-; CHECK-NEXT:    [[C:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    store i8 0, i8* [[A]], align 1
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    store i8 0, i8* [[C]], align 1
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[B]], [[COND_TRUE]] ], [ [[A]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    call void @use(i8* [[P]])
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/MemCpyOpt/memcpy.ll

;
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %a2, i8* align 4 %P, i64 8, i1 false)
   %x = load i8, i8* %a2
   call void @test4a(i8* align 1 byval(i8) %a2)
   ret i8 %x
 }
 
 define void @test4_non_local(i8 *%P, i1 %c) {
 ; CHECK-LABEL: @test4_non_local(
-; CHECK-NEXT:    [[A1:%.*]] = alloca [[TMP1:%.*]], align 8
-; CHECK-NEXT:    [[A2:%.*]] = bitcast %1* [[A1]] to i8*
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 [[A2]], i8* align 4 [[P:%.*]], i64 8, i1 false)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CALL:%.*]], label [[EXIT:%.*]]
 ; CHECK:       call:
-; CHECK-NEXT:    call void @test4a(i8* byval(i8) align 1 [[P]])
+; CHECK-NEXT:    call void @test4a(i8* byval(i8) align 1 [[P:%.*]])
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   %a1 = alloca %1
   %a2 = bitcast %1* %a1 to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 %a2, i8* align 4 %P, i64 8, i1 false)
   br i1 %c, label %call, label %exit