[DSE] Use optimized access if available for redundant store elimination.

[fhahn]

Summary

Using the optimized access enables additional optimizations in cases
where the defining access is a non-aliasing store.

Alternatively we could also walk upwards and skip non-aliasing defs
here, but my experiments so far showed that this will noticeably
increase compile-time for little extra gain compared to just using the
optimized access.

Improvements of dse.NumRedundantStores on MultiSource/CINT2006/CPF2006
on X86 with -O3:

test-suite...-typeset/consumer-typeset.test     1.00                  76.00              7500.0%
test-suite.../Benchmarks/Bullet/bullet.test     3.00                  12.00              300.0%
test-suite...006/453.povray/453.povray.test     3.00                   6.00              100.0%
test-suite...telecomm-gsm/telecomm-gsm.test     1.00                   2.00              100.0%
test-suite...ediabench/gsm/toast/toast.test     1.00                   2.00              100.0%
test-suite...marks/7zip/7zip-benchmark.test     1.00                   2.00              100.0%
test-suite...ications/JM/lencod/lencod.test     7.00                  10.00              42.9%
test-suite...6/464.h264ref/464.h264ref.test     6.00                   8.00              33.3%
test-suite...ications/JM/ldecod/ldecod.test     6.00                   7.00              16.7%
test-suite...006/447.dealII/447.dealII.test    33.00                  33.00               0.0%
test-suite...6/471.omnetpp/471.omnetpp.test    NaN                     1.00               nan%
test-suite...006/450.soplex/450.soplex.test    NaN                     2.00               nan%
test-suite.../CINT2006/403.gcc/403.gcc.test    NaN                     7.00               nan%
test-suite...lications/ClamAV/clamscan.test    NaN                     1.00               nan%
test-suite...CI_Purple/SMG2000/smg2000.test    NaN                     3.00               nan%

Follow-up to D111727.

[fhahn]

Rebase on top of 0a2b052eb0a59e0df3c8227c1f39d9b1017b38a6.

[xbolva00]

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

505–506

Not related to this patch, but this should be strcpy, no?

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1979

Can you please add a comment to document this choice?

This is unusual ... the typical way to do this is: upperDef = getClobberingMemoryAccess which internally returns the optimized access if already optimized, or does the walk if not.
You're looking for bypassing that, due to increase in compile time from the walk. You want the optimized if available, but to not do the walk otherwise and default to the defining access.

Would adding a new API (e.g. getOptimizedIfAvailable) for this sort of info be useful?

[fhahn]

Add comment as suggested and add run lines with flag added in D112313

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1979

Thanks, I added a comment to hopefully make things clearer.

Would adding a new API (e.g. getOptimizedIfAvailable) for this sort of info be useful?

I'm not sure if it is worth to do so just yet. Do you anticipate this kind of use-case to become more common?

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1979

I don't have another use case in mind at the moment, so agreed on keeping it as is; the comment is good.

[fhahn]

ping :)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1979

Thanks, so is this now good as is?

[nikic]

LGTM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

   bool eliminateRedundantStoresOfExistingValues() {
     bool MadeChange = false;
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
                          "already existing value\n");
     for (auto *Def : MemDefs) {
       if (SkipStores.contains(Def) || MSSA.isLiveOnEntryDef(Def) ||
           !isRemovable(Def->getMemoryInst()))
         continue;
-      auto *UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
+      MemoryDef *UpperDef;
+      if (Def->isOptimized())
+        UpperDef = dyn_cast<MemoryDef>(Def->getOptimized());
+      else
+        UpperDef = dyn_cast<MemoryDef>(Def->getDefiningAccess());
       if (!UpperDef || MSSA.isLiveOnEntryDef(UpperDef))
         continue;
       auto *DefInst = Def->getMemoryInst();
       auto *UpperInst = UpperDef->getMemoryInst();
       auto MaybeUpperLoc = getLocForWriteEx(UpperInst);
       if (!MaybeUpperLoc || !DefInst->isIdenticalTo(UpperInst) ||
           isReadClobber(*MaybeUpperLoc, DefInst))
         continue;

llvm/test/Transforms/DeadStoreElimination/stores-of-existing-values.ll

 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 10, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 %c, label %bb1, label %bb2
 
 bb1:
   store i32 10, i32* %Q
   br label %bb3

 ; CHECK-NEXT:    store i64 0, i64* [[PTR]], align 8
 ; CHECK-NEXT:    ret void
 ;
   %ptr.i8 = bitcast i64* %ptr to i8*
   call void @llvm.memset.p0i8.i64(i8* %ptr.i8, i8 0, i64 24, i1 false)
   store i64 0, i64* %ptr
   ret void
 }
 
 define void @pr49927(i32* %q, i32* %p) {
 ; CHECK-LABEL: @pr49927(
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    store i32 [[V]], i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %v = load i32, i32* %p, align 4
   store i32 %v, i32* %q, align 4