llvm dev - Aug 2014 - [LLVMdev] Good reference papers for the TypeBasedAliasAnalysis pass

Hi Guys,

         Could anyone recommend some good reference papers for the
TypeBasedAliasAnalysis pass? I am a beginner in the field and would like to
read on some fundamentals on the subject before trying to make some sense
out of the comments in the TypeBasedAliasAnalysis.cpp. Thanks.

Best Regards,
Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140811/8c95d1ff/attachment.html>

There aren't any real papers i'm aware of on TBAA, because it is
entirely dictated by language specific standards, and thus, the rules
differ from language to language.

The only even mildly useful *paper* would be
http://dl.acm.org/citation.cfm?id=277670

Honestly, there are no real fundamentals unless you want to talk about
specific languages.
Otherwise, everything could be described as:

1. Each language has some rules about type compatibility. Violation of
these rules usually results in undefined behavior.
2. The compiler takes advantage of this to make assumptions about
aliasing of variables of two different types, on the assumtion that
your program does not exhibit undefined behavior.

LLVM's implementation is really separable into two pieces:

Type based aliasing
Access-path aliasing

Both exist in TypeBasedAliasAnalysis.cpp, but are somewhat unrelated
(in practice, #2 gets almost all of it's power from being able to say
things about various offsets, not about types).
#1 is what is traditionally referred to when people talk about TBAA.

LLVM's implementation theoretically consists of a TBAA DAG that is
written out by the frontend, and has various properties (every child
is a alias subset of the parent, for example), that correspond to
various language rules.

The loads/stores are annotated with the set ids.  The TBAA alias
implementation compares the set ids and their positions in the TBAA
DAG to see whether two things alias.
That is the theory.
In practice, you can encode all kinds of interesting analysis results
as TBAA metadata, whether it's type-based or not.
It happens to be a useful datastructure for doing so.

So there is actually no guarantee that any of the metadata you see is
actually related to types in the source language or language rules.


On Mon, Aug 11, 2014 at 10:36 AM, Paul Vario <paul.paul.mit at gmail.com>
wrote:
> Hi Guys,
>
>          Could anyone recommend some good reference papers for the
> TypeBasedAliasAnalysis pass? I am a beginner in the field and would like to
> read on some fundamentals on the subject before trying to make some sense
> out of the comments in the TypeBasedAliasAnalysis.cpp. Thanks.
>
> Best Regards,
> Paul
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Daniel,

If you could point to documentation describing the exact rules for the 
TBAA, and maybe an example or two of how to use them to encode 
interesting properties, I'd be very interested in seeing it.  I looked 
for something like this a while back, but was never able to find 
something with enough detail to be useful.  I'm looking at this from the 
perspective of writing a language frontend and trying to figure out how 
to encode various aliasing rules in ways LLVM would understand.

Philip

On 08/11/2014 11:22 AM, Daniel Berlin wrote:
> There aren't any real papers i'm aware of on TBAA, because it is
> entirely dictated by language specific standards, and thus, the rules
> differ from language to language.
>
> The only even mildly useful *paper* would be
> http://dl.acm.org/citation.cfm?id=277670
>
> Honestly, there are no real fundamentals unless you want to talk about
> specific languages.
> Otherwise, everything could be described as:
>
> 1. Each language has some rules about type compatibility. Violation of
> these rules usually results in undefined behavior.
> 2. The compiler takes advantage of this to make assumptions about
> aliasing of variables of two different types, on the assumtion that
> your program does not exhibit undefined behavior.
>
> LLVM's implementation is really separable into two pieces:
>
> Type based aliasing
> Access-path aliasing
>
> Both exist in TypeBasedAliasAnalysis.cpp, but are somewhat unrelated
> (in practice, #2 gets almost all of it's power from being able to say
> things about various offsets, not about types).
> #1 is what is traditionally referred to when people talk about TBAA.
>
> LLVM's implementation theoretically consists of a TBAA DAG that is
> written out by the frontend, and has various properties (every child
> is a alias subset of the parent, for example), that correspond to
> various language rules.
>
> The loads/stores are annotated with the set ids.  The TBAA alias
> implementation compares the set ids and their positions in the TBAA
> DAG to see whether two things alias.
> That is the theory.
> In practice, you can encode all kinds of interesting analysis results
> as TBAA metadata, whether it's type-based or not.
> It happens to be a useful datastructure for doing so.
>
> So there is actually no guarantee that any of the metadata you see is
> actually related to types in the source language or language rules.
>
>
> On Mon, Aug 11, 2014 at 10:36 AM, Paul Vario <paul.paul.mit at
gmail.com> wrote:
>> Hi Guys,
>>
>>           Could anyone recommend some good reference papers for the
>> TypeBasedAliasAnalysis pass? I am a beginner in the field and would
like to
>> read on some fundamentals on the subject before trying to make some
sense
>> out of the comments in the TypeBasedAliasAnalysis.cpp. Thanks.
>>
>> Best Regards,
>> Paul
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev