<div dir="ltr">Hello all,<div><br></div><div>I think not_poison (Johannes's used keyword) makes sense. We can simulate the original UB semantics by simply attaching it, as explained.</div><div>For the attributes other than nonnull, we may need more discussion; align attribute seems to be okay with defining it as poison, dereferenceable may need UB even without nonnull (because it needs to be non-poison as shown Nuno's hoisting example).</div><div><br></div><div>The reason why I think not_poison is good even if it may cause divergence of attribute semantics is that it brings a few more opportunities to optimizations.</div><div><br></div><div><br></div><div>(1) We can do optimizations that require certain operands to be never poison.</div><div><br></div><div>This is important for, say, hoisting of division:<br></div><div><br></div><div>void f(int x, int y) {</div><div>int x0 = x > 0 ? x : 1; // x0 is never zero *or poison(undef)*</div><div>loop() { f(y / x0); }</div><div>}</div><div>=></div><div><div>void f(int x, int y) { ; x shouldn't be undef/poison<br></div></div><div><div>int x0 = x > 0 ? x : 1;</div><div>int tmp = y / x0; // this may raise UB</div><div>loop() { f(tmp); }</div><div>}</div><div><br></div><div>This optimization is incorrect if x is undef or poison. If x has non_poison, this becomes valid.</div><div><br></div></div><div><div>I guess in many cases Rust/Swift functions can be lowered into IR functions with not_poison flags attached (though I'm not an Rust/Swift expert, so just a guess)</div><div>For C, people may want to allow idioms like below, so further investigation is needed:</div><div><br></div><div>int x, y;</div><div>if (cond) x = 1; else y = 1;</div><div>f(cond, x, y);</div><div></div></div><div><br></div><div><br></div><div>(2) Hoisting of function call becomes easier and semantically clearer</div><div><br></div><div><a href="https://godbolt.org/z/ThYt29">https://godbolt.org/z/ThYt29</a><br></div><div>f() call is hoisted out of the loop thanks to `speculatable` attribute, but this is problematic if nonnull was defined to raise UB.<br></div><div>We should have
syntactically
prohibited having nonnull and speculatable in a single function declaration, but this may block optimization opportunities.</div><div>By adding not_poison and making nonnull to have poison semantics, this problem is resolved.</div><div><br></div><div><br></div><div>Thanks,</div><div>Juneyoung Lee</div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Feb 19, 2020 at 6:37 AM Eli Friedman <<a href="mailto:efriedma@quicinc.com">efriedma@quicinc.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I think calling the attribute "used" is confusing. I'd suggest the following:<br>
<br>
"not_poison": If an argument is marked not_poison, and the argument is poison at runtime, the call is instant UB. Whether an argument is poison is checked after the rules for other attributes like "nonnull" and "align" are applied.<br>
<br>
This makes it clear that the IR semantics don't depend on the implementation of the called function. And it's the logical extension of the way we define the relationship between UB and poison for instructions.<br>
<br>
-Eli<br>
<br>
> -----Original Message-----<br>
> From: Doerfert, Johannes <<a href="mailto:jdoerfert@anl.gov" target="_blank">jdoerfert@anl.gov</a>><br>
> Sent: Tuesday, February 18, 2020 12:14 PM<br>
> To: Nuno Lopes <<a href="mailto:nuno.lopes@ist.utl.pt" target="_blank">nuno.lopes@ist.utl.pt</a>><br>
> Cc: 'Juneyoung Lee' <<a href="mailto:juneyoung.lee@sf.snu.ac.kr" target="_blank">juneyoung.lee@sf.snu.ac.kr</a>>; 'llvm-dev' <llvm-<br>
> <a href="mailto:dev@lists.llvm.org" target="_blank">dev@lists.llvm.org</a>>; 'Roman Lebedev' <<a href="mailto:lebedev.ri@gmail.com" target="_blank">lebedev.ri@gmail.com</a>>; llvm-<br>
> <a href="mailto:dev@redking.me.uk" target="_blank">dev@redking.me.uk</a>; Eli Friedman <<a href="mailto:efriedma@quicinc.com" target="_blank">efriedma@quicinc.com</a>>; 'Philip Reames'<br>
> <<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>>; Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>; 'Chung-Kil Hur'<br>
> <<a href="mailto:gil.hur@sf.snu.ac.kr" target="_blank">gil.hur@sf.snu.ac.kr</a>>; 'John Regehr' <<a href="mailto:regehr@cs.utah.edu" target="_blank">regehr@cs.utah.edu</a>><br>
> Subject: [EXT] Re: [llvm-dev] The semantics of nonnull attribute<br>
><br>
> I think we are actually in agreement. "Used" should be removable, it would<br>
> potentially define UB but that is valid and happening anyway everywhere.<br>
> Maybe my initial mail might have been confusing but I tried to show that with<br>
> this snippet:<br>
><br>
> > void @foo(nonnull);<br>
> > void @bar(nonnull used);<br>
> ><br>
> > > foo(NULL) // <- argument is poison inside of @foo<br>
> > > bar(NULL) // <- UB at the call site of @bar<br>
><br>
> If we remove `used`, thus go from @bar to @foo, we get a poison argument<br>
> instead of UB, which is fine.<br>
><br>
> WDYT?<br>
><br>
><br>
> > Even if the function is just a load of the pointer argument.<br>
><br>
> The Attributor does infer `nonnull` and `dereferenceable` in this case already so<br>
> `used` would follow the same logic (+ look for uses in branches etc)<br>
><br>
><br>
> FWIW, frontends that want `nonnull`, `align`, `dereferenceable`, etc. to keep the<br>
> UB behavior can just add `used` as well.<br>
><br>
> ________________________________________<br>
> From: Nuno Lopes <<a href="mailto:nuno.lopes@ist.utl.pt" target="_blank">nuno.lopes@ist.utl.pt</a>><br>
> Sent: Tuesday, February 18, 2020 12:29<br>
> To: Doerfert, Johannes<br>
> Cc: 'Juneyoung Lee'; 'llvm-dev'; 'Roman Lebedev'; <a href="mailto:llvm-dev@redking.me.uk" target="_blank">llvm-dev@redking.me.uk</a>; 'Eli<br>
> Friedman'; 'Philip Reames'; Finkel, Hal J.; 'Chung-Kil Hur'; 'John Regehr'<br>
> Subject: RE: [llvm-dev] The semantics of nonnull attribute<br>
><br>
> Hi Johannes,<br>
><br>
> >> Not sure the semantics of "used" you propose is sufficient. AFAIU the<br>
> >> proposal, "used" could only be used in cases where the function will<br>
> >> always trigger UB if poison is passed as argument. The semantics of<br>
> >> attributes is usually the other way around, since function calls need<br>
> >> to have UB as strong as the worst behavior of the function. If a<br>
> >> function may for some reason trigger UB with a given set of arguments,<br>
> >> then the function call has to trigger UB as well.<br>
> ><br>
> >"Used", as other attributes are "best effort". We can drop them any time, so<br>
> having "insufficient information" is not a correctness problem but an<br>
> optimization problem. I mean, even if the function always causes UB if a `null`<br>
> argument is given we do not need to know/annotate/exploit that. In fact, we<br>
> can, and do, throw away that information, e.g., by removing the instruction<br>
> known to cause UB which effectively defines some semantic for the UB program<br>
> (which is then "w/o UB"). Long story short, I don't think "as strong as the worst<br>
> behavior" is plausible (nor possible TBH).<br>
><br>
> I agree with the motivation, but not with the exact semantics. The reason is that<br>
> it seems that removing "used" wouldn't be possible. This is because a function<br>
> with "used" gives poison, and without gives UB. It should the other way around,<br>
> such that optimizers can freely remove "used".<br>
> To make it clear, what I understood was:<br>
> - %v = call @fn(nonnull null) -- %v == poison<br>
> - %v = call @fn(nonnull used null) -- UB<br>
><br>
> Even if the function is just a load of the pointer argument.<br>
><br>
> Nuno<br>
><br>
><br>
><br>
> > Imagine something like:<br>
> > Call f(null, 1)<br>
> ><br>
> > int f(nonnull %ptr, int c) {<br>
> > if (c)<br>
> > deref %ptr<br>
> > }<br>
> ><br>
> > You can't use the "used" attribute, since UB is only conditional.<br>
><br>
> Agreed, for the callee (f) you cannot annotate "used". You can place "used" on<br>
> the call site though*. And you can place it on the callee (f) if it was internal or<br>
> you copy it to make it internal. So the optimization potential is still there, even if<br>
> it is a little trickier.<br>
><br>
> * FWIW, one-level of selective context sensitive propagaton is planned<br>
> for the Attributor.<br>
><br>
><br>
> > we would say the return value of f(null, 1) is poison. But if you<br>
> > inline the function you get UB. Inlining has to continue to be correct<br>
> > without exceptions.<br>
><br>
> The attributes will just never represent the possible UB exhaustively.<br>
> I mean, inlining is still correct and the UB that it will expose, together with SCCP,<br>
> was there all along. With one-level of context sensitivity we could have even<br>
> known, without we just didn't know but that is fine too.<br>
><br>
> > ...<br>
> [ moved to the front ]<br>
><br>
><br>
> I hope this makes some sense.<br>
><br>
> Cheers,<br>
> Johannes<br>
><br>
> P.S.<br>
> I think I'll write "used" deduction later so we can take a look at how<br>
> this would look like.<br>
><br>
><br>
> > Thanks,<br>
> > Nuno<br>
> ><br>
> ><br>
> > -----Original Message-----<br>
> > From: Johannes Doerfert <<a href="mailto:jdoerfert@anl.gov" target="_blank">jdoerfert@anl.gov</a>><br>
> > Sent: 18 de fevereiro de 2020 02:35<br>
> > Subject: Re: [llvm-dev] The semantics of nonnull attribute<br>
> ><br>
> > Hi Juneyoung,<br>
> ><br>
> > thank you for starting this discussion again, the last one [0] did not<br>
> > really end in a solution but the issue remains and will only become<br>
> > worse, e.g., enable the Attributor and you might see all of the<br>
> > problems below exposed in a single pass [1-4].<br>
> ><br>
> > As I argued in [0], UB is problematic and I am strongly in favor of<br>
> > poison. In some sense I see UB as a very "strong" guarantee and poison<br>
> > as a fairly "week" one. We will have a hard time deriving the strong<br>
> > one and it might cause us to break things along the way, I mean your<br>
> > examples show that we already miscompile codes.<br>
> ><br>
> > I agree that poison is on its own not "strong enough" for certain<br>
> > optimization, as you pointed out below, but we could reasonably<br>
> > augment it with another attribute, let's call it `used`, that<br>
> > basically bridges the gap:<br>
> ><br>
> > void @foo(nonnull);<br>
> > void @bar(nonnull used);<br>
> ><br>
> > foo(NULL) // <- argument is poison inside of @foo<br>
> > bar(NULL) // <- UB at the call site of @bar<br>
> ><br>
> > A value is `used` if it would inevitably cause UB if it was poison at<br>
> > this program point. I hope this makes some sense if not I can explain<br>
> > in more detail.<br>
> ><br>
> > Btw. I think this also integrates well with other attribute problems<br>
> > we had in the past, e.g., memcpy(NULL, NULL, 0), since the pointers in<br>
> > this example were "not used" (in some naive implementation of memcpy<br>
> > at least).<br>
> ><br>
> > Maybe I have overlooked a problem with this solution so let me know<br>
> > what you think.<br>
> ><br>
> > Cheers,<br>
> > Johannes<br>
> ><br>
> ><br>
> > [0] <a href="https://reviews.llvm.org/D70749" rel="noreferrer" target="_blank">https://reviews.llvm.org/D70749</a><br>
> > [1] 1. below: <a href="https://godbolt.org/z/J4wFVw" rel="noreferrer" target="_blank">https://godbolt.org/z/J4wFVw</a> [2] 2. below:<br>
> > <a href="https://godbolt.org/z/TAkSC6" rel="noreferrer" target="_blank">https://godbolt.org/z/TAkSC6</a> [3] 3. below:<br>
> > <a href="https://godbolt.org/z/UqYi6S" rel="noreferrer" target="_blank">https://godbolt.org/z/UqYi6S</a> (doesn't work yet, will though) [4] 4.<br>
> > below: <a href="https://godbolt.org/z/Qkkc_E" rel="noreferrer" target="_blank">https://godbolt.org/z/Qkkc_E</a><br>
> > <a href="https://godbolt.org/z/uXAfp_" rel="noreferrer" target="_blank">https://godbolt.org/z/uXAfp_</a><br>
> > ...<br>
> ><br>
> > On 02/18, Juneyoung Lee via llvm-dev wrote:<br>
> > > Hello all,<br>
> > ><br>
> > > LangRef says it is undefined behavior to pass null to a nonnull<br>
> > > argument (`call f(nonnull null);`), but the semantics is too strong<br>
> > > for a few existing optimizations.<br>
> > > To support these, we can relax the semantics so `f(nonnull null)` is<br>
> > > equivalent to `f(poison)`, but (A) it again blocks another set of<br>
> > > optimizations, and (B) this makes the semantics of nonnull deviate<br>
> > > from other attributes like dereferenceable.<br>
> > > I found that there was a similar discussion about this issue in the<br>
> > > past as well, but seems it is not settled yet.<br>
> > > What should the semantics of nonnull be?<br>
> > > I listed a few optimizations that are relevant with this issue.<br>
> > ><br>
> > ><br>
> > > 1. Propagating nonnull attribute to callee's arg (<br>
> > > <a href="https://godbolt.org/z/-cVsVP" rel="noreferrer" target="_blank">https://godbolt.org/z/-cVsVP</a> )<br>
> > ><br>
> > > g(i8* ptr) {<br>
> > > f(nonnull ptr);<br>
> > > }<br>
> > > =><br>
> > > g(i8* nonnull ptr) {<br>
> > > f(nonnull ptr);<br>
> > > }<br>
> > ><br>
> > > This is correct if f(nonnull null) is UB. If ptr == null, f(nonnull<br>
> > > null) should have raised UB, so ptr shouldn't be null.<br>
> > > However, this transformation is incorrect if f(nonnull null) is<br>
> > > equivalent to f(poison).<br>
> > > If f was an empty function, f(nonnull null) never raises UB<br>
> > > regardless of ptr. So we can't guarantee ptr != null at other uses of ptr.<br>
> ><br>
> > For the given code snipped it is not even invalid to propagate nonnull<br>
> > in the poison case but your point is not wrong, if we have f(poison)<br>
> > we cannot derive anything from it if the argument might be unused.<br>
> ><br>
> ><br>
> > > 2. InstCombine (<a href="https://godbolt.org/z/HDQ7rD" rel="noreferrer" target="_blank">https://godbolt.org/z/HDQ7rD</a> ):<br>
> > ><br>
> > > %ptr_inb = gep inbounds %any_ptr, 1<br>
> > > f(%ptr_inb)<br>
> > > =><br>
> > > %ptr_inb = .. (identical)<br>
> > > f(nonnull %ptr_inb)<br>
> > ><br>
> > > This optimization is incorrect if `f(nonnull null)` is UB. The<br>
> > > reason is as follows.<br>
> > > If `gep inbounds %any_ptr, 1` yields poison, the source is<br>
> > > `f(poison)` whereas the optimized one is `f(nonnull poison)`.<br>
> > > `f(nonnull poison)` should be UB because `f(nonnull null)` is UB.<br>
> > > So, the transformation introduced UB.<br>
> > > This optimization is correct if both `f(nonnull null)` and<br>
> > > `f(nonnull poison)` are equivalent to `f(poison)`.<br>
> > ><br>
> > ><br>
> > > 3. <a href="https://reviews.llvm.org/D69477" rel="noreferrer" target="_blank">https://reviews.llvm.org/D69477</a><br>
> > ><br>
> > > f(nonnull ptr);<br>
> > > use(ptr);<br>
> > > =><br>
> > > llvm.assume(ptr != null);<br>
> > > use(ptr);<br>
> > > f(nonnull ptr);<br>
> > ><br>
> > > If f(nonnull null) is f(poison), this is incorrect. If ptr was null,<br>
> > > the added llvm.assume(ptr != null) raises UB whereas the source may<br>
> > > not raise UB at all. (e.g. assume that f() was an empty function) If<br>
> > > f(nonnull null) is UB, this is correct.<br>
> > ><br>
> > ><br>
> > > 4. Dead argument elimination (from <a href="https://reviews.llvm.org/D70749" rel="noreferrer" target="_blank">https://reviews.llvm.org/D70749</a> )<br>
> > ><br>
> > > f(nonnull ptr); // f's argument is dead => f(nonnull undef);<br>
> > ><br>
> > > This is incorrect if f(nonnull null) is UB. To make this correct,<br>
> > > nonnull should be dropped. This becomes harder to fix if nonnull was<br>
> > > attached at the signature of a function (not at the callee site).<br>
> > > It is correct if f(nonnull null) is f(poison).<br>
> > ><br>
> > > Actually the D70749's thread had an end-to-end miscompilation<br>
> > > example due to the interaction between this DAE and the optimization<br>
> > > 3 (insertion of llvm.assume).<br>
> > ><br>
> > > Thanks,<br>
> > > Juneyoung Lee<br>
> ><br>
><br>
> --<br>
><br>
> Johannes Doerfert<br>
> Researcher<br>
><br>
> Argonne National Laboratory<br>
> Lemont, IL 60439, USA<br>
><br>
> <a href="mailto:jdoerfert@anl.gov" target="_blank">jdoerfert@anl.gov</a><br>
<br>
</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>