This is an archive of the discontinued LLVM Phabricator instance.

[CFLAA] Split CFL-AA into one unification-based pass and one inclusion-based pass
ClosedPublic

Authored by grievejia on Jun 30 2016, 2:58 PM.

Details

Summary

This patch renames the existing CFLAliasAnalysis pass to CFLSteensAliasAnalysis, and introduces a new pass CFLAndersAliasAnalysis. The pass name "cfl-aa" gets replaced by "cfl-steens-aa" and "cfl-anders-aa". The "use-cfl-aa" and "use-cfl-aa-in-codegen" flags gets changed from a boolean flags to enum flags (none/steens/anders).

Precision enhancements are getting more and more difficult to add to the existing CFLAliasAnalysis pass due to its unification-based nature. Since extending CFL-AA with features like field sensitivity and inclusion-based semantics won't share too much of the existing codes anyway, it's much cleaner to start anew (and perhaps factor out certain parts of the original codes that can be shared by all CFL-based alias analysis) than to keep increasing the code complexity in CFLAliasAnalysis.cpp.

The newly added pass contains only a stub implementation of alias() currently. Its body will be gradually filled out in subsequent patches.

Diff Detail

Repository
rL LLVM

Event Timeline

grievejia updated this revision to Diff 62426.Jun 30 2016, 2:58 PM
grievejia retitled this revision from to [CFLAA] Split CFL-AA into one unification-based pass and one inclusion-based pass.
grievejia updated this object.
grievejia added a subscriber: llvm-commits.

Given you basically want to reuse the graph, you should refactor that out
too.

The only difference between the steens and inclusion based ones should be
how they walk the graph and what preprocessing they do, if any.

(This also lets you layer them without having to rebuild the entire graph.

As we discussed offline, in a perfect world, you want to do something like
quickly ask the steens if they are no-alias. If it says "no-alias", you
return that, otherwise, you do inclusion based walking)

Given you basically want to reuse the graph, you should refactor that out
too.

That's the plan. I've already changed a lot of things here so it may be safer to do that in another patch.

As we discussed offline, in a perfect world, you want to do something like
quickly ask the steens if they are no-alias. If it says "no-alias", you
return that, otherwise, you do inclusion based walking)

Agreed. But for now let's build cfl-anders first before we worry about how to combine it with cfl-steens?

Cfl-anders can be implemented in various ways. We could ahead-compute everything just like what we did in cfl-steens, or like you said we could keep the cfl graph and walk it in a memoized demand-driven fashion. If we did it on-demand, we could also either put the logic that combines cfl-anders and cfl-steens into cfl-anders, or we can offload that task to the aa pass manager. It seems that there are lots of design decision to be made here, and I'm still trying to figure out what the best choice would be...

include/llvm/Analysis/CFLAndersAliasAnalysis.h
35 ↗(On Diff #62426)

Please remove

41 ↗(On Diff #62426)

Maybe take out "of sets" here, if this won't be using StratifiedSets?

include/llvm/Analysis/CFLSteensAliasAnalysis.h
64 ↗(On Diff #62426)

Looks like this comment got broken.

lib/Analysis/CFLAndersAliasAnalysis.cpp
1 ↗(On Diff #62426)

.cpp :)

12 ↗(On Diff #62426)

I think a number of CFLAndersAliasAnalysis in here should be CFLSteensAliasAnalysis

18 ↗(On Diff #62426)

please delete, or add //

lib/Analysis/CFLSteensAliasAnalysis.cpp
1 ↗(On Diff #62426)

.cpp :)

lib/CodeGen/TargetPassConfig.cpp
116 ↗(On Diff #62426)

So... Is the goal to ultimately only allow one or the other to be run per compilation? Or will we be able to e.g. throw CFLsteens before CFLanders at a later point?

grievejia marked 6 inline comments as done.Jul 1 2016, 4:52 PM
grievejia added inline comments.
include/llvm/Analysis/CFLAndersAliasAnalysis.h
41 ↗(On Diff #62426)

I would imagine that we still need some kinds of set. It won't be StratifiedSets, but it will be other set :)

lib/Analysis/CFLAndersAliasAnalysis.cpp
12 ↗(On Diff #62426)

Oops, a typical problem caused by blind search-replace...

lib/CodeGen/TargetPassConfig.cpp
116 ↗(On Diff #62426)

Yeah I agree it would be useful to be able to run cfl-anders and cfl-steens on the same pipeline.

Let me address your concern by adding another enum option "Both".

grievejia updated this revision to Diff 62576.Jul 1 2016, 5:07 PM
grievejia marked 2 inline comments as done.

Fixed broken comments and added a new option to use both variants of cfl-aa

LGTM -- will commit later today. Thanks for the patch!

This revision was automatically updated to reflect the committed changes.
llvm/trunk/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll