<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 11, 2017 at 2:08 PM, David Majnemer via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">IMO, canonicalization is driven by a few priorities:<div>- How easy is it for the rest of the optimizer to reason about the IR<br><div>- How easy is it to lower the IR to "The Right Thing (TM)"</div><div><br></div><div>I think it is hard to know which is best without resorting to a case-by-case analysis, mostly because of stuff like ComputeKnownBits.</div><div><br></div><div>Outside a few special cases, ComputeKnownBits isn't very smart when it comes to select: it just takes the intersection of the two possibilities. This can lose quite a bit of information.</div></div></div></blockquote><div><br></div><div>This is essentially unfixable without a real bit range analysis.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><br></div><div>I'd feel a lot better about always canonicalizing to select if the backends are strengthened to lower those selects to something good (without relying on CMOV, etc.) and if ComputeKnownBits dealt with select better.</div></div></div></blockquote><div><br></div><div>The latter is going to take real design and work :)</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div class="h5"><div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 11, 2017 at 2:00 PM, Nuno Lopes via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">FWIW: it would be nice to start canonicalizing more on select. Some of the inscombine rewrites we have at the moment canonicalize to arithmetic instead, and it is very hard to justify the correctness of these (to say the least).<br>
So canonicalizing more stuff on select would give us critical mass to remove all the remaining canonicalizations to arithmetic.<br>
<br>
Thanks,<br>
Nuno<br>
<br>
<br>
-----Original Message----- From: Sanjay Patel via llvm-dev<br>
Sent: Saturday, July 1, 2017 7:45 PM<br>
To: llvm-dev<br>
Subject: [llvm-dev] [IR canonicalization] 6 ways to choose {-1,0,1}<div class="m_5946521227923061654gmail-HOEnZb"><div class="m_5946521227923061654gmail-h5"><br>
<br>
<br>
I'm looking at the output of memcmp() expansion (D34904), and I noticed that there are many ways to produce the common positive/zero/negative comparison result in IR.<br>
<br>
For the following 6 functionally equivalent C source functions, we produce 6 different versions of IR which leads to 6 different asm outputs for x86. Which of these should we choose as canonical IR form?<br>
<br>
1. Two selects<br>
int zero_negone_one(int x, int y) {<br>
if (x == y) return 0;<br>
if (x < y) return -1;<br>
return 1;<br>
}<br>
<br>
define i32 @zero_negone_one(i32, i32) {<br>
%3 = icmp eq i32 %0, %1<br>
%4 = icmp slt i32 %0, %1<br>
%5 = select i1 %4, i32 -1, i32 1<br>
%6 = select i1 %3, i32 0, i32 %5<br>
ret i32 %6<br>
}<br>
<br>
<br>
2. Two selects, but different<br>
int zero_one_negone(int x, int y) {<br>
if (x == y) return 0;<br>
if (x > y) return 1;<br>
return -1;<br>
}<br>
<br>
define i32 @zero_one_negone(i32, i32) {<br>
%3 = icmp eq i32 %0, %1<br>
%4 = icmp sgt i32 %0, %1<br>
%5 = select i1 %4, i32 1, i32 -1<br>
%6 = select i1 %3, i32 0, i32 %5<br>
ret i32 %6<br>
}<br>
<br>
<br>
3. Select and zext<br>
int negone_one_zero(int x, int y) {<br>
if (x < y) return -1;<br>
if (x > y) return 1;<br>
return 0;<br>
}<br>
<br>
define i32 @negone_one_zero(i32, i32) {<br>
%3 = icmp slt i32 %0, %1<br>
%4 = icmp sgt i32 %0, %1<br>
%5 = zext i1 %4 to i32<br>
%6 = select i1 %3, i32 -1, i32 %5<br>
ret i32 %6<br>
}<br>
<br>
<br>
4. Select and sext<br>
int negone_zero_one(int x, int y) {<br>
int sel = x < y ? -1 : 0;<br>
if (x > y) return 1;<br>
return sel;<br>
}<br>
<br>
define i32 @negone_zero_one(i32, i32) {<br>
%3 = icmp sgt i32 %0, %1<br>
%4 = icmp slt i32 %0, %1<br>
%5 = sext i1 %4 to i32<br>
%6 = select i1 %3, i32 1, i32 %5<br>
ret i32 %6<br>
}<br>
<br>
<br>
5. Subs and shifts<br>
int neg101_sub_shifty(int x, int y) {<br>
int r = (x - y) >> 31;<br>
r += (unsigned)(y - x) >> 31;<br>
return r;<br>
}<br>
<br>
define i32 @neg101_sub_shifty(i32, i32) {<br>
%3 = sub nsw i32 %0, %1<br>
%4 = ashr i32 %3, 31<br>
%5 = sub nsw i32 %1, %0<br>
%6 = lshr i32 %5, 31<br>
%7 = add nsw i32 %4, %6<br>
ret i32 %7<br>
}<br>
<br>
<br>
6. Zexts and sub<br>
int neg101_cmp_sub(int x, int y) {<br>
return (x>y) - (x<y);<br>
}<br>
<br>
define i32 @neg101_cmp_sub(i32, i32) {<br>
%3 = icmp sgt i32 %0, %1<br>
%4 = zext i1 %3 to i32<br>
%5 = icmp slt i32 %0, %1<br>
%6 = zext i1 %5 to i32<br>
%7 = sub nsw i32 %4, %6<br>
ret i32 %7<br>
}<br>
<br>
<br>
<a href="https://godbolt.org/g/UnM9H7" rel="noreferrer" target="_blank">https://godbolt.org/g/UnM9H7</a><br>
<br>
Show these are logically equivalent:<br>
<a href="http://rise4fun.com/Alive/b4D" rel="noreferrer" target="_blank">http://rise4fun.com/Alive/b4D</a><br>
<br>
Recent patch related to this pattern:<br>
<a href="https://reviews.llvm.org/D34278" rel="noreferrer" target="_blank">https://reviews.llvm.org/D3427<wbr>8</a><br>
<br>
<br></div></div><div class="m_5946521227923061654gmail-HOEnZb"><div class="m_5946521227923061654gmail-h5">
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a> <br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div></div></div></div></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div></div>