[llvm-dev] What is TBAA's advantage over BasicAA?

[Hal Finkel via llvm-dev]

On 07/08/2018 01:55 PM, Bekket McClane via llvm-dev wrote:
> Hi all,
>
> I’m currently studying TBAA. I understand that it provide a “struct-path” analysis, which should do well on analyzing struct-like type in high level language.
> However, I got one simple question - Why don’t we just trace back the GEP chains from a given pointer, evaluate the pointer as some sort of BasePtr + Offset form, then compare if two pointers have same forms - just exactly what BasicAA do in its aliasGEP function ?
> What is TBAA’s advantage over BasicAA, and its necessity of providing a decent type system, which actually looks like another form of Base + Offset?
>
> Currently I only come up with one example: addresses of A[i].firstField and A[j].secondField, where A is SomeStruct* type. 
> As the two pointers is accessing different fields of a struct, they would never alias regardless of offsets i and j against A. 
> BasicAA would try to evaluate them into (A + sizeof(A) * i + Offset1) and (A + sizeof(A) * j + Offset2), and probably fail to continue since i and j are not constants.
> But I don’t think this is the only reason TBAA is invented. Could someone give me examples showing TBAA performs over BasicAA in some domains?

TBAA is available so that the frontend can provide the optimizer with
aliasing information that the optimizer can't possibly deduce. As a
simple example, consider this function:

void foo(int *x, float *y) {
  *x = 5;
  *y = 8.0f;
}

can the optimizer reorder those stores? It can't, unless it knows that
the pointers cannot alias. If this is an extern function, such that it
can be called by code outside of the LLVM module being compiled, the
optimizer has no way to know that the pointers can't alias. The fact
that they can't come from semantics provided by the source language (C
or C++, in this case), and TBAA can provide that information. There's
nothing that BasicAA can do to figure this out on its own.

 -Hal 

>
> Thank you
>
> Bekket McClane
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory