This is an archive of the discontinued LLVM Phabricator instance.

Last of the major pieces to NewGVN - yay!
ClosedPublic

Authored by dberlin on Apr 17 2017, 8:43 PM.

Details

Summary

NewGVN: Handle equivalence between phi of ops and op of phis.

This makes our GVN mostly-complete. It would be complete, modulo some
deliberate choices we make. This means it detects roughly all herband
equivalences in polynomial time, including cases notoriously hard for
other GVN's to detect. It also detects a very large swath of the
cases we currently rely on instcombine to detect that involve folding
upwards through phis.

I am still doing benchmarking, tweaking, and testing. on our current
approach, but this was getting large enough to throw up here.

Fixes PR 31125, 31463, PR 31868

Diff Detail

Repository
rL LLVM

Event Timeline

dberlin created this revision.Apr 17 2017, 8:43 PM
  • Add some more comments

Good job! How many of old gvn tests are still failing with newgvn?

include/llvm/Transforms/Scalar/GVNExpression.h
487 ↗(On Diff #95528)

member initialization instead? (bool AllRealOps = false;)

lib/Transforms/Scalar/NewGVN.cpp
1745 ↗(On Diff #95528)

does this comment still hold?

1829–1830 ↗(On Diff #95528)

The second if expression seems to be cheaper, and they seems to be independent. What about switching them?

2042 ↗(On Diff #95528)

debug?

Good job! How many of old gvn tests are still failing with newgvn?

Of them:

  1. NewGVN passes all but one or two subtest of each of them.
  2. Most of them are things we need to fix in other infrastructure (IE be able to have simplification use value numbering to ignore blocks, etc).
  3. The one significant one is that we don't insert inequalities temporarily, which means that we don't eliminate opposite icmps that are not branches.

IE we will handle:

if (a)
  if (!a)

but not:
icmp a == b
icmp a != b

NewGVN is actually on by default for a number of significant LLVM users at this point :)
It also has 15 tests that *GVN* doesn't pass.

Our goal was never to try to get every GVN test before we turned it on by default, only not regress performance :)
Most people already felt GVN did too much.
I suspect we will meet that goal.

Good job! How many of old gvn tests are still failing with newgvn?

Of them:

  1. NewGVN passes all but one or two subtest of each of them.
  2. Most of them are things we need to fix in other infrastructure (IE be able to have simplification use value numbering to ignore blocks, etc).
  3. The one significant one is that we don't insert inequalities temporarily, which means that we don't eliminate opposite icmps that are not branches.

IE we will handle:

if (a)
  if (!a)

but not:
icmp a == b
icmp a != b

NewGVN is actually on by default for a number of significant LLVM users at this point :)
It also has 15 tests that *GVN* doesn't pass.

Our goal was never to try to get every GVN test before we turned it on by default, only not regress performance :)
Most people already felt GVN did too much.
I suspect we will meet that goal.

Awesome news! I will try to fix the MemorySSA to support invariant.groups, but for that I will need your help (see the mail) :)

davide edited edge metadata.Apr 18 2017, 8:19 PM

This is really nice =)
I'll do some performance testing myself tomorrow, some comments in the meanwhile.

lib/Transforms/Scalar/NewGVN.cpp
725–729 ↗(On Diff #95528)

I see how you're looking at the RPO ordering to determine if it's a backedge, but for people reading the code for the first time, maybe we can add a longer comment (maybe an example?)

741–743 ↗(On Diff #95528)

Style'ish, ternary operator (up to you, can be a later cleanup).

2042 ↗(On Diff #95528)

DEBUG or comment out.

2087 ↗(On Diff #95528)

I think hiding getMemoryAccess in an helper is nice, but can be split.

3345 ↗(On Diff #95528)

unrelated?

3361 ↗(On Diff #95528)

unrelated?

Still tracking down all the bugs this exposes elsewhere (last count, 1 BasicAA bug, 2 instructionsimplify bugs, etc).
sigh.

  • First version of rewritten, on-demand, phi of ops. Gets rid of need for most temp instructions.

This passes bootstrap and test. I'm tuning it (we are likely to have to tune the amount of selects and adds it handles to not screw up iv analysis, etc).

Oh look, i accidentally git add'd a diff file.
Just ignore it.

(I also will clean up the dead code you see in some places)

I'm running tests on this one during the week.

  • Updated to not hash expressions twice.
davide accepted this revision.May 15 2017, 9:59 AM

LGTM. I think we can iterate on this in tree. Thank you so much for this piece of work!

lib/Analysis/BasicAliasAnalysis.cpp
686–688 ↗(On Diff #98192)

This is unrelated (but you already anticipated).

lib/Transforms/Scalar/NewGVN.cpp
2395–2397 ↗(On Diff #98192)

I starred at this very closely and I think it's correct.

This revision is now accepted and ready to land.May 15 2017, 9:59 AM
This revision was automatically updated to reflect the committed changes.