<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jan 27, 2015 at 7:23 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><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">Hi David,<br>
<br>
I spent some time thinking about poison semantics this way, but here<br>
is where I always get stuck:<br>
<br>
Consider the IR fragment<br>
<br>
%x = zext i32 %maybe_poison to i64<br>
%y = lshr i64 %x 32<br>
%ptr = gep %global, %y<br>
store 42 to %ptr<br>
<br>
If %maybe_poison is poison, then is %y poison? For all i32 values of<br>
%maybe_poison, %y is i64 0, so in some sense you can determine the<br>
value %y without looking at %x.</blockquote><div><br></div><div>I agree, this makes sense.</div><div> </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">Given that, the store in the above<br>
fragment is not undefined behavior even if %maybe_poison is poison.<br>
However, this means if "%maybe_poison" is "add nuw %m, %n" it cannot<br>
be optimized to "add nuw (zext %m) (zext %n)" since that will change<br>
program behavior in an otherwise well-defined program.<br></blockquote><div><br></div><div>Hmm, I'm not so sure this is right.</div><div><br></div><div>Are we talking about transforming:</div><div>%add = add nuw i32 %x, %y<br></div><div>%res = zext i32 %add to i64<br></div><div><br></div><div>to:</div><div>%z1 = zext i32 %x to i64<br></div><div>%z2 = zext i32 %y to i64<br></div><div>%res = add nuw i64 %z1, %z2<br></div><div><br></div><div>?</div><div><br></div><div>This is OK because performing a zext by that many bits cannot result in a NUW violation.</div><div> </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">
<br>
One way out of this is to say that zext and sext of a value that is<br>
dependent on poison is poison. We'll have to do something similar for<br>
load shearing.<br></blockquote><div><br></div><div>sext must be dependent on the underlying value because it splats the sign bit.</div><div> </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">
<br>
The above "problem" can also be seen in<br>
<span class=""><br>
> ### Does comparing a poison value result in poison?<br>
><br>
> It depends. If the comparison couldn't solely be determined by<br>
> looking at the other operand, the result is poison.<br>
<br>
</span>This means we cannot do the C-style optimization "int a = ...; a <<br>
(a + 1)" ==> "true". In the case "a + 1" overflows, a is<br>
INT_SIGNED_MAX. But if a is INT_SIGNED_MAX, "a < X" is always false,<br>
for all values of X. So "a < a + 1" is defined; and it is true for "a<br>
!= INT_SIGNED_MAX" but false for "a == INT_SIGNED_MAX". Hence the<br>
expression cannot be folded to true.<br></blockquote><div><br></div><div>This part sounds tricky, I'm not immediately sure what to do.</div><div> </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">
<br>
<br>
I think the reason why poison is hard to formalize is that it<br>
fundamentally tries to give an N bit value behavior that cannot be<br>
justified by _any_ N bit value. It "breaks" llvm's type system.<br>
<span class=""><font color="#888888"><br>
-- Sanjoy<br>
</font></span><span class="im"><br>
<br>
On Tue, Jan 27, 2015 at 6:50 PM, David Majnemer<br>
<<a href="mailto:david.majnemer@gmail.com">david.majnemer@gmail.com</a>> wrote:<br>
</span><div class=""><div class="h5">> Hello,<br>
><br>
> What follows is my attempt to describe how poison works. Let me know what<br>
> you think.<br>
><br>
> --<br>
> David<br>
><br>
><br>
> # LLVM Poison Semantics<br>
><br>
> Poison is an LLVM concept which exists solely to enable further optimization<br>
> of LLVM IR. The exact behavior of poison has been, to say the least,<br>
> confusing for users, researchers and engineers working with LLVM.<br>
><br>
> This document hopes to clear up some of the confusion of poison and<br>
> hopefully explain *why* it has its semantics.<br>
><br>
> ## A Quick Introduction to Poison<br>
><br>
> Let's start with a concrete motivating example in C:<br>
> ```<br>
> int isSumGreater(int a, int b) {<br>
> return a + b > a;<br>
> }<br>
> ```<br>
><br>
> The C specification permits us to optimize the comparison in `isSumGreater`<br>
> to `b > 0` because signed overflow results in undefined behavior. A<br>
> reasonable translation of `isSumGreater` to LLVM IR could be:<br>
><br>
> ```<br>
> define i32 @isSumGreater(i32 %a, i32 %b) {<br>
> entry:<br>
> %add = add i32 %a, %b<br>
> %cmp = icmp sgt i32 %add, %a<br>
> %conv = zext i1 %cmp to i32<br>
> ret i32 %conv<br>
> }<br>
> ```<br>
><br>
> However, LLVM cannot determine that `%cmp` should not consider cases where<br>
> `%add` resulted in signed overflow. We need a way to communicate this<br>
> information to LLVM.<br>
><br>
> This is where the `nsw` and `nuw` flags come into play. `nsw` is short for<br>
> "no signed wrap", `nuw` is short for "no unsigned wrap".<br>
><br>
> With these, we can come up with a new formulation of `%add`: `add i32 nsw<br>
> %a, %b`.<br>
> LLVM can take this into account when it is optimizing the `%cmp` and replace<br>
> it with: `icmp sgt i32 %b, 0`.<br>
><br>
> ## Differences Between LLVM and C/C++<br>
><br>
> There are some interesting differences between what C++ and C specify and<br>
> how LLVM behaves with respect to performing an operationg which is not<br>
> permitted to overflow.<br>
><br>
> Perhaps chief among them is that evaluating an expression in C++ or C which<br>
> results performs an overflow is undefined behavior. In LLVM, executing an<br>
> instruction which is marked `nsw` but which violates signed overflow results<br>
> in poison. Values which have no relationship with poisoned values are not<br>
> effected by them.<br>
><br>
> Let us take the following C program into consideration:<br>
> ```<br>
> int calculateImportantResult(int a, int b) {<br>
> int result = 0;<br>
> if (a) {<br>
> result = a + b;<br>
> }<br>
> return result;<br>
> }<br>
> ```<br>
><br>
> A straightforward lowering to LLVM IR could be:<br>
> ```<br>
> define i32 @calculateImportantResult(i32 %a, i32 %b) {<br>
> entry:<br>
> %tobool = icmp ne i32 %a, 0<br>
> br i1 %tobool, label %if.then, label %if.end<br>
><br>
> if.then:<br>
> %add = add nsw i32 %a, %b<br>
> br label %if.end<br>
><br>
> if.end:<br>
> %result = phi i32 [ %add, %if.then ], [ 0, %entry ]<br>
> ret i32 %result<br>
> }<br>
> ```<br>
><br>
> Moving `%add` to the `%entry` block would be preferable and would allow<br>
> further optimizations:<br>
> ```<br>
> define i32 @calculateImportantResult(i32 %a, i32 %b) {<br>
> entry:<br>
> %tobool = icmp ne i32 %a, 0<br>
> %add = add nsw i32 %a, %b<br>
> %result = select i1 %tobool, i32 0, i32 %add<br>
> ret i32 %result<br>
> }<br>
> ```<br>
><br>
> In the original code, the calculation of `%add` was control dependent.<br>
> Now, `%add` might result in signed overflow in violation of the `nsw` flag.<br>
> Despite this, the program should behave as it did before because the<br>
> poisoned value is masked-out by the select. The next section will dive into<br>
> this in greater detail.<br>
><br>
> # Computation Involving Poison Values<br>
> Poison in a computation results in poison if the result cannot be<br>
> constrained by its non-poison operands.<br>
><br>
> Examples of this rule which will result in poison:<br>
> ```<br>
> %add = add i32 %x, %always_poison<br>
> %sub = sub i32 %x, %always_poison<br>
> %xor = xor i32 %x, %always_poison<br>
> %mul = mul i32 %always_poison, 1<br>
> ```<br>
><br>
> Examples of this rule which do not result in poison:<br>
> ```<br>
> %or = or i32 %always_poison, 2<br>
> %and = and i32 %always_poison, 2<br>
> %mul = mul i32 %always_poison, 0<br>
> ```<br>
><br>
> In fact, it would be reasonable to optimize `%or` to `2` and `%and` to `0`.<br>
> In this respect, poison is not different from `undef`.<br>
><br>
> The following example is only poison if `%cond` is false:<br>
> ```<br>
> %sel = select i1 %cond, i32 2, %always_poison<br>
> ```<br>
><br>
> ### Is it safe to have poison as a `call` argument?<br>
><br>
> A `call` instruction may or may not result in poison depending on exactly<br>
> how the callee uses the supplied arguments, it is not necessarily the case<br>
> that `call i32 @someFunction(i32 %always_poison)` results in poison.<br>
><br>
> LLVM cannot forbid poison from entering `call` arguments without prohibiting<br>
> an optimization pass from outlining code.<br>
><br>
> ### Is it safe to store poison to memory?<br>
><br>
> `store i32 %always_poison, i32* %mem` does not result in undefined behavior.<br>
> A subsequent load instruction like `%load = load i32* %mem` will result in<br>
> `%load` being a poison value.<br>
><br>
> ### Is it safe to load or store a poison memory location?<br>
><br>
> No. Poison works just like `undef` in this respect.<br>
><br>
> ### Does comparing a poison value result in poison?<br>
><br>
> It depends. If the comparison couldn't solely be determined by looking at<br>
> the other operand, the result is poison.<br>
><br>
> For example, `icmp i32 ule %always_poison, 4294967295` is `true`, not<br>
> poison.<br>
> However, `icmp i32 ne %always_poison, 7` is poison.<br>
><br>
> ### What if the condition operand in a `select` is poison?<br>
><br>
> In the example `%sel = select i1 %always_poison, i1 true, false`, `%sel` is<br>
> either `true` or `false`. Because, `%sel` depends on `%always_poison` it<br>
> too is poison.<br>
</div></div></blockquote></div><br></div></div>