<html>
  <head>
    <meta content="text/html; charset=windows-1252"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <div class="moz-cite-prefix">I'm going to try to compare the
      proposed semantics of poison with undef.  This may be completely
      wrong, but I'm hoping the corrections will help clarify the
      semantics.<br>
      <br>
      Begin attempt:<br>
      <br>
      poison is similar to undef in that the optimizer is free to assume
      any value for the poison bits in an *input* to an instruction. 
      Where it differs is that bits in the *output* which are not
      "entirely controlled by a non-poison input bit" are *also*
      poison.  <br>
      <br>
      This is different from undef in that there may be bits in the
      output whose values would be known for *any* specific value chosen
      for the poison input.  For undef, these bits would not be undef
      and would instead be known.  For poison, these bits are
      unconditionally poison.  <br>
      <br>
      (I'm having a hard time finding an example for this part; this
      implies it probably isn't true.)<br>
      <br>
      Similarly, the choice of domain of input choices may restrict the
      output of an instruction when supplied undef.  Such restrictions
      do not apply when the input is poison.  <br>
      <br>
      The simplest example of this difference might be:<br>
      %2 = sext i1 %1 to i32<br>
      <br>
      If %1 is undef, the %2 can take only two values: all zeros, or all
      ones.<br>
      <br>
      If %1 is poison, all bits of %2 are poison.  %2 can thus take
      *any* value representable by an i32.<br>
      <br>
      Note however that given a zext on the same input, 31 of the output
      bits would be defined in either case.  Only the last bit would be
      either undef or poison depending.  Note that the distinction
      between the two is important here in that it may influence
      propagation in later instructions.  <br>
      <br>
      <br>
      To phrase these two differently, undef must take a specific value
      (or set of values) on input to an instruction.  The only legal
      outputs are those which can result from all such values.  Poison
      does not need to take a specific value and propagates to any
      output bit which is influenced by the value of a poison input.  <br>
      <br>
      ------<br>
      <br>
      Ok, how wrong was I?<br>
      <br>
      Philip<br>
      <br>
      <br>
      <br>
      <br>
      <br>
      <br>
      <br>
      On 01/28/2015 08:53 PM, Philip Reames wrote:<br>
    </div>
    <blockquote cite="mid:54C9BCB8.8040904@philipreames.com" type="cite">
      <meta content="text/html; charset=windows-1252"
        http-equiv="Content-Type">
      <div class="moz-cite-prefix">On 01/28/2015 07:02 AM, Sean Silva
        wrote:<br>
      </div>
      <blockquote
cite="mid:CAHnXoakT0X5f7ova84iLb4Whq8YGF_2KO+6dssbcOp1CXypVMA@mail.gmail.com"
        type="cite">
        <div dir="ltr">Could you maybe provide an example where
          replacing `%always_poison` with `undef` will change the
          meaning? At least for me, the thing that I'm most unclear
          about is how poison differs from undef.</div>
      </blockquote>
      I will second this request for much the same reason.<br>
      <blockquote
cite="mid:CAHnXoakT0X5f7ova84iLb4Whq8YGF_2KO+6dssbcOp1CXypVMA@mail.gmail.com"
        type="cite">
        <div dir="ltr">
          <div><br>
          </div>
          <div>-- Sean Silva</div>
        </div>
        <div class="gmail_extra"><br>
          <div class="gmail_quote">On Wed, Jan 28, 2015 at 2:50 AM,
            David Majnemer <span dir="ltr"><<a
                moz-do-not-send="true"
                href="mailto:david.majnemer@gmail.com" target="_blank">david.majnemer@gmail.com</a>></span>
            wrote:<br>
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <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>
              _______________________________________________<br>
              LLVM Developers mailing list<br>
              <a moz-do-not-send="true"
                href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> 
                     <a moz-do-not-send="true"
                href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
              <a moz-do-not-send="true"
                href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
                target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
              <br>
            </blockquote>
          </div>
          <br>
        </div>
        <br>
        <fieldset class="mimeAttachmentHeader"></fieldset>
        <br>
        <pre wrap="">_______________________________________________
LLVM Developers mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a moz-do-not-send="true" 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>
      <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>