[DSE] Look through memory PHI arguments when removing noop stores in MSSA.

[zoecarver]

Summary

Adds support for "following" memory through MSSA PHI arguments. This will help catch more noop stores that exist between blocks.

Originally part of D79391.

[zoecarver]

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

96

I'm going to add a few negative tests.

[zoecarver]

After running this on the LLVM test suite here are the stats:

dse.NumRemainingStores

Program                                        stats_opt stats_master diff

test-suite...lications/sqlite3/sqlite3.test   13683.00  13723.00      0.3%
test-suite...decode/alacconvert-decode.test   547.00    547.00        0.0%
test-suite...nia/pathfinder/pathfinder.test    16.00     16.00        0.0%
test-suite...s-C/unix-smail/unix-smail.test   218.00    218.00        0.0%
test-suite...langs-C/unix-tbl/unix-tbl.test   227.00    227.00        0.0%
test-suite...s/Ptrdist/anagram/anagram.test   124.00    124.00        0.0%
test-suite.../Benchmarks/Ptrdist/bc/bc.test   983.00    983.00        0.0%
test-suite.../Benchmarks/Ptrdist/ft/ft.test   154.00    154.00        0.0%
test-suite.../Benchmarks/Ptrdist/ks/ks.test    88.00     88.00        0.0%
test-suite...marks/Ptrdist/yacr2/yacr2.test   307.00    307.00        0.0%
test-suite...Rodinia/backprop/backprop.test    76.00     76.00        0.0%
test-suite...s/Rodinia/hotspot/hotspot.test    22.00     22.00        0.0%
test-suite...chmarks/Rodinia/srad/srad.test    50.00     50.00        0.0%
test-suite.../Prolangs-C/loader/loader.test    93.00     93.00        0.0%
test-suite...marks/SciMark2-C/scimark2.test    91.00     91.00        0.0%
Geomean difference                                                    nan%

dse.NumNoopStores

Program                                        stats_opt stats_master diff

test-suite...lications/ClamAV/clamscan.test     2.00      2.00        0.0%
test-suite...pplications/oggenc/oggenc.test     2.00      2.00        0.0%
test-suite...TimberWolfMC/timberwolfmc.test     1.00      1.00        0.0%
test-suite.../Prolangs-C/loader/loader.test     1.00      1.00        0.0%
test-suite...decode/alacconvert-decode.test    NaN       NaN          nan%
test-suite...encode/alacconvert-encode.test    NaN       NaN          nan%
test-suite...ce/Applications/Burg/burg.test    NaN       NaN          nan%
test-suite...ications/JM/ldecod/ldecod.test    NaN       NaN          nan%
test-suite...ications/JM/lencod/lencod.test    NaN       NaN          nan%
test-suite...lications/SIBsim4/SIBsim4.test    NaN       NaN          nan%
test-suite.../Applications/SPASS/SPASS.test    NaN        1.00        nan%
test-suite...urce/Applications/aha/aha.test    NaN       NaN          nan%
test-suite...plications/d/make_dparser.test    NaN       NaN          nan%
test-suite...urce/Applications/hbd/hbd.test    NaN       NaN          nan%
test-suite...cations/hexxagon/hexxagon.test    NaN       NaN          nan%
Geomean difference                                                    nan%

[zoecarver]

Also, MultiSource/Applications/SPASS/SPASS.test is failing for some reason. The error it's giving me is:

/Users/zoe/Developer/llvm-source/stats-build/tools/fpcmp-target: files differ without tolerance allowance

It looks like this may be an issue with the time it took to execute the test? That may be because I'm running these tests on a laptop (so both compile time and execution time aren't going to be accurate metrics).

[fhahn]

In D82588#2115091, @zoecarver wrote:

Also, MultiSource/Applications/SPASS/SPASS.test is failing for some reason. The error it's giving me is:

/Users/zoe/Developer/llvm-source/stats-build/tools/fpcmp-target: files differ without tolerance allowance

It looks like this may be an issue with the time it took to execute the test? That may be because I'm running these tests on a laptop (so both compile time and execution time aren't going to be accurate metrics).

Does it pass without the patch? If it only fails with the patch, the patch is likely introducing a mis-compile.

[zoecarver]

Does it pass without the patch? If it only fails with the patch, the patch is likely introducing a mis-compile.

Yes, you're right. Investigating now.

[zoecarver]

• Check all MemoryAccesses (fix segfault when one block is noop but another uses the store).

[zoecarver]

All tests now pass. dse.NumNoopStores still hasn't changed.

[fhahn]

Sorry for the long delay, this review dropped off my radar somehow.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2382

