Re: [llvm-dev] killing undef and spreading poison

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev

1. ————— 
Dan,
       The reasoning given below for how GVN operates seems odd to me,

Poison is an attribute of a value,  just like nsw is an attribute of an operation,

So when GVN sees a pair of equal values, one of which has an extra attribute,
The proper choice for representative value is the one without the attribute,

Just like when GVN sees a pair of add operations, one of which has an extra attribute,
The proper choice for representative is the one without the attribute


2. —————
Nuno,
         If Dan agrees with the above then can we come up with a better example
for why branch-on-poison should be “undefined behavior”.



Thoughts ?
Comments ?
Questions ?

Peter Lawrence.

-------------------------------------------------------------------------------------------
>Nuno Lopes via llvm-dev at lists.llvm.org
>Tue Oct 18 08:10:41 PDT 2016
>
>>> Note that having branch on poison not trigger UB has its own problems.
>> Can you please elaborate on these problems?
>
>Sure! For example, the following transformation would be wrong if branch on poison was a non-deterministic branch instead of >UB:
>
>    %a = add i32 %x, 1
>    %c = icmp eq i32 %a, %p
>    br i1 %c, label %bb1, label %bb2
>bb1:
>    %b = add i32 %x, 1
>    %d = call i32 @bar(i32 %b)
> ------>
> bb1:
>    %d = call i32 @bar(i32 %p)

>GVN will perform this kind of transformation: it concludes that %a, %b, and %p are all equal and picks one representative value. However, these values are equal only when they are not poison.  If %p is indeed poison, then the transformation is wrong because before it was passing an ok value to bar() and after the transformation it is passing poison.
On the other hand, if branching on poison is UB, the original program was executing UB already because %p (and therefore %c) were poison. So the transformation is ok.
-------------------------------------------------------------------------------------------

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev


On Wed, Jun 14, 2017 at 1:26 PM, Peter Lawrence via llvm-dev <[hidden email]> wrote:

1. ————— 
Dan,
       The reasoning given below for how GVN operates seems odd to me,

Poison is an attribute of a value,  just like nsw is an attribute of an operation,

So when GVN sees a pair of equal values, one of which has an extra attribute,
The proper choice for representative value is the one without the attribute,

There are many many choices of what make *good* representative values in NewGVN.
I would deny any assertion that there is a proper choice, and that if there is one, it must be what you suggest :)
You actually can prove that there is no optimal such choice.  Different choices will lead you to discover different congruences in any practical algorithms, even complete ones (as the issues here are orthogonal to herbrand equivalence., and instead related to inference of facts from control flow and other things, as well as what the results from symbolic evaluation and simplification)
There are examples in the paper cited by newgvn of situations where different choices of values for predicate and phi inference will enable you to discover different congruences.

More importantly, given the other purpose of the representatives is to be used during simplification and symbolic evaluation, something we know we *cannot* possibly be optimal at, i do not believe you can assert that there is such an easily knowable best representative.

There is also no representation we could pick that would avoid all issues for others



Thoughts ?
Comments ?
Questions ?

The middle one.

I'm going to be frank and honest:
I don't feel like i have a good understanding of what your goal here is, or what you see your role as.
I can tell you, again, completely personally, that i find your approach off-putting at times.
To give a concrete example, here, what i see (again, from *my* perspective), is you are asserting things to me and asking me to confirm them or disprove them. I generally have not found this to be a good collaborative approach to increasing understanding.  You then say"If Dan agrees with the above then can we come up with a better example".  In practice, so far, that has meant "can *Nuno* come up with a better example" (IE the we seems to be turning into work for others).

I do not say this as a true complaint so much as a explanation of why i don't feel like i understand your perspective on things, and i think it would be  helpful for me to be able to.
I also certainly do not claim that there are not multiple ways to approach problem solving, communities, etc, or that what I or anyone else does is best.



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
Daniel,
           Thanks for taking the time to respond.

Regarding GVN and newGVN, I recently finished a search through the
llvm-dev archives for “nsw” in the subject line, and GVN was discussed in
some of those threads [1].

In particular it was claimed that there was a right choice for GVN to make given
two ADD instructions, one with the “nsw” attribute and one without, the one
without ‘nsw’ must be the representative.

This was described as a correctness issue, not an optimality issue. IE if you
are going to CSE those two ADDs, it is safe to loose information (drop the ‘nsw’)
but it is unsafe to put ‘nsw’ on to an operation that didn’t already have it
because that is like inserting an “llvm.assume" where there was none.

So I  am extrapolating from ’nsw’ instruction attribute, to ‘poison’ value attribute,
And wondering if (expecting that) you think the same logic applies.

I make no claim as to optimality, which seems to be what you are getting at.

Are you saying the post I am citing is incorrect ?
Or that I misunderstood it ?
Or could it be that you misread my email ?



Yes I am hoping *Nuno* can come up with a better example.  There is a claim
that “branch on poison is undefined behavior” is the right definition,  which is
not justified in the Paper [2], which John is waffling on,  which no one seems to
be able to justify, and which gives the appearance at least of flying in the face 
of common sense.

This is the IR definition we’re talking about here, the literal heart and soul of
the compiler, everyone should be at least a little bit concerned.


Peter Lawrence.


[1.   I’m having difficulty locating the post, here’s one that is similar

Tue Jul 22, 2014 “On semantics of add instruction - nsw, nuw”

   It also occurs to me that the more detailed post I am remembering but
   can’t find might have been about SCEV rather than GVN ]


[2.  “Taming undefined behavior in LLVM” ]





On Jun 14, 2017, at 2:12 PM, Daniel Berlin <[hidden email]> wrote:



On Wed, Jun 14, 2017 at 1:26 PM, Peter Lawrence via llvm-dev <[hidden email]> wrote:

1. ————— 
Dan,
       The reasoning given below for how GVN operates seems odd to me,

Poison is an attribute of a value,  just like nsw is an attribute of an operation,

So when GVN sees a pair of equal values, one of which has an extra attribute,
The proper choice for representative value is the one without the attribute,

There are many many choices of what make *good* representative values in NewGVN.
I would deny any assertion that there is a proper choice, and that if there is one, it must be what you suggest :)
You actually can prove that there is no optimal such choice.  Different choices will lead you to discover different congruences in any practical algorithms, even complete ones (as the issues here are orthogonal to herbrand equivalence., and instead related to inference of facts from control flow and other things, as well as what the results from symbolic evaluation and simplification)
There are examples in the paper cited by newgvn of situations where different choices of values for predicate and phi inference will enable you to discover different congruences.

More importantly, given the other purpose of the representatives is to be used during simplification and symbolic evaluation, something we know we *cannot* possibly be optimal at, i do not believe you can assert that there is such an easily knowable best representative.

There is also no representation we could pick that would avoid all issues for others



Thoughts ?
Comments ?
Questions ?

The middle one.

I'm going to be frank and honest:
I don't feel like i have a good understanding of what your goal here is, or what you see your role as.
I can tell you, again, completely personally, that i find your approach off-putting at times.
To give a concrete example, here, what i see (again, from *my* perspective), is you are asserting things to me and asking me to confirm them or disprove them. I generally have not found this to be a good collaborative approach to increasing understanding.  You then say"If Dan agrees with the above then can we come up with a better example".  In practice, so far, that has meant "can *Nuno* come up with a better example" (IE the we seems to be turning into work for others).

I do not say this as a true complaint so much as a explanation of why i don't feel like i understand your perspective on things, and i think it would be  helpful for me to be able to.
I also certainly do not claim that there are not multiple ways to approach problem solving, communities, etc, or that what I or anyone else does is best.




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
The GVN example we provided was supposed to be a sufficient argument.
But.. see section 3.2 of the paper you mentioned for another example  
of why a non-deterministic jump on poison/undef is not a good idea.
Alternatively see slide 12 of this:  
http://llvm.org/devmtg/2016-11/Slides/Lopes-LongLivePoison.pdf
And a miscompilation: https://bugs.llvm.org/show_bug.cgi?id=21412

