<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 24, 2016, at 9:41 PM, Chandler Carruth via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, Feb 24, 2016 at 9:35 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;">----- Original Message -----<br class=""><br class="">> From: "Chandler Carruth via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class="">> To: "Philip Reames" <<a href="mailto:listmail@philipreames.com" target="_blank" class="">listmail@philipreames.com</a>>, "Duncan P. N. Exon<br class="">> Smith" <<a href="mailto:dexonsmith@apple.com" target="_blank" class="">dexonsmith@apple.com</a>>, "Sanjoy Das"<br class="">> <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank" class="">sanjoy@playingwithpointers.com</a>><br class="">> Cc: "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>><br class="">> Sent: Wednesday, February 24, 2016 10:29:23 PM<br class="">> Subject: Re: [llvm-dev] Possible soundness issue with<br class="">> available_externally (split from "RFC: Add guard intrinsics")<br class=""><br class="">> Yea, I'm pretty sad about all of this. I'm also not seeing a lot of<br class="">> awesome paths forward.<br class=""><br class="">> Here is the least bad strategy I can come up with. Curious if folks<br class="">> think this is sufficient:<br class=""><br class="">I may not completely understand the problem, but this seems like overkill. The underlying restriction is that, if the compiler makes a non-determinism-collapsing choice when optimizing a function, it must make the same choice for all definitions of that function (undefined behavior excluded).</blockquote><div class=""><br class=""></div><div class="">This isn't enough, because some definition in some other module may *not be optimized at all*, and yet may get selected at link time.</div><div class=""><br class=""></div><div class="">Put another way, it must *prove* that the same choice will *always* be made for all definitions. This is akin to proving that the optimizer is run over all translation units for C++ linkonce_odr functions, which you can't do.</div></div></div></div></blockquote><div><br class=""></div><div>Even if the optimizer is ran, it could take different decision because the context would be different:</div><div><br class=""></div><div>linkonce_odr foo() {</div><div> bar();</div><div>}</div><div><br class=""></div><div>If bar() is present in the TU it can gets inlined into foo(). So the optimizer would optimize differently foo().</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote"><div class=""><br class=""></div><div class="">The result would be failing to optimize the bodies of linkonce_odr functions in any way which was externally detectable such as this. I think that would be *much* worse than losing the ability to do function attribute deduction for such functions?</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;">Thus, with an externally_available function, the CSE in Sanjoy's original example should be forbidden. Richard's example again demonstrates this principle, although in this case the non-determinism is in the choice of a globally-visible implementation technique rather than non-determinism from memory-subsystem reordering.<br class=""><br class="">There is a complication, which you imply in your proposal, that such optimizations need to be forbidden not just in the externally_available functions themselves, but in any local function transitively called by one. This, however, we can take care of with an (easily-deduced) attribute.<br class=""></blockquote></div></div></div></blockquote><div><br class=""></div><div>I'm not sure why " such optimizations need to be forbidden [...] in any local function transitively called by one", can you illustrate with an example?</div><div><br class=""></div>-- </div><div>Mehdi</div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><br class="">In short, it is not clear to me that the number of problematic optimizations is large (seems likely restricted to things involving atomics in practice),</blockquote></div></div></div></blockquote><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;">and while I understand the auditing difficulties here, we should just restrict these in appropriate contexts instead of trying to restrict all information flow into or out of comdats.<br class=""><br class=""> -Hal<br class=""><br class="">> 1) Stop deducing function attributes within comdats by examining the<br class="">> bodies of the functions (so that we remain free to transform the<br class="">> bodies of functions).<br class="">> 2) Teach frontends to emit (even at O0!!!) trivially deduced function<br class="">> attributes for comdats so that we continue to catch easy cases.<br class="">> 3) Ensure and specify that we never hoist code *into* a comdat group<br class="">> in which it would not have been executed previously. I don't know of<br class="">> anything in LLVM that does this today, but it would become an<br class="">> important invariant.<br class="">> 4) Work a lot harder to do internalizing and removing of this<br class="">> restriction.<br class=""><br class="">> Pretty horrible. But I think it is correct.<br class=""><br class="">> As a slight modification to #1 and #2, we could have a very carefully<br class="">> crafted deduction rule where we only deduce function attributes for<br class="">> functions prior to any modification of their function bodies. Such<br class="">> attributes should be conservatively correct because we would never<br class="">> lift new code into the function bodies. This would at least allow us<br class="">> to do bottom-up deduction to catch interprocedural cases. But it<br class="">> would become incredibly subtle that this is only valid prior to<br class="">> *any* transformations of the comdat-containing functions.<br class=""><br class="">> I'm starting to think this subtle rule might be worth it. But I'm<br class="">> frankly terrified by the implications.<br class=""><br class="">> On Wed, Feb 24, 2016 at 8:13 PM Philip Reames via llvm-dev <<br class="">><span class="Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><span class="Apple-converted-space"> </span>> wrote:<br class=""><br class="">> > On 02/24/2016 08:10 PM, Duncan P. N. Exon Smith via llvm-dev wrote:<br class="">><br class="">> > >> On 2016-Feb-24, at 19:46, Sanjoy Das <<br class="">> > >><span class="Apple-converted-space"> </span><a href="mailto:sanjoy@playingwithpointers.com" target="_blank" class="">sanjoy@playingwithpointers.com</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >><br class="">><br class="">> > >> On Wed, Feb 24, 2016 at 7:38 PM, Chandler Carruth <<br class="">> > >><span class="Apple-converted-space"> </span><a href="mailto:chandlerc@google.com" target="_blank" class="">chandlerc@google.com</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >>> On Wed, Feb 24, 2016 at 7:34 PM Duncan P. N. Exon Smith<br class="">><br class="">> > >>> <<span class="Apple-converted-space"> </span><a href="mailto:dexonsmith@apple.com" target="_blank" class="">dexonsmith@apple.com</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >>>><br class="">><br class="">> > >>>>> On 2016-Feb-24, at 19:17, Chandler Carruth <<br class="">> > >>>>><span class="Apple-converted-space"> </span><a href="mailto:chandlerc@google.com" target="_blank" class="">chandlerc@google.com</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >>>>><br class="">><br class="">> > >>>>> On Wed, Feb 24, 2016 at 7:10 PM Sanjoy Das via llvm-dev<br class="">><br class="">> > >>>>> <<span class="Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >>>>> On Wed, Feb 24, 2016 at 6:51 PM, Duncan P. N. Exon Smith<br class="">><br class="">> > >>>>> <<span class="Apple-converted-space"> </span><a href="mailto:dexonsmith@apple.com" target="_blank" class="">dexonsmith@apple.com</a><span class="Apple-converted-space"> </span>> wrote:<br class="">><br class="">> > >>>>>>> If we do not inline @foo(), and instead re-link the call<br class="">> > >>>>>>> site<br class="">> > >>>>>>> in<br class="">><br class="">> > >>>>>>> @main<br class="">><br class="">> > >>>>>>> to some non-optimized copy (or differently optimized copy)<br class="">> > >>>>>>> of<br class="">> > >>>>>>> @foo,<br class="">><br class="">> > >>>>>>> then it is possible for the program to have the behavior<br class="">> > >>>>>>> {print("Y");<br class="">><br class="">> > >>>>>>> print ("X")}, which was disallowed in the earlier program.<br class="">><br class="">> > >>>>>>><br class="">><br class="">> > >>>>>>> In other words, opt refined the semantics of @foo() (i.e.<br class="">> > >>>>>>> reduced the<br class="">><br class="">> > >>>>>>> set of behaviors it may have) in ways that would make later<br class="">><br class="">> > >>>>>>> optimizations invalid if we de-refine the implementation of<br class="">> > >>>>>>> @foo().<br class="">><br class="">> > >>>>>> I'm probably missing something obvious here. How could the<br class="">> > >>>>>> result of<br class="">><br class="">> > >>>>>> `%t0 != %t1` be different at optimization time in one file<br class="">> > >>>>>> than from<br class="">><br class="">> > >>>>>> runtime in the "real" implementation? Doesn't this make the<br class="">> > >>>>>> CSE<br class="">><br class="">> > >>>>>> invalid?<br class="">><br class="">> > >>>>> `%t0` and `%t1` are "allowed" to "always be the same", i.e.<br class="">> > >>>>> an<br class="">><br class="">> > >>>>> implementation of @foo that always feeds in the same<br class="">><br class="">> > >>>>> value for `%t0` and `%t1` is a valid implementation (which is<br class="">> > >>>>> why the<br class="">><br class="">> > >>>>> CSE was valid); but it is not the *only* valid<br class="">> > >>>>> implementation.<br class="">> > >>>>> If I<br class="">><br class="">> > >>>>> don't CSE the two load instructions (also a valid thing to<br class="">> > >>>>> do),<br class="">> > >>>>> and<br class="">><br class="">> > >>>>> this is a second thread writing to `%par`, then the two<br class="">> > >>>>> values<br class="">> > >>>>> loaded<br class="">><br class="">> > >>>>> can be different, and you could end up printing `"X"` in<br class="">> > >>>>> `@foo`.<br class="">><br class="">> > >>>>><br class="">><br class="">> > >>>>> Did that make sense?<br class="">><br class="">> > >>>> Yes. To be sure I understand the scope: this is only a problem<br class="">> > >>>> for<br class="">><br class="">> > >>>> atomics, correct? (Because multi-threaded behaviour with other<br class="">> > >>>> globals<br class="">><br class="">> > >>>> is UB?)<br class="">><br class="">> > >>>><br class="">><br class="">> > >>>>>> Does linkonce_odr linkage have the same problem?<br class="">><br class="">> > >>>>>> - If so, do you want to change it too?<br class="">><br class="">> > >>>>>> - Else, why not?<br class="">><br class="">> > >>>>> Going by the specification in the LangRef, I'd say it depends<br class="">> > >>>>> on how<br class="">><br class="">> > >>>>> you define "definitive". If you're allowed to replace the<br class="">> > >>>>> body<br class="">> > >>>>> of a<br class="">><br class="">> > >>>>> function with a differently optimized body, then the above<br class="">> > >>>>> problem<br class="">><br class="">> > >>>>> exists.<br class="">><br class="">> > >>>>><br class="">><br class="">> > >>>>> I believe that is the case, and I strongly believe the<br class="">> > >>>>> problem<br class="">> > >>>>> you<br class="">><br class="">> > >>>>> outline exists for linkonce_odr exactly as it does for<br class="">> > >>>>> available_externally.<br class="">><br class="">> > >>>>><br class="">><br class="">> > >>>>> Which is what makes this scary: every C++ inline function<br class="">> > >>>>> today<br class="">> > >>>>> can<br class="">><br class="">> > >>>>> trigger this.<br class="">><br class="">> > >>>> Every C/C++ inline or template function. But only the ones<br class="">> > >>>> that<br class="">> > >>>> use<br class="">><br class="">> > >>>> atomics, right?<br class="">><br class="">> > >>><br class="">><br class="">> > >>> Well, with *this* example...<br class="">><br class="">> > >> Atomic are one source of non-determinism that compilers can<br class="">> > >> reason<br class="">><br class="">> > >> about. I don't know if the following snippet is well defined or<br class="">> > >> not,<br class="">><br class="">> > >> but you could have similar issues with<br class="">><br class="">> > >><br class="">><br class="">> > >><br class="">><br class="">> > >> void foo() {<br class="">><br class="">> > >> int *p = malloc(sizeof(int));<br class="">><br class="">> > >> if (*p < 10) print("X");<br class="">><br class="">> > >> }<br class="">><br class="">> > >><br class="">><br class="">> > >> or (again, I don't know if this is actually well defined)<br class="">><br class="">> > >><br class="">><br class="">> > >> void foo() {<br class="">><br class="">> > >> int t; // it is probably reasonable to fold compares with<br class="">><br class="">> > >> ptrtoint(alloca) to undef<br class="">><br class="">> > >> if ((intptr_t)(&t) < 10) print("X");<br class="">><br class="">> > >> }<br class="">><br class="">> > >><br class="">><br class="">> > > The first one at least is UB, but as Richard pointed out the<br class="">> > > scope<br class="">><br class="">> > > is certainly broader than atomics (it's not even just<br class="">> > > well-defined<br class="">><br class="">> > > non-deterministism).<br class="">><br class="">> > ><br class="">><br class="">> > > I'm kind of terrified by the implications.<br class="">><br class="">> > Me too. :(<br class="">><br class="">> > ><br class="">><br class="">> > >> -- Sanjoy<br class="">><br class="">> > >><br class="">><br class="">> > >>>><br class="">><br class="">> > >>>> Not that I'm sure that will end up being a helpful<br class="">> > >>>> distinction.<br class="">><br class="">> > >>><br class="">><br class="">> > >>> Right. See Richard's comment. I think that sums up the real<br class="">> > >>> issue<br class="">> > >>> here. =/<br class="">><br class="">> > > _______________________________________________<br class="">><br class="">> > > LLVM Developers mailing list<br class="">><br class="">> > ><span class="Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">><br class="">> > ><span class="Apple-converted-space"> </span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">><br class=""><br class="">> > _______________________________________________<br class="">><br class="">> > LLVM Developers mailing list<br class="">><br class="">> ><span class="Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">><br class="">> ><span class="Apple-converted-space"> </span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">><br class=""><br class="">> _______________________________________________<br class="">> LLVM Developers mailing list<br class="">><span class="Apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">><span class="Apple-converted-space"> </span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""><br class="">--<br class=""><br class="">--<br class="">Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<br class=""></blockquote></div></div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span></div></blockquote></div><br class=""></body></html>