<div dir="ltr"><div dir="ltr"><div dir="ltr"><div>I think it is slightly different, let me explain the reason.</div><div><br></div><div>Lowering `z = add nsw x, y` into the following assembly is valid, but `z = add x, y` into this isn't.</div><div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">if (x + y overflows)<br></div><div style="color:rgb(0,0,0)">  z = 0;</div><div style="color:rgb(0,0,0)">else</div><div style="color:rgb(0,0,0)">  z = ADD x y</div></div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">Lowering `z = add x, y` should be more 'precise'.</div><div style="color:rgb(0,0,0)">Instead of storing zero, 2's complement of x + y should be stored. This can be more expensive.</div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">Juneyoung</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Oct 30, 2020 at 5:13 AM Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com">stefanos.baziotis@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Juneyoung,<br><br>> Okay, previously I was assuming that P has two kinds of additions (trapping add & silent add).<div dir="ltr">> Maybe this isn't true, and P always traps when overflow happens? I hope my understanding is correct now.<br><br>Exactly, P has only one add that explodes on overflow. (btw just to be clear, the point is</div><div>not P - P was just introduced as an example to showcase the implicit semantics that poison adds).</div><div><br></div><div>I think I understood most of what you said above. My point was not so much nsw vs dropping nsw but in</div><div>any case, IIUC, dropping nsw is only bad since it only disables using arithmetic properties and their</div><div>codegen is the same.</div><br><div>> If we keep `add nsw` poison, lowering `add nsw` needs check, but the generated code is slightly different from `add`:</div><div>> ...</div><div>I'd think that this is the codegen of both `add nsw` and simply `add`. They both have to check whether there is overflow.</div><div><br></div><div>> In case of `add x, y` without nsw, z should be 2's complement otherwise.</div><div>I'm not sure I got that, but if P only supports 2's complement arithmetic anyway, that means that the codegen of the two (`add` and `add nsw`)</div><div>is identical right ?</div><div><br></div><div>Thanks again,<br>Stefanos</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Πέμ, 29 Οκτ 2020 στις 7:49 μ.μ., ο/η Juneyoung Lee <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr">Okay, previously I was assuming that P has two kinds of additions (trapping add & silent add).</div><div dir="ltr">Maybe this isn't true, and P always traps when overflow happens? I hope my understanding is correct now.</div><div dir="ltr"><br></div><div dir="ltr"><br></div><div>There is `add` without nsw in IR, and the backend should still put overflow check when lowering it.</div><div>If `add nsw` raises UB, dropping `nsw` from `add` will make the instruction more costly, so optimizations that drop nsw should be done more carefully.</div><div><br></div><div><br></div><div dir="ltr"><div>If we keep `add nsw` poison, lowering `add nsw` needs check, but the generated code is slightly different from `add`:</div><div><br></div><div>// Assume that we're lowering `z = add nsw x, y` in IR into P's assembly</div><div>if (x + y overflows)<br></div><div>  z = garbage value; // the backend can choose which value to put here</div><div>else</div><div>  z = x + y; // never traps</div><div><br></div><div>In case of `add x, y` without nsw, z should be 2's complement otherwise.</div><div><br></div><div>In perspective of optimizations, `add nsw` is still different from `add` because it allows simplifying more expressions using arithmetic properties.<br></div><div>But, dropping nsw will make the instruction expensive (as the UB case), so it should be carefully done as well.</div><div><br></div><div><br></div><div>If clang explicitly inserts the overflow check in IR (either in if or llvm.assume), I think that can be a good hint for code generation.</div><div>Code motion of adds should be more carefully done though, because the hint might be missed.</div><div><br></div><div>Juneyoung</div></div><div><br></div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 29, 2020 at 7:21 PM Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank">stefanos.baziotis@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Juneyoung,<br><div><br></div><div>I think I lost you in your last example. First, I'm not sure if this last C code corresponds to LLVM IR code or after-LLVM-IR code. Assuming that we're talking about LLVM IR and for my imaginary platform P:</div><div>The checking for overflow is not something that we have to do in LLVM IR, since as outlined in my previous email, LLVM IR has added the semantics that</div><div>signed overflow does not explode / trap (because if it didn't add these semantics, additions that exploded and which did not happen in the original program will happen now etc.). It is the lowering of LLVM IR that has to add it.</div><div><br></div><div>So, AFAIU, the "timeline" looks like this:</div><div><br></div><div>-- Before (LLVM IR):</div><div><div>for(i < n) {</div><div>  y = add nsw x + 1  <-- notice: no check, we don't need to do it, semantics say it doesn't trap</div><div>  use(y)</div><div>}</div></div><div>-- After (LLVM IR):</div><div>int tmp = add nsw x + 1;  <-- still no check..</div><div><div></div><div><div>for(i < n) {</div><div>  y =  tmp;</div><div>  use(y)</div><div>}</div></div></div><div><br></div><div>Now, we get that after and go ahead to lower it (i.e. after-LLVM-IR, back-end work). I'll actually try to do a better job than</div><div>my original email:</div><div><br></div><div>int tmp;</div><div>if (x != INT_MAX)  <-- notice the !=. This check is to _guarantee_ that the addition won't explode / trap since if that happened, it would violate the semantics, that we implicitly added, of LLVM IR.</div><div><div>  tmp = add nsw x + 1;</div><div><div></div><div><div>for(i < n) {</div><div>  y =  tmp;</div><div>  use(y)</div><div>}</div></div></div></div><div><br></div><div>So this (your example):<br><div>for(i < n) {</div><div>if (x == INT_MAX)</div><div>  trap</div><div>y = add nsw x + 1</div><div>use(y)</div><div>}</div><div>=></div><div><div style="color:rgb(0,0,0)">y = add nsw x + 1 // hoisted</div><div style="color:rgb(0,0,0)">for(i < n) {</div><div style="color:rgb(0,0,0)">if (x == INT_MAX)</div><div style="color:rgb(0,0,0)">  trap</div><div style="color:rgb(0,0,0)">use(y)</div><div style="color:rgb(0,0,0)">}</div></div><div style="color:rgb(0,0,0)"><br></div></div><div style="color:rgb(0,0,0)">does not make sense to me either in the LLVM IR level or in the after-LLVM-IR level. For the former, it doesn't make sense since I don't see why we have to do the check inside the loop;</div><div style="color:rgb(0,0,0)">the semantics mandate that it doesn't happen so we're ok, the burden is on the back-end. For the latter (i.e. we're in LLVM IR lowering, ISel or smth), we simply can't hoist this add outside without a check</div><div style="color:rgb(0,0,0)">since if x == INT_MAX, the platform P will explode _immediately_, no matter what the value of `n` (and of course, if `n == 0`, the original code wouldn't explode).</div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">Do I miss something ?</div><div style="color:rgb(0,0,0)">Guess: I think that what I miss is this: The semantics we added is not that signed wrapping won't explode. Rather: It does not explode _if it is not used in one of the X ways_. That would justify</div><div style="color:rgb(0,0,0)">your example transformation in the LLVM IR level.</div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">I hope this was not confusing, thanks for your time!</div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">- Stefanos</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Στις Πέμ, 29 Οκτ 2020 στις 4:29 π.μ., ο/η Juneyoung Lee <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>> έγραψε:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr">Hi Stefanos,<div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">So, to justify this transformation as correct, implicitly, poison has<br>_added definedness_ to signed wrapping: specifically, that the<br>computer won't explode if SW happens. AFAIU, that is ok as far as C++ semantics<br>are concerned:<br>Since signed wrapping was UB, making it more defined is ok.</blockquote></div><div><br></div><div><div>Your understanding is correct. Since signed overflow is UB in C/C++, lowering from C to IR can make such programs more defined.</div></div><div><br></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Instead, they have to lower it as something like:<br>if (x == INT_MAX)<br>  skip or whatever</blockquote></div><div><br></div><div>Yes.</div><div>This means that the overflow check and the actual add operation can be separated. This requires instruction selection to carefully combine the check and add, but for optimization this is beneficial because add can still be freely moved.</div><div><br></div><div>for(i < n) {</div><div>if (x == INT_MAX)</div><div>  trap</div><div>y = add nsw x + 1</div><div>use(y)</div><div>}</div><div>=></div><div><div style="color:rgb(0,0,0)">y = add nsw x + 1 // hoisted</div><div style="color:rgb(0,0,0)">for(i < n) {</div><div style="color:rgb(0,0,0)">if (x == INT_MAX)</div><div style="color:rgb(0,0,0)">  trap</div><div style="color:rgb(0,0,0)">use(y)</div><div style="color:rgb(0,0,0)">}</div></div><div style="color:rgb(0,0,0)"><br></div><div style="color:rgb(0,0,0)">Juneyoung</div></div></div></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 29, 2020 at 5:56 AM Stefanos Baziotis <<a href="mailto:stefanos.baziotis@gmail.com" target="_blank">stefanos.baziotis@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Juneyoung,<br><br>First of all, great job on your talk!<div><br>This is a question I guess you'd be the best person to answer but the rest of the LLVM community might want to participate.<div><br></div><div>I was thinking about a UB-related example that has been discussed by multiple people</div><div>(including you), all of them basically authors of this paper (<a href="https://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf" target="_blank">https://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf</a>):</div><div><br>-- Before opt:</div><div>for (int i = 0; i < n; ++i) {</div><div>  a[i] = x + 1;</div><div>}<br></div><div><br></div><div>-- After opt (LICM):</div><div>int tmp = x + 1;</div><div><div>for (int i = 0; i < n; ++i) {</div><div>  a[i] = tmp;</div><div>}</div></div><div>// Assume `tmp` is never used again.</div><div><br></div><div>The reasoning here, is let's make signed wrapping _deferred_ UB that will only</div><div>occur if the value is used in one of X ways (e.g. as a denominator). To that end, if</div><div>n == 0 and x == INT_MAX, UB will never occur because the value is never used.</div><div><br></div><div>But, by doing that, the first point is:</div><div>If we translate this into machine code, the signed wrapping _will_ happen, no matter </div><div>the value won't be used.</div><div><br></div><div>Now, imagine that on some platform P, signed wrapping explodes the computer.</div><div>The computer _will_ explode (should explode ? more on that later)</div><div>even if `n == 0`, something that would not happen in the original code.</div><div><br></div><div>So, to justify this transformation as correct, implicitly, poison has</div><div>_added definedness_ to signed wrapping: specifically, that the</div><div>computer won't explode if SW happens. AFAIU, that is ok as far as C++ semantics</div><div>are concerned:</div><div>Since signed wrapping was UB, making it more defined is ok.</div><div><br></div><div>But that definedness now has created a burden to whoever is writing a back-end</div><div>from LLVM IR to P (the SW exploding platform).</div><div>That is, now, if they see a `add <nsw>`, they can't lower it to a trivial signed add,<br></div><div>since if they do that and x == INT_MAX, the computer will explode and that violates</div><div>the semantics of _LLVM IR_ (since we mandated that SW doesn't explode the machine).</div><div><br></div><div>Instead, they have to lower it as something like:</div><div>if (x == INT_MAX)</div><div>  skip or whatever</div><div><br></div><div>Is this whole thinking correct ? UB, undef and poison all are very subtle so I'm trying</div><div>to wrap my head around.<br><br>Thanks,<br>Stefanos Baziotis</div></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div>
</blockquote></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div></div></div></div></div>
</blockquote></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div></div></div></div>