See also my reply to your email yesterday. You cannot drop poison like  
you drop nsw; that doesn't exist (currently).

Nuno



Citando Peter Lawrence via llvm-dev <[hidden email]>:

> Daniel,
>            Thanks for taking the time to respond.
>
> Regarding GVN and newGVN, I recently finished a search through the
> llvm-dev archives for “nsw” in the subject line, and GVN was discussed in
> some of those threads [1].
>
> In particular it was claimed that there was a right choice for GVN  
> to make given
> two ADD instructions, one with the “nsw” attribute and one without, the one
> without ‘nsw’ must be the representative.
>
> This was described as a correctness issue, not an optimality issue. IE if you
> are going to CSE those two ADDs, it is safe to loose information  
> (drop the ‘nsw’)
> but it is unsafe to put ‘nsw’ on to an operation that didn’t already have it
> because that is like inserting an “llvm.assume" where there was none.
>
> So I  am extrapolating from ’nsw’ instruction attribute, to ‘poison’  
> value attribute,
> And wondering if (expecting that) you think the same logic applies.
>
> I make no claim as to optimality, which seems to be what you are getting at.
>
> Are you saying the post I am citing is incorrect ?
> Or that I misunderstood it ?
> Or could it be that you misread my email ?
>
>
>
> Yes I am hoping *Nuno* can come up with a better example.  There is a claim
> that “branch on poison is undefined behavior” is the right  
> definition,  which is
> not justified in the Paper [2], which John is waffling on,  which no  
> one seems to
> be able to justify, and which gives the appearance at least of  
> flying in the face
> of common sense.
>
> This is the IR definition we’re talking about here, the literal  
> heart and soul of
> the compiler, everyone should be at least a little bit concerned.
>
>
> Peter Lawrence.
>
>
> [1.   I’m having difficulty locating the post, here’s one that is similar
>
> Tue Jul 22, 2014 “On semantics of add instruction - nsw, nuw”
>
>    It also occurs to me that the more detailed post I am remembering but
>    can’t find might have been about SCEV rather than GVN ]
>
>
> [2.  “Taming undefined behavior in LLVM” ]
>
>
>
>
>
>> On Jun 14, 2017, at 2:12 PM, Daniel Berlin <[hidden email]> wrote:
>>
>>
>>
>> On Wed, Jun 14, 2017 at 1:26 PM, Peter Lawrence via llvm-dev  
>> <[hidden email] <mailto:[hidden email]>> wrote:
>>
>> 1. —————
>> Dan,
>>        The reasoning given below for how GVN operates seems odd to me,
>>
>> Poison is an attribute of a value,  just like nsw is an attribute  
>> of an operation,
>>
>> So when GVN sees a pair of equal values, one of which has an extra  
>> attribute,
>> The proper choice for representative value is the one without the attribute,
>>
>> There are many many choices of what make *good* representative  
>> values in NewGVN.
>> I would deny any assertion that there is a proper choice, and that  
>> if there is one, it must be what you suggest :)
>> You actually can prove that there is no optimal such choice.  
>> Different choices will lead you to discover different congruences  
>> in any practical algorithms, even complete ones (as the issues here  
>> are orthogonal to herbrand equivalence., and instead related to  
>> inference of facts from control flow and other things, as well as  
>> what the results from symbolic evaluation and simplification)
>> There are examples in the paper cited by newgvn of situations where  
>> different choices of values for predicate and phi inference will  
>> enable you to discover different congruences.
>>
>> More importantly, given the other purpose of the representatives is  
>> to be used during simplification and symbolic evaluation, something  
>> we know we *cannot* possibly be optimal at, i do not believe you  
>> can assert that there is such an easily knowable best representative.
>>
>> There is also no representation we could pick that would avoid all  
>> issues for others
>>
>>
>>
>> Thoughts ?
>> Comments ?
>> Questions ?
>>
>> The middle one.
>>
>> I'm going to be frank and honest:
>> I don't feel like i have a good understanding of what your goal  
>> here is, or what you see your role as.
>> I can tell you, again, completely personally, that i find your  
>> approach off-putting at times.
>> To give a concrete example, here, what i see (again, from *my*  
>> perspective), is you are asserting things to me and asking me to  
>> confirm them or disprove them. I generally have not found this to  
>> be a good collaborative approach to increasing understanding.  You  
>> then say"If Dan agrees with the above then can we come up with a  
>> better example".  In practice, so far, that has meant "can *Nuno*  
>> come up with a better example" (IE the we seems to be turning into  
>> work for others).
>>
>> I do not say this as a true complaint so much as a explanation of  
>> why i don't feel like i understand your perspective on things, and  
>> i think it would be  helpful for me to be able to.
>> I also certainly do not claim that there are not multiple ways to  
>> approach problem solving, communities, etc, or that what I or  
>> anyone else does is best.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
Nuno,
          I am confused, you have not shown why branch on poison should
