[DSE] Use walker to skip noalias stores between current & clobber def.

[fhahn]

Summary

Instead of getting the defining access we should be able to use
getClobberingMemoryAccess to skip non-aliasing MemoryDefs. No additional
checks should be needed, because we only remove the starting def if it
matches the defining access of the load. All we need to worry about is
that there are no (may)alias stores between the starting def and the
load and getClobberingMemoryAccess should guarantee that.

Partly fixes PR47887.

This improves the number of redundant stores removed in some cases
(numbers below for MultiSource, SPEC2000, SPEC2006 on X86 with -flto
-O3).

Same hash: 226 (filtered out)
Remaining: 11
Metric: dse.NumRedundantStores

Program base patch1 diff
test-suite...:: External/Povray/povray.test 1.00 5.00 400.0%
test-suite...chmarks/MallocBench/gs/gs.test 1.00 3.00 200.0%
test-suite...0/253.perlbmk/253.perlbmk.test 21.00 37.00 76.2%
test-suite...0.perlbench/400.perlbench.test 24.00 37.00 54.2%
test-suite.../Applications/SPASS/SPASS.test 3.00 4.00 33.3%
test-suite...006/453.povray/453.povray.test 15.00 18.00 20.0%
test-suite...T2006/445.gobmk/445.gobmk.test 27.00 29.00 7.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 136.00 137.00 0.7%
test-suite.../CINT2000/176.gcc/176.gcc.test 6.00 6.00 0.0%
test-suite.../Benchmarks/Bullet/bullet.test NaN 3.00 nan%
test-suite.../Benchmarks/Ptrdist/bc/bc.test NaN 1.00 nan%

[zoecarver]

Fantastic, this LGTM.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
         // Fast path: the defining accesses are the same.
         if (LoadAccess == Def->getDefiningAccess())
           return true;
 
         // Look through phi accesses. Recursively scan all phi accesses by
         // adding them to a worklist. Bail when we run into a memory def that
         // does not match LoadAccess.
         SetVector<MemoryAccess *> ToCheck;
-        MemoryAccess *Current = Def->getDefiningAccess();
+        MemoryAccess *Current =
+            MSSA.getWalker()->getClobberingMemoryAccess(Def);
         // We don't want to bail when we run into the store memory def. But,
         // the phi access may point to it. So, pretend like we've already
         // checked it.
         ToCheck.insert(Def);
         ToCheck.insert(Current);
         // Start at current (1) to simulate already having checked Def.
         for (unsigned I = 1; I < ToCheck.size(); ++I) {
           Current = ToCheck[I];

llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll

 declare void @llvm.init.trampoline(i8*, i8*, i8*)
 
 ; **** Noop load->store tests **************************************************
 
 ; We CAN optimize volatile loads.
 define void @test_load_volatile(i32* %Q) {
 ; CHECK-LABEL: @test_load_volatile(
 ; CHECK-NEXT:    [[A:%.*]] = load volatile i32, i32* [[Q:%.*]], align 4
-; CHECK-NEXT:    store i32 [[A]], i32* [[Q]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %a = load volatile i32, i32* %Q
   store i32 %a, i32* %Q
   ret void
 }
 
 ; We can NOT optimize volatile stores.

 bb3:
   ret i32 0
 }
 
 ; Test case from PR47887.
 define void @test_noalias_store_between_load_and_store(i32* noalias %x, i32* noalias %y) {
 ; CHECK-LABEL: @test_noalias_store_between_load_and_store(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[X:%.*]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[Y:%.*]], align 4
-; CHECK-NEXT:    store i32 [[LV]], i32* [[X]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %lv = load i32, i32* %x, align 4
   store i32 0, i32* %y, align 4
   store i32 %lv, i32* %x, align 4
   ret void
 }