llvm dev - Jun 2017 - killing undef and spreading poison

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>

Can you explain how this is a register allocation problem?  If I have
"values" then I cannot elide them when performing shuffle
transformation,
but when I have 'undef's I can.

I think that it is also essential to differentiate between "undefined
behaviour" and "implementation defined behaviour".  These are
discrete
concepts in the ISO Standards lexicon because they have very different
meanings and purpose.

    MartinO

On 19 June 2017 at 15:14, Peter Lawrence via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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> 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
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> 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/89662f1f/attachment.html>

Hi Peter,

On Mon, Jun 19, 2017 at 7:14 AM, Peter Lawrence
<peterl95124 at sbcglobal.net> wrote:
>             My belief is that this is a register allocation problem
> that should not be addressed in the IR.
This is getting weird since you've started so many threads, but it
isn't *just* a register allocator problem (edit: just noticed that
Martin something similar) -- in your "live in undef value" scheme
there also are mid-level optimizations we will not be able to do.
> However you have changed the subject, and we still need an example
I'm not convinced that I changed the subject.  You said
>           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).
There are two ways we can avoid branching on “Branching on poison is
immediate-UB” and still have GVN propagate equalities:

 - Propagate equalities only if the thing we're propagating isn't
poison.  As I've stated in this thread, that's almost impossible to
prove in interesting cases.
 - Ditch poison and have an `undef` like instruction (which is
equivalent to a live-in undef register), which brings us the regalloc
and mid-level opt problem.

So both of the thing I said seem on-topic to me.

-- Sanjoy

Sanjoy,
            we still need an example, some C source code, that shows
clearly why the definition of immediate-UB for branch-on-undef / poison
is the right choice. Talking, even on topic, isn’t an example.

Peter Lawrence.

> On Jun 19, 2017, at 9:43 AM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
>> 
>> However you have changed the subject, and we still need an example
> 
> I'm not convinced that I changed the subject.  You said
> 
>>          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).
> 
> There are two ways we can avoid branching on “Branching on poison is
> immediate-UB” and still have GVN propagate equalities:
> 
> - Propagate equalities only if the thing we're propagating isn't
> poison.  As I've stated in this thread, that's almost impossible to
> prove in interesting cases.
> - Ditch poison and have an `undef` like instruction (which is
> equivalent to a live-in undef register), which brings us the regalloc
> and mid-level opt problem.
> 
> So both of the thing I said seem on-topic to me.
> 
> -- Sanjoy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170623/a158e2c7/attachment.html>