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

Hi Alexandre,

On Wed, Oct 19, 2016 at 11:19 AM, Alexandre Isoard
<alexandre.isoard at gmail.com> wrote:
> I am probably missing something important, but what I mean is that you can
> always convert:
>
> %y = xor %x, %x
> to
> %y = 0
>
> Regardless of if %x is/might be an undef. That is, consider that reading %x
> any number of times always give the value of its definition (as SSA
> suggest). Therefore, disregarding the special semantic of undef (which is
> always safe in this direction).
>
> Is there an example of transformation which is forbidden by the fact that a
> variable might be undef?
There are some examples earlier in this thread, but this is one:
http://www.playingwithpointers.com/problem-with-undef.html

(Writing the blog post is already paying off :) )

-- Sanjoy

Hi Sanjoy,

Really interesting read. I am perplexed now, and am not even sure what is
the meaning of undef anymore.

Example (unrelated to your blog post, but still weird):
%x = sext i1 undef to i2

I understand that I can replace it by either of:
%x = i2 0
%x = i2 -1

But can I replace it by:
%x = i2 undef

I would have said no, at first sight, because -2 and 1 should not be
possible values.
But if I look at each bit, independently, each one can be either 0 or 1.
Then, if we
forget their "entanglement" (like we do shamelessly with xor %x, %x),
and
then
concatenate them back together, we get the i2 undef...

So I have no clue what is the actual semantic of undef.

On Wed, Oct 19, 2016 at 8:38 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Alexandre,
>
> On Wed, Oct 19, 2016 at 11:19 AM, Alexandre Isoard
> <alexandre.isoard at gmail.com> wrote:
> > I am probably missing something important, but what I mean is that you
> can
> > always convert:
> >
> > %y = xor %x, %x
> > to
> > %y = 0
> >
> > Regardless of if %x is/might be an undef. That is, consider that
reading
> %x
> > any number of times always give the value of its definition (as SSA
> > suggest). Therefore, disregarding the special semantic of undef (which
is
> > always safe in this direction).
> >
> > Is there an example of transformation which is forbidden by the fact
> that a
> > variable might be undef?
>
> There are some examples earlier in this thread, but this is one:
> http://www.playingwithpointers.com/problem-with-undef.html
>
> (Writing the blog post is already paying off :) )
>
> -- Sanjoy
>


-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161020/56061dc6/attachment.html>

Hi Alexandre,

On Wed, Oct 19, 2016 at 6:27 PM, Alexandre Isoard
<alexandre.isoard at gmail.com> wrote:
> Really interesting read. I am perplexed now, and am not even sure what is
> the meaning of undef anymore.
Welcome aboard. :)
> Example (unrelated to your blog post, but still weird):
> %x = sext i1 undef to i2
>
> I understand that I can replace it by either of:
> %x = i2 0
> %x = i2 -1
>
> But can I replace it by:
> %x = i2 undef
>
> I would have said no, at first sight, because -2 and 1 should not be
> possible values.
> But if I look at each bit, independently, each one can be either 0 or 1.
> Then, if we
> forget their "entanglement" (like we do shamelessly with xor %x,
%x), and
> then
> concatenate them back together, we get the i2 undef...
Yes.

If your definition of sext is:

sext(x):
  if x == 0 then 0 else -1

then things are fine.  However, if your definition of sext is something like:

sext(x):
  t = zext x
  result = 0
  for i = 0 to bitwidth:
    result |= t << i;
  return result

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".

-- Sanjoy