[llvm-dev] Alias analysis results

Daniel Berlin via llvm-dev llvm-dev at lists.llvm.org
Mon Jun 19 11:38:30 PDT 2017


On Thu, May 11, 2017 at 1:50 AM, Ivan A. Kosarev via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hello,
>
> I'm trying to get the whole picture of what we are doing in terms
> of alias analysis in LLVM. Being new to this I may be missing
> some well known things so my apologies if I seem to ask obvious
> things.
>
> There are lots of questions arise in my head as I read related
> bug reports, sources and documentation, of which looks to be the
> most simple is,
>
> Why the current TBAA implementation returns NoAlias for pairs of
> accesses for which it has no idea if they really alias?
>

TBAA is broken in various ways, but in general, it is because it knows they
can't legally do so.


>
> Let me elaborate on this. My understanding of what the TBAA
> implementation is supposed to respond is whether a given pair of
> accesses is allowed to alias by the rules of the input language.
>
No.
TBAA is a bad name for what LLVM is doing, because it's not really TBAA at
that point.  I've objected to the name before as it confuses people.
It's really anti-alias sets/subsets structured as a tree.  Loads/stores are
tagged with which set they belong to.

In C/C++, those sets are  generated by  TBAA rules.  You could generate
them however you want.

(Which in turn leads me to another question, that is, whether
> we are really trying to perform C/C++ alias analysis in a
> [language-neutral] codegen pass, but let's postpone this for
> later.)
>

No, we are not trying to do so.


>
> This consideration assumes that what the TBAA implementation
> actually returns as a result is orthogonal to the
> Must/No/MayAlias set,


No, it is exactly a noalias set.

>
> The latter combination is what I would expect for illegal type
> puns, for whatever definition of "illegal". Note that for such
> cases we currently get MustAlias from BasicAA and NoAlias from
> TBAA.


This is, IMHO, very very broken and should be fixed in clang.


> In some comments this is considered okay whereas I have to
> admit that I don't understand how that may possibly be okay,
> meaning it's hard to imagine how a pair of accesses can be
> aliasing and non-aliasing at the same time.


Note that it will always be the case
It is entirely possible for one alias analysis to say must alias, and
another to say no-alias, depending on the source of the info.




> To me it appears
> like that the root cause if this inconsistency is not that any of
> these analyses is not correct, but that we are trying to
> represent their responses in an inadequate form and we are trying
> to use BasicAA as a faster replacement for TBAA in simple cases.
>

I don't really see this at all.

THe use of BasicAA to go with TBAA is, IMHO, just broken.
it's not trying to be faster, it's doing it for correctness.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170619/68e8b584/attachment.html>


More information about the llvm-dev mailing list