llvm dev - Oct 2016 - Killing undef and spreading poison

> On Oct 18, 2016, at 12:44 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> 
> Nuno Lopes wrote:
> 
>>> Okay; so the problem is that an instruction that is
value-equivalent
>>> to a poison value is not itself necessarily poison?
>> 
>> Right.
>> I think there were other examples, but I don't have them here
handy. But
>> at least this one is very problematic for GVN.
> 
> Another example is this:
> 
> void f(int k) {
>  if (k != 0) {
>    for (< finite loop >) {
>      if (always_false_at_runtime) {
>        print(1 / k);
>      }
>    }
>  }
> }
> 
> We'd like to hoist the `1 / k` computation to the preheader.  However,
we can't do that today if `k` is undef, and we've defined branching on
undef to be a non-deterministic choice.
This one isn’t clear to me: you can fold 1/k -> 1 when k is undef. And then
it is a constant which makes no point to hoist?

— 
Mehdi

> 
> I have some more details at:
http://www.playingwithpointers.com/problem-with-undef.html
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

>>>> Okay; so the problem is that an instruction that is
value-equivalent
>>>> to a poison value is not itself necessarily poison?
>>>
>>> Right.
>>> I think there were other examples, but I don't have them here
handy. But
>>> at least this one is very problematic for GVN.
>>
>> Another example is this:
>>
>> void f(int k) {
>>  if (k != 0) {
>>    for (< finite loop >) {
>>      if (always_false_at_runtime) {
>>        print(1 / k);
>>      }
>>    }
>>  }
>> }
>>
>> We'd like to hoist the `1 / k` computation to the preheader. 
However, we
>> can't do that today if `k` is undef, and we've defined
branching on undef
>> to be a non-deterministic choice.
>
> This one isn’t clear to me: you can fold 1/k -> 1 when k is undef. And 
> then it is a constant which makes no point to hoist?
Imagine that k is not a constant. Then you would like to hoist it to outside 
of the loop.
It seems safe to hoist it since we know k != 0 by the enclosing 'if'. 
And
so we transform the function into:

if (k != 0) {
   int t = 1 / k;
   for (< finite loop >) {
      if (always_false_at_runtime) {
         print(t);
      }
   }
}

Now you realize that k is undef and you get:
if (<non-deterministic branch>) {
   int t = 1 / undef;
   for (< finite loop >) {
      if (always_false_at_runtime) {
         print(t);
      }
   }
}

We can know chose to change the if condition to true and the undef in the 
division to zero (remember each use of undef can yield a different result).
Now we have undefined behavior (UB) because we've introduced a division by 
zero (which would not happen in the original program).
If branching on poison was UB instead then the original program was already 
executing UB so the transformation was fine.

This example can be fixed by freezing k instead. That way we ensure that k 
is actually non-zero within the 'if' statement.

Nuno

On Tue, Oct 18, 2016 at 5:42 PM, Nuno Lopes via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Okay; so the problem is that an instruction that is value-equivalent
>>>>> to a poison value is not itself necessarily poison?
>>>>>
>>>>
>>>> Right.
>>>> I think there were other examples, but I don't have them
here handy. But
>>>> at least this one is very problematic for GVN.
>>>>
>>>
>>> Another example is this:
>>>
>>> void f(int k) {
>>>  if (k != 0) {
>>>    for (< finite loop >) {
>>>      if (always_false_at_runtime) {
>>>        print(1 / k);
>>>      }
>>>    }
>>>  }
>>> }
>>>
>>> We'd like to hoist the `1 / k` computation to the preheader. 
However,
>>> we can't do that today if `k` is undef, and we've defined
branching on
>>> undef to be a non-deterministic choice.
>>>
>>
>> This one isn’t clear to me: you can fold 1/k -> 1 when k is undef.
And
>> then it is a constant which makes no point to hoist?
>>
>
> Imagine that k is not a constant. Then you would like to hoist it to
> outside of the loop.
> It seems safe to hoist it since we know k != 0 by the enclosing
'if'.  And
> so we transform the function into:
>
> if (k != 0) {
>   int t = 1 / k;
>   for (< finite loop >) {
>      if (always_false_at_runtime) {
>         print(t);
>      }
>   }
> }
>
> Now you realize that k is undef and you get:
>
Can IR (with/without your proposal) differentiate between C's "trap
representations" and "unspecified values"?

> if (<non-deterministic branch>) {
>   int t = 1 / undef;
>   for (< finite loop >) {
>      if (always_false_at_runtime) {
>         print(t);
>      }
>   }
> }
>
> We can know chose to change the if condition to true and the undef in the
> division to zero (remember each use of undef can yield a different result).
> Now we have undefined behavior (UB) because we've introduced a division
by
> zero (which would not happen in the original program).
> If branching on poison was UB instead then the original program was
> already executing UB so the transformation was fine.
>
> This example can be fixed by freezing k instead. That way we ensure that k
> is actually non-zero within the 'if' statement.
>
> Nuno
> _______________________________________________
> 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/20161018/294be250/attachment.html>