be defined to be UB, you have shown why “each use of ‘undef’ can yield
a different result” is a bad definition. 

So we still don’t have a good reason that justifies “branch on poison is UB”.


Peter Lawrence.


On Jun 15, 2017, at 7:31 AM, Nuno Lopes <[hidden email]> wrote:

The GVN example we provided was supposed to be a sufficient argument.
But.. see section 3.2 of the paper you mentioned for another example of why a non-deterministic jump on poison/undef is not a good idea.

Here’s what 3.2 says: 

“Since each use of ‘undef’ can yield a different result, we can have the top level if-condition being true and still divide by zero”,

it says nothing about branch on undefined or branch on poison.



Slide 12 is an exact duplicate of the example in the Paper.

It actually has arrows pointing to the two uses of ‘k’ that can have different values
because of the bad definition of “undef"



Again, this bug shows the exact same thing once you reduce it to simplest form.


See also my reply to your email yesterday. You cannot drop poison like you drop nsw; that doesn't exist (currently).

Nuno










Citando Peter Lawrence via llvm-dev <[hidden email]>:

Daniel,
          Thanks for taking the time to respond.

Regarding GVN and newGVN, I recently finished a search through the
llvm-dev archives for “nsw” in the subject line, and GVN was discussed in
some of those threads [1].

In particular it was claimed that there was a right choice for GVN to make given
two ADD instructions, one with the “nsw” attribute and one without, the one
without ‘nsw’ must be the representative.

This was described as a correctness issue, not an optimality issue. IE if you
are going to CSE those two ADDs, it is safe to loose information (drop the ‘nsw’)
but it is unsafe to put ‘nsw’ on to an operation that didn’t already have it
because that is like inserting an “llvm.assume" where there was none.

So I  am extrapolating from ’nsw’ instruction attribute, to ‘poison’ value attribute,
And wondering if (expecting that) you think the same logic applies.

I make no claim as to optimality, which seems to be what you are getting at.

Are you saying the post I am citing is incorrect ?
Or that I misunderstood it ?
Or could it be that you misread my email ?



Yes I am hoping *Nuno* can come up with a better example.  There is a claim
that “branch on poison is undefined behavior” is the right definition,  which is
not justified in the Paper [2], which John is waffling on,  which no one seems to
be able to justify, and which gives the appearance at least of flying in the face
of common sense.

This is the IR definition we’re talking about here, the literal heart and soul of
the compiler, everyone should be at least a little bit concerned.


Peter Lawrence.


[1.   I’m having difficulty locating the post, here’s one that is similar

Tue Jul 22, 2014 “On semantics of add instruction - nsw, nuw”

  It also occurs to me that the more detailed post I am remembering but
  can’t find might have been about SCEV rather than GVN ]


[2.  “Taming undefined behavior in LLVM” ]





On Jun 14, 2017, at 2:12 PM, Daniel Berlin <[hidden email]> wrote:



