This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by zoecarver on Jun 25 2020, 11:09 AM.

Details

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.

Diff Detail

Event Timeline

zoecarver created this revision.Jun 25 2020, 11:09 AM
zoecarver marked an inline comment as done.Jun 25 2020, 11:11 AM
zoecarver added inline comments.
llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll
96

I'm going to add a few negative tests.

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%

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).

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.

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.

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

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

fhahn requested changes to this revision.Jul 25 2020, 10:07 AM

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.

This revision now requires changes to proceed.Jul 25 2020, 10:07 AM
zoecarver marked 3 inline comments as done.Sep 27 2020, 5:33 PM
zoecarver added inline comments.
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 marked 2 inline comments as done.Sep 27 2020, 5:46 PM

@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 updated this revision to Diff 294581.Sep 27 2020, 5:47 PM
  • Fix bug and add two tests

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 added inline comments.Sep 30 2020, 10:18 AM
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 added inline comments.Sep 30 2020, 10:44 AM
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 added inline comments.Sep 30 2020, 7:37 PM
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 added a comment.Oct 1 2020, 12:55 AM

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 updated this revision to Diff 295613.Oct 1 2020, 10:23 AM
  • Fix based on review

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 accepted this revision.Oct 1 2020, 10:29 AM

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");

This revision is now accepted and ready to land.Oct 1 2020, 10:29 AM
zoecarver updated this revision to Diff 295618.Oct 1 2020, 10:39 AM
  • If -> assert
  • Reflow/rewrite comments
This revision was landed with ongoing or failed builds.Oct 1 2020, 10:42 AM
This revision was automatically updated to reflect the committed changes.
xbolva00 added inline comments.
llvm/test/Transforms/DeadStoreElimination/MSSA/noop-stores.ll
124

use update_test_checks.py script to regenerate test checks?

236

No longer todo?

zoecarver added inline comments.Oct 8 2020, 12:03 PM
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 added a comment.Oct 9 2020, 12:00 PM

@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 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.