This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Use PhiValuesAnalysis if available when handling phi alias
ClosedPublic

Authored by john.brawn on Mar 16 2018, 7:06 AM.

Details

Summary

By using PhiValuesAnalysis we can get all the values reachable from a phi, so we can be more precise instead of giving up when a phi has phi operands. We can't make BaseicAA directly use PhiValuesAnalysis though, as the user of BasicAA may modify the function in ways that PhiValuesAnalysis can't cope with.

For this optional usage to work correctly BasicAAWrapperPass now needs to be not marked as CFG-only (i.e. it is now invalidated even when CFG is preserved) due to how the legacy pass manager handles dependent passes being invalidated, namely the depending pass still has a pointer to the now-dead dependent pass.

Diff Detail

Event Timeline

john.brawn created this revision.Mar 16 2018, 7:06 AM
john.brawn planned changes to this revision.Mar 16 2018, 7:07 AM

What you've implemented (or trying to) is really the SCC algorithm from from "Simple and Efficient
Construction of Static Single Assignment Form" at
http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf

That will find the values you seek here :)
(you don't have to do the recursive simplification it does)

https://reviews.llvm.org/D28934 has a version of the SCC finder you can
borrow if you want (TarjanSCC class)

My primary concern here is that SimplifyInstruction needs to be "constant" time; if you put a linear traversal over the entire function here, you'll cause compile-time explosions all over the compiler.

Yeah, that is why on the other thread i suggested it probably makes sense
to just change how AA is doing it rather than all simplification users

I also agree that InstCombine is expected to have O(1) complexity of its operations, and this code attempts to traverse the entire tree consisting of Phi nodes which is O(N), and it can actually start from any node of this tree. I don't feel that this is right.

lib/Analysis/InstructionSimplify.cpp
3956 ↗(On Diff #138694)

Please use SmallPtrSet here.

3961 ↗(On Diff #138694)

Before that, assert that PHINodesSeen does not contain ThisPN?

3982 ↗(On Diff #138694)

Why not else if instead of continue?

3989 ↗(On Diff #138694)

{} not needed.

john.brawn retitled this revision from [InstSimplify] Look at the whole PHI graph when simplifying a PHI node to [BasicAA] Relax restriction on PHI node handling..
john.brawn edited the summary of this revision. (Show Details)

I've gone for the approach of doing this in alias analysis, which works without any test failures. I'd also considered doing it in GetUnderlyingObject, or adjusting aliasCheck to use GetUnderlyingObjects instead, but the problem there is that they look also through GEPs and there would have to be a parallel change to DecomposeGEPExpression to add a bunch of PHI handling there as well.

mkazantsev added inline comments.Mar 20 2018, 4:09 AM
lib/Analysis/BasicAliasAnalysis.cpp
1538

Please follow LLVM naming convention.

1599

V1Srcs.empty()?

1599

How do we know that V1Srcs is not empty at this point?

john.brawn added inline comments.Mar 20 2018, 11:15 AM
lib/Analysis/BasicAliasAnalysis.cpp
1599

For that to happen we would have to have a phi with no underlying non-phi values, which I'm pretty sure can only happen in unreachable blocks, e.g. something like

define void @fn(i32* %p) {
entry:
  br label %exit

exit:
  ret void

unreachable:
  %phi = phi i32* [ %phi, %unreachable ]
  %load1 = load i32, i32* %p, align 4
  %load2 = load i32, i32* %phi, align 4
  %cmp = icmp ne i32 %load1, %load2
  br i1 %cmp, label %exit, label %unreachable
}

Which we shouldn't ever normally see, but it is possible to manually craft such IR (e.g. the above) and it currently causes a crash so I'll adjust it to fix that.

Address review comments.

I don't see any more problems, but I'm not the best person to give reviews in BasicAA. Please wait for someone else to take a look.

I've added some people who made commits to BasicAA recently. Could you please take a look into this patch? It has been on review for a while with no progress.

xbolva00 accepted this revision.Apr 25 2018, 11:14 AM
This revision is now accepted and ready to land.Apr 25 2018, 11:14 AM

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

This revision now requires review to proceed.Apr 25 2018, 1:29 PM

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

Yes, this comes from GVN where it temporarily introduces phi nodes like this that are later removed, but which in the meantime prevent PRE from happening because of this inaccurate alias analysis. I'd previously gone for the approach of fixing this in GVN in D44160, but the conclusion there was to do it in alias analysis.

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

If I understand you correctly, you're suggesting adding a new alias analysis pass which just handles phis (but by analyising them forwards, instead of backwards as BasicAA does), yes? This alias analysis would have to make use of the results of other alias analyses though: what we're doing is comparing a phi P against a value V by finding the underlying values of P then calling aliasCheck for those values and V. Is one alias analysis using the results of another alias analysis something that works?

Actually thinking about this while writing the above, it would probably make more sense to do things the other way around: have an analysis which gets the underlying values for a phi, and have BasicAA use that. So instead of building up V1Srcs here, we would instead do something like V1Srcs = PhiAnalysis.getUnderlyingValues(PN). I think that would be better?

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

Yes, this comes from GVN where it temporarily introduces phi nodes like this that are later removed, but which in the meantime prevent PRE from happening because of this inaccurate alias analysis. I'd previously gone for the approach of fixing this in GVN in D44160, but the conclusion there was to do it in alias analysis.

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

If I understand you correctly, you're suggesting adding a new alias analysis pass which just handles phis (but by analyising them forwards, instead of backwards as BasicAA does), yes?

Yes.

This alias analysis would have to make use of the results of other alias analyses though: what we're doing is comparing a phi P against a value V by finding the underlying values of P then calling aliasCheck for those values and V.

FWIW: What we do is actually not great.
What you really *want* to do is build the SCC's formed solely by the phi nodes so you collapse any cycles and only have to look at the operands that aren't phis.
You can see an example of this kind of algorithm in the scc based phi minimization here:
https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf

Then, somewhat similar to what you see driving that, the outerops is the set of stuff to check what the phi can alias.

Is one alias analysis using the results of another alias analysis something that works?

Yes, this works fine, AFAIK. We definitely do it right now :)

Actually thinking about this while writing the above, it would probably make more sense to do things the other way around: have an analysis which gets the underlying values for a phi, and have BasicAA use that. So instead of building up V1Srcs here, we would instead do something like V1Srcs = PhiAnalysis.getUnderlyingValues(PN). I think that would be better?

This is actually not possible, but that isn't going to be obvious to someone who hasn't delved into this.

Let me also try to back up and give a little context and see if you still come to that answer:
The way it works right now is that the AA code walks through a hierarchy of AA analysis, and keeps asking each until it gets NoAlias or MustAlias.
BasicAA is one of those passes.

Because of <technical reasons not worth getting into>, it used to be hard to build another AA that reused results from another analysis, and so people shoved more and more complex stuff stuff in BasicAA :)

Unfortunately, BasicAA is meant to be stateless and explicitly does no caching, and so these expensive computations occur every time you ask it an aliasing question.
You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.
The long term goal is to move those expensive computations somewhere else where they can be cached, and where the AA can be invalidated.

The personal way i viewed it was you have something like:

BasicAA <- gives simple, stateless AA answers that are ideally, constant time.
<One or more CachingAA depending on what we discover as we do this > <- gives the answers that are currently linear time or worse.

Right now, because BasicAA is so slow, it's at the *bottom* and not *the top*. We actually ask everything *before* we ask BasicAA, because it's N^2 (excepting depth limiting trying to keep it linear).

In this new world orders, BasicAA is at the top, doing quick checks, and checks get more expensive as you get down (similar to dependence analysis)

You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.

But it looks like that's already happening? Looking at BasicAA::run it uses DominatorTreeAnalysis, and BasicAAResult::invalidate returns true if DominatorTreeAnalysis is invalidated.

Also, with regards to invalidation, how is this supposed to happen in the middle of a pass? What's happening in GVN currently is:

  • A load is determined to be partially redundant
  • A chain of phis is inserted, which ends up using the load
  • The load is removed and all uses replaced with the end of the phi chain, which causes the phi chain to contain a loop with only one underlying value
  • GVN then goes on to analyze another load which used to use the value of the first load but which now uses this phi chain
  • GVN asks MemoryDependenceAnalysis about the dependencies of this load
  • MemoryDependenceAnalysis asks AAResults
  • AAResults asks BasicAAResult
  • BasicAAResult now has to figure out this phi chain

If we have some analysis which looks at phis and caches the results (either PhiAnalysis calculating the underlying values of phis, or PhiAA calculating what phis alias with) then it needs to be recalculated somewhere between GVN removing the load and AAResults being asked about the phi that's been inserted. How is this supposed to happen?

You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.

But it looks like that's already happening?

Not really intentionally, it just grew this way :-)

Looking at BasicAA::run it uses DominatorTreeAnalysis, and BasicAAResult::invalidate returns true if DominatorTreeAnalysis is invalidated.

Right, but that doesn't help your problem below either :)

Also, with regards to invalidation, how is this supposed to happen in the middle of a pass?

Which?
BasicAA invalidation or PhiAA invalidation?
Because you actually have the same problem below if the assumptions or dominator tree change in the middle of GVN.
Nothing will invalidate BasicAA in that case right now.
In that regard, we are not actually worse off.

What's happening in GVN currently is:

  • A load is determined to be partially redundant
  • A chain of phis is inserted, which ends up using the load
  • The load is removed and all uses replaced with the end of the phi chain, which causes the phi chain to contain a loop with only one underlying value
  • GVN then goes on to analyze another load which used to use the value of the first load but which now uses this phi chain
  • GVN asks MemoryDependenceAnalysis about the dependencies of this load
  • MemoryDependenceAnalysis asks AAResults
  • AAResults asks BasicAAResult
  • BasicAAResult now has to figure out this phi chain

If we have some analysis which looks at phis and caches the results (either PhiAnalysis calculating the underlying values of phis, or PhiAA calculating what phis alias with) then it needs to be recalculated somewhere between GVN removing the load and AAResults being asked about the phi that's been inserted.

Again, besides BasicAA *already* having this problem (and it just happens that you aren't touching a part that uses assumes or domtree), memdep has this problem too, and tries to provide an incremental invalidation/update interface.
Similarly, we would do the same for PhiAA.
In this case, MemDep's invalidation interface would invalidate PhiAA.
This also assumes a bunch of stuff (for example, that more powerful analysis can't resolve this regardless of the load being there, etc)

How is this supposed to happen?

Nothing here, in any way, is an entirely well designed and architected complete solution to these problems :)
You are welcome to suggest one :)

After some tinkering I've come up with the following solution (I have something that seems to work, but it needs cleaning up and testing):

  • Add a PhiAnalysis analysis pass which returns a PhiInfo
  • PhiInfo::getUnderlyingPhiValues takes a PHINode and returns the set of non-phi values reachable from that phi
  • PhiInfo stores a map of PHINode->values which is initially empty, but is incrementally updated whenever getUnderlyingPhiValues is called on a phi we haven't yet calculated
  • BasicAA uses PhiAnalysis if it's available
  • When it is BasicAAResults::aliasPHI populates V1Srcs from getUnderlyingPhiValues, otherwise it does what it currently does
  • MemoryDependenceAnalysis uses PhiAnalysis, which then makes it available to BasicAA
  • MemoryDependenceResults::removeInstruction clears the PhiInfo map, to make sure later queries are correct

Doing all this gets me what I want, which is GVN getting correct aliasing information for the phis that it inserts. I've avoided doing this by adding another alias analysis to basically limit how much work I need to do to get this working, and it means whoever does do that in the future can just make the new alias analysis use PhiAnalysis for that part of it. Also there's maybe other parts of the compiler that want this kind of information.

Does this seem reasonable?

sebpop added a subscriber: sebpop.May 22 2018, 9:32 AM

After some tinkering I've come up with the following solution (I have something that seems to work, but it needs cleaning up and testing):

  • Add a PhiAnalysis analysis pass which returns a PhiInfo

I think this makes sense as Danny suggested to move everything that is not constant time
away from BasicAA in different analysis passes whose results could be cached and invalidated.

  • PhiInfo::getUnderlyingPhiValues takes a PHINode and returns the set of non-phi values reachable from that phi

I think this makes sense as it goes in the same direction where Danny was pointing earlier:
"What you really *want* to do is build the SCC's formed solely by the phi nodes so you collapse any cycles and only have to look at the operands that aren't phis."

  • PhiInfo stores a map of PHINode->values which is initially empty, but is incrementally updated whenever getUnderlyingPhiValues is called on a phi we haven't yet calculated
  • BasicAA uses PhiAnalysis if it's available
  • When it is BasicAAResults::aliasPHI populates V1Srcs from getUnderlyingPhiValues, otherwise it does what it currently does
  • MemoryDependenceAnalysis uses PhiAnalysis, which then makes it available to BasicAA
  • MemoryDependenceResults::removeInstruction clears the PhiInfo map, to make sure later queries are correct

Doing all this gets me what I want, which is GVN getting correct aliasing information for the phis that it inserts. I've avoided doing this by adding another alias analysis to basically limit how much work I need to do to get this working, and it means whoever does do that in the future can just make the new alias analysis use PhiAnalysis for that part of it. Also there's maybe other parts of the compiler that want this kind of information.

Does this seem reasonable?

I think this proposal is reasonable, although Danny should comment on it.
In the mean time, could you please post the updated patch? Thanks!

A bit of an update on this: instead of the circuitous route of having PhiInfo be optionally used by BasicAA then having MemoryDependenceAnalysis use PhiInfo in order to make it available to BasicAA I've gone for making BasicAA use it directly but have PhiInfo use ValueHandles (in a way rather similar to AssumptionCache does) in a way that gets it automatically updated if the function changes. This makes everything much simpler in terms of how it gets used, but it's been taking a while to get the implementation right.

john.brawn retitled this revision from [BasicAA] Relax restriction on PHI node handling. to [BasicAA] Use PhiValuesAnalysis when handling phi alias.
john.brawn edited the summary of this revision. (Show Details)

Modify this so that it uses the PhiValuesAnalysis pass added by D47893. This patch also now depends on D44160 as this modifies a test added by that.

john.brawn retitled this revision from [BasicAA] Use PhiValuesAnalysis when handling phi alias to [BasicAA] Use PhiValuesAnalysis if available when handling phi alias.
john.brawn edited the summary of this revision. (Show Details)

It turns out that we can't safely use PhiValuesAnalysis always from BasicAA, so instead a pass has to explicitly use it if it knows it is safe. I have a follow-on patch from this to make MemoryDependenceAnalysis do that, but it's not quite finished yet (I need to adjust some tests).

Meinersbur resigned from this revision.Jun 21 2018, 10:49 AM
Meinersbur removed a reviewer: Meinersbur.

Making memory dependence analysis use phi values analysis so basicaa can use it is in D48489.

john.brawn updated this revision to Diff 154224.Jul 5 2018, 6:47 AM
john.brawn edited the summary of this revision. (Show Details)
john.brawn set the repository for this revision to rL LLVM.

@brzycki pointed out to me a test case where we get a crash with this patch which turns out to be due to BasicAA using stale PhiValuesAnalysis results due to how the legacy pass manager handles pass dependencies. Updated this patch to fix that problem by marking BasicAA as not CFG-only.

Rebased patch on top of recent changes.

We have a check in aliasSameBasePointerGEPs to avoid PR32314 (which I'll glibly summarize as: we need to be careful about looking through PHIs so that we don't, without realizing it, end up comparing values from different loop iterations). The fact that this looks back through an unknown number of PHIs makes me concerned that we'll get into a similar situation.

I apologize for ignoring this review for so long, but I think that this is really important. Even with the PR32314 check currently there, I suspect that the fundamental algorithm for looking back through PHIs in BasicAA is still not sound, and we need to be careful going forward. As such, I'd like to see this patch updated with additional comments explaining:

  1. Can we get back values from different loop iterations from PhiValues.
  2. If so, is there special care that must be taken in handling them.
  3. Are we currently doing what's necessary to handle them correctly.

Thanks!

We have a check in aliasSameBasePointerGEPs to avoid PR32314 (which I'll glibly summarize as: we need to be careful about looking through PHIs so that we don't, without realizing it, end up comparing values from different loop iterations). The fact that this looks back through an unknown number of PHIs makes me concerned that we'll get into a similar situation.

I apologize for ignoring this review for so long, but I think that this is really important. Even with the PR32314 check currently there, I suspect that the fundamental algorithm for looking back through PHIs in BasicAA is still not sound, and we need to be careful going forward. As such, I'd like to see this patch updated with additional comments explaining:

  1. Can we get back values from different loop iterations from PhiValues.
  2. If so, is there special care that must be taken in handling them.
  3. Are we currently doing what's necessary to handle them correctly.

Thanks!

I've been looking looking around basicaa for a while and how it's handling this kind of thing, and I think the short answer here is that this patch means we're doing more of the same thing that we're already doing so it doesn't introduce any new bugs but could possibly make already-existing bugs (if there are any) reveal themselves in more situations, but if so the fix would be elsewhere not here.

The long answer (which I've written mostly to make sure I have my own thoughts in order, so possibly not especially coherent):

The general structure of BasicAAResult::aliasCheck, the main alias-checking function, seems to be:

  • See if, by looking at V1 and V2 as atomic things, we can determine if V1 and V2 definitely point to either the same or different things.
  • If not, and V1 or V2 is a gep, phi, or select, try breaking up V1 or V2 into component parts and comparing it with the other.
  • If that doesn't give us MustAlias or NoAlias, go check the other alias analyses.

What we have to be careful about then is that we don't have a situation where we break up V1 into individual components, see that there's no alias with V2, then conclude that there's no alias between V1 and V2 as a whole but actually there is.

Going and looking at PR32314 specifically, a simplified version of that is

loop:
 %phi1 = phi [ undef, %entry ], [ %gep2, %loop ]
 %phi2 = phi [ 1, %entry ], [ %inc, %loop ]
 %inc = add %phi2, 1
 %sub = add %phi2, -1
 %gep1 = getelementptr %arr, %sub
 %gep2 = getelementptr %arr, %phi2
 store %foo, %gep1
 %bar = load %phi1

The problem here is that for the same value of %phi2, %gep1 and %gep2 point to different memory locations, but when comparing %phi1 and %gep1 we can't just say "given that %phi's only value is %gep2, we can check if %phi1 and %gep1 alias by checking if %gep1 and %gep2 alias" because the value of %phi2 in the context of the value of %gep2 on the loop back-edge is different to the value of %phi2 in the %gep1 not on that back-edge.

The question then is: is it the responsibility of the phi node handling when it's doing the recursive aliasCheck to do something special to handle this, or is it the responsibility of aliasCheck to realise that the same sub-expression in V1 and V2 may have different values? Currently, it looks like it's the responsibility of aliasCheck, or at least the fix for PR32314 was done by making a specific part of aliasSameBasePointerGEPs aware that the same phi in a subexpression of the indices of two geps could have different values.

So, getting back to this patch, what's changed? Instead of just looking at the direct incoming values of a phi, and giving up if one of those is a phi, we get the total set of non-phi values gotten by traversing the phi tree. From the perspective of avoiding path-sensitive value difference there's no change to before: it's up to the recursive aliasCheck call to get things right, and doing things differently in this way doesn't fundamentally change things as far as I can tell: we either get it right, or we get it wrong, and if we get it wrong there would have been some other situation where originally we would have got it wrong as well.

So to answer your specific questions:

Can we get back values from different loop iterations from PhiValues.

Yes, but that's no change to how things were before.

If so, is there special care that must be taken in handling them.

Nothing that we didn't already need to do.

Are we currently doing what's necessary to handle them correctly.

I assume so, but the necessary handling would be in the recursive aliasCheck call, not here.

sebpop accepted this revision.Jul 27 2018, 12:14 PM

Looks good to me. Thanks!

This revision is now accepted and ready to land.Jul 27 2018, 12:14 PM
This revision was automatically updated to reflect the committed changes.

@brzycki pointed out to me a test case where we get a crash with this patch which turns out to be due to BasicAA using stale PhiValuesAnalysis results due to how the legacy pass manager handles pass dependencies. Updated this patch to fix that problem by marking BasicAA as not CFG-only.

Would you mind sharing this test case if this is still the case?
I'd like to understand if we can lift the restriction of marking BasicAA as not CFG-only, and I see no test crashes from making this change at ToT.
Did the changes in https://reviews.llvm.org/rL340613 resolve this?

Herald added a project: Restricted Project. · View Herald TranscriptFeb 6 2020, 1:46 PM