This is an archive of the discontinued LLVM Phabricator instance.

NewGVN: Add basic dead store elimination
ClosedPublic

Authored by dberlin on Jan 25 2017, 2:25 PM.

Details

Summary

This adds basic dead store elimination to NewGVN. Unlike our current
DSE, it will happily do cross-block DSE if it meets our requirements.

We get a bunch of DSE's simple.ll cases, and some stuff it doesn't.
Unlike DSE, however, we only try to eliminate stores of the same value
to the same memory location, not just general stores to the same
memory location.

Event Timeline

dberlin created this revision.Jan 25 2017, 2:25 PM
dberlin added inline comments.Jan 25 2017, 2:32 PM
lib/Transforms/Scalar/NewGVN.cpp
2223

I'll remove the {'s.

2273

This is leftover from when i was trying to only walk the members once, but harmless.
removing it.

This version is slightly busted, it's missing the hasMemberOtherThanUs check, which it turns out we do need.
Posting updated patch in a second.

Not sure I would call this dead store elimination; you aren't proving the store is dead, just that it's redundant.

Not sure I would call this dead store elimination; you aren't proving the store is dead, just that it's redundant.

We actually prove both in some cases?
Happy to call it whatever.

Most value numbering implementations call it dead store elimination.

Note that our current DSE is the same in some cases. Some stores it proves dead, some redundant.

See, e.g, eliminateNoopStore

Most value numbering implementations call it dead store elimination.

That's a good reason to continue using that name.

davide edited edge metadata.Jan 26 2017, 8:42 AM

The logic is sound, I left some comments inline while I try on my tests and see how it performs =)

lib/Transforms/Scalar/NewGVN.cpp
90

I would use "dead/redundant stores eliminated" here, but up to you.

351–352

This constness is independent? Probably it's not worth changing it separately, just checking.

1496–1503

Is there a way to test this behaviour? (self-referencing phis)

1972–1979

Add a comment (at the top of the function) to explain what this function is doing?

1986

This comment can be probably removed, as it *must* be an instruction =)

2126

Spurious newline? Here and the next two)

2154–2156

I still prefer the explicit type here as it's not obvious which is (well the name implies, but still). Anyway, up to you.

2273

Thanks.

dberlin marked 7 inline comments as done.Jan 26 2017, 11:10 AM

This now depends on a fix for 31761 to be committed, but otherwise shoudl be in good shape once i added the self-reference testcase.

lib/Transforms/Scalar/NewGVN.cpp
90

fixed

351–352

yes

1496–1503

It's hard to get it to occur naturall
I believe i can add an irreducible testcase where the phis are in a cycle that resolves to themselves.

1972–1979

Done

2126

Killed

2154–2156

I put it back

dberlin marked 4 inline comments as done.
Depends on PR31761 fix now, and rebased on top of it.
- Update for review comments
- Add testcase for being optimistic on self-phis
davide accepted this revision.Jan 26 2017, 1:28 PM

LGTM (left some nits inline). You marked some earlier comments as done but the old code still shows up, probably you updated an earlier diff. Anyway, this can go in without a new round of review with the comments addressed.

lib/Transforms/Scalar/NewGVN.cpp
763–769

This #if 1 can go away, I think.

1214–1218

This can go away, no?

2342

Typo: s/dominater/dominated/

test/Transforms/NewGVN/basic-cyclic-opt.ll
230–243 ↗(On Diff #85950)

thank you very much =)

test/Transforms/NewGVN/pr31758.ll
1–19 ↗(On Diff #85950)

It seems this test is unrelated (no stores) and you already committed it, FWIW.

This revision is now accepted and ready to land.Jan 26 2017, 1:28 PM

Sorry, most of the issues here are because arc picked up the rebase, and isn't showing the fix for 31761 as the base.
(the fix is what contains the #if blocks, etc)

This revision was automatically updated to reflect the committed changes.