<div>
                    Hi,
                </div><div><br></div><div>I work on DDC, the compiler of a research Haskell dialect, Disciple (<a href="http://disciple.ouroborus.net">disciple.ouroborus.net</a>). 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).</div><div><br></div><div>As an example, consider the following contrived piece of code, in which we assume (b `no-alias` d) and (c `no-alias` d): </div><div><div><br></div><div><font face="Courier New">%1 = load i32* %b, align 4      , !tbaa !1</font></div><div><font face="Courier New">%2 = load i32* %c, align 4      , !tbaa !4</font></div><div><font face="Courier New">%3 = add nsw i32 %2, %1        </font></div><div><font face="Courier New">store i32 %3, i32* %d, align 4  , !tbaa !5, !tbaa !2</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">; these two loads should be eliminated</font></div><div><font face="Courier New">%4 = load i32* %b, align 4      , !tbaa !1</font></div><div><font face="Courier New">%5 = load i32* %c, align 4      , !tbaa !4</font></div><div><font face="Courier New">%6 = add nsw i32 %5, %4         </font></div></div><div><span style="font-family: 'Courier New'; ">…</span></div><div><div><font face="Courier New">!0 = metadata !{ metadata !"root-distinct-bd" }</font></div><div><font face="Courier New">!1 = metadata !{ metadata !"b", metadata !0, i64 0 }</font></div><div><font face="Courier New">!2 = metadata !{ metadata !"d1", metadata !0, i64 0 }</font></div><div><font face="Courier New">!3 = metadata !{ metadata !"root-distinct-cd" }</font></div><div><font face="Courier New">!4 = metadata !{ metadata !"c", metadata !3, i64 0 }</font></div><div><font face="Courier New">!5 = metadata !{ metadata !"d2", metadata !3, i64 0 }</font></div></div><div><br></div>
                <div><div>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 "<font face="Courier New">opt -S -tbaa -basicaa -gvn -o -</font>":</div><div><br></div><div><div><font face="Courier New">%1 = load i32* %b, align 4, !tbaa !0</font></div><div><font face="Courier New">%2 = load i32* %c, align 4, !tbaa !2</font></div><div><font face="Courier New">%3 = add nsw i32 %2, %1</font></div><div><font face="Courier New">store i32 %3, i32* %d, align 4, !tbaa !4</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">; only one of the two loads is optimised out</font></div><div><font face="Courier New">%4 = load i32* %b, align 4, !tbaa !0</font></div><div><font face="Courier New">%5 = add nsw i32 %2, %4</font></div></div><div><font face="Courier New">…</font></div><div><div><font face="Courier New">!0 = metadata !{metadata !"b", metadata !1, i64 0}</font></div><div><font face="Courier New">!1 = metadata !{metadata !"root-distinct-bd"}</font></div><div><font face="Courier New">!2 = metadata !{metadata !"c", metadata !3, i64 0}</font></div><div><font face="Courier New">!3 = metadata !{metadata !"root-distinct-cd"}</font></div><div><font face="Courier New">!4 = metadata !{metadata !"d2", metadata !3, i64 0}</font></div></div><div><br></div><div>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?</div><div><br></div><div>Cheers,</div><div><br></div><div>-- </div><div>Tran Ma</div><div><br></div></div>