Perhaps you could use the incoming_values iterator range here? for (Value *V : PhiAccess->incoming_values()) {

2397

I think we could also cover more cases here, by skipping no-aliasing MemoryDefs and checking that there are no aliasing reads.. But that's future work. Perhaps a comment/TODO would be good.

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

294 ↗

(On Diff #273772)

The changes in this test file are not legal transforms I think. In this example, we cannot remove the start as the store at line 311 might overwrite %p, if %p == %p2 and then the store is not dead.

[zoecarver]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2397

Added a TODO.

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

294 ↗

(On Diff #273772)

You're right. We shouldn't exit early when we hit a MemoryDef. Fixed.

[zoecarver]

@fhahn Thanks for the review. Sorry for letting this sit for so long. All the tests in the llvm-test-suite are now passing.

[zoecarver]

• Fix bug and add two tests

[fhahn]

Thanks for updating the patch! Some more comments inline, but I think it is almost there.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2405

I think it would be easier to get rid of the IsDead variable and just have

if (LoadAccess == Def->getDefiningAccess()) return true

2421

I think this won't build. I think you'd need to use auto &Use : and insert(cast<MemoryAccess>(&Use)).

2432

I think this may lead to incorrect results, if the first incoming value is not the LoadAccess but the second one is. For example, consider the function below. I think we can just return false if LoadAccess != Current. And it should be safe to assert that current is a MemoryDef here.

define i32 @test(i1 %c, i32* %p) {
entry:
  %v = load i32, i32* %p, align 4
  br i1 undef, label %bb0, label %bb0.0

bb0:
  store i32 0, i32* %p
  br label %bb1

bb0.0:
  br label %bb1

bb1:
  store i32 %v, i32* %p, align 4
  br label %bb2
bb2:
  ret i32 0
}

2440

I don't think we can reach this code? Both the incoming values and getDefiningAccess should return either a MemoryDef or a MemoryPhi, but never a MemoryUse. I don't think this code is needed.

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

119

It would be good to avoid using branches on undef, because that's UB. Instead you can use i1 arguments for example. In this case, you could use the %c argument, (Same for other tests)

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

8

IIUC we should now handle the original case correctly? Can you move it to simple.ll and perhaps add the additional case to noop-stores.ll?

[zoecarver]

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

8

Original case? Do you mean test31? I've added that to noop-stores.ll. Also, what do you mean by the additional case? test47?

test47 we don't yet support but it's a pretty simple fix, I think we can just check if the def is a StoreInst and run it through storeIsNoop and if that returns true we can continue instead of returning false.

[fhahn]

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

8

Original case? Do you mean test31? I've added that to noop-stores.ll.

that's fine, I missed that.

test47 we don't yet support but it's a pretty simple fix, I think we can just check if the def is a StoreInst and run it through storeIsNoop and if that returns true we can continue instead of returning false.

yes I meant test47. simple-todo.ll only contains cases from the original simple.ll that MSSA-backed DSE did not support. So it would be best to add new test cases to noop-stores.ll and remove simple-todo.ll once all test cases have been moved out of there.

[zoecarver]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2405

Fair enough. Done.

2421

Oops, somehow I missed this.

2432

You're right.

But, in the example, it would be valid to remove both stores. It is guaranteed that store i32 %v will always happen immediately after store i32 0.

Anyway, I've applied your suggested fix. I'll also add a similar test case.

2440

Yep, you're right. We'll never get here. I originally thought that we may get here through an operand from a phi access but, it looks like those can only be memory defs (which makes sense, I don't know how you'd have a use as a definition without it being a... definition).

[fhahn]

From the comments it seems like you updated the patch, but is it possible that something went wrong with uploading it to reviews.llvm.org? It seems like the patch has not been updated here.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2432

But, in the example, it would be valid to remove both stores. It is guaranteed that store i32 %v will always happen immediately after store i32 0.

yes, but I think with the current ordering of transformations (removing noop stores first) we would remove store i32 %v, i32* %p, align 4 and leave store i32 0, i32* %p. There are a few cases like this, where the result depends on the exact ordering in which we visit stores & apply transformations.

2440

like those can only be memory defs

and memory phis, but never plain memory uses

[zoecarver]

• Fix based on review

[zoecarver]

From the comments it seems like you updated the patch, but is it possible that something went wrong with uploading it to reviews.llvm.org? It seems like the patch has not been updated here.

Just an issue with arc. Sorry for the confusion. I also applied you're other suggested edits (using %c and moving test47). Thanks for the review!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2432

When I tested it we removed both (albeit for the wrong reason). Maybe because we visit them in reverse order.

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2408

nit: bail when we run into a memory def that does not match LoadAccess.

2427

It should be possible to replace the if () with assert(isa<MemoryDef>(Current) && "only MemoryDefs should reach here");

[zoecarver]

• If -> assert
• Reflow/rewrite comments

[xbolva00]

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

124

use update_test_checks.py script to regenerate test checks?

236

No longer todo?

[zoecarver]

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

124

I think the below checks are sufficient. Is the norm to use update_test_checks.py? If you'd like, I can submit another patch after updating the tests.

236

This is still a TODO. See the X-CHECKs below.

[fhahn]

@zoecarver just FYI, there's another missing optimization that might be related to your earlier patches, in case you are interested https://bugs.llvm.org/show_bug.cgi?id=16520

[zoecarver]

@zoecarver just FYI, there's another missing optimization that might be related to your earlier patches, in case you are interested https://bugs.llvm.org/show_bug.cgi?id=16520

@fhahn thanks! I've got a lot on my plate this week and next but I'll put up a patch as soon as I have the time.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a trivial dead store elimination that only considers
for (int I = MemDefs.size() - 1; I >= 0; I--) {
       // uncommon. If it turns out to be important, we can use
       // getUnderlyingObjects here instead.
       const Value *UO = getUnderlyingObject(DefLoc->Ptr);
       if (!UO || !isInvisibleToCallerAfterRet(UO))
         continue;
 
       if (isWriteAtEndOfFunction(Def)) {
         // See through pointer-to-pointer bitcasts
         LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
                              "of the function\n");
         deleteDeadInstruction(DefI);
         ++NumFastStores;
         MadeChange = true;
       }
     }
     return MadeChange;
   }
 
   /// \returns true if \p Def is a no-op store, either because it
   /// directly stores back a loaded value or stores zero to a calloced object.
   bool storeIsNoop(MemoryDef *Def, MemoryLocation DefLoc, const Value *DefUO) {
     StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
     if (!Store)
       return false;
 
     if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
       if (LoadI->getPointerOperand() == Store->getOperand(1)) {
+        // Get the defining access for the load.
         auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
-        // If both accesses share the same defining access, no instructions
-        // between them can modify the memory location.
-        return LoadAccess == Def->getDefiningAccess();
+        // Fast path: the defining accesses are the same.
+        bool IsDead = LoadAccess == Def->getDefiningAccess();
+        if (IsDead)
+          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.
+        SetVector<MemoryAccess *> ToCheck;
+        MemoryAccess *Current = Def->getDefiningAccess();
+        // 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];
+          if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
+            // Check all the operands.
+            for (auto *V : PhiAccess->incoming_values())
+              ToCheck.insert(V);
+            continue;
+          }
+
+          // If we found a memory def, bail. This happens when we have an unrelated
+          // write in between an otherwise noop store.
+          if (isa<MemoryDef>(Current)) {
+            // TODO: Skip no alias MemoryDefs that have no aliasing reads.
+            // We are searching for the definition of the store's destination. So, if
+            // that is the same definition as the load, then this is a noop.
+            IsDead = LoadAccess == Current;
+            // Either way, we need to keep checking to make sure there aren't
+            // any other MemoryDefs.
+            continue;
+          }
+
+          // The store is also a noop if the defining access of a use of the store's
+          // memory is the same as the load's defining access.
+          if (cast<MemoryUse>(Current)->getDefiningAccess() == LoadAccess)
+            IsDead = true;
+        }
+        return IsDead;
       }
     }
 
     Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
     if (StoredConstant && StoredConstant->isNullValue()) {
       auto *DefUOInst = dyn_cast<Instruction>(DefUO);
       if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
         auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));

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

 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %v = load i32, i32* %p, align 4
   br i1 %c, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   br label %bb3
 bb3:
   store i32 %v, i32* %p, align 4
   ret i32 0
 }
 
