<div dir="ltr">Yes.<div>Clang generates tbaa trees that are not conservatively correct in the face of unions, for any definition of correct you have :)</div><div><br></div><div>We mostly rely on basicaa to say things are must-alias, but if it says may-alias, in the case of unions, tbaa will often say "noalias".</div><div><br></div><div><br><br><div class="gmail_quote"><div dir="ltr">On Wed, Mar 1, 2017, 4:00 PM Flamedoge <<a href="mailto:code.kchoi@gmail.com" target="_blank">code.kchoi@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_-777621513946442001gmail_msg">Pardon my exclamation, are you saying TBAA will return NoAlias between union members under current implementation?<div class="m_-777621513946442001gmail_msg">If so, this is definitely a concern.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Kevin</div></div><div class="gmail_extra m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><div class="gmail_quote m_-777621513946442001gmail_msg"></div></div><div class="gmail_extra m_-777621513946442001gmail_msg"><div class="gmail_quote m_-777621513946442001gmail_msg">On Wed, Mar 1, 2017 at 3:30 PM, Daniel Berlin via llvm-dev <span dir="ltr" class="m_-777621513946442001gmail_msg"><<a href="mailto:llvm-dev@lists.llvm.org" class="m_-777621513946442001gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br class="m_-777621513946442001gmail_msg"></div></div><div class="gmail_extra m_-777621513946442001gmail_msg"><div class="gmail_quote m_-777621513946442001gmail_msg"><blockquote class="gmail_quote m_-777621513946442001gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="m_-777621513946442001gmail_msg">So, <a href="https://bugs.llvm.org/show_bug.cgi?id=32056" class="m_-777621513946442001gmail_msg" target="_blank">https://bugs.llvm.org/show_<wbr>bug.cgi?id=32056</a> is an example showing our current TBAA tree for union generation is definitely irretrievably broken.<div class="m_-777621513946442001gmail_msg">I'll be honest here. I'm pretty sure your proposal doesn't go far enough.</div><div class="m_-777621513946442001gmail_msg">But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.</div><div class="m_-777621513946442001gmail_msg">Let me try to simplify what you are suggesting, and what we have.</div><div class="m_-777621513946442001gmail_msg">Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.<br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Given</div><div class="m_-777621513946442001gmail_msg">union {int a, short b};</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">GCC's will be:</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"> union</div><div class="m_-777621513946442001gmail_msg">  /   \</div><div class="m_-777621513946442001gmail_msg">short int</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Our metadata has no child links, and only a single parent link.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Your suggestion is to invert this as a struct</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">short  int</div><div class="m_-777621513946442001gmail_msg">   |    / </div><div class="m_-777621513946442001gmail_msg">union</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">We don't allow multiple parents, however.</div><div class="m_-777621513946442001gmail_msg">Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Let me suggest something different:</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">We know the current structure fails us in a number of ways.</div><div class="m_-777621513946442001gmail_msg">Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.</div><div class="m_-777621513946442001gmail_msg">We make contained types descendants instead of ancestors.</div><div class="m_-777621513946442001gmail_msg">We allow multiple children at each offset and for scalar type nodes.x`<br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.</div><div class="m_-777621513946442001gmail_msg">(If someone really does like the ancestor form, i'd love to understand why :P)</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg">So if we are going to change it, we should change it to something that is easier to understand.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">something like:<br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">scalar type node -> {name, children nodes} </div><div class="m_-777621513946442001gmail_msg">struct node -> {name, array of {offset, child node} }</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">Paths are separate from the tbaa tree itself, and are just:</div><div class="m_-777621513946442001gmail_msg">path node -> {struct node, offset} or whatever.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">This also has a well-defined upgrade path.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)</div><div class="m_-777621513946442001gmail_msg">.</div><div class="m_-777621513946442001gmail_msg">Anything with a "new-style" DAG, we know is usable.</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">In this representation, the most generic tbaa node is just the one that contains the other.</div><div class="m_-777621513946442001gmail_msg">If neither contains the other, you can just make one that has both as children and use that.</div><div class="m_-777621513946442001gmail_msg">(instead of now, where you'd have to have multiple parents again).</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">(The above also may be better for other languages)</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg">--Dan</div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div><div class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div></div><div class="m_-777621513946442001m_9110299790174687636HOEnZb m_-777621513946442001gmail_msg"><div class="m_-777621513946442001m_9110299790174687636h5 m_-777621513946442001gmail_msg"><div class="gmail_extra m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><div class="gmail_quote m_-777621513946442001gmail_msg">On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <span dir="ltr" class="m_-777621513946442001gmail_msg"><<a href="mailto:perrons@ca.ibm.com" class="m_-777621513946442001gmail_msg" target="_blank">perrons@ca.ibm.com</a>></span> wrote:<br class="m_-777621513946442001gmail_msg"><blockquote class="gmail_quote m_-777621513946442001gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">Seems like the comments have stopped.  I'll
try to get a patch together.  Then we can continue the discussion
from there.  </font><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">Hubert, as for the issue with the llvm
optimizations losing the TBAA information, it should be the responsibility
to make sure the aliasing is changed in the correct way.  One function
related to this has already been mentioned:  getMostGenericTBAA.</font><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">Later,</font><br class="m_-777621513946442001gmail_msg"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">Steven Perron</font><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><font size="1" color="#5f5f5f" face="sans-serif" class="m_-777621513946442001gmail_msg">From:      
 </font><font size="1" face="sans-serif" class="m_-777621513946442001gmail_msg">Hubert Tong <<a href="mailto:hubert.reinterpretcast@gmail.com" class="m_-777621513946442001gmail_msg" target="_blank">hubert.reinterpretcast@gmail.<wbr>com</a>></font><br class="m_-777621513946442001gmail_msg"><font size="1" color="#5f5f5f" face="sans-serif" class="m_-777621513946442001gmail_msg">To:      
 </font><font size="1" face="sans-serif" class="m_-777621513946442001gmail_msg">Steven Perron/Toronto/IBM@IBMCA</font><br class="m_-777621513946442001gmail_msg"><font size="1" color="#5f5f5f" face="sans-serif" class="m_-777621513946442001gmail_msg">Cc:      
 </font><font size="1" face="sans-serif" class="m_-777621513946442001gmail_msg">Daniel Berlin <<a href="mailto:dberlin@dberlin.org" class="m_-777621513946442001gmail_msg" target="_blank">dberlin@dberlin.org</a>>,
llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="m_-777621513946442001gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a>>, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="m_-777621513946442001gmail_msg" target="_blank">sanjoy@playingwithpointers.<wbr>com</a>></font><br class="m_-777621513946442001gmail_msg"><font size="1" color="#5f5f5f" face="sans-serif" class="m_-777621513946442001gmail_msg">Date:      
 </font><font size="1" face="sans-serif" class="m_-777621513946442001gmail_msg">2017/02/15 07:44 AM</font><span class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><font size="1" color="#5f5f5f" face="sans-serif" class="m_-777621513946442001gmail_msg">Subject:    
   </font><font size="1" face="sans-serif" class="m_-777621513946442001gmail_msg">Re: [llvm-dev]
RFC: Representing unions in TBAA</font><br class="m_-777621513946442001gmail_msg"></span><hr noshade class="m_-777621513946442001gmail_msg"><div class="m_-777621513946442001m_9110299790174687636m_-4597938816413461551HOEnZb m_-777621513946442001gmail_msg"><div class="m_-777621513946442001m_9110299790174687636m_-4597938816413461551h5 m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><font size="3" class="m_-777621513946442001gmail_msg">On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <</font><a href="mailto:perrons@ca.ibm.com" class="m_-777621513946442001gmail_msg" target="_blank"><font size="3" color="blue" class="m_-777621513946442001gmail_msg"><u class="m_-777621513946442001gmail_msg">perrons@ca.ibm.com</u></font></a><font size="3" class="m_-777621513946442001gmail_msg">>
wrote:</font><br class="m_-777621513946442001gmail_msg"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">3) How should we handle a reference
directly through a union, and a reference that is not through the union?
 </font><font size="3" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></font><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg">My solution was to look for each member of the union overlaps the given
offset, and see if any of those members aliased the other reference. 
If no member aliases the other reference, then the answer is no alias. 
Otherwise the answer is may alias.  The run time for this would be
proportional to  "distance to the root" * "number of
overlapping members".  This could be slow if there are unions
with many members or many unions of unions.</font><font size="3" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></font><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg">Another option is to say that they do not alias.  This would mean
that all references to unions must be explicitly through the union.</font><br class="m_-777621513946442001gmail_msg"><font size="3" class="m_-777621513946442001gmail_msg">From what I gather from the thread so far, the access
through the union may be lost because of LLVM transformations. I am not
sure how, in the face of that, TBAA could indicate NoAlias safely (without
the risk of functional-correctness issues in correct programs) between
types which overlap within any union (within some portion of the program).<br class="m_-777621513946442001gmail_msg"></font><br class="m_-777621513946442001gmail_msg"><font size="3" class="m_-777621513946442001gmail_msg">As for the standards, it is definitely not true that all
references to unions must be explicitly through the union. However, if
you are trying to perform union-based type punning (under C11), then it
appears that it is intended that the read must be through the union.</font><br class="m_-777621513946442001gmail_msg"><font size="3" class="m_-777621513946442001gmail_msg"> </font><br class="m_-777621513946442001gmail_msg"><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg">This would be the least restrictive
aliasing allowing the most optimization.  The implementation would
be simple.  I believe we make the parent of the TBAA node for the
union to be "omnipotent char".  This might be similar to
treating the union TBAA node more like a scalar node instead of a struct-path.
 Then the traversal of the TBAA nodes will be quick.  I'll have
to work this out a bit more, but, if this is good enough to meet the requirements
of the standard, I can try to think this through a little more.  I'll
need Hubert and Daniel to comment on that since I am no expert on the C
and C++ standards.</font><font size="3" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></font><font size="2" face="sans-serif" class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg">The third option is to be pessimistic and say "may alias" all
of the time (conservatively correct), and rely on other alias analysis
to improve it.  This will have good compile time, but could hinder
optimization.  Personally I do not like this option.  Most of
the time it will not have a negative effect, but there will be a reasonable
number of programs where this will hurt optimization more that it needs
to.</font><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"><br class="m_-777621513946442001gmail_msg"></div></div></blockquote></div><br class="m_-777621513946442001gmail_msg"></div>
</div></div><br class="m_-777621513946442001gmail_msg"></blockquote></div></div><div class="gmail_extra m_-777621513946442001gmail_msg"><div class="gmail_quote m_-777621513946442001gmail_msg"><blockquote class="gmail_quote m_-777621513946442001gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">______________________________<wbr>_________________<br class="m_-777621513946442001gmail_msg">
LLVM Developers mailing list<br class="m_-777621513946442001gmail_msg">
<a href="mailto:llvm-dev@lists.llvm.org" class="m_-777621513946442001gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a><br class="m_-777621513946442001gmail_msg">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" class="m_-777621513946442001gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br class="m_-777621513946442001gmail_msg">
<br class="m_-777621513946442001gmail_msg"></blockquote></div></div></blockquote></div></div></div>