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,

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

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

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")

By “dropped” do you mean that the metadata is not propagated/preserved during the transformation?

If anyone knows which passes in particular are doing this, I would be happy to try to come up with a patch!

~kavon

By “dropped” do you mean that the metadata is not propagated/preserved during the transformation?

Yes

If anyone knows which passes in particular are doing this, I would be happy to try to come up with a patch!

+Ben