[LLVMdev] Alias Analysis pass ordering in LLVM (and Clang)

[Chandler Carruth]

(sorry for the wide distribution, but this impacts Clang users quite a bit)

It's come up a few times in reviews of CFL-AA (a new alias analysis for
LLVM), so I wanted to write down what I think the current state actually is
for AA pass ordering, why, and how it should look eventually. I may have
some bugs here, so please correct me if I miss anything. And I'd love
thoughts about the end state.

Today, we have a strange ordering which is primarily motivated by trying to
support both TBAA and union-based local type punning:

1) Run BasicAA. If it hits NoAlias, MustAlias, or PartialAlias, done. If it
hits MayAlias, delegate to #2.
2) See if there is scoped no-alias metadata that can produce NoAlias and
return that if so. If not, delegate to #3.
3) See if there is TBAA metadata that can produce NoAlias and return that
if so. If not, delegate to #4.
4) If using CFL-AA, ask it and use its answer as the final answer.

The primary reason for running BasicAA first is so that it can return
MustAlias for local type puns, bypassing the more strict behavior of TBAA.
Having TBAA not fire on local type puns was a critical need for the Darwin
platform and maybe for others as well. However, this implementation
strategy is problematic for a host of reasons:

a) There are other users of LLVM that might want strict TBAA, and they
can't get that today.
b) BasicAA can hit partial-alias in cases that aren't even type puns and
which either TBAA or some other more-powerful AA like CFL-AA would return
no-alias. In these cases, we produce a too-conservative answer.
c) I'm worried that BasicAA does caching that isn't valid for all possible
AA implementations.

I think we should change these things in the following way to get to a more
principled place.

First, we should make the order something a bit more obvious which has to
do with which AA passes have the most information:

1) Run the scoped no-alias AA and return any final answers it produces.
2) Run TBAA and return any final answers it produces.
3) Run CFL-AA (if enabled, or any other advanced AA implementations we
want) and return any final answers it produces (IE, anything more precise
than 'may-alias').
4) Run BasicAA and use its answer.

I then think we should teach TBAA to have an explicit flag which causes it,
when discovering a 'no-alias' result, to query BasicAA for a contradiction
of must-alias or partial-alias, and to ignore the no-alias in that case.
That should more precisely model the desired behavior of
TBAA-except-for-local-type-puns.

Finally, I think we should teach Clang to have two flags:
"-fstrict-aliasing" and '-fstrict-local-type-pun-aliasing'. By default,
strict-aliasing can imply strict-local-type-pun-aliasing. Darwin and any
other platforms that want the current aliasing behavior can make the use of
strict-aliasing by default *not* imply strict-local-type-pun-aliasing. This
would still make it available behind a flag, and let other platforms line
up the defaults in other ways that make sense to them.

Thoughts?
-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/92588819/attachment.html>