On Wed, Jun 14, 2017 at 1:26 PM, Peter Lawrence via llvm-dev <[hidden email] <[hidden email]>> wrote:

1. —————
Dan,
      The reasoning given below for how GVN operates seems odd to me,

Poison is an attribute of a value,  just like nsw is an attribute of an operation,

So when GVN sees a pair of equal values, one of which has an extra attribute,
The proper choice for representative value is the one without the attribute,

There are many many choices of what make *good* representative values in NewGVN.
I would deny any assertion that there is a proper choice, and that if there is one, it must be what you suggest :)
You actually can prove that there is no optimal such choice.  Different choices will lead you to discover different congruences in any practical algorithms, even complete ones (as the issues here are orthogonal to herbrand equivalence., and instead related to inference of facts from control flow and other things, as well as what the results from symbolic evaluation and simplification)
There are examples in the paper cited by newgvn of situations where different choices of values for predicate and phi inference will enable you to discover different congruences.

More importantly, given the other purpose of the representatives is to be used during simplification and symbolic evaluation, something we know we *cannot* possibly be optimal at, i do not believe you can assert that there is such an easily knowable best representative.

There is also no representation we could pick that would avoid all issues for others



Thoughts ?
Comments ?
Questions ?

The middle one.

I'm going to be frank and honest:
I don't feel like i have a good understanding of what your goal here is, or what you see your role as.
I can tell you, again, completely personally, that i find your approach off-putting at times.
To give a concrete example, here, what i see (again, from *my* perspective), is you are asserting things to me and asking me to confirm them or disprove them. I generally have not found this to be a good collaborative approach to increasing understanding.  You then say"If Dan agrees with the above then can we come up with a better example".  In practice, so far, that has meant "can *Nuno* come up with a better example" (IE the we seems to be turning into work for others).

I do not say this as a true complaint so much as a explanation of why i don't feel like i understand your perspective on things, and i think it would be  helpful for me to be able to.
I also certainly do not claim that there are not multiple ways to approach problem solving, communities, etc, or that what I or anyone else does is best.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
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.




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev


On Thu, Jun 15, 2017 at 6:32 AM, Peter Lawrence <[hidden email]> wrote:
Daniel,
           Thanks for taking the time to respond.

This is going to be my last response.
 
Regarding GVN and newGVN, I recently finished a search through the
llvm-dev archives for “nsw” in the subject line, and GVN was discussed in
some of those threads [1].

In particular it was claimed that there was a right choice for GVN to make given
two ADD instructions, one with the “nsw” attribute and one without, the one
without ‘nsw’ must be the representative.

GVN does not choose representatives based on the kind of attributes you refer to because they are not properties of the value for the purposes of representation, nor do i see how it would ever make sense to do so.
GVN can always patch the instructions after the fact to make sure the set of attributes of the *operations* where the instructions occur is correct for where they came from.



This was described as a correctness issue, not an optimality issue. IE if you
are going to CSE those two ADDs, it is safe to loose information (drop the ‘nsw’)
but it is unsafe to put ‘nsw’ on to an operation that didn’t already have it
because that is like inserting an “llvm.assume" where there was none.

This is unrelated to the choice of representative, and related to ensuring that operations are modified for the properties of the representative chosen.
Anything else would avoid value numbering 

"add a, b" and "add nsw a, b"

to the same thing, when at worst, i just may have to drop the NSW if i replace the second with the first



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
Hi  Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
Hi Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
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 <[hidden email]> wrote:

Hi  Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<[hidden email]> 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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
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 <[hidden email]> 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 <[hidden email]> wrote:

Hi  Peter,

On Fri, Jun 16, 2017 at 5:32 PM, Peter Lawrence via llvm-dev
<[hidden email]> 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
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] killing undef and spreading poison

Tim Northover via llvm-dev
In reply to this post by Tim Northover via llvm-dev
Hi Peter,

On Mon, Jun 19, 2017 at 7:14 AM, Peter Lawrence
<[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Loading...