Thanks for your answers.
Another example of unsound transformation on Boolean algebra.
According to the LLVM documentation
(http://llvm.org/docs/LangRef.html#undefined-values) it is unsafe to
consider ' a & undef = undef ' and ' a | undef = undef ' but
'undef xor
undef = undef' is safe.
Now, given an expression ((a & (~b)) | ((~a) & b)) where a and b are
undef
expressions, the value must be specialized to some constant (e.g. 0).
But, if the expression is transformed to $a xor b$ then it may return
'undef'.
As a result, the transformation ' ((a & (~b)) |((~a) & b)) ~>
xor a b '
is unsound. LLVM presently performs this transformation.
Best Regards,
soham
source
----------
int foo(){
int a,b; // unintialized and 'undef'
return ((a & (~b)) |((~a) & b));
}
unoptimized IR // clang++ -emit-llvm udf.cpp -S
----------------------
define i32 @_Z3foov() #0 {
entry:
%a = alloca i32, align 4
%b = alloca i32, align 4
%0 = load i32, i32* %a, align 4
%1 = load i32, i32* %b, align 4
%neg = xor i32 %1, -1
%and = and i32 %0, %neg
%2 = load i32, i32* %a, align 4
%neg1 = xor i32 %2, -1
%3 = load i32, i32* %b, align 4
%and2 = and i32 %neg1, %3
%or = or i32 %and, %and2
ret i32 %or
}
Here %or must return some constant e.g. 0.
optimized IR // opt -O3 udf.ll -S
-------------------
define i32 @_Z3foov() #0 {
entry:
ret i32 undef
}
> Sanjoy Das wrote:
> > Here is a simpler example of a similar issue: `X - X` is not
> > equivalent `0`, in that `0` cannot be replaced with `X - X`, even
> > though `X - X` can be folded to `0`.
>
> I forgot to state that `X` above is some unknown value which can
> potentially be `undef`. A full example would be:
>
> ```
> define i32 @f_0(i32 %x) {
> ret i32 0
> }
>
> define i32 @f_1(i32 %x) {
> %v = sub i32 %x, %x
> ret i32 %v
> }
> ```
>
> `@f_1` can be optimized to `@f_0` but not vice versa, unless you
> somehow know that `%x` cannot be `undef`.
>
> -- Sanjoy
>
Hi Soham, Soham Chakraborty wrote: > As a result, the transformation ' ((a& (~b)) |((~a)& b)) ~> xor a b ' > is unsound. LLVM presently performs this transformation. This transform looks fine to me. For simplicity let's look at an `i1` expression. Since these are bitwise ops we can extend the reasoning below to iN. Transform: ((A & (~B)) | ((~A) & B)) ~> A ^ B Neither A nor B are undef: Transform is correct by normal boolean algebra Both A and B are undef: LHS = (undef & undef) | (undef & undef) = undef // Since ~undef = undef RHS = undef Thus transform is correct. A is undef but B is not undef: LHS = ((undef & (~B)) | (undef & B)) // Since ~undef = undef Now, by choosing 0 for undef in LHS, we can make LHS be equal to 0, and by choosing 1 for undef in LHS, we can make LHS be equal to 1. Therefore LHS = undef RHS = undef ^ B = undef Thus the transform is correct. A is not undef but B is undef: Similar reasoning follows. -- Sanjoy
Hi,
> Both A and B are undef:
> LHS = (undef & undef) | (undef & undef) = undef // Since ~undef
=
undef
> RHS = undef
> Thus transform is correct.
LLVM documentation (http://llvm.org/docs/LangRef.html#undefined-values)
suggests that
it is unsafe to consider (a & undef = undef) and (a | undef = undef).
"As such, it is unsafe to optimize or assume that the result of the
‘|and|‘ is ‘|undef|‘. However, it is safe to assume that all bits of the
‘|undef|‘ could be 0, and optimize the ‘|and|‘ to 0. Likewise, it is
safe to assume that all the bits of the ‘|undef|‘ operand to the ‘|or|‘
could be set, allowing the ‘|or|‘ to be folded to -1."
As a result,
LHS = (undef & undef) | (undef & undef) = c_1 | c_2 where c_1 and
c_2 are constants and as a result,
And finally, LHS = c where c is a constant; not undef.
Please correct me if I am missing something.
Best Regards,
soham
On 9/13/2016 7:27 PM, Sanjoy Das wrote:> Hi Soham,
>
> Soham Chakraborty wrote:
> > As a result, the transformation ' ((a& (~b)) |((~a)&
b)) ~> xor
> a b '
> > is unsound. LLVM presently performs this transformation.
>
> This transform looks fine to me.
>
> For simplicity let's look at an `i1` expression. Since these are
> bitwise ops we can extend the reasoning below to iN.
>
> Transform: ((A & (~B)) | ((~A) & B)) ~> A ^ B
>
> Neither A nor B are undef:
> Transform is correct by normal boolean algebra
>
> Both A and B are undef:
> LHS = (undef & undef) | (undef & undef) = undef // Since ~undef
=
> undef
> RHS = undef
> Thus transform is correct.
>
> A is undef but B is not undef:
> LHS = ((undef & (~B)) | (undef & B)) // Since ~undef = undef
>
> Now, by choosing 0 for undef in LHS, we can make LHS be equal to 0,
> and by choosing 1 for undef in LHS, we can make LHS be equal to 1.
> Therefore
>
> LHS = undef
> RHS = undef ^ B = undef
>
> Thus the transform is correct.
>
> A is not undef but B is undef:
> Similar reasoning follows.
>
> -- Sanjoy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160914/2f61b9d5/attachment.html>