[LLVMdev] tbaa

[Daniel Berlin]

On Mon, Dec 5, 2011 at 6:08 PM,  <ggan at codeaurora.org> wrote:
> Hi Yi,
>
> I didn't get a chance to run your code. But from the debug information you
> posted about tbaa alias analysis:
>
> Alias Set Tracker: 1 alias sets for 7 pointer values.
>  AliasSet[0x207f860, 7] may alias, Mod/Ref   Pointers: (i32* %1, 4),
> (i32* %x, 4), (i32** %p, 8), (i32** %q, 8), (float* %z, 4), (float** %t,
> 8), (i32* %2, 4)
>
> I guess it is because of the way how TBAA alias analysis treats pointers.
> See file: tools/clang/lib/CodeGen/CodeGenTBAA.cpp, line 147&148
>
>    147   if (Ty->isPointerType())
>    148     return MetadataCache[Ty] = getTBAAInfoForNamedType("any pointer",
>    149                                                        getChar());
>
> For any pointer, no matter which object it points to, TBAA will generate
> the same type of tbaa metadata, which is called "any pointer". Since the
> elements in the alias set you posted are all pointers, TBAA will think
> that they all "may alias" each other.

Err, no.
This would in fact, defeat the entire purpose of TBAA, which is to
make it so pointers to one type are not considered to alias pointed-to
variables of other types

IE int * does not point to a float.

The above TBAA info generated by clang is "conservatively correct" (it
misses that float ** can't point to int *, and there is a FIXME about
this in the source, which correctly states the real issue in makign
this work), but still does not explain his may-alias situation,
because when clang compiled it, the tbaa tag assigned to float would
not match the tbaa tag assigned to the int.

For a test program,
void foo(float *);
void bar(int *);
int main()
{
  int x=0;
  int* p=&x;
  int* q=&x;
 bar(p);
  float z=0;
   float* t=&z;
   foo(t);
return *p;
 }

I get

define i32 @main() nounwind uwtable ssp {
  %x = alloca i32, align 4
  %z = alloca float, align 4
  store i32 0, i32* %x, align 4, !tbaa !0
  call void @bar(i32* %x) nounwind
  store float 0.000000e+00, float* %z, align 4, !tbaa !3
  call void @foo(float* %z) nounwind
  %1 = load i32* %x, align 4, !tbaa !0
  ret i32 %1
}

declare void @bar(i32*)

declare void @foo(float*)

!0 = metadata !{metadata !"int", metadata !1}
!1 = metadata !{metadata !"omnipotent char", metadata !2}
!2 = metadata !{metadata !"Simple C/C++ TBAA", null}
!3 = metadata !{metadata !"float", metadata !1}

You can see int and float were assigned different tbaa tags (both
children of the omnipotent char type, which is "conservatively
correct"), and that it should know that these two don't alias.
The TBAA analysis code is correct
(http://llvm.org/svn/llvm-project/llvm/trunk/lib/Analysis/TypeBasedAliasAnalysis.cpp),
it walks up the tree and checks whether they are ancestors of each
other

(Note, in deep TBAA trees, this can be done significantly faster using
the same thing I did for  dominators, DFS number the TBAA tree once
you have all the initial sets, renumber if invalidated)

Yet, aa-eval still says otherwise.


Function: main: 2 pointers, 2 call sites
  MayAlias:	float* %z, i32* %x
  Both ModRef:  Ptr: i32* %x	<->  call void @bar(i32* %x) nounwind
  Both ModRef:  Ptr: float* %z	<->  call void @bar(i32* %x) nounwind
  Both ModRef:  Ptr: i32* %x	<->  call void @foo(float* %z) nounwind
  Both ModRef:  Ptr: float* %z	<->  call void @foo(float* %z) nounwind
  Both ModRef:   call void @bar(i32* %x) nounwind <->   call void
@foo(float* %z) nounwind
  Both ModRef:   call void @foo(float* %z) nounwind <->   call void
@bar(i32* %x) nounwind

I'm too busy to debug further, i don't have a debug binary of opt
handy, but these results are fairly clearly wrong :)