+; Remove redundant store if loaded value is in another block inside a loop.
+define i32 @test31(i1 %c, i32* %p, i32 %i) {
+; CHECK-LABEL: @test31(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  ret i32 0
+}
+
+; Don't remove "redundant" store if %p is possibly stored to.
+define i32 @test46(i1 %c, i32* %p, i32* %p2, i32 %i) {
+; CHECK-LABEL: @test46(
+; CHECK:  load
+; CHECK:  store
+; CHECK:  store
+; CHECK:  ret i32 0
+;
+entry:
+  %v = load i32, i32* %p, align 4
+  br label %bb1
+bb1:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb1, label %bb2
+bb2:
+  store i32 0, i32* %p2, align 4
+  br i1 undef, label %bb3, label %bb1
+bb3:
+  ret i32 0
+}
+
 declare void @unknown_func()
 
 ; Remove redundant store, which is in the lame loop as the load.
 define i32 @test33(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test33(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:

 ; CHECK-LABEL: @test45(
 ; CHECK-NEXT:    [[A:%.*]] = load
 ; CHECK-NEXT:    store i32 [[A]]
 ; CHECK-NEXT:    ret void
   %a = load i32, i32* %Q
   store i32 10, i32* %Q
   store i32 %a, i32* %Q
   ret void
 }
-
-

llvm/test/Transforms/DeadStoreElimination/MSSA/simple-todo.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; XFAIL: *
 ; RUN: opt < %s -basic-aa -dse -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
-; Remove redundant store if loaded value is in another block inside a loop.
-define i32 @test31(i1 %c, i32* %p, i32 %i) {
-; CHECK-LABEL: @test31(
+; Remove both redundant stores if loaded value is in another block inside a loop.
+define i32 @test47(i1 %c, i32* %p, i32 %i) {
+; CHECK-LABEL: @test47(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2:
+; CHECK-NEXT:    br i1 undef, label [[BB2]], label [[BB3:%.*]]
+; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %v = load i32, i32* %p, align 4
   br label %bb1
 bb1:
   store i32 %v, i32* %p, align 4
   br i1 undef, label %bb1, label %bb2
 bb2:
+  store i32 %v, i32* %p, align 4
+  br i1 undef, label %bb3, label %bb1
+bb3:
   ret i32 0
 }