<font size=2 face="sans-serif">Thanks Daniel and Sanjoy for you comments.
I'll try to list the issues I need to respond to, and double check
my understand.</font><br><br><font size=2 face="sans-serif">1) Sometimes I think of things a certain
way, and I assume other people think the same way. When I say that
I do not want to rely on basic alias analysis to override the TBAA, I do
not consider "may-alias" an answer. I want to avoid the
situation where TBAA says "no-alias, but that might be wrong",
at least for legal code. In the same spirit, I primarily work on
optimizing code, so, when I say the main point is functional correctness,
I really mean to make things functionally correct while still being able
to optimize as much as possible.</font><br><br><font size=2 face="sans-serif">2) Any function that deals with the
TBAA nodes directly must be updated to handle the new form, a struct-path
with multiple member at offset 0. One example is getMostGenericTBAA.
I'll look into that function and see what we can do about it. I'll
need to look for other. However, I do not consider this something
that should stop us from implementing something like this. I believe
they can all be handled in a reasonable way. "getMostGenericTBAA"
could be handled by Making recursive calls with each member of the union,
or something equivalent. </font><br><br><font size=2 face="sans-serif">3) How should we handle a reference
directly through a union, and a reference that is not through the union?
</font><br><br><font size=2 face="sans-serif">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><br><br><font size=2 face="sans-serif">Another option is to say that they do
not alias. This would mean that all references to unions must be
explicitly through the union. 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><br><br><font size=2 face="sans-serif">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><br><font size=2 face="sans-serif">4) Sonjoy asked a question about how
I would be using length information:</font><br><br><tt><font size=2>It was not clear how you'll take the length into consideration.
Are<br>you talking about inferences like "I know the access was 4 bytes long,<br>so it can't be accessing the `short` field"? If so, we'd need
to<br>verify (and maintain) that no passes ask AA about a subsegment of a<br>memory access (i.e. "does that store alias the first two bytes of
this<br>i32 load"); or at least prevent them from using TBAA when they refine<br>their queries this way.</font></tt><br><br><font size=2 face="sans-serif">The answer is no, I will not be trying
to infer length information from the access type. The idea is if
I have two references to the same union. One if offset o1 and size
s1, the other with offset o2 and size s2. Suppose without lose of
generality that o1 <= o2. Then if o1+s1 <= o2, then the references
do not alias. Otherwise they may alias. There may be a few
case where a size is not available. When dealing with call site for
example. In this case, we have to treat the size as "infinite"
pessimizing the aliasing.</font><br><br><font size=2 face="sans-serif">Again thanks for your comments.</font><br><br><font size=2 face="sans-serif">Later,</font><br><font size=2 face="sans-serif">Steven Perron</font><br><br><tt><font size=2>Daniel Berlin <dberlin@dberlin.org> wrote on
2017/02/14 10:05:29 AM:<br><br>> From: Daniel Berlin <dberlin@dberlin.org></font></tt><br><tt><font size=2>> To: Hubert Tong <hubert.reinterpretcast@gmail.com></font></tt><br><tt><font size=2>> Cc: Sanjoy Das <sanjoy@playingwithpointers.com>,
Steven Perron/<br>> Toronto/IBM@IBMCA, llvm-dev <llvm-dev@lists.llvm.org></font></tt><br><tt><font size=2>> Date: 2017/02/14 10:05 AM</font></tt><br><tt><font size=2>> Subject: Re: [llvm-dev] RFC: Representing unions
in TBAA</font></tt><br><tt><font size=2>> <br>> On Tue, Feb 14, 2017 at 5:51 AM, Hubert Tong <hubert.reinterpretcast@gmail.com<br>> > wrote:</font></tt><br><tt><font size=2>> On Mon, Feb 13, 2017 at 10:39 PM, Daniel Berlin
<dberlin@dberlin.org> wrote:</font></tt><br><tt><font size=2>> <br>> On Mon, Feb 13, 2017 at 10:07 AM, Hubert Tong <<br>> hubert.reinterpretcast@gmail.com> wrote:</font></tt><br><tt><font size=2>> On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin
via llvm-dev <llvm-<br>> dev@lists.llvm.org> wrote:</font></tt><br><tt><font size=2>> <br>> I don't think this fully solves the problem -- you'll also need to
fix<br>> getMostGenericTBAA. That is, even if you implement the above
scheme,<br>> say you started out with:<br>> <br>> union U {<br>> int i;<br>> float f;<br>> };<br>> <br>> float f(union U *u, int *ii, float *ff, bool c) {<br>> if (c) {<br>> *ii = 10;<br>> *ff = 10.0;<br>> } else {<br>> u->i = 10; // S0<br>> u->f = 10.0; // S1<br>> }<br>> return u->f;<br>> }<br>> <br>> (I presume you're trying to avoid reordering S0 and S1?)<br>> <br>> SimplifyCFG or some other such pass may transform f to:<br>> <br>> float f(union U *u, int *ii, float *ff, bool c) {<br>> int *iptr = c ? ii : &(u->i);<br>> int *fptr = c ? ff : &(u->f);<br>> *iptr = 10; // S2<br>> *fptr = 10.0; // S3<br>> return u->f;<br>> }<br>> <br>> then getMostGenericTBAA will infer scalar "int" TBAA for
S2 and scalar<br>> "float" TBAA for S3, which will be NoAlias and allow the
reordering<br>> you were trying to avoid.</font></tt><br><tt><font size=2>> <br>> FWIW, i have to read this in detail, but a few things pop out at me.</font></tt><br><tt><font size=2>> <br>> 1. We would like to live in a world where we don't depend on TBAA
<br>> overriding BasicAA to get correct answers. We do now, but don't
want to.<br>> Hopefully this proposal does not make that impossible.</font></tt><br><tt><font size=2>> <br>> 2. Literally the only way that GCC ends up getting this right
is two fold:</font></tt><br><tt><font size=2>> It only guarantees things about direct access
through union.</font></tt><br><tt><font size=2>> If you take the address of the union member (like
the transform <br>> above), it knows it will get a wrong answer.</font></tt><br><tt><font size=2>> So what it does is it finds the type it has to
stop at (here, the <br>> union) to keep the TBAA set the same, and makes the transform end
there.</font></tt><br><tt><font size=2>> So the above would not occur.</font></tt><br><tt><font size=2>> <br>> 3. A suggestion that TBAA follow all possible paths seems .. very
slow.</font></tt><br><tt><font size=2>> <br>> 4. "The main motivation for this is functional correctness of
code <br>> using unions". I believe you mean "with tbaa and strict-aliasing
on".</font></tt><br><tt><font size=2>> If not,functional correctness for unions should
not be in any way <br>> related to requiring TBAA.</font></tt><br><tt><font size=2>> <br>> 5. Unions are among the worst area of the standard in terms of <br>> "nobody has really thought super-hard about the interaction of
<br>> aliasing and unions in a way that is coherent".</font></tt><br><tt><font size=2>> So when you say things like 'necessary for functional
correctness of<br>> unions', just note that this is pretty much wrong. You probably
<br>> mean "necessary for a reasonable interpretation" or something.</font></tt><br><tt><font size=2>> <br>> Because we would be *functionally correct* by the standard by <br>> destroying the program if you ever read the member you didn't
set :)</font></tt><br><tt><font size=2>> C11 subclause 6.5.2.3 paragraph 3, has in footnote
95:</font></tt><br><tt><font size=2>> If the member used to read the contents of a
union object is not the<br>> same as the member last used to store a value in the object, the <br>> appropriate part of the object representation of the value is <br>> reinterpreted as an object representation in the new type as <br>> described in 6.2.6 (a process sometimes called "type punning").
This<br>> might be a trap representation.<br></font></tt><br><tt><font size=2>> So, the intent is at least that the use of the
. operator or the -> <br>> operator to access a member of a union would "safely" perform
type punning.</font></tt><br><tt><font size=2>> </font></tt><br><tt><font size=2>> Certainly, if you can quote this, you know this
is new to C11 (and <br>> newer versions of C++).</font></tt><br><tt><font size=2>> :)</font></tt><br><tt><font size=2>> Yes, this is new to C11; however, the question
for us here is <br>> whether, and under what options, we would support such intended use
<br>> of the language.</font></tt><br><tt><font size=2>> <br>> I was on board with it :)</font></tt><br><tt><font size=2>> I remember pointing out most of the cases
we have bugs for when <br>> struct-path TBAA was designed (on a whiteboard, in fact) and the <br>> consensus answer i got back was basically "we'll just punt on
unions<br>> for now". I did say i suspected this would not work out
well, <br>> soundness wise, but the clear consensus was against me, so here we
are :)</font></tt><br><tt><font size=2>> In any case, reading this in detail:</font></tt><br><tt><font size=2>> 1. "In the struct path TBAA, it is
assumed that the length of a member extends</font></tt><br><tt><font size=2>> to the start of the next. This will not
be true for unions."</font></tt><br><tt><font size=2>> <br>> Staring at the langref, i don't see where it assumes this.</font></tt><br><tt><font size=2>> it is just offset, size, tbaa type, which seems
correct to me.</font></tt><br><tt><font size=2>> <br>> If you mean "the implementation assumes", then yeah, the
<br>> implementation should just be fixed.</font></tt><br><tt><font size=2>> <br>> "In TypeBasedAAResult::alias, we will also have to deal with
the <br>> fact that unions</font></tt><br><tt><font size=2>> have multiple members all at offset 0.
This means that, unlike structs, the<br>> compiler will not be able to tell which member of the union the <br>> memory reference<br>> actually used. To deal with this, TypeBasedAAResult::alias (and
thefunctions<br>> it calls) will have to acts as if all of the unions members could
have been<br>> accessed. "</font></tt><br><tt><font size=2>> <br>> Actually, for correctness, it just has to give a conservative answer<br>> of "may-alias"</font></tt><br><tt><font size=2>> <br>> This is papering over the fact that if it does that, basicaa overrides
it.</font></tt><br><tt><font size=2>> That we should just fix that, not rely on making
TBAA work harder to<br>> be correct (working harder to optimize is fine).</font></tt><br><tt><font size=2>> <br>> That is, say "these are may-alias, this is a final answer"
instead <br>> of "these are may-alias, maybe you can do better?"</font></tt><br><tt><font size=2>> <br>> But yes, if you are trying to optimize unions harder (and i don't
<br>> know why you would :P), yes, you'd have to follow all intersecting
members.</font></tt><br><tt><font size=2>> In gcc we just sort the list, and use offset,
size info to see what <br>> fields it overlaps with.</font></tt><br><tt><font size=2>> <br>> But note: Your correctness still depends on being able to tell these<br>> are union accesses.</font></tt><br><tt><font size=2>> That's bad, because as sanjoy says, we do transforms
that may cause <br>> this to be non-recoverable.</font></tt><br><tt><font size=2>> <br>> If you can't have TBAA say "may-alias, final answer", you
lose.</font></tt><br><tt><font size=2>> <br>> (Note, while you are improving this, i'll note the info should also
<br>> be used to differentiate structure fields and solve the issue discussed
here:</font></tt><br><tt><font size=2>> </font></tt><a href="http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160523/date.html"><tt><font size=2>http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160523/date.html</font></tt></a><br><tt><font size=2>> <br>> The offset, size info is useful and should be used to differentiate
<br>> struct accesses *regardless of type* in cases where we can.</font></tt><br><tt><font size=2>> It doesn't actually matter if one field is an
int and the other a <br>> float. If they are different fields, and we can prove it, they can't<br>> alias anyway)</font></tt><BR>