[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

1854

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

1869

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

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

1869

Added a TODO.

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

294

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

1814

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

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

1830

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

1841

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
}

1849

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

119

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

119

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

119

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

1814

Fair enough. Done.

1830

Oops, somehow I missed this.

1841

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.

1849

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

1841

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.

1849

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

1841

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

1817

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

1836

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?

215

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.

215

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

bool isDSEBarrier(Instruction *SI, MemoryLocation &SILoc,
                     MemoryLocation &NILoc) const {
     // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
     // like object that does not escape.
     if (NI->mayThrow() && !InvisibleToCallerBeforeRet.count(SILocUnd))
       return true;
 
     if (NI->isAtomic()) {
       if (auto *NSI = dyn_cast<StoreInst>(NI)) {
         if (isStrongerThanMonotonic(NSI->getOrdering()))
           return true;
       } else
         llvm_unreachable(
             "Other instructions should be modeled/skipped in MemorySSA");
     }
 
     return false;
   }
 };
 
 /// \returns true if \p KillingDef stores the result of \p Load to the source of
 /// \p Load.
 static bool storeIsNoop(MemorySSA &MSSA, LoadInst *Load,
                         MemoryDef *KillingDef) {
   Instruction *Store = KillingDef->getMemoryInst();
   // If the load's operand isn't the destination of the store, bail.
   if (Load->getPointerOperand() != Store->getOperand(1))
     return false;
 
   // Get the defining access for the load.
   auto *LoadAccess = MSSA.getMemoryAccess(Load)->getDefiningAccess();
-  // The store is dead if the defining accesses are the same.
-  return LoadAccess == KillingDef->getDefiningAccess();
+  // Fast path: the defining accesses are the same.
+  bool IsDead = LoadAccess == KillingDef->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 = KillingDef->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(KillingDef);
+  ToCheck.insert(Current);
+  // Start at current (1) to simulate already having checked KillingDef.
+  for (unsigned I = 1; I < ToCheck.size(); ++I) {
+    Current = ToCheck[I];
+    if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
+      // Check all the operands.
+      for (unsigned PhiIndex = 0; PhiIndex < PhiAccess->getNumOperands();
+           ++PhiIndex)
+        ToCheck.insert(PhiAccess->getOperand(PhiIndex));
+      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)) {
+      // 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;
+      if (!IsDead)
+        break;
+      // If the store is not dead, we need to keep checking.
+      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;
 }
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                   MemorySSA &MSSA, DominatorTree &DT,
                                   PostDominatorTree &PDT,
                                   const TargetLibraryInfo &TLI) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   bool MadeChange = false;

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
+}
+
 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-NEXT:    br label [[BB2:%.*]]

 ; 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

;
   %m.addr = alloca i32
   %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
   store i32 0, i32* %k.addr.m.addr, align 4
   ret void
 }
 
 declare void @unknown_func()
 
-; 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
-}
-
 define void @test43a(i32* %P, i32* noalias %Q) {
 ; CHECK-LABEL: @test43a(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store atomic i32 50331649, i32* [[P:%.*]] unordered, align 4
 ; CHECK-NEXT:    store atomic i32 2, i32* [[Q:%.*]] unordered, align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store atomic i32 1, i32* %P unordered, align 4
   %P2 = bitcast i32* %P to i8*
   store atomic i32 2, i32* %Q unordered, align 4
   store atomic i8 3, i8* %P2 unordered, align 4
   ret void
 }

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

bb3:
   store i32 %v, i32* %p, align 4
   ret i32 0
 }
 
 ; Don't remove redundant store because of may-aliased store.
 define i32 @test29(i1 %c, i32* %p, i32* %p2, i32 %i) {
 ; CHECK-LABEL: @test29(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 [[I:%.*]], i32* [[P2:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; 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:
   ; Might overwrite value at %p
   store i32 %i, i32* %p2, align 4
   br label %bb3
 bb3:
   store i32 %v, i32* %p, align 4
   ret i32 0
 }
 
 declare void @unknown_func()
 
 ; Don't remove redundant store because of unknown call.
 define i32 @test30(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test30(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    call void @unknown_func()
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; 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:
   ; Might overwrite value at %p
   call void @unknown_func()
   br label %bb3
 bb3:
   store i32 %v, i32* %p, align 4
   ret i32 0
 }
 
 ; Don't remove redundant store in a loop with a may-alias store.
 define i32 @test32(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test32(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 [[V]], i32* [[P]], align 4
 ; CHECK-NEXT:    call void @unknown_func()
 ; 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