[llvm-dev] Killing undef and spreading poison

[Nuno Lopes via 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