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>
> On Sep 14, 2016, at 4:55 AM, sohachak via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 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 <http://llvm.org/docs/LangRef.html#undefined-values>) suggests that > > it is unsafe to consider (a & undef = undef) and (a | undef = undef).Yes, but the documentation specifies correctly "a & undef”, which does not have the same properties as “undef & undef”. While “a & undef” (for an arbitrary a) can’t be folded to undef, “undef & undef” can be folded to undef. — Mehdi> > "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 > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160914/96ae3220/attachment-0001.html>
I get your point. I agree the transformation is correct. As I understand, Instead of evaluating/folding (a & undef) and (~a & undef) individually, LLVM creates a^undef directly and then it is safe to evaluate a^undef to undef. Thanks to all for the discussion. Best Regards, soham On 9/14/2016 5:27 PM, Mehdi Amini wrote:> >> On Sep 14, 2016, at 4:55 AM, sohachak via llvm-dev >> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: >> >> 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). > > > Yes, but the documentation specifies correctly "a & undef”, which does > not have the same properties as “undef & undef”. > While “a & undef” (for an arbitrary a) can’t be folded to undef, > “undef & undef” can be folded to undef. > > — > Mehdi > > > >> >> "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 >> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160915/81f8a3ee/attachment.html>