<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">(Responding to original post since this
is somewhat orthogonal to the discussion to date.) <br>
<br>
After reading through the thread to date, I'm coming to conclusion
that finding a single semantics for poison that both allows
speculation and optimization of a nsw optimization under the
assumption that overflow "never happens" is *hard*. Thinking
about it a bit, do we actually need to solve that problem?<br>
<br>
An alternate approach would be to split "nsw" into two pieces:
"nsw unreachable" and "nsw undef". A frontend for C or C++ would
produce "nsw unreachable".<br>
<br>
"nsw unreachable" allows the compiler to assume that the overflow
path can't happen. This enables all of the zext, comparison
folding, and other desirable optimizations we've mentioned.<br>
<br>
"nsw undef" only allows to the compiler to assume that overflow
produces an undefined value. In particular, the value produced is
not "poison"; it is simply undef.<br>
<br>
When the compiler speculates an "nsw unreachable" instruction, it
would replace it with an "nsw undef". However, if the compiler
can *prove* that the original instruction would execute on all
paths without a constraint which prevents overflow, it can
preserve "nsw unreachable". LICM today has logic that is close to
this in the form of isGuaranteedToExecute. (i.e. an add with loop
invariant operands overflows in the preheader exactly when it does
in the loop header)<br>
<br>
This approach would suffer from a tension between the
profitability of speculation and the potential lost optimizations
by going from "nsw unreachable" to "nsw undef". In practice, I
don't have a strong sense for how painful this would be. Does
anyone have a good sense for how aggressive we are, in practice,
about exploiting nsw? <br>
<br>
My intuition is that we already work hard to handle the
"guaranteed to execute" case due to needing to avoid newly
faulting loads. I suspect that we do (or at least can and should)
be surprisingly effective about recognizing the cases where we can
safely speculate the full "nsw unreachable" semantic. <br>
<br>
(An alternate way to phrase the above would be to say that a) add
"nsw unreachable" faults on overflow and b) we can't introduce
faults into a well defined program. This is very very similar to
how we reason about loads and dereferencability.)<br>
<br>
Philip<br>
<br>
p.s. It would also be interesting to weigh the profitability of
speculating a guarded/predicated form of an "add nsw
unreachable". But we should probably do predicated loads and
stores before we consider predication for simple arithmetic. <br>
<br>
On 01/27/2015 06:50 PM, David Majnemer wrote:<br>
</div>
<blockquote
cite="mid:CAL7bZ_dbtGC1fUBzoN75DWGnpzp5kmeBDUjWLA=L_X2hx2PKeA@mail.gmail.com"
type="cite">
<div dir="ltr">Hello,
<div><br>
</div>
<div>What follows is my attempt to describe how poison works.
Let me know what you think.</div>
<div><br>
</div>
<div>-- </div>
<div>David</div>
<div><br>
</div>
<div><br>
</div>
<div>
<div># LLVM Poison Semantics</div>
<div><br>
</div>
<div>Poison is an LLVM concept which exists solely to enable
further optimization of LLVM IR. The exact behavior of
poison has been, to say the least, confusing for users,
researchers and engineers working with LLVM.</div>
<div><br>
</div>
<div>This document hopes to clear up some of the confusion of
poison and hopefully explain *why* it has its semantics.</div>
<div><br>
</div>
<div>## A Quick Introduction to Poison</div>
<div><br>
</div>
<div>Let's start with a concrete motivating example in C:</div>
<div>```</div>
<div>int isSumGreater(int a, int b) {</div>
<div> return a + b > a;</div>
<div>}</div>
<div>```</div>
<div><br>
</div>
<div>The C specification permits us to optimize the comparison
in `isSumGreater` to `b > 0` because signed overflow
results in undefined behavior. A reasonable translation of
`isSumGreater` to LLVM IR could be:</div>
<div><br>
</div>
<div>```</div>
<div>define i32 @isSumGreater(i32 %a, i32 %b) {</div>
<div>entry:</div>
<div> %add = add i32 %a, %b</div>
<div> %cmp = icmp sgt i32 %add, %a</div>
<div> %conv = zext i1 %cmp to i32</div>
<div> ret i32 %conv</div>
<div>}</div>
<div>```</div>
<div><br>
</div>
<div>However, LLVM cannot determine that `%cmp` should not
consider cases where `%add` resulted in signed overflow. We
need a way to communicate this information to LLVM.</div>
<div><br>
</div>
<div>This is where the `nsw` and `nuw` flags come into play.
`nsw` is short for "no signed wrap", `nuw` is short for "no
unsigned wrap".</div>
<div><br>
</div>
<div>With these, we can come up with a new formulation of
`%add`: `add i32 nsw %a, %b`.</div>
<div>LLVM can take this into account when it is optimizing the
`%cmp` and replace it with: `icmp sgt i32 %b, 0`.</div>
<div><br>
</div>
<div>## Differences Between LLVM and C/C++</div>
<div><br>
</div>
<div>There are some interesting differences between what C++
and C specify and how LLVM behaves with respect to
performing an operationg which is not permitted to overflow.
</div>
<div><br>
</div>
<div>Perhaps chief among them is that evaluating an expression
in C++ or C which results performs an overflow is undefined
behavior. In LLVM, executing an instruction which is marked
`nsw` but which violates signed overflow results in poison.
Values which have no relationship with poisoned values are
not effected by them.</div>
<div><br>
</div>
<div>Let us take the following C program into consideration:</div>
<div>```</div>
<div>int calculateImportantResult(int a, int b) {</div>
<div> int result = 0;</div>
<div> if (a) {</div>
<div> result = a + b;</div>
<div> }</div>
<div> return result;</div>
<div>}</div>
<div>```</div>
<div><br>
</div>
<div>A straightforward lowering to LLVM IR could be:</div>
<div>```</div>
<div>define i32 @calculateImportantResult(i32 %a, i32 %b) {</div>
<div>entry:</div>
<div> %tobool = icmp ne i32 %a, 0</div>
<div> br i1 %tobool, label %if.then, label %if.end</div>
<div><br>
</div>
<div>if.then:</div>
<div> %add = add nsw i32 %a, %b</div>
<div> br label %if.end</div>
<div><br>
</div>
<div>if.end:</div>
<div> %result = phi i32 [ %add, %if.then ], [ 0, %entry ]</div>
<div> ret i32 %result</div>
<div>}</div>
<div>```</div>
<div><br>
</div>
<div>Moving `%add` to the `%entry` block would be preferable
and would allow further optimizations:</div>
<div>```</div>
<div>define i32 @calculateImportantResult(i32 %a, i32 %b) {</div>
<div>entry:</div>
<div> %tobool = icmp ne i32 %a, 0</div>
<div> %add = add nsw i32 %a, %b</div>
<div> %result = select i1 %tobool, i32 0, i32 %add</div>
<div> ret i32 %result</div>
<div>}</div>
<div>```</div>
<div><br>
</div>
<div>In the original code, the calculation of `%add` was
control dependent.</div>
<div>Now, `%add` might result in signed overflow in violation
of the `nsw` flag.</div>
<div>Despite this, the program should behave as it did before
because the poisoned value is masked-out by the select. The
next section will dive into this in greater detail.</div>
<div><br>
</div>
<div># Computation Involving Poison Values</div>
<div>Poison in a computation results in poison if the result
cannot be constrained by its non-poison operands.</div>
<div><br>
</div>
<div>Examples of this rule which will result in poison:</div>
<div>```</div>
<div> %add = add i32 %x, %always_poison</div>
<div> %sub = sub i32 %x, %always_poison</div>
<div> %xor = xor i32 %x, %always_poison</div>
<div> %mul = mul i32 %always_poison, 1</div>
<div>```</div>
<div><br>
</div>
<div>Examples of this rule which do not result in poison:</div>
<div>```</div>
<div> %or = or i32 %always_poison, 2</div>
<div> %and = and i32 %always_poison, 2</div>
<div> %mul = mul i32 %always_poison, 0</div>
<div>```</div>
<div><br>
</div>
<div>In fact, it would be reasonable to optimize `%or` to `2`
and `%and` to `0`. In this respect, poison is not different
from `undef`.</div>
<div><br>
</div>
<div>The following example is only poison if `%cond` is false:</div>
<div>```</div>
<div> %sel = select i1 %cond, i32 2, %always_poison</div>
<div>```</div>
<div><br>
</div>
<div>### Is it safe to have poison as a `call` argument?</div>
<div><br>
</div>
<div>A `call` instruction may or may not result in poison
depending on exactly how the callee uses the supplied
arguments, it is not necessarily the case that `call i32
@someFunction(i32 %always_poison)` results in poison.</div>
<div><br>
</div>
<div>LLVM cannot forbid poison from entering `call` arguments
without prohibiting an optimization pass from outlining
code.</div>
<div><br>
</div>
<div>### Is it safe to store poison to memory?</div>
<div><br>
</div>
<div>`store i32 %always_poison, i32* %mem` does not result in
undefined behavior. A subsequent load instruction like
`%load = load i32* %mem` will result in `%load` being a
poison value.</div>
<div><br>
</div>
<div>### Is it safe to load or store a poison memory location?</div>
<div><br>
</div>
<div>No. Poison works just like `undef` in this respect.</div>
<div><br>
</div>
<div>### Does comparing a poison value result in poison?</div>
<div><br>
</div>
<div>It depends. If the comparison couldn't solely be
determined by looking at the other operand, the result is
poison.</div>
<div><br>
</div>
<div>For example, `icmp i32 ule %always_poison, 4294967295` is
`true`, not poison.</div>
<div>However, `icmp i32 ne %always_poison, 7` is poison.</div>
<div><br>
</div>
<div>### What if the condition operand in a `select` is
poison?</div>
<div><br>
</div>
<div>In the example `%sel = select i1 %always_poison, i1 true,
false`, `%sel` is either `true` or `false`. Because, `%sel`
depends on `%always_poison` it too is poison.</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>