<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Sean,<div class=""><br class=""></div><div class="">Dan Gohman’s “transform” changes a loop induction variable, but does not change the CFG,</div><div class=""><br class=""></div><div class="">Hal’s “transform” deletes blocks out of the CFG, fundamentally altering it.</div><div class=""><br class=""></div><div class="">These are two totally different transforms.</div><div class=""><br class=""></div><div class="">And even the analysis is different,</div><div class=""><br class=""></div><div class="">The first is based on an *assumption* of non-UB (actually there is no analysis to perform)</div><div class=""><br class=""></div><div class="">the second Is based on a *proof* of existence of UB (here typically some non-trivial analysis is required)</div><div class=""><br class=""></div><div class="">These have, practically speaking, nothing in common.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter Lawrence.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 21, 2017, at 5:00 PM, Sean Silva <<a href="mailto:chisophugis@gmail.com" class="">chisophugis@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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_extra"><br class="Apple-interchange-newline"><br class=""><div class="gmail_quote">On Jul 21, 2017 3:24 PM, "Peter Lawrence" <<a href="mailto:peterl95124@sbcglobal.net" class="">peterl95124@sbcglobal.net</a>> wrote:<br type="attribution" class=""><blockquote class="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;"><div style="word-wrap: break-word;" class=""><br class=""><div class=""><div class="quoted-text"><blockquote type="cite" class=""><div class="">On Jul 20, 2017, at 11:22 AM, David Blaikie <<a href="mailto:dblaikie@gmail.com" target="_blank" class="">dblaikie@gmail.com</a>> wrote:</div><br class="m_-996355277070279085Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, Jul 19, 2017 at 10:17 AM Peter Lawrence via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</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;"><div style="word-wrap: break-word;" class="">Chandler,<div class=""> The only thing David made clear that wasn’t already clear</div><div class="">is that he believes UB to be “comparatively rare”, which is in agreement</div><div class="">with what Hal already said which is that he does not expect deleting</div><div class="">UB will be of benefit to for example SPEC benchmarks.</div><div class=""><br class=""></div><div class="">Given that it is “comparatively rare”, why all the effort to delete it ? </div></div></blockquote><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;"><div style="word-wrap: break-word;" class=""><div class="">And why make deleting it the default rather than warning about it ? </div></div></blockquote><div class=""><br class="">There seems to be some confusion/misunderstanding here. My best understanding is that when David said this:<br class=""><br class="">"<span style="color: rgb(33, 33, 33); font-size: 13px;" class="">The cases where the compiler can statically prove that undefined behaviour is present are comparatively rare."<br class=""></span><br class="">What he was referring to/describing was a contrast with the optimizations described prior to that.<br class=""><br class="">It's something like this:<br class=""><br class="">UB-based optimizations don't prove UB is present - they optimize on the assumption that it is not present due to some unproven (by the compiler, but assumed to be known by the developer) invariants in the program.<br class=""><br class="">Think about a simple case like array bounds - the compiler emits an unconditional load to the memory because it assumes the developer correctly validated the bounds or otherwise constructed so that out of bounds indexes never reach that piece of code. This is quite common - that UB is assumed to not happen, and the compiler optimizes on this fact.<br class=""><br class="">What is less common, is for the compiler to be able to (in reasonable time) prove that UB /does/ happen (in many cases this would require complex interprocedural analysis - the array is defined in one function, maybe with a complex dynamic bound, then passed to another function and indexed using a non-trivial dynamic expression... statically proving that to be true or false is complex/expensive and so basically not done by any compiler - so any cases that are caught by the compiler are relatively trivial ("oh, you declared a const null pointer value, then dereferenced it within the same function", etc) & so don't happen very often (because they're also fairly obvious to developers too))<br class=""><br class="">Does that help explain the difference/distinction being drawn here?<br class=""></div></div></div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div></div><div class="">Dave,</div><div class=""> <span class="Apple-converted-space"> </span>perhaps you missed these parts of the discussion</div><div class=""><br class=""></div><div class=""><div class="">Here is the definition, acknowledged by Hal, of what we’re doing</div><div class="quoted-text"><div class=""><br class=""></div><div class=""><blockquote type="cite" class="">1. Sometimes there are abstraction penalties in C++ code<br class="">2. That can be optimized away after template instantiation, function inlining, etc<br class="">3. When they for example exhibit this pattern<br class=""><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span>if (A) {<br class=""><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span>stuff;<br class=""><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span>} else {<br class=""><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span>other stuff including “undefined behavior”;<br class=""><span class="m_-996355277070279085Apple-tab-span" style="white-space: pre-wrap;"> </span>}<br class="">4. Where the compiler assumes “undefined behavior” doesn’t actually happen because<br class=""> In the C language standard it is the users responsibility to avoid it<br class="">5. Therefore in this example the compiler can a) delete the else-clause<br class=""> b) delete the if-cond, c) assume A is true and propagate that information<br class=""></blockquote><div class=""><br class=""></div></div></div></div><div class=""><br class=""></div><div class="">And, here’s the optimization that according to Sean we’re using to delete UB</div><div class=""><br class=""></div><div class=""><div class=""><div class=""><blockquote type="cite" class="">[ … ]</blockquote><blockquote type="cite" class=""><br class=""></blockquote></div></div><blockquote type="cite" class=""><span style="float: none; display: inline !important;" class="">In other words, if we can prove "when program statement A executes then</span><br class=""><span style="float: none; display: inline !important;" class="">program statement B is guaranteed to execute and have undefined behavior"</span><br class=""><span style="float: none; display: inline !important;" class="">then we can assume that program statement A is never executed.</span><br class=""><br class=""><span style="float: none; display: inline !important;" class="">In particular, deleting program statement A is a correct transformation.</span><br class=""><span style="float: none; display: inline !important;" class="">Deleting program statement B itself is a special case of this (when A = B).</span><br class=""><br class=""><span style="float: none; display: inline !important;" class="">And yes, this does include everything up to and including `main`,</span><br class=""><span style="float: none; display: inline !important;" class="">intraprocedurally and interprocedurally.</span><br class=""><br class=""><br class=""><span style="float: none; display: inline !important;" class="">[ … ]</span></blockquote><blockquote type="cite" class=""><br class=""><span style="float: none; display: inline !important;" class="">-- Sean Silva</span></blockquote><div class=""><span style="float: none; display: inline !important;" class=""><br class=""></span></div><div class=""><span style="float: none; display: inline !important;" class=""><br class=""></span></div></div><div class="">This is entirely a separate issue from what Dan Gohman did to optimize sign extension</div><div class="">of i32 induction variables out of loops for LP64 target machines, where the optimization</div><div class="">is justified based on “the assumption that UB does not happen”, and no actual UB</div><div class="">exists either statically or dynamically.</div><div class=""></div></div></div></blockquote></div></div></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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="">Sorry, the way I phrased this in terms of program statements may have made this unclear, but this is precisely the particular case A=B that I mentioned. In this case, A=B="the induction variable increment" and we use that to deduce that the statement will not execute and overflow, which is what justifies the widening.</div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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="">Notice that I mentioned that deleting code is only a particular case. In the general case we deduce that dynamically something simply does not happen, which is what we do in order to prove that induction variable widening is safe (overflow cannot happen).</div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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="">There is nothing special about induction variable widening with respect to UB. It is justified by applying the same principles as all other UB-related transformations.</div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""><span style="font-family: sans-serif;" class="">Briefly, there is only one axiom in the compiler writer's toolbox w.r.t. UB and that is "the input program does not execute UB". Everything else is derived from that by pure logical reasoning. Does that make sense? Can you see how all the descriptions I gave above are derivable from that axiom?</span><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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="">The common application of this is that we can assume any program property P whatsoever (not just liveness, but variable ranges, etc.) if we can prove that the program would execute UB should that property P fail to hold.</div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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="">-- Sean Silva</div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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=""><br class=""></div><div dir="auto" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: 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_extra"><div class="gmail_quote"><blockquote class="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;"><div style="word-wrap: break-word;" class=""><div class=""><div class=""><br class=""></div><div class="">But when it comes to actual provable UB the plan is to delete it.</div><div class="">On that there is no confusion, and there is no mis-understanding.</div><font color="#888888" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter Lawrence.</div></font><div class="elided-text"><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><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-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;" class=""><div class="gmail_quote"><div class=""><br class="">- Dave</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;"><div style="word-wrap: break-word;" class=""><div class=""><br class=""></div><div class="">Peter</div></div><div style="word-wrap: break-word;" class=""><div class=""><br class=""></div><div class=""><br class=""><div class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 13, 2017, at 2:15 PM, Chandler Carruth <<a href="mailto:chandlerc@gmail.com" target="_blank" class="">chandlerc@gmail.com</a>> wrote:</div><br class="m_-996355277070279085m_5407134396719276379Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_quote"><div dir="ltr" class="">On Thu, Jul 13, 2017 at 5:13 PM Peter Lawrence via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</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;">David,<br class=""> <span class="m_-996355277070279085Apple-converted-space"> </span>Here is the definition accepted by Hal of what we’re doing<br class=""><br class="">> 1. Sometimes there are abstraction penalties in C++ code<br class="">> 2. That can be optimized away after template instantiation, function inlining, etc<br class="">> 3. When they for example exhibit this pattern<br class="">> if (A) {<br class="">> stuff;<br class="">> } else {<br class="">> other stuff including “undefined behavior”;<br class="">> }<br class="">> 4. Where the compiler assumes “undefined behavior” doesn’t actually happen because<br class="">> In the C language standard it is the users responsibility to avoid it<br class="">> 5. Therefore in this example the compiler can a) delete the else-clause<br class="">> b) delete the if-cond, c) assume A is true and propagate that information<br class=""><br class=""><br class=""><br class="">We are actively deleting undefined behavior, and the question is why<br class="">given that doing so potentially masks a real source code bug.<br class="">At the very least deleting undefined behavior should not be the default.<br class=""></blockquote><div class=""><br class=""></div><div class="">You are asserting this (again), but others have clearly stated that they disagree. David gave detailed and clear reasons why. Continuing to re-state positions is not productive.</div><div class=""><br class=""></div><div class="">-Chandler</div></div></div></div></blockquote></div><br class=""></div></div></div>______________________________<wbr class="">_________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a></blockquote></div></div></div></blockquote></div></div></div></blockquote></div></div></div></div></blockquote></div><br class=""></div></body></html>