llvm dev - Oct 2016 - RFC: Killing undef and spreading poison

Hi Mehdi,

On Wed, Oct 19, 2016 at 8:29 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>> sext(x):
>>  t = zext x
>>  result = 0
>>  for i = 0 to bitwidth:
>>    result |= t << i;
>>  return result
>
> I don’t understand this definition of sext?
> Are you trying to express that we will copy the sign one bit at a time, and
so every `new` bit is a new “read” of the undef sign?
Yes, that's what I was trying to express.  But, as you pointed out,
that isn't the actual definition of sext as specified in the lang ref.
>> then sext(undef) is, in fact, undef for the reason you highlighted.
>> In general, you cannot increase the number of uses of undef and
>> preserve semantics.
>>
>> You could say that the "zext x" above is "either 0 or
1" (i.e. it
>> implicitly freezes its input), but then e.g. (in todays scheme)
>> "trunc(zext(x))" cannot be replaced by "x”.
>
> I didn’t get this last part?
If zext(x) is defined to always produce a concrete value (that is,
zext(undef) is either 0 or 1), then this program can never fail the
assert:

  %t = zext i1 %some_val to i2
  %t.trunc = trunc(%t) to i1
  assert(%t.trunc == %t.trunc)

even if %some_val is undef.

However, if you get rid of the trunc/zext pair, and transform this to:

  assert(%some_val == %some_val)

then it can fail the assert if %some_val is undef.


For the transform above to be allowed, zext(undef) needs to retain the
"undefness" in its result (that is, it needs to be a non-deterministic
choice between 0 and 1 at each use site).

Does that answer your question, or were you asking something else?

-- Sanjoy

> On Oct 19, 2016, at 8:40 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Mehdi,
> 
> On Wed, Oct 19, 2016 at 8:29 PM, Mehdi Amini <mehdi.amini at
apple.com> wrote:
>>> sext(x):
>>> t = zext x
>>> result = 0
>>> for i = 0 to bitwidth:
>>>   result |= t << i;
>>> return result
>> 
>> I don’t understand this definition of sext?
>> Are you trying to express that we will copy the sign one bit at a time,
and so every `new` bit is a new “read” of the undef sign?
> 
> Yes, that's what I was trying to express.  But, as you pointed out,
> that isn't the actual definition of sext as specified in the lang ref.
> 
>>> then sext(undef) is, in fact, undef for the reason you highlighted.
>>> In general, you cannot increase the number of uses of undef and
>>> preserve semantics.
>>> 
>>> You could say that the "zext x" above is "either 0
or 1" (i.e. it
>>> implicitly freezes its input), but then e.g. (in todays scheme)
>>> "trunc(zext(x))" cannot be replaced by "x”.
>> 
>> I didn’t get this last part?
> 
> If zext(x) is defined to always produce a concrete value (that is,
> zext(undef) is either 0 or 1), then this program can never fail the
> assert:
> 
>  %t = zext i1 %some_val to i2
>  %t.trunc = trunc(%t) to i1
>  assert(%t.trunc == %t.trunc)
> 
> even if %some_val is undef.
> 
> However, if you get rid of the trunc/zext pair, and transform this to:
> 
>  assert(%some_val == %some_val)
> 
> then it can fail the assert if %some_val is undef.
> 
> 
> For the transform above to be allowed, zext(undef) needs to retain the
> "undefness" in its result (that is, it needs to be a
non-deterministic
> choice between 0 and 1 at each use site).
> 
> Does that answer your question, or were you asking something else?
That answers my question. 
But that’s not how we consider undef right now, is it?
I expect folding trunc(zext(x)) to x perfectly valid (i.e. the possibility that
“maybe” X is undef should not prevent this transformation).

It comes back to how we “freeze” the undef, and this case does not seem much
different from X ^ X to me right now.

— 
Mehdi

Hi Mehdi,

On Wed, Oct 19, 2016 at 9:32 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>> Does that answer your question, or were you asking something else?
>
> That answers my question.
> But that’s not how we consider undef right now, is it?
No, I don't think we consider a zext as freezing the undef today.

-- Sanjoy