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

Hi,

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:

Alias sets for function 'foo':
Alias Set Tracker: 2 alias sets for 2 pointer values.
  AliasSet[0x7f9b23d0c510, 1] must alias, Mod       Pointers: (i64* %a, 8)
  AliasSet[0x7f9b23d0c5a0, 1] must alias, Mod       Pointers: (i64* %b, 8)

===== Alias Analysis Evaluator Report ====  1 Total Alias Queries Performed
  0 no alias responses (0.0%)
  1 may alias responses (100.0%)
  0 partial alias responses (0.0%)
  0 must alias responses (0.0%)
  Alias Analysis Evaluator Pointer Alias Summary: 0%/100%/0%/0%
  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!


What is going on here? Am I doing something wrong?

Thanks,
Kavon

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

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