<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Hi,</p>
<font color="#993300">> Both A and B are undef:<br>
> LHS = (undef & undef) | (undef & undef) = undef
// Since ~undef = undef<br>
> RHS = undef<br>
> Thus transform is correct.<br>
<br>
</font><font face="Arial">LLVM documentation
(<a class="moz-txt-link-freetext" href="http://llvm.org/docs/LangRef.html#undefined-values">http://llvm.org/docs/LangRef.html#undefined-values</a>) suggests that
</font><br>
<div style="font-size: small; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;"><font face="Arial"><br>
it is unsafe to consider (a & undef = undef) and (a | undef
= undef). <br>
<br>
<font color="#3366ff">"</font></font><font face="Arial"><font
color="#3366ff"><span style="font-family: "Lucida
Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">As such, it is unsafe
to optimize or assume that the result of the ‘</span><code
class="docutils literal" style="font-family:
Consolas,"Deja Vu Sans Mono","Bitstream Vera
Sans Mono",monospace; font-size: 0.95em; font-style:
normal; font-variant-ligatures: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
line-height: 21px; text-align: left; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="pre">and</span></code><span style="font-family:
"Lucida Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ is ‘</span><code
class="docutils literal" style="font-family:
Consolas,"Deja Vu Sans Mono","Bitstream Vera
Sans Mono",monospace; font-size: 0.95em; font-style:
normal; font-variant-ligatures: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
line-height: 21px; text-align: left; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="pre">undef</span></code><span style="font-family:
"Lucida Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘. However, it is
safe to assume that all bits of the ‘</span><code
class="docutils literal" style="font-family:
Consolas,"Deja Vu Sans Mono","Bitstream Vera
Sans Mono",monospace; font-size: 0.95em; font-style:
normal; font-variant-ligatures: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
line-height: 21px; text-align: left; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="pre">undef</span></code><span style="font-family:
"Lucida Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ could be 0, and
optimize the ‘</span><code class="docutils literal"
style="font-family: Consolas,"Deja Vu Sans
Mono","Bitstream Vera Sans Mono",monospace;
font-size: 0.95em; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height:
21px; text-align: left; text-indent: 0px; text-transform:
none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="pre">and</span></code><span
style="font-family: "Lucida Grande","Lucida
Sans Unicode",Geneva,Verdana,sans-serif; font-size:
14px; font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ to 0. Likewise, it
is safe to assume that all the bits of the ‘</span><code
class="docutils literal" style="font-family:
Consolas,"Deja Vu Sans Mono","Bitstream Vera
Sans Mono",monospace; font-size: 0.95em; font-style:
normal; font-variant-ligatures: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
line-height: 21px; text-align: left; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="pre">undef</span></code><span style="font-family:
"Lucida Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ operand to the ‘</span><code
class="docutils literal" style="font-family:
Consolas,"Deja Vu Sans Mono","Bitstream Vera
Sans Mono",monospace; font-size: 0.95em; font-style:
normal; font-variant-ligatures: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
line-height: 21px; text-align: left; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing:
0px; background-color: rgb(255, 255, 255);"><span
class="pre">or</span></code><span style="font-family:
"Lucida Grande","Lucida Sans
Unicode",Geneva,Verdana,sans-serif; font-size: 14px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ could be set,
allowing the ‘</span><code class="docutils literal"
style="font-family: Consolas,"Deja Vu Sans
Mono","Bitstream Vera Sans Mono",monospace;
font-size: 0.95em; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height:
21px; text-align: left; text-indent: 0px; text-transform:
none; white-space: normal; word-spacing: 0px;
background-color: rgb(255, 255, 255);"><span class="pre">or</span></code><span
style="font-family: "Lucida Grande","Lucida
Sans Unicode",Geneva,Verdana,sans-serif; font-size:
14px; font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; line-height: 21px; text-align: left;
text-indent: 0px; text-transform: none; white-space: normal;
word-spacing: 0px; display: inline ! important; float: none;
background-color: rgb(255, 255, 255);">‘ to be folded to -1.</span>"</font><br>
<br>
</font></div>
<div style="font-size: small; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;"><font face="Arial"><br>
</font></div>
<div style="font-size: small; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;"><font face="Arial">As a
result, <br>
</font></div>
<div style="font-size: small; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; line-height: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;"><font face="Arial"> LHS
= (undef & undef) | (undef & undef) = c_1 | c_2 where
c_1 and c_2 are constants and as a result, <br>
<br>
And finally, LHS = c where c is a constant; not undef.</font></div>
<div style="font-family: arial,sans-serif; font-size: small;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: normal; letter-spacing:
normal; line-height: normal; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; word-spacing: 0px;"><font
face="Arial"> <br>
<br>
</font><font face="Arial"></font>Please correct me if I am missing
something. </div>
<p>Best Regards,</p>
<p>soham<br>
</p>
<br>
<div class="moz-cite-prefix">On 9/13/2016 7:27 PM, Sanjoy Das wrote:<br>
</div>
<blockquote cite="mid:57D83706.104@playingwithpointers.com"
type="cite">Hi Soham,
<br>
<br>
Soham Chakraborty wrote:
<br>
> As a result, the transformation ' ((a& (~b))
|((~a)& b)) ~> xor a b '
<br>
> is unsound. LLVM presently performs this transformation.
<br>
<br>
This transform looks fine to me.
<br>
<br>
For simplicity let's look at an `i1` expression. Since these are
<br>
bitwise ops we can extend the reasoning below to iN.
<br>
<br>
Transform: ((A & (~B)) | ((~A) & B)) ~> A ^ B
<br>
<br>
Neither A nor B are undef:
<br>
Transform is correct by normal boolean algebra
<br>
<br>
Both A and B are undef:
<br>
LHS = (undef & undef) | (undef & undef) = undef //
Since ~undef = undef
<br>
RHS = undef
<br>
Thus transform is correct.
<br>
<br>
A is undef but B is not undef:
<br>
LHS = ((undef & (~B)) | (undef & B)) // Since ~undef =
undef
<br>
<br>
Now, by choosing 0 for undef in LHS, we can make LHS be equal to
0,
<br>
and by choosing 1 for undef in LHS, we can make LHS be equal to
1.
<br>
Therefore
<br>
<br>
LHS = undef
<br>
RHS = undef ^ B = undef
<br>
<br>
Thus the transform is correct.
<br>
<br>
A is not undef but B is undef:
<br>
Similar reasoning follows.
<br>
<br>
-- Sanjoy
<br>
</blockquote>
<br>
</body>
</html>