[LLVMdev] bending the limits of tbaa metadata

[Tran Ma]

Hi,  

I work on DDC, the compiler of a research Haskell dialect, Disciple (disciple.ouroborus.net (http://disciple.ouroborus.net)). We are looking to make use of LLVM's type-based alias analysis metadata to encode non-aliasing information between variables. We have found that the tbaa structure is somewhat limited in its expressivity. In particular we couldn't encode intransitive relations such as "no-alias", e.g. (x `no-alias` y) and (y `no-alias` z) but not (x `no-alias` z), where x, y and z are all variables (not types).

As an example, consider the following contrived piece of code, in which we assume (b `no-alias` d) and (c `no-alias` d):  

%1 = load i32* %b, align 4      , !tbaa !1
%2 = load i32* %c, align 4      , !tbaa !4
%3 = add nsw i32 %2, %1         
store i32 %3, i32* %d, align 4  , !tbaa !5, !tbaa !2

; these two loads should be eliminated
%4 = load i32* %b, align 4      , !tbaa !1
%5 = load i32* %c, align 4      , !tbaa !4
%6 = add nsw i32 %5, %4          

…
!0 = metadata !{ metadata !"root-distinct-bd" }
!1 = metadata !{ metadata !"b", metadata !0, i64 0 }
!2 = metadata !{ metadata !"d1", metadata !0, i64 0 }
!3 = metadata !{ metadata !"root-distinct-cd" }
!4 = metadata !{ metadata !"c", metadata !3, i64 0 }
!5 = metadata !{ metadata !"d2", metadata !3, i64 0 }


Here we have invented different nodes for one variable (d) and annotate the store with both of them, in hope that LLVM would make use of both nodes. Unfortunately for us it seems to be ignoring all but the last one, here is the code I got with "opt -S -tbaa -basicaa -gvn -o -":

%1 = load i32* %b, align 4, !tbaa !0
%2 = load i32* %c, align 4, !tbaa !2
%3 = add nsw i32 %2, %1
store i32 %3, i32* %d, align 4, !tbaa !4

; only one of the two loads is optimised out
%4 = load i32* %b, align 4, !tbaa !0
%5 = add nsw i32 %2, %4

…
!0 = metadata !{metadata !"b", metadata !1, i64 0}
!1 = metadata !{metadata !"root-distinct-bd"}
!2 = metadata !{metadata !"c", metadata !3, i64 0}
!3 = metadata !{metadata !"root-distinct-cd"}
!4 = metadata !{metadata !"d2", metadata !3, i64 0}


Is there a way to encode this relation using existing tbaa metadata that I'm missing? Or am I consigned to writing my own alias analysis pass?

Cheers,

--  
Tran Ma

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120823/8b9b12fc/attachment.html>