Alias Analysis pass ordering in LLVM (and Clang)

Project Infrastructure LLVM Dev List Archives
1

(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

2

From: "Chandler Carruth" <chandlerc@google.com>
To: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Daniel Berlin" <dannyb@google.com>, "Hal Finkel"
<hfinkel@anl.gov>, "George Burgess IV" <george.burgess.iv@gmail.com>, apazos@codeaurora.org, "Nick Lewycky"
<nlewycky@google.com>, "clang-dev Developers" <cfe-dev@cs.uiuc.edu>
Sent: Friday, January 16, 2015 3:52:33 PM
Subject: Alias Analysis pass ordering in LLVM (and Clang)

(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.

They might, but because I can't imagine a use case where provably-incorrect answers are desired, it seems that (b) is really the underlying issue. That having been said, there might be a significant compile-time savings if TBAA, etc. is used extensively.

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.

I'd argue that these are bugs in BasicAA that should be fixed. BasicAA, like any other AA, should only return PartialAlias when it has *proved* a partial overlap. Otherwise, it should delegate. Papering over these by flipping the pass order is not desirable -- I know you're not proposing that, but I don't view bugs in BasicAA as a good motivation for a pass-ordering change.

c) I'm worried that BasicAA does caching that isn't valid for all
possible AA implementations.

Interesting point; BasicAA's caching is supposed to serve as a guard against unbounded recursion, and is keyed off of the queried pair of AA::Location objects. I feel, however, that this must be universally valid. There is a complication, which is that Location's auxiliary metadata-based members (for TBAA, etc.) have control-flow dependencies, and so BasicAA can only cache results for locations with those members in blocks that are predecessors of the original query instructions (i.e. it can only walk up). I'm pretty sure this is what it does, but if not, there could be problems.

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.

I agree this would be cleaner.

Finally, I think we should teach Clang to have two flags:
"-fstrict-aliasing" and '-fstrict-local-type-pun-aliasing'.

To engage in some bikeshedding, I'd prefer that we have:

-fstrict-aliasing=<mode names>, where -fstrict-aliasing without a mode name has a target-dependent default, perhaps, as you've suggested. We could use a name like 'pedantic' or 'standard' for the stricter mode and 'loose' or 'heuristic' for the current mode.

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.

I'm in favor of the additional conceptual clarity this would provide, and I also like the potential compile-time savings by not aggressively computing BasicAA results when TBAA, etc. can answer the query directly.

Regardless, however, we should fix the exiting bugs in BasicAA's delegation/PartialAlias logic.

-Hal

3

(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.

Because the user want to ignore the aliases (real) or they just want
diagnostics?

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.

Are there bugs tracking them?

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.

It might be useful to collect some compile time data. The alias query cost
also depends on the type of memory references used the program. Simple
base+offset alias check is cheap. If the program has lots of accesses with
known base objects, basicaa might be the only thing needed -- pushing it to
the end of the pipeline may hurt compile time.

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.

This is a good idea. In general, the aliaser can have two chains of alias
infos. One chain consists of analysis based alias results while the other
chain is assertion/language rule based.

Definitive results from one AA can skip the rest of the AAs in the same
chain, but may need to go through the other chain if the option is on --
i.e. must alias from basicAA will go through TBAA for checking, or NoAlias
from TBAA will go through BasicAA .. The compiler decides who wins in case
of contradiction and emits warnings appropriately.

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.

this makes sense to me.

David

4

> From: "Chandler Carruth" <chandlerc@google.com>
> To: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "Daniel
Berlin" <dannyb@google.com>, "Hal Finkel"
> <hfinkel@anl.gov>, "George Burgess IV" <george.burgess.iv@gmail.com>,
apazos@codeaurora.org, "Nick Lewycky"
> <nlewycky@google.com>, "clang-dev Developers" <cfe-dev@cs.uiuc.edu>
> Sent: Friday, January 16, 2015 3:52:33 PM
> Subject: Alias Analysis pass ordering in LLVM (and Clang)
>
>
>
> (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.

They might, but because I can't imagine a use case where
provably-incorrect answers are desired, it seems that (b) is really the
underlying issue. That having been said, there might be a significant
compile-time savings if TBAA, etc. is used extensively.

> 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.

I'd argue that these are bugs in BasicAA that should be fixed. BasicAA,
like any other AA, should only return PartialAlias when it has *proved* a
partial overlap. Otherwise, it should delegate. Papering over these by
flipping the pass order is not desirable -- I know you're not proposing
that, but I don't view bugs in BasicAA as a good motivation for a
pass-ordering change.

> c) I'm worried that BasicAA does caching that isn't valid for all
> possible AA implementations.
>

Interesting point; BasicAA's caching is supposed to serve as a guard
against unbounded recursion, and is keyed off of the queried pair of
AA::Location objects. I feel, however, that this must be universally valid.
There is a complication, which is that Location's auxiliary metadata-based
members (for TBAA, etc.) have control-flow dependencies, and so BasicAA can
only cache results for locations with those members in blocks that are
predecessors of the original query instructions (i.e. it can only walk up).
I'm pretty sure this is what it does, but if not, there could be problems.

>
> 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.
>

I agree this would be cleaner.

>
> Finally, I think we should teach Clang to have two flags:
> "-fstrict-aliasing" and '-fstrict-local-type-pun-aliasing'.

To engage in some bikeshedding, I'd prefer that we have:

-fstrict-aliasing=<mode names>, where -fstrict-aliasing without a mode
name has a target-dependent default, perhaps, as you've suggested. We could
use a name like 'pedantic' or 'standard' for the stricter mode and 'loose'
or 'heuristic' for the current mode.

Adding flavor to -fstrict-aliasing seems reasonable.

David