This is an archive of the discontinued LLVM Phabricator instance.

[PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatible with the new pass manager, and no longer relying on analysis groups.
ClosedPublic

Authored by chandlerc on Aug 17 2015, 4:43 AM.

Details

Summary
NOTE: This is a WIP patch. There are still failing and crashing tests, but this is a massive patch so I wanted to go ahead and start the review.

This builds essentially a ground-up new AA infrastructure stack for
LLVM. The core ideas are the same that are used throughout the new pass
manager: type erased polymorphism and direct composition. The design is
as follows:

  • FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function.
  • AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure.
  • All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager.
  • BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function.

All of the references to getting alias analysis results have been
updated to use the new aggregation interface. All the preservation and
other pass management code has been updated accordingly.

The way the FunctionAAResultsWrapperPass works is to detect the
available alias analyses when run, and add them to the results object.
This means that we should be able to continue to respect when various
passes are added to the pipeline, for example adding CFL or adding TBAA
passes should just cause their results to be available and to get folded
into this. The exception to this rule is BasicAA which really needs to
be a function pass due to using dominator trees and loop info. As
a consequence, the FunctionAAResultsWrapperPass directly depends on
BasicAA and always includes it in the aggregation.

This has significant implications for preserving analyses. Generally,
most passes shouldn't both preserving FunctionAAResultsWrapperPass
because rebuilding the results just updates the set of known AA passes.
The exception to this rule are LoopPass instances which need to preserve
all the function analyses that the loop pass manager will end up
needing. This means preserving both BasicAAWrapperPass and the
aggregating FunctionAAResultsWrapperPass.

Now, when preserving an alias analysis, you do so by directly preserving
that analysis. This is only necessary for non-immutable-pass-provided
alias analyses though, and there are only three: BasicAA, GlobalsAA
(formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when
needed because it (like DominatorTree and LoopInfo) is marked as
a CFG-only pass. I've expanded GlobalsAA into the preserved set
everywhere we previously were preserving all of AliasAnalysis, and I'll
be adding SCEVAA in the intersection of that with where we preserve SCEV
itself.

One significant challenge to all of this is that the CGSCC passes were
actually using the alias analysis implementations by taking advantage of
a pretty amazing set of loop holes in the old pass manager's analysis
management code which allowed analysis groups to slide through in many
cases. Moving away from analysis groups makes this problem much more
obvious. To fix it, I've leveraged the flexibility the design of the new
PM components provides to just directly construct the relevant alias
analyses for the relevant functions in the IPO passes that need them.
This is a bit hacky, but should go away with the new pass manager, and
is already in many ways cleaner than the prior state.

Another significant challenge is that various facilities of the old
alias analysis infrastructure just don't fit any more. The most
significant of these is the alias analysis 'counter' pass. That pass
relied on the ability to snoop on AA queries at different points in the
analysis group chain. Instead, I've built printing functionality
directly into the aggregation layer.

Depends on D12075

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 32290.Aug 17 2015, 4:43 AM
chandlerc retitled this revision from to [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatible with the new pass manager, and no longer relying on analysis groups..
chandlerc updated this object.
chandlerc added a subscriber: llvm-commits.
chandlerc updated this revision to Diff 32291.Aug 17 2015, 4:46 AM

Update with clang-format fixes.

chandlerc updated this revision to Diff 32498.Aug 18 2015, 8:57 PM

Complete all of the porting, wire up all the pass preservation semantics, fix
all of the test cases, etc. Also rebase onto top-of-tree which includes several
fixes needed to get the AA stuff working.

This patch now passes all tests and could be landed. The only substantial
feature (that I'm aware of) missing is a repalcement for AliasAnalysisCounter.
I'd like to do that in a follow-up patch as no tests actually need it.

Please review! (Seriously, the sooner the better, this thing is a nightmare to
rebase...)

chandlerc updated this revision to Diff 32499.Aug 18 2015, 8:59 PM

Now without random files that should never have been in the patch.

hfinkel added inline comments.
include/llvm/Analysis/AliasAnalysis.h
163 ↗(On Diff #32499)

Which version of MSVC? I'd like that recorded if possible so that when we eventually drop support for that version we can remove the workarounds.

lib/Analysis/AliasAnalysis.cpp
402 ↗(On Diff #32499)

This design means that we cannot add new AA passes, nor change their order via the pass-manager interface, because it is really hard-coded here for a closed universe of AA passes. Is this really necessary? I'd prefer we have some kind of registration interface.

lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #32499)

What is this doing? (when would we not have an FAR?

777 ↗(On Diff #32499)

Why is it not an assert? It just returns MayAlias otherwise regardless.

813 ↗(On Diff #32499)

Same here.

863 ↗(On Diff #32499)

Same here.

lib/Transforms/InstCombine/InstructionCombining.cpp
3080 ↗(On Diff #32499)

Why is this here specifically?

3106 ↗(On Diff #32499)

Do you also need?

INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)

since you added it as required above?

lib/Transforms/Scalar/Float2Int.cpp
65 ↗(On Diff #32499)

I don't understand why you've added this to some passes and not others.

lib/Transforms/Scalar/GVN.cpp
742 ↗(On Diff #32499)

Same question here about GlobalsAAWrapperPass and the INITIALIZE_* macro.

lib/Transforms/Scalar/LICM.cpp
127 ↗(On Diff #32499)

I understand that SCEVAA needs to be added, because of the LPM invalidation restrictions, but why is GlobalsAAWrapperPass here and not in IndVarSimplify?

chandlerc marked 2 inline comments as done.Aug 19 2015, 1:05 AM
chandlerc added inline comments.
include/llvm/Analysis/AliasAnalysis.h
163 ↗(On Diff #32499)

We don't do this elsewhere. This comment is essentially verbatim from everywhere else we've commented this. We can go and update all of them, but please not in this patch.

lib/Analysis/AliasAnalysis.cpp
402 ↗(On Diff #32499)

First off, I feel like you're missing a key point in the design.

The *infrastructure* here doesn't hardcode anything. It is only the "factory" that we use with the legacy pass manager that hard codes a list of the AAs. The reason is because it is expedient. I'm really uninterested in building complex registration facilities for the legacy pass manager, especially as it is *exactly* such a registration facility (and all of its bugs, limitations and problems) that I'm removing with this patch. =/

I've also arranged for it to be OK to add experimental, disabled, and otherwise unused AAs here so we can still experiment and develop things in-tree.

The new pass manager will be able to use all this infrastructure to build a custom set of alias analyses easily. We will still probably "hard code" a list *somewhere*, but it will be much higher up the stack in the Passes library. And there, rather than actually hard coding the list, my plan was to parse the list out of the command line.

The core idea of having a single place that *specifically* spells out what alias analyses are used and exactly what order was actually a design point that I discussed with several folks, yourself included, and I thought was an explicit desire. Personally, I find using a registration system to establish the layering of alias analyses extremely brittle and confusing.

lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #32499)

You can create a BasicAAResults object without using the FunctionAAResults aggregation layer. I didn't want to bake the cycle into the entire implementation. I can go back and do that if you think it's the right thing, but it makes this not *really* an analysis pass any longer, which I find very unfortunate.

777 ↗(On Diff #32499)

I really didn't want to be adding asserts that might crash in the wild and might make a well over 100 file patch get reverted. ;]

813 ↗(On Diff #32499)

Same answer.

863 ↗(On Diff #32499)

And same answer.

lib/Transforms/InstCombine/InstructionCombining.cpp
3080 ↗(On Diff #32499)

I explained this in my summary: everywhere we previously were preserving the analysis group I have added preservation of globals-aa to preserve behavior prior to my patch.

3106 ↗(On Diff #32499)

Yes, good catch. I've added it.

lib/Transforms/Scalar/Float2Int.cpp
65 ↗(On Diff #32499)

As I explained in the summary (i think?) I've added it everywhere that previously preserved AliasAnalysis.

Note that it *seems* to have been removed from some, but those are MachineFunctionPasses and I added the preservation to the common logic for all of those.

I've checked, and I *think* I got this right, but if there is an inconsistency there, let me know.

lib/Transforms/Scalar/GVN.cpp
742 ↗(On Diff #32499)

Done here as well.

lib/Transforms/Scalar/LICM.cpp
127 ↗(On Diff #32499)

Because IndVarSimplify did not historically preserve AliasAnalysis and so preserving GlobalsAAWrapperPass would change behavior.

I think every function pass can preserve GlobalsAAWrapperPass after my changes to make it more conservative, but I've tried very hard to change is little functionality as conceivably possible with this patch.

Preserving SCEVAA above is actually a bug, and I've removed it.

chandlerc updated this revision to Diff 32518.Aug 19 2015, 1:32 AM
chandlerc marked 2 inline comments as done.

Update rebasing to head and addressing a few bugs spotted by Hal in review.

hfinkel added inline comments.Aug 19 2015, 1:43 AM
include/llvm/Analysis/AliasAnalysis.h
163 ↗(On Diff #32499)

We don't do this elsewhere.

Well, that's a mistake, but I'm fine with consistency. Let's update the comments in a separate change.

lib/Analysis/AliasAnalysis.cpp
402 ↗(On Diff #32499)

Okay; this is fine. But, please add a comment to this function (and something in getAnalysisUsage) explaining that this fixed list/ordering is relevant only for the legacy pass manager.

lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #32499)

Okay, please add a comment explaining this. The key question is this: If I were looking at this code in order to write new code in BasicAAResult, or in some other *AAResult class, would I need to do this?

777 ↗(On Diff #32499)

Okay ;)

lib/Transforms/InstCombine/InstructionCombining.cpp
3106 ↗(On Diff #32499)

Please check them all; I stopped commenting on them at some point.

lib/Transforms/Scalar/LICM.cpp
127 ↗(On Diff #32518)

Preserving SCEVAA above is actually a bug, and I've removed it.

Why was it a bug? We preserve SCEV here, and we also used to preserve the AA group.

lib/Transforms/Scalar/LoopDeletion.cpp
71 ↗(On Diff #32518)

Do you need an INITIALIZE_ for SCEVAA here?

chandlerc marked 23 inline comments as done.Aug 19 2015, 3:05 AM
chandlerc added inline comments.
lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #32518)

I've added the comment to getFunctionAAResults in AAResultBase so that hopefully it is a bit more discoverable than this. Let me know if that comment isn't sufficient.

lib/Transforms/Scalar/LICM.cpp
127 ↗(On Diff #32518)

We should (and do) preserve SCEVAA *here*. This is in LICM that preserved both AliasAnalysis and ScalarEvolution before.

We shouldn't preserve (and now don't) SCEVAA *above* as part of IndVarSimplify because that pass *did not* preserve AliasAnalysis previously.

I had let a large number of erroneous additional preservation of SCEVAA in. I've fixed all of it and made everything much more consistent now. Sorry for the noise there.

chandlerc updated this revision to Diff 32528.Aug 19 2015, 3:06 AM
chandlerc marked an inline comment as done.

Address more feedback from Hal, and notably make the preservation of SCEVAA
much more conservative for this iteration.

chandlerc updated this revision to Diff 32666.Aug 20 2015, 1:13 AM

Rebase as the prerequisite patches have landed. Also fix a build break.

chandlerc updated this revision to Diff 32896.Aug 21 2015, 8:25 PM

Renamed everything to use a shorter name (AAResults and co.).

This reflects that this isn't really about a *function* AA, its about an
intra-procedural AA which is thoe only way we know how to formulate AA right
now in LLVM. If we ever grow a truly inter-procedural AA, it'll like need
a very different interface (that we can't predict today).

hfinkel added inline comments.Aug 27 2015, 10:49 AM
lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #33186)

That comment is good, but let me clarify something: Is this the general pattern necessary for recursion in AA? Specifically, if there is an aggregation object, then recurse through the aggregation object so the entire chain participates, otherwise, just recurse directly? If this is the general pattern, then we should add it as a utility function and not repeat it everywhere it might be necessary. In short, what to do when one AA can reduce an aliasing query to another one on some underlying pointers should be something that is clear within the interface.

1237 ↗(On Diff #32499)

Shouldn't this, for example, also use the same potential-aggregator recursion pattern?

chandlerc added inline comments.Aug 27 2015, 11:22 AM
lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #33186)

Any suggestions about *how* to factor this out? I tried to come up with a way, and it involved horrible templates and pointers-to-members or std::bind craziness. I'll try again myself...

1237–1238 ↗(On Diff #33186)

I really don't know... The old code had different fallback strategies and it wasn't always clear to me whether they would fully recurse or partially recurse, etc.

In particular, does this inf-loop? Anyways, I'll try to make this more rigorous. I need to find out if it would infloop and the old code was trying to delegate to the *other* AAs by doing this, and if so, have it return MayAlias.

hfinkel added inline comments.Aug 27 2015, 12:07 PM
lib/Analysis/BasicAliasAnalysis.cpp
603 ↗(On Diff #33186)

Maybe just type out the functions? I've always found this pattern difficult to template (as you point out, you can do it with pointers-to-members, etc., but the number of tokens in the template glue relative to the underlying logic might be quite large).

My concern is not that that the if statement is a lot of code to copy-and-paste, but that because code might appear functional without it (by just hard coding a direct recursion within the pass), it could easily be forgotten unless it is somehow builtin to the interface that the existing implementations all use.

1237–1238 ↗(On Diff #33186)

As far as I can tell, in the old system, calling the base class here (AliasAnalysis::alias), would cause the query to continue up the chain with the new pointers (in this case, likely the same as the original pointers, except perhaps with casts stripped).

So maybe I'm confused about what this code does, but it looks like AAResultBase::alias just returns MayAlias, and that does not match the old behavior.

chandlerc updated this revision to Diff 33723.Sep 1 2015, 1:36 PM

Update to use a proxy to handle the delegation to either self or an aggregation
of AA results.

Also, rebase and fix up the edits that have come in to basic-aa while the patch
has been out for review.

chandlerc marked 4 inline comments as done.Sep 1 2015, 1:43 PM

Hopefully we're really close at this point? I think I've gotten everything addressed here.

lib/Analysis/BasicAliasAnalysis.cpp
675 ↗(On Diff #33723)

I've built a tiny proxy class to model this and now we get the proxy class and call through it. This kept the interface consistent but hides the delegation logic as suggested. I can add comments there if you have anywhere you think they would help clarify.

1346–1348 ↗(On Diff #33723)

So, I'm now pretty sure that this does match the old behavior.

Returning MayAlias here causes the AAResults aggregation layer to continue to the next result it has available, and query that layer. So in essence, returning MayAlias triggers the expected behavior.

There is one difference here, but it shouldn't be observable. In the old system, BasicAA's cache ended up populated by the results provided from querying other AAs. With my change, we will just cache "MayAlias" and then directly query the next layer. In essence, this change may cause us to query more layers of the AA stack, but I would not expect that to change behavior or to be a significant compile time shift as all the other layers are much faster than BasicAA already.

Does this make more sense?

I would still like to take the caching out of BasicAA and teach the aggregation layer to do all the caching, which would recover the compile time performance (and get more performance as well) but I think that should be in a follow-up patch.

hfinkel added inline comments.Sep 1 2015, 2:02 PM
lib/Analysis/BasicAliasAnalysis.cpp
675 ↗(On Diff #33723)

Looks good.

1346–1348 ↗(On Diff #33723)

So, I'm now pretty sure that this does match the old behavior.

Returning MayAlias here causes the AAResults aggregation layer to continue to the next result it has available, and query that layer. So in essence, returning MayAlias triggers the expected behavior.

There is one difference here, but it shouldn't be observable. In the old system, BasicAA's cache ended up populated by the results provided from querying other AAs. With my change, we will just cache "MayAlias" and then directly query the next layer. In essence, this change may cause us to query more layers of the AA stack, but I would not expect that to change behavior or to be a significant compile time shift as all the other layers are much faster than BasicAA already.

Does this make more sense?

I think I understand what you're saying, but I'm not convinced that this is correct. This is the mechanism that BasicAA uses to do recursive analysis, including based on other passes. So let's say that we have both BasicAA and CFLAA. Given some query on two GEPs, BasicAA might be able to reduce that query to some query on the base pointers of those GEPs, and then recurse up the chain allowing CFLAA to determine that the base pointers don't alias. Thus, both BasicAA and CFLAA can work together on the query, producing an answer neither would have been able to produce alone.

It seems important to keep the system's ability to function this way.

I would still like to take the caching out of BasicAA and teach the aggregation layer to do all the caching, which would recover the compile time performance (and get more performance as well) but I think that should be in a follow-up patch.

Yes, but you'd also need to be careful about the optimistic phi-based analysis that rely on the caching for correctness (to prevent infinite recursion).

chandlerc updated this revision to Diff 34187.Sep 7 2015, 9:41 PM
chandlerc marked an inline comment as done.

Update to a fresh baseline, and add logic to recurse back through the entire
set of AA results within BasicAA. This should more accurately follow the
original logic of the analysis group implementation.

At last updated. Please let me know if there are any comments that you still want a reply to, I've somewhat lost track at this point.

lib/Analysis/BasicAliasAnalysis.cpp
1346–1348 ↗(On Diff #33723)

After entirely too much debugging considering the simplicity of the change, I've done this.

I don't think it matters at all though. I'll go back to my original claim -- this doesn't matter. Note that we don't recurse with O1 and O2 here which are the result of GetUnderlyingObject, and in fact we can't as that would invalidate the sizes. We recurse on V1 and V2. The only effect this has is to recurse after stripping pointer casts, which I would expect any AA pass to do itself... But perhaps they do not. Anyways, I think this faithfully achieves what you were looking for here. Let me know what you think.

hfinkel accepted this revision.Sep 8 2015, 3:57 PM
hfinkel added a reviewer: hfinkel.
hfinkel added inline comments.
lib/Analysis/BasicAliasAnalysis.cpp
1346–1348 ↗(On Diff #33723)

It matters because aliasCheck is also called from aliasGEP, aliasSelect and aliasPHI in order to recurse on underlying pointers as determined by those functions. As you say, at the top level, it has indeed only stripped casts, but that's not the important case.

In any case, let's see where this takes us... LGTM. Thanks for all of your work on this!

This revision is now accepted and ready to land.Sep 8 2015, 3:57 PM
This revision was automatically updated to reflect the committed changes.
llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp