Page MenuHomePhabricator

[GVN] Don't use the eliminated load as an available value in phi construction
ClosedPublic

Authored by john.brawn on Mar 6 2018, 9:27 AM.

Details

Summary

In ConstructSSAForLoadSet if an available value is actually the load that we're doing SSA construction to eliminate, then we can omit it as SSAUpdate will add in the value for the phi that will be replacing it anyway. This can result in simpler IR which can allow further optimisation.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn created this revision.Mar 6 2018, 9:27 AM

To me it looks fine, but please wait for Daniel or Eli to take a look.

So this looks like a really weird optimization to avoid AA being broken.
As you say, the code it inserts will be fixed up later (and you are taking an O(1) function and making it O(N).
We should just fix AA.

It should see no difference between the two.
If we really can't fix AA, i'd like to understand why before we go this route.
Because we shouldnt' be working around these problems this way.

In particular, i feel this way because GVN should already get your case
without this.
The fact that it doesn't is an issue with AA.
Working around it like this only fixes GVN's ability to optimize this.
There will be plenty of cases something *else* could eliminate code like
that will not be able to
Fixing AA fixes it for everyone (and doesn't require pass-specific
workarounds).

So i'd like to understand what is going wrong in AA before we start trying
to hack around it in GVN.

Alias analysis uses GetUnderlyingObject from ValueTracking to figure out the 'real' value of the phi and that uses SimplifyInstruction, so I think there's where we should do this. SimplifyPHINode already handles the simple case of a single phi node, and extending it to work on a chain of phi nodes (which is what we need here) looks doable though a bit fiddly to get right in all cases.

I've posted by attempt to fix this in alias anlysis in D44564, but the problem is that it's actually InstSimplify that's the underlying thing being used to figure out the value of the PHI, and that's used all over the place and causes knock-on changes that require work to be done elsewhere.

FWIW: It's also possible to just fix AA without InstSimplify just by
replacing what it uses with something more powerful.
That would avoid disturbing the other users.

mkazantsev resigned from this revision.May 6 2018, 11:50 PM
reames added inline comments.May 9 2018, 4:55 PM
lib/Transforms/Scalar/GVN.cpp
786 ↗(On Diff #137215)

Maybe I'm missing something, but couldn't we get the same effect you're looking for by adding the check for LI as our AV into this loop? This would have the effect of telling the SSAUpdator about only one def in your example which should avoid the need for any phi creation.

Then there's no concern about change in O() since this loop is already O(ValuesPerBloc).

To be clear, I don't really care about the side effect of "fixing" AA, but reducing redundant IR always seems like a win since it's likely to let the rest of the GVN run be more effective.

john.brawn added inline comments.May 22 2018, 6:24 AM
lib/Transforms/Scalar/GVN.cpp
786 ↗(On Diff #137215)

I hadn't realised that SSAUpdater would work if you did that, but from some testing it looks like that does work. I'll update this patch to do that. It doesn't solve the problem entirely in more complicated cases though, which will need better alias analysis (which I'll continue working on).

john.brawn retitled this revision from [GVN] Detect fully redundant loads when we have more than one available value to [GVN] Don't use the eliminated load as an available value in phi construction.
john.brawn edited the summary of this revision. (Show Details)

Go with the approach of not adding the eliminated load to SSAUpdate.

john.brawn set the repository for this revision to rL LLVM.

Adjusted to require that the load must be available in the block the load is in, as in some cases not having that causes things to go wrong (test for this also added).

Sorry, thought I'd reviewed this. I apparently didn't hit submit.

lib/Transforms/Scalar/GVN.cpp
769 ↗(On Diff #152063)

Don't you need to add the original LI to the SSA updater at least once? Starting at the original block?

john.brawn added inline comments.Jul 6 2018, 4:54 AM
lib/Transforms/Scalar/GVN.cpp
769 ↗(On Diff #152063)

There's no inherent need to do that, I'm pretty sure. Adding LI to the SSA updater really means adding the value that LI will be replaced with, which is exactly what the SSA updater is itself deciding. So adding LI as available value in the block it's in is like saying "the value in this block is the value that's going to be in this block", and the SSA updater already knows that.

reames accepted this revision.Jul 20 2018, 3:25 PM

LGTM

lib/Transforms/Scalar/GVN.cpp
769 ↗(On Diff #152063)

You are correct. I was confusing myself by thinking the following two (wrong) things:

  1. That we still had to reason about potentially unavailable blocks at this point.
  2. That there might be store somewhere in the block. (Can't because otherwise we'd not have circled all the way around.)
This revision is now accepted and ready to land.Jul 20 2018, 3:25 PM
This revision was automatically updated to reflect the committed changes.