[DSE] Support redundant stores eliminated by memset.

[fhahn]

Summary

This patch adds support to remove stores that write the same value
as earlier memesets.

It uses isOverwrite to check that a memset completely overwrites a later
store. The candidate store must store the same bytewise value as the
byte stored by the memset.

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

test-suite...oxyApps-C++/miniFE/miniFE.test     1.00                           5.00             400.0%
test-suite...marks/7zip/7zip-benchmark.test     2.00                           8.00             300.0%
test-suite...lications/sqlite3/sqlite3.test     2.00                           7.00             250.0%
test-suite...lications/ClamAV/clamscan.test     1.00                           2.00             100.0%
test-suite.../CINT2006/403.gcc/403.gcc.test     7.00                          11.00             57.1%
test-suite...006/447.dealII/447.dealII.test    33.00                          51.00             54.5%
test-suite...0.perlbench/400.perlbench.test     2.00                           3.00             50.0%
test-suite.../Benchmarks/Bullet/bullet.test    12.00                          16.00             33.3%
test-suite.../Applications/lemon/lemon.test     5.00                           6.00             20.0%
test-suite...DOE-ProxyApps-C/CoMD/CoMD.test     6.00                           7.00             16.7%
test-suite...pplications/oggenc/oggenc.test     7.00                           8.00             14.3%
test-suite...3.xalancbmk/483.xalancbmk.test    62.00                          67.00              8.1%
test-suite...T2006/458.sjeng/458.sjeng.test    NaN                             1.00              nan%
test-suite...CFP2006/444.namd/444.namd.test    NaN                             1.00              nan%
test-suite...nsumer-jpeg/consumer-jpeg.test    NaN                             3.00              nan%
test-suite...rks/tramp3d-v4/tramp3d-v4.test    NaN                            13.00              nan%
test-suite...oxyApps-C/miniGMG/miniGMG.test    NaN                            25.00              nan%

Motivating C test case https://clang.godbolt.org/z/dfEnv7f5x:

#include <string.h>
void foo(int** ptr, int *foo) {
    memset(ptr, 0, 128);
    ptr[1] = foo;
    ptr[2] = NULL;
}

[nikic]

LGTM

[xbolva00]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1998

Shouldnt this condition also handle pr50339 testcase in stores-of-existing-values.ll?

[fhahn]

rebase so this can be landed without the preceding patches.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

for (auto *Def : MemDefs) {
         continue;
       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();
+
+      Instruction *DefInst = Def->getMemoryInst();
+      Instruction *UpperInst = UpperDef->getMemoryInst();
+      auto IsRedundantStore = [this, DefInst,
+                               UpperInst](MemoryLocation UpperLoc) {
+        if (DefInst->isIdenticalTo(UpperInst))
+          return true;
+        if (auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
+          if (auto *SI = dyn_cast<StoreInst>(DefInst)) {
+            auto MaybeDefLoc = getLocForWriteEx(DefInst);
+            if (!MaybeDefLoc)
+              return false;
+            int64_t InstWriteOffset = 0;
+            int64_t DepWriteOffset = 0;
+            auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
+                                  InstWriteOffset, DepWriteOffset);
+            Value *StoredByte = isBytewiseValue(SI->getValueOperand(), DL);
+            return StoredByte && StoredByte == MemSetI->getOperand(1) &&
+                   OR == OW_Complete;
+          }
+        }
+        return false;
+      };
+
       auto MaybeUpperLoc = getLocForWriteEx(UpperInst);
-      if (!MaybeUpperLoc || !DefInst->isIdenticalTo(UpperInst) ||
+      if (!MaybeUpperLoc || !IsRedundantStore(*MaybeUpperLoc) ||
           isReadClobber(*MaybeUpperLoc, DefInst))
         continue;
       deleteDeadInstruction(DefInst);
       NumRedundantStores++;
       MadeChange = true;
     }
     return MadeChange;
   }
if (!Shortend && isRemovable(KillingI) &&
                         << '\n');
       State.deleteDeadInstruction(KillingI);
       NumRedundantStores++;
       MadeChange = true;
       continue;
     }
   }
 
-  MadeChange |= State.eliminateRedundantStoresOfExistingValues();
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
+  MadeChange |= State.eliminateRedundantStoresOfExistingValues();
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//

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

bb3:
   ret void
 }
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg) #1
 
 define void @test12_memset_simple(i8* %ptr) {
 ; CHECK-LABEL: @test12_memset_simple(
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[PTR:%.*]], i8 0, i64 10, i1 false)
-; CHECK-NEXT:    [[PTR_5:%.*]] = getelementptr i8, i8* [[PTR]], i64 4
-; CHECK-NEXT:    store i8 0, i8* [[PTR_5]], align 1
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* %ptr, i8 0, i64 10, i1 false)
   %ptr.5 = getelementptr i8, i8* %ptr, i64 4
   store i8 0, i8* %ptr.5
   ret void
 }
 
 define void @test12_memset_other_store_in_between(i8* %ptr) {
 ; CHECK-LABEL: @test12_memset_other_store_in_between(
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* [[PTR:%.*]], i8 0, i64 10, i1 false)
 ; CHECK-NEXT:    [[PTR_4:%.*]] = getelementptr i8, i8* [[PTR]], i64 4
 ; CHECK-NEXT:    store i8 8, i8* [[PTR_4]], align 1
-; CHECK-NEXT:    [[PTR_5:%.*]] = getelementptr i8, i8* [[PTR]], i64 5
-; CHECK-NEXT:    store i8 0, i8* [[PTR_5]], align 1
 ; CHECK-NEXT:    ret void
 ;
   call void @llvm.memset.p0i8.i64(i8* %ptr, i8 0, i64 10, i1 false)
   %ptr.4 = getelementptr i8, i8* %ptr, i64 4
   store i8 8, i8* %ptr.4
   %ptr.5 = getelementptr i8, i8* %ptr, i64 5
   store i8 0, i8* %ptr.5
   ret void