<div dir="ltr"><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">Hi all,</font></p><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">A while ago there was a discussion on changing the current "set of trees" representation of TBAA metadata to be more expressive, prompted by the need to support C structs. Dan Gohman also talked about the issue here: <a href="http://llvm.org/devmtg/2012-11/Gohman-AliasAnalysis.pdf" target="_blank">http://llvm.org/devmtg/2012-11/Gohman-AliasAnalysis.pdf</a>. It was suggested that the trees be replaced by a type DAG then. While working on <a href="http://disciple.ouroborus.net/" target="_blank">this compiler</a>, I ended up using an undirected graph to represent aliasing instead, I believe it might be suitable for TBAA's purposes as well, for the following reasons.</font></p>
<p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">* Does the graph need to be acyclic? Consider these struct types:</font></p><div class="im" style="font-family:arial,sans-serif;font-size:13.513513565063477px">
<p style="font-size:13px"><font face="courier new, monospace" color="#000000"> struct a { type1 x; type2 y }</font></p><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> struct b { type2 y; type3 z }</font></p>
<p style="font-size:13px"><font face="courier new, monospace" color="#000000"> struct c { type3 z; type1 x }</font></p></div><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">They form the following alias graph (sorry about the crappy ascii art):</font></p>
<div class="im" style="font-family:arial,sans-serif;font-size:13.513513565063477px"><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> a --> b --> c -+</font></p><p style="font-size:13px">
<font color="#000000"><span style="font-family:'courier new',monospace"> ^______________|</span> </font></p></div><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">Which won't be representable if we force our tbaa graph to be acyclic.</font></p>
<p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">* Does it need to be directed? If we use a directed graph, then I suppose we'd be relying on "reachability" in both directions to find out if something aliases something else:</font></p>
<div class="im" style="font-family:arial,sans-serif;font-size:13.513513565063477px"><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> +--> char <--+ </font></p><p style="font-size:13px">
<font face="courier new, monospace" color="#000000"> | |</font></p><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> float int</font></p><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> ^ ^</font></p>
<p style="font-size:13px"><font face="courier new, monospace" color="#000000"> |___ MyClass __|</font></p><p style="font-size:13px"><font color="#000000">To answer "does myclass alias char?", we'd need to check (myclass is reachable from char <font face="courier new, monospace">||</font> <font face="arial, helvetica, sans-serif">char is reachable from myclass), similar to how two things alias if they are ascendant/descendant of each other in the current tree representation. Since we're going both ways, I think it makes sense to</font> just reify the reachability edges like this (note the lack of direction, now to check if two things alias, we simply ask if there is an edge connecting them):</font></p>
<p style="font-size:13px"><font face="courier new, monospace" color="#000000"> +--- char ---+</font></p><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> | | |</font></p><p style="font-size:13px">
<font face="courier new, monospace" color="#000000"> float | int</font></p><p style="font-size:13px"><font face="courier new, monospace" color="#000000"> |___ MyClass __|</font></p><p style="font-size:13px"><font color="#000000">This can be represented with a (pretty dense) adjacency matrix and queried in constant time, so I thought it might be faster. </font></p>
</div><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">From what I can gather without delving deep into the codebase, it's easiest right now to change from the "set of trees" representation to a directed graph, but I don't think changing to an undirected graph would be much harder (please correct me if I'm wrong). I'd like to try and tackle the implementation as well, if that's ok.</font></p>
<p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">Thoughts?</font></p><p style="font-family:arial,sans-serif;font-size:13px"><font color="#000000">Thanks!</font></p><font color="#000000">-- <br>
</font><div dir="ltr"><font face="arial, helvetica, sans-serif" color="#000000">Tran.</font></div><div dir="ltr"><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div>
</div>