[cfe-dev] Alias Analysis pass ordering in LLVM (and Clang)

[Xinliang David Li]

On Sun, Jan 25, 2015 at 7:57 AM, Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at google.com>
> > To: "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Daniel
> Berlin" <dannyb at google.com>, "Hal Finkel"
> > <hfinkel at anl.gov>, "George Burgess IV" <george.burgess.iv at gmail.com>,
> apazos at codeaurora.org, "Nick Lewycky"
> > <nlewycky at google.com>, "clang-dev Developers" <cfe-dev at 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


>
> >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
>
> >
> >
> > Thoughts?
> > -Chandler
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150125/61387beb/attachment.html>