Hi,
> >>> It seems like folding undef/X to undef isn't safe either though,
here is my understanding of how to fold undef. I hope it clarifies
this confusing area. Of course, I could be confused myself but I
hope not :)
(1) When is it OK to fold "y=foo(undef)" to "y=undef"? I claim that
it is OK if and only if foo is surjective, i.e. if for each possible
value for y there exists a value for x such that y=foo(x). "Surjective"
is sometimes called "onto".
Before I explain why I think this, an example:
y=(undef == z)
The possible values of y are 0 and 1 because the result of == is
an i1. Surjectivity means: can I get (undef==z) to produce each of
0 and 1 by plugging in different values for undef? Obviously I can,
so in this case I can fold to "y=undef".
OK, now let me justify my claim. If foo is surjective then every
possible value of y can be obtained by varying the value of undef
put into foo(undef) so clearly putting y=undef is OK. More interesting
is why if f is *not* surjective then it is wrong to fold to y=undef:
if f is not surjective then by definition there is some y0 which cannot
be obtained as foo(x) no matter what x you try. Consider the following
code:
y = foo(undef)
z = (y == y0)
The value of z is deterministic: it is always 0 because it is impossible
to have foo(anything)==y0. But if we fold to y=undef then this becomes
z = (undef == y0)
which is (correctly) folded to z=undef. Conclusion: if foo is not surjective
then folding "y=foo(undef)" to "y=undef" can result in wrong future deductions,
in this case, z=undef rather than z=0.
Example:
y = undef udiv 2.
Here foo(x)=x udiv 2 is not surjective so it is wrong to fold to y=undef,
as observed by Dan.
Example:
y = undef + 2.
Here, thanks to circular arithmetic, foo(x)=x+2 is surjective so we can
fold to y=undef.
(2) What to do when foo is not surjective? Choose some value for undef
and fold to "y=foo(value_chosen)". In general foo will involve some
other variables, so the trick is to find a constant value for y that is
always obtainable no matter what those other variables are (while it is
logically correct to replace y with a function of those other variables,
which is what foo(0) will give in general for example, it is more efficient
to use a constant value if possible).
Example: folding "y=undef udiv x". This could be folded to 0 or to 1,
since 0 is what you get by substituting undef=0, and 1 is what you get
by substituting undef=x. (If x=0 then in both cases you get 0/0 which
is, I hear, undefined so you can choose it to be 0 or 1 as you like).
Of course you could also fold it to "1 div x" or "intmax div x" or
"(x*x) div x" if you really felt like it, but 0 and 1 are the only
constants that can always be obtained regardless of the value of x,
so they are the most efficient choices.
Ciao,
Duncan.
> >>>
> >>> with
> >>> the way it sounds like undef is intended to work. This code:
> >>>
> >>> %x = udiv i32 undef, %intmax
> >>> %y = udiv i32 %x, 2
> >>>
> >>> will always set %y to 0. Maybe instcombine can fold the second
> >>> udiv by looking through its operands, but it can't safely fold the
> >>> first. The best it could do is try to fold away all of %x's uses so
> >>> that %x isn't needed anymore.
>
> Duncan pointed out that I confused myself. If something is undef, we
> can choose to pick any specific value for the undef to pick the
> cancellation.
>
> >> Ug, excellent point. At this point, I'm inclined to just give up
> >> folding of udiv undefs. What do you think?
> >
> > udiv isn't the only one, the way this is going...
> >
> > %x = mul i32 undef, 2
> > %y = srem i32 %x, 2
>
> This is fine, we fold the mul to 0 (because the undef could be zero).
>
> > %x = and i32 undef, 0xffff0000
> > %y = and i32 %x, 0x0000ffff
> >
> > and so on for a lot of others.
>
> For and, we fold undef to 0 (because the undef could be 0)
> For or undef, X, we fold to -1, because the undef could be -1.
>
> >>> Even simple things like undef+X don't seem to be safe to fold.
> >>>
> >>> %x = undef;
> >>> if (%x >= 0)
> >>> %z = %y / (%x + 1); // don't divide by undef!
> >>
> >> Fortunately, this isn't a problem. LLVM has no copy instruction, so
> >> the code is really this:
> >>
> >>> if (undef >= 0)
> >>> %z = %y / (undef + 1); // don't divide by undef!
> >>
> >> There is nothing that specifies the two undefs are the same value.
> >> Also, in C, if you have an undefined variable, you aren't guaranteed
> >> to get the same undef value each time you read the variable, so
> >> transforming C into LLVM is ok :)
> >
> > In C, an uninitialized variable has an "indeterminate value", which is
> > potentially a trap representation, which can't even be multiplied by
> > zero without incurring undefined behavior. I don't know where it
> > suggests that a variable with indeterminate value might be different
> > on each read though.
>
> There have been discussions about this issue on the GCC list. I
> remember the resolution (they take the same basic approach we do),
> but I don't remember why. I think a DR may be submitted to the C
> committee on the issue.
>
> IIRC, the basic reason this (allowing an undefined value to have
> multiple values) bites GCC is due to regalloc. For example, if you
> have:
>
> int x;
> int y;
>
> y = 1;
> print(x, y);
> ...
>
> y = 2;
> print(x, y);
>
> Because there is no live range for x (just uses) x and y can be
> allocated to the same register. Doing so causes the value of x to
> follow the value of y.
>
> > LLVM does so have copy instructions. The syntax is a little odd
> > though,
> > and the keyword is spelled 'bitcast' ;-).
>
> Point taken. :)
>
> -Chris
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
