llvm dev - Apr 2017 - TBAA falsely reporting may alias?

Thanks for the explanation Sanjoy!

Another question I have is: are there are any passes that invalidate or make the
TBAA analysis information less precise?

I noticed that TBAA is only run once, early on in the pass ordering for O1
through O3. My thinking is that if a pass that duplicates code is run, the
analysis info may not have data for the result of the new load/stores. A
solution might be to add -tbaa after each -basicaa.

~kavon
> On Apr 14, 2017, at 4:45 AM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Kavon,
> 
> On April 13, 2017 at 11:31:17 AM, Kavon Farvardin via llvm-dev
> (llvm-dev at lists.llvm.org) wrote:
>> I'm trying to work with Type Based Alias Analysis (TBAA).
Here's the example program
>> I'm working with:
>> 
>> ;;;;;;;;;;;;;;;;;;;;;;
>> 
>> define void @foo(i64* %a, i64* %b, i64 %x, i64 %y) {
>> store i64 %x, i64* %a, !tbaa !2 ; write to stack
>> store i64 %y, i64* %b, !tbaa !3 ; write to heap
>> ret void
>> }
>> 
>> !1 = !{!"root"}
>> !2 = !{!"stack", !1}
>> !3 = !{!"heap", !1}
>> 
>> ;;;;;;;;;;;;;;;;;;;;;;
>> 
>> When I run: opt -disable-output -disable-basicaa -tbaa -aa-eval
-print-alias-sets
>> simple_tbaa.ll
>> 
>> I get something unusual, as the two pointers %a and %b are in disjoint
alias sets, but aa-eval
>> reports that they may alias:
> 
> Given the IR you have, what you know is that the two store
> *operations* do not alias, not that %a does not alias %b.  In the
> specific case above, you can use the information about the stores to
> say something about the aliasing between %a and %b, but that's not
> true in general of TBAA.
> 
> To make -aa-eval also report the aliasing between loads and stores,
> you can pass in -evaluate-aa-metadata to opt (along with -aa-eval), in
> which case you'll get 1 NoAlias (between the two stores) and one
> MayAlias (between the two pointers %a and %b) on the above IR.
> 
> -- Sanjoy

On 04/14/2017 08:03 AM, Kavon Farvardin via llvm-dev
wrote:
> Thanks for the explanation Sanjoy!
>
> Another question I have is: are there are any passes that invalidate or
make the TBAA analysis information less precise?
Some transformation drop TBAA information when they might invalidate it, 
but it should be preserved in most places.
>
> I noticed that TBAA is only run once, early on in the pass ordering for O1
through O3. My thinking is that if a pass that duplicates code is run, the
analysis info may not have data for the result of the new load/stores. A
solution might be to add -tbaa after each -basicaa.
It only needs to be "run" once, which just serves to insert the TBAA 
analysis in the pipeline. Because the analysis itself is completely 
stateless, it is never invalidated, and thus is always available/used 
after insertion.

  -Hal
>
> ~kavon
>
>> On Apr 14, 2017, at 4:45 AM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
>>
>> Hi Kavon,
>>
>> On April 13, 2017 at 11:31:17 AM, Kavon Farvardin via llvm-dev
>> (llvm-dev at lists.llvm.org) wrote:
>>> I'm trying to work with Type Based Alias Analysis (TBAA).
Here's the example program
>>> I'm working with:
>>>
>>> ;;;;;;;;;;;;;;;;;;;;;;
>>>
>>> define void @foo(i64* %a, i64* %b, i64 %x, i64 %y) {
>>> store i64 %x, i64* %a, !tbaa !2 ; write to stack
>>> store i64 %y, i64* %b, !tbaa !3 ; write to heap
>>> ret void
>>> }
>>>
>>> !1 = !{!"root"}
>>> !2 = !{!"stack", !1}
>>> !3 = !{!"heap", !1}
>>>
>>> ;;;;;;;;;;;;;;;;;;;;;;
>>>
>>> When I run: opt -disable-output -disable-basicaa -tbaa -aa-eval
-print-alias-sets
>>> simple_tbaa.ll
>>>
>>> I get something unusual, as the two pointers %a and %b are in
disjoint alias sets, but aa-eval
>>> reports that they may alias:
>> Given the IR you have, what you know is that the two store
>> *operations* do not alias, not that %a does not alias %b.  In the
>> specific case above, you can use the information about the stores to
>> say something about the aliasing between %a and %b, but that's not
>> true in general of TBAA.
>>
>> To make -aa-eval also report the aliasing between loads and stores,
>> you can pass in -evaluate-aa-metadata to opt (along with -aa-eval), in
>> which case you'll get 1 NoAlias (between the two stores) and one
>> MayAlias (between the two pointers %a and %b) on the above IR.
>>
>> -- Sanjoy
> _______________________________________________
> 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

On Fri, Apr 14, 2017 at 6:12 AM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On 04/14/2017 08:03 AM, Kavon Farvardin via llvm-dev wrote:
>
>> Thanks for the explanation Sanjoy!
>>
>> Another question I have is: are there are any passes that invalidate or
>> make the TBAA analysis information less precise?
>>
>
> Some transformation drop TBAA information when they might invalidate it,
> but it should be preserved in most places.
>
>
FWIW, I believe some folks at Google in a different group have come to the
conclusion it is dropped in about 20-30% of cases.
(I said "file bugs")
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170414/179ff6bf/attachment.html>