[LLVMdev] Good reference papers for the TypeBasedAliasAnalysis pass

[Philip Reames]

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