llvm dev - Jun 2017 - killing undef and spreading poison

Nuno,
          we still need some examples showing that the definition
“Branching on poison is immediate-UB” is the best choice,
so far we only have arguments against it (the one for loop-switching).


Excerpts from the Paper [1]

Here’s the example you give for GVN

        t = x + 1;
        if (t == y) {
          w = x + 1;
          foo(w); 
        }
        Therefore, GVN can pick y as the representative value and transform the
code into:
        t = x + 1;
        if (t == y) {
          foo(y);
        }
        However, if y is a poison value and w is not

This really hinges on an incorrect choice for representative value of  w.

Any value with the “poison” attribute is not a valid representative for any
seemingly equivalent value.  If GVN is actually doing this it is a bug in GVN.

So this example doesn’t really show anything about branching.


Peter Lawrence.


[1.  http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
<http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf> ]

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170616/07993e10/attachment.html>

Hi  Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Nuno,
>           we still need some examples showing that the definition
> “Branching on poison is immediate-UB” is the best choice,
> so far we only have arguments against it (the one for loop-switching).
The alternative that allows us to propagate equalities in GVN (which
you seem to be alluding at) is to use an undef "instruction" that
produces a fixed but arbitrary value (just like "freeze(poison)" would
today).  However, that's bad for codegen since in some cases we will
have to keep around a live register containing consistent garbage.
Having both freeze and poison lets us use poison when we can (with
better codegen), and freeze when we must (with worse codegen) -- this
is the having-our-cake-and-eating-it-too scenario I was referring to
earlier.

-- Sanjoy
>
>
> Excerpts from the Paper [1]
>
> Here’s the example you give for GVN
>
>         t = x + 1;
>         if (t == y) {
>           w = x + 1;
>           foo(w);
>         }
>         Therefore, GVN can pick y as the representative value and transform
> the code into:
>         t = x + 1;
>         if (t == y) {
>           foo(y);
>         }
>         However, if y is a poison value and w is not
>
> This really hinges on an incorrect choice for representative value of  w.
>
> Any value with the “poison” attribute is not a valid representative for any
> seemingly equivalent value.  If GVN is actually doing this it is a bug in
> GVN.
>
> So this example doesn’t really show anything about branching.
>
>
> Peter Lawrence.
>
>
> [1.  http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf ]
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Hi Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Here’s the example you give for GVN
>
>         t = x + 1;
>         if (t == y) {
>           w = x + 1;
>           foo(w);
>         }
>         Therefore, GVN can pick y as the representative value and transform
> the code into:
>         t = x + 1;
>         if (t == y) {
>           foo(y);
>         }
>         However, if y is a poison value and w is not
>
> This really hinges on an incorrect choice for representative value of  w.
>
> Any value with the “poison” attribute is not a valid representative for any
> seemingly equivalent value.  If GVN is actually doing this it is a bug in
> GVN.
Fixing this "bug" is impractical, since in most cases we won't be
able
to prove that a value isn't poison.  So we want a semantics that lets
us do the above transform without having to prove that y isn't poison.

-- Sanjoy

Sanjoy,
            My belief is that this is a register allocation problem
that should not be addressed in the IR.

However you have changed the subject, and we still need an example
showing why the proposed definition for branch is the right one.


Peter Lawrence.

> On Jun 16, 2017, at 7:39 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi  Peter,
> 
> On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>> Nuno,
>>          we still need some examples showing that the definition
>> “Branching on poison is immediate-UB” is the best choice,
>> so far we only have arguments against it (the one for loop-switching).
> 
> The alternative that allows us to propagate equalities in GVN (which
> you seem to be alluding at) is to use an undef "instruction" that
> produces a fixed but arbitrary value (just like "freeze(poison)"
would
> today).  However, that's bad for codegen since in some cases we will
> have to keep around a live register containing consistent garbage.
> Having both freeze and poison lets us use poison when we can (with
> better codegen), and freeze when we must (with worse codegen) -- this
> is the having-our-cake-and-eating-it-too scenario I was referring to
> earlier.
> 
> -- Sanjoy
> 
>> 
>> 
>> Excerpts from the Paper [1]
>> 
>> Here’s the example you give for GVN
>> 
>>        t = x + 1;
>>        if (t == y) {
>>          w = x + 1;
>>          foo(w);
>>        }
>>        Therefore, GVN can pick y as the representative value and
transform
>> the code into:
>>        t = x + 1;
>>        if (t == y) {
>>          foo(y);
>>        }
>>        However, if y is a poison value and w is not
>> 
>> This really hinges on an incorrect choice for representative value of 
w.
>> 
>> Any value with the “poison” attribute is not a valid representative for
any
>> seemingly equivalent value.  If GVN is actually doing this it is a bug
in
>> GVN.
>> 
>> So this example doesn’t really show anything about branching.
>> 
>> 
>> Peter Lawrence.
>> 
>> 
>> [1.  http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf ]
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170619/316d3135/attachment.html>