<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="">Dave,<div class=""> I will try to locate and take a look at the actual llvm logic that deletes based</div><div class="">on UB-presence, one of these days, and report back. In the mean time...</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Your “For example:" is a plausibility argument only. It is not meaningful until </div><div class="">you can show this happening in real source code from real applications</div><div class="">that are compiler warning free and static analysis warning free.</div><div class=""><br class=""></div><div class="">Hal already conceded that this is never likely to happen in for example SPEC</div><div class="">benchmarks, I’m willig to bet it never happens even in a highly abstracted application</div><div class="">like llvm itself.</div><div class=""><br class=""></div><div class="">Saying “The C++ language lets me assume that that won’t happen, & optimize </div><div class="">on that basis” is an assumption that that’s what the user wants, but you</div><div class="">haven’t asked you’ve just assumed, and AFAICT it is an incorrect assumption.</div><div class="">What’s worse is that there isn’t any way to opt-out of this assumption</div><div class="">(-fsanitize=undefined isn’t opt’ing out, its opt’ing in to a lot extra that I</div><div class="">might or might not want).</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 31, 2017, at 9:48 AM, David Blaikie <<a href="mailto:dblaikie@gmail.com" class="">dblaikie@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Mon, Jul 31, 2017 at 7:40 AM Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" class="">peterl95124@sbcglobal.net</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Dave,<div class=""> Dead code elimination is generally done in a pass called dead code elimination,</div><div class="">Can you give concrete examples why the same would not be true for UB code elimination ?</div></div></blockquote><div class=""><br class="">I haven't actually looked at how optimizations on the basis of the code being UB-free cause code to be eliminated - I'd hazard a guess that many optimizations would replace certain code with undef or unreachable not only a specific pass intended for that purpose. At least I'm pretty sure that's how it is today (I know we don't have a "UB code elimination" pass - it comes out as a result of many other passes making steps like mutation to undef/unreachable)<br class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class="">Yes, speculatively hoisting code requires it to be UB-free, but that has nothing to do with<br class=""></div><div class="">UBCE deleting entire blocks of code because of the existence of UB. </div></div></blockquote><div class=""><br class="">There's more similarity there than might first appear - if we assume the code is UB-free, then when an unconditional store to a null pointer is found we assume that must be dynamically unreachable (& the only reason it came up is due to inlining, etc - not that the user wrote/intended to store to null - maybe this particular call site got inlined and now what was a dynamic property (the user always called that function with a parameter that ensured the program didn't go down that code path and load from the pointer - but other callers do, so that's fine and good and correct) is a static property of this particular version/post-inlining state so the compiler can trivially observe it and replace it with unreachable)<br class=""><br class="">For example:<br class=""><br class=""><div class=""><font face="monospace" class="">inline __attribute__((always_inline)) void f1(bool b, int *i) {</font></div><div class=""><font face="monospace" class=""> if (b)</font></div><div class=""><font face="monospace" class=""> *i = 3;</font></div><div class=""><font face="monospace" class="">}<br class=""><br class="">bool f2(int*);</font></div><div class=""><font face="monospace" class=""><br class=""></font></div><div class=""><font face="monospace" class="">void f3() {</font></div><div class=""><font face="monospace" class=""> int *x = nullptr;</font></div><div class=""><font face="monospace" class=""> f1(f2(x), x);</font></div><div class=""><font face="monospace" class="">}</font></div> <br class="">For the sake of argument, you could imagine that this code arose from perfectly reasonable user code - the user knows that 'f2' always returns false for a null pointer because it says so in the name (in the user code, with real names, etc).<br class=""><br class="">& it's actually Jump Threading that makes the code in the 'if' block (once inlined into f3) unreachable:<br class=""><br class=""><div class=""><font face="monospace" class="">*** IR Dump Before Jump Threading ***</font></div><div class=""><font face="monospace" class="">; Function Attrs: uwtable</font></div><div class=""><font face="monospace" class="">define void @_Z2f3v() local_unnamed_addr #1 {</font></div><div class=""><font face="monospace" class="">entry:</font></div><div class=""><font face="monospace" class=""> %call = call zeroext i1 @_Z2f2Pi(i32* null)</font></div><div class=""><font face="monospace" class=""> br i1 %call, label %if.then.i, label %_Z2f1bPi.exit</font></div><div class=""><font face="monospace" class=""><br class=""></font></div><div class=""><font face="monospace" class="">if.then.i: ; preds = %entry</font></div><div class=""><font face="monospace" class=""> store i32 3, i32* null, align 4, !tbaa !2</font></div><div class=""><font face="monospace" class=""> br label %_Z2f1bPi.exit</font></div><div class=""><font face="monospace" class=""><br class=""></font></div><div class=""><font face="monospace" class="">_Z2f1bPi.exit: ; preds = %entry, %if.then.i</font></div><div class=""><font face="monospace" class=""> ret void</font></div><div class=""><font face="monospace" class="">}</font></div><div class=""><font face="monospace" class="">*** IR Dump After Jump Threading ***</font></div><div class=""><font face="monospace" class="">; Function Attrs: uwtable</font></div><div class=""><font face="monospace" class="">define void @_Z2f3v() local_unnamed_addr #1 {</font></div><div class=""><font face="monospace" class="">entry:</font></div><div class=""><font face="monospace" class=""> %call = call zeroext i1 @_Z2f2Pi(i32* null)</font></div><div class=""><font face="monospace" class=""> br i1 %call, label %if.then.i, label %_Z2f1bPi.exit</font></div><div class=""><font face="monospace" class=""><br class=""></font></div><div class=""><font face="monospace" class="">if.then.i: ; preds = %entry</font></div><div class=""><font face="monospace" class=""> call void @llvm.trap()</font></div><div class=""><font face="monospace" class=""> unreachable</font></div><div class=""><font face="monospace" class=""><br class=""></font></div><div class=""><font face="monospace" class="">_Z2f1bPi.exit: ; preds = %entry</font></div><div class=""><font face="monospace" class=""> ret void</font></div><div class=""><font face="monospace" class="">}</font></div><div class=""><br class=""></div>Sure, it didn't remove the block, but it certainly removed the code. Nice enough to replace it with a trap, though. (so, yeah, not a perfect example - but you get the idea, all sorts of optimizations might decide to simplify code on the basis that UB can't actually happen)<br class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class="">The former requires</div><div class="">an analysis proving UB-absense, the later requires an analysis proving UB-presence. But it</div><div class="">isn’t logical to say you must delete UB-presence to enable proving UB-absense, because</div><div class="">in the real world after programs have passed static-analysis there won’t be any UB-presence</div><div class="">to delete.</div></div></blockquote><div class=""><br class=""></div><div class="">I don't understand this last bit, sorry. Without knowledge of the whole program I can't prove that the example above will never execute UB - but the C++ language lets me, the compiler, assume that that won't happen & optimize on that basis. No local static analysis could prove it - but the assumption helps improve the code. (& even if we had the whole program, some invariants would be difficult/impossible to practically prove - programmer indexes into an array based on the number of elementsn in a hash table - pretty darn difficult to statically analyze the whole probing hash table system, and the dynamic logic that populates it, to prove that only N elements will ever end up in the hash table, and thus using its size as an index into an array of N elements is safe - but we can assume, so there's no need to synthesize bounds checks around the array access, etc)</div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter Lawrence.</div></div><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 27, 2017, at 7:45 PM, David Blaikie <<a href="mailto:dblaikie@gmail.com" target="_blank" class="">dblaikie@gmail.com</a>> wrote:</div><br class="m_9100368324655226475Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Thu, Jul 27, 2017 at 7:30 PM Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Dave,<div class=""> The way I see it there should be just one pass that implements</div><div class="">deleting UB (maybe it would come to be called UBCE), and that one pass </div><div class="">should have a command line option simply for the reason than all passes</div><div class="">should have one.</div></div></blockquote><div class=""><br class="">I would hazard a guess that would be very difficult to implement the same functionality (as the compiler has today) efficiently with that approach - many optimizations would be inhibited from making progress because they couldn't prove the code didn't have UB, etc.<br class=""><br class="">Generally, even deleting UB code isn't approached directly, but may come about as a consequence of various other steps the compiler is taking.<br class=""><br class="">- Dave<br class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter Lawrence.</div></div><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 26, 2017, at 10:02 PM, David Blaikie <<a href="mailto:dblaikie@gmail.com" target="_blank" class="">dblaikie@gmail.com</a>> wrote:</div><br class="m_9100368324655226475m_2141608741726357655Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, Jul 26, 2017 at 9:23 PM Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">David,<div class=""> -fsanitize=undefined sounds great, but is not quite what I want.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">I recently ran into a problem with <span style="background-color:rgb(255,255,255)" class="">"CodeGen/MachineSink.cpp” [*], for a target</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">that has to expand Select into control flow.</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">The original IR had two select in a row that were based on the same condition,</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">so the CMP that sets the FLAGS reg in the second select was MCSE’ed to the</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">earlier CMP in the first select, so here we see the second Select without a CMP:</span></div><div class=""><span style="background-color:rgb(255,255,255)" class=""><br class=""></span></div><div class=""><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">BB#10: derived from LLVM BB %for.body.5</span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> Predecessors according to CFG: BB#3 BB#9</span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> %vreg49<def> = PHI %vreg47, <BB#9>, %vreg48, <BB#3>; DataRegs:%vreg49,%vreg47,%vreg48</span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""><br class=""></span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> //// <=== this SLLI clobbers FLAGS <============</span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> %vreg46<def> = SLLI %vreg5, 1, %FLAGS<imp-def,dead>; DataRegs:%vreg46,%vreg5</span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> BCC 2, <BB#12>, %FLAGS<imp-use></span></div><div style="margin:0px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> Successors according to CFG: BB#11 BB#12</span></div></div><div class=""><span style="font-variant-ligatures:no-common-ligatures" class=""><br class=""></span></div><div class=""><span style="background-color:rgb(255,255,255)" class=""><br class=""></span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">The problem is that Machine Code Sinking put an “SLLI"</span><span style="background-color:rgb(255,255,255)" class=""> instruction, that</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">modifies the FLAGS registers, in between the CMP and the BCC.</span></div><div class=""><span style="background-color:rgb(255,255,255)" class=""><br class=""></span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">The way I was able to work around this problem was to add</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">a command line option to “MachineSink.cpp” that defaults to false,</span></div><div class=""><span style="background-color:rgb(255,255,255)" class="">and add a check in </span>its runOnMachineFunction() to omit this pass.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">But I should not have had to, every FunctionPass and MachineFunctionPass</div><div class="">should have a name and a command line option to disable it by name.</div><div class=""><br class=""></div><div class="">Other compilers I’ve worked on have had such options, and I use them to</div><div class="">track down compiler bugs. In this case I instead had to "—debug-after-all"</div><div class="">and very tediously search through thousands of lines of output to locate</div><div class="">this bug.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">So I hope you can see where I’m coming from, the pass that deletes UB</div><div class="">should be no different, I should be able to disable it from the command line</div><div class="">as a matter of course.</div><div class=""><br class=""></div><div class="">Thoughts ?</div></div></blockquote><div class=""><br class="">These things seem like distinct goals to me - debuggability of the compiler and dealing with UB. I think -fsanitize=undefined is a pretty good way to help users deal with, diagnose, and act on UB. It isolates the issue - rather than having all optimizations have ways of switching themselves off when part of their analysis relies on UB - instead the optimizations rely on the IR definitions to make valid transformations, and it's a separate pass in the frontend (clang) that can add extra checks to avoid UB (& diagnose it as such, if that's the best thing to do).<br class=""><br class="">One could make an IR version of UBSan, that could take some IR and add null checks around every load/store, all the other things UBSan does. But I wouldn't expect that would be a priority for anyone to build (as it's more a compiler developer tool at that point - smaller audience, etc).<br class=""><br class="">For your debugging situation - bugpoint can slice & dice the pass list to try to reduce both the set of code being optimized, and the particular optimization that seems to be causing the problem. That might be worth a shot for you in cases like this?<br class=""><br class="">Otherwise I find print-after-all or the like to be pretty handy. Usually I reduce the input code first (with something like creduce or delta) so the IR isn't massive/hard to read. (bugpoint can help with that reduction as well)<br class=""><br class="">- Dave<br class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Peter.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">[* I haven’t reported this as a bug yet because I’m on 3.7.1, and haven’t had time</div><div class=""> to replicate it in 4.0.1, but should be able to within a month. My target resembles</div><div class=""> MSP430, so I’ll try to replicate it for that target in 4.0.1 ]</div></div><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 24, 2017, at 9:08 AM, David Blaikie <<a href="mailto:dblaikie@gmail.com" target="_blank" class="">dblaikie@gmail.com</a>> wrote:</div><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707Apple-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 Mon, Jul 24, 2017 at 9:02 AM Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</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=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 21, 2017, at 10:55 PM, Mehdi AMINI <<a href="mailto:joker.eph@gmail.com" target="_blank" class="">joker.eph@gmail.com</a>> wrote:</div><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">2017-07-21 22:44 GMT-07:00 Peter Lawrence<span class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</a>></span>:<br class=""><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=""><span style="font-size:14px" class="">Mehdi,</span><div class=""><span style="font-size:14px" class=""> Hal’s transformation only kicks in in the *presence* of UB</span></div></div></blockquote><div class=""><br class=""></div><div class="">No, sorry I entirely disagree with this assertion: I believe we optimize program where there is no UB. We delete dead code, code that never runs, so it is code that does not exercise UB.</div></div></div></div></div></blockquote><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div></div></div></div></blockquote><div class=""><br class=""></div></div></div><div style="word-wrap:break-word" class=""><div class=""><div class=""><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">Mehdi,</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> I had to read that sentence several times to figure out what the problem</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">is, which is sloppy terminology on my part</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">Strictly speaking the C standard uses “undefined behavior” to describe what</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">happens at runtime when an “illegal” construct is executed. I have been using</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">“undefined behavior” and UB to describe the “illegal” construct whether it is</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">executed or not.</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> </span><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420webkit-block-placeholder"></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">Hence I say “Hal’s transform is triggered by UB”, when I should be saying</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">“Hal’s transformation is triggered by illegal IR”.</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">All I can say is I’m not the only one being sloppy, what started this entire </span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">conversation is the paper titled “Taming Undefined Behavior in LLVM”, while</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">the correct title would be “Taming Illegal IR in LLVM”. (I think we are all</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">pretty confident that LLVM itself is UB-free, or at least we all hope so :-).</span></div><div style="margin:0px;line-height:normal;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span></div></div><div class="">I believe you are being sloppy when you say "we optimize program </div><div class="">where there is no UB”, because I believe you mean "we optimize program </div><div class="">under the assumption that there is no UB”. In other words we recognize</div><div class="">“Illegal” constructs and then assume they are unreachable, and delete </div><div class="">them, even when we can’t prove by any other means that they are</div><div class="">unreachable. We don’t know that there is no (runtime) UB, we just assume it.</div></div></div><div style="word-wrap:break-word" class=""><div class=""><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class="">The example Hal showed does not exhibit UB, it is perfectly valid according to the standard.</div><div class=""><br class=""></div></div></div></div></div></blockquote><div class=""><br class=""></div></div></div><div style="word-wrap:break-word" class=""><div class=""><div class="">Whether it exhibits UB at runtime or not is not the issue, the issue is what </div><div class="">a static analyzer or compiler can tell before runtime, see below</div></div></div><div style="word-wrap:break-word" class=""><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><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"><div style="word-wrap:break-word" class=""><div class=""><span style="font-size:14px" class="">, and</span></div><div class=""><span style="font-size:14px" class="">it does not matter how that UB got there, whether by function inlining</span></div><div class=""><span style="font-size:14px" class="">or without function inlining.</span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class="">The problem with Hal’s argument is that the compiler does not have</span></div><div class=""><span style="font-size:14px" class="">a built in ouija board with which it can conjure up the spirit of the</span></div><div class=""><span style="font-size:14px" class="">author of the source code and find out if the UB was intentional</span></div><div class=""><span style="font-size:14px" class="">with the expectation of it being deleted, or is simply a bug.</span></div><div class=""><span style="font-size:14px" class="">Function inlining does not magically turn a bug into not-a-bug, nor</span></div><div class=""><span style="font-size:14px" class="">does post-inlining simplification magically turn a bug into not-a-bug.</span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class="">Let me say it again: if the compiler can find this UB (after whatever</span></div><div class=""><span style="font-size:14px" class="">optimizations it takes to get there) then the static analyzer must</span></div><div class=""><span style="font-size:14px" class="">be able to do the same thing, forcing the programmer to fix it</span></div><div class=""><span style="font-size:14px" class="">rather than have the compiler optimize it.</span></div></div></blockquote><div class=""><br class=""></div><div class="">This is again incorrect: there is no UB in the program, there is nothing the static analyzer should report.</div></div></div></div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div></div></div><div style="word-wrap:break-word" class=""><div class=""><div class="">Hal’s example starts with this template</div><div class=""><br class=""></div><div class=""><div class=""><blockquote type="cite" style="background-color:rgb(255,255,255)" class=""><div class=""><div class="">template <typename T></div><div class="">int do_something(T mask, bool cond) {</div><div class=""> if (mask & 2)</div><div class=""> return 42;</div><div class=""><br class=""></div><div class=""> if (cond) {</div><div class=""> T high_mask = mask >> 48; // UB if sizeof(T) < 8, and cond true</div><div class=""> if (high_mask > 5)</div><div class=""> do_something_1(high_mask);</div><div class=""> else</div><div class=""> do_something_2();</div><div class=""> }</div><div class=""><br class=""></div><div class=""> return 0;</div><div class="">}</div></div></blockquote></div><div class=""><div class=""></div></div></div><div class=""><br class=""></div><div class="">Which is then instantiated with T = char,</div><div class="">and where it is impossible for either a static analyzer or a </div><div class="">compiler to figure out and prove that ‘cond’ is always false.</div><div class=""><br class=""></div><div class="">Hence a static analyzer issues a warning about the shift,</div><div class="">while llvm gives no warning and instead optimizes the entire</div><div class="">if-statement away on the assumption that it is unreachable.</div><div class=""><br class=""></div><div class="">Yes a static analyzer does issue a warning in this case.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">This is not the only optimization to be based on assumption</div><div class="">rather than fact, for example type-based-alias-analysis is</div><div class="">based on the assumption that the program is free of this sort</div><div class="">of aliasing. The difference is that a user can disable TBAA</div><div class="">and only TBAA if a program seems to be running incorrectly </div><div class="">when optimized and thereby possibly track down a bug, but</div><div class="">so far there is no command line option to disable UB-based-</div><div class="">analysis (or ‘illegal-IR-based” :-), but there really needs to be.</div><div class=""><br class=""></div><div class="">Do we at least agree on that last paragraph ?</div></div></div></blockquote><div class=""><br class="">We likely agree it's good to have tools to help developers identify/diagnose UB in their programs. And we have that: -fsanitize=undefined (not only does it effectively disable many UB-based optimizations (because it makes them not undefined - by conditionalizing the code to check that UB isn't reached, as such) - it even provides pretty diagnostics (of course you can't actually continue running the program - if the line after the diagnostic will dereference a null pointer - there's no non-null pointer we can magic-up, so execution must stop))<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=""><div class=""><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></div></div><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">The compile is still able to delete some code, because of breaking the abstraction through inlining or template instantiation for example (cf Hal example).</div><div class=""><br class=""></div><div class="">-- </div><div class="">Mehdi</div><div class=""><br class=""></div><div 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=""><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class="">Or, to put it another way: there is no difference between a compiler</span></div><div class=""><span style="font-size:14px" class="">and a static analyzer [*]. So regardless of whether it is the compiler or</span></div><div class=""><span style="font-size:14px" class="">the static analyzer that finds any UB, the only rational thing to do with</span></div><div class=""><span style="font-size:14px" class="">it is report it as a bug.</span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class="">Peter Lawrence.</span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><span style="font-size:14px" class="">[* in fact that’s one of the primary reasons Apple adopted llvm, to use</span></div><div class=""><span style="font-size:14px" class=""> <span class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707Apple-converted-space"> </span>It as a base for static analysis]</span></div><div class=""><div class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420h5"><div class=""><span style="font-size:14px" class=""><br class=""></span></div><div class=""><br class=""></div><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Jul 21, 2017, at 10:03 PM, Mehdi AMINI <<a href="mailto:joker.eph@gmail.com" target="_blank" class="">joker.eph@gmail.com</a>> wrote:</div><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420m_794137231564833888Apple-interchange-newline"><div class=""><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420m_794137231564833888Apple-interchange-newline"><br 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" 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">2017-07-21 21:27 GMT-07:00 Peter Lawrence<span class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420m_794137231564833888Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</a>></span>:<br class=""><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=""><font face="Menlo" class="">Sean,</font><div class=""><font face="Menlo" class=""> Let me re-phrase a couple words to make it perfectly clear</font></div><div class=""><br class=""><div class=""><span class=""><blockquote type="cite" class=""><div class=""><font face="Menlo" class="">On Jul 21, 2017, at 6:29 PM, Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" target="_blank" class="">peterl95124@sbcglobal.net</a>> wrote:</font></div><font face="Menlo" class=""><br class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420m_794137231564833888m_2150444843056015504Apple-interchange-newline"></font><div class=""><div style="word-wrap:break-word" class=""><font face="Menlo" class="">Sean,</font><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">Dan Gohman’s “transform” changes a loop induction variable, but does not change the CFG,</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">Hal’s “transform” deletes blocks out of the CFG, fundamentally altering it.</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><span style="font-family:Menlo" class="">These are two totally different transforms.</span></div></div></div></blockquote><blockquote type="cite" class=""><div style="word-wrap:break-word" class=""><div class=""><br class=""></div><div class=""><span style="font-family:Menlo" class=""><br class=""></span></div></div></blockquote><blockquote type="cite" class=""><div class=""><div style="word-wrap:break-word" class=""><div class=""><font face="Menlo" class="">And even the analysis is different,</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">The first is based on an *assumption* of non-UB (actually there is no analysis to perform)</font></div></div></div></blockquote></span><font face="Menlo" class=""> the *absence* of UB<br class=""></font><span class=""><blockquote type="cite" class=""><div style="word-wrap:break-word" class=""><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">the second Is based on a *proof* of existence of UB (here typically some non-trivial analysis is required)</font></div></div></blockquote></span><font face="Menlo" class=""> <span class="m_9100368324655226475m_2141608741726357655m_-1088913725511589707m_-3161789555371559420m_794137231564833888Apple-converted-space"> </span>the *presence* of UB<br class=""></font><span class=""><br class=""><blockquote type="cite" class=""><div style="word-wrap:break-word" class=""><div class=""><font face="Menlo" class="">These have, practically speaking, nothing in common.</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div></div></blockquote><div class=""><br class=""></div><div class=""><br class=""></div></span><div class=""><font face="Menlo" class="">In particular, the first is an optimization, while the second is a transformation that</font></div><div class=""><font face="Menlo" class="">fails to be an optimization because the opportunity for it happening in real world</font></div><div class=""><font face="Menlo" class="">code that is expected to pass compilation without warnings, static analysis without</font></div><div class=""><font face="Menlo" class="">warnings, and dynamic sanitizers without warnings, is zero.</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">Or to put it another way, if llvm manages to find some UB that no analyzer or</font></div><div class=""><font face="Menlo" class="">sanitizer does, and then deletes the UB, then the author of that part of llvm</font></div><div class=""><font face="Menlo" class="">is in the wrong group, and belongs over in the analyzer and/or sanitizer group.</font></div></div></div></div></blockquote><div class=""><br class=""></div><div class="">I don't understand your claim, it does not match at all my understand of what we managed to get on agreement on in the past.</div><div class=""><br class=""></div><div class="">The second transformation (dead code elimination to simplify) is based on the assumption that there is no UB.</div><div class=""><br class=""></div><div class="">I.e. after inlining for example, the extra context of the calling function allows us to deduce the value of some conditional branching in the inline body based on the impossibility of one of the path *in the context of this particular caller*.</div><div class=""><br class=""></div><div class="">This does not mean that the program written by the programmer has any UB inside.</div><div class=""><br class=""></div><div class="">This is exactly the example that Hal gave.</div><div class=""><br class=""></div><div class="">This can't be used to expose any meaningful information to the programmer, because it would be full of false positive. Basically a program could be clean of any static analyzer error, of any UBSAN error, and totally UB-free, and still exhibit tons and tons of such issues.</div><div class=""><br class=""></div><div class="">-- </div><div class="">Mehdi</div></div></div></blockquote></div></div></div></div></div></blockquote></div></div></div></div></blockquote></div></div></blockquote></div></div></div></blockquote></div><br class=""></div></div></blockquote></div></div>
</div></blockquote></div><br class=""></div></div></blockquote></div></div>
</div></blockquote></div><br class=""></div></div></blockquote></div></div>
</div></blockquote></div><br class=""></div></body></html>