[llvm-dev] [IR canonicalization] 6 ways to choose {-1,0,1}

[Daniel Berlin via llvm-dev]

Just to offer some random pieces of data:
>From a GVN/CSE/etc perspective, the non-zext'd versions are the most likely
to be optimized, and of the non-zext'd versions, the icmp/select is the
most likely to be optimized.

Especially when combined as part of larger IR.   That is, an "and of zext'd
icmp and regular icmp" is less likely to be optimized.
I mean this from the perspective of "be able to deduce later things about
it".

But past that, i'd say pretty much any of them are fine.



On Sat, Jul 1, 2017 at 11:45 AM, Sanjay Patel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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.
>
> 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?
>
> 1. Two selects
> int zero_negone_one(int x, int y) {
>   if (x == y) return 0;
>   if (x < y) return -1;
>   return 1;
> }
>
> define i32 @zero_negone_one(i32, i32) {
>   %3 = icmp eq i32 %0, %1
>   %4 = icmp slt i32 %0, %1
>   %5 = select i1 %4, i32 -1, i32 1
>   %6 = select i1 %3, i32 0, i32 %5
>   ret i32 %6
> }
>
>
> 2. Two selects, but different
> int zero_one_negone(int x, int y) {
>   if (x == y) return 0;
>   if (x > y) return 1;
>   return -1;
> }
>
> define i32 @zero_one_negone(i32, i32) {
>   %3 = icmp eq i32 %0, %1
>   %4 = icmp sgt i32 %0, %1
>   %5 = select i1 %4, i32 1, i32 -1
>   %6 = select i1 %3, i32 0, i32 %5
>   ret i32 %6
> }
>
>
> 3. Select and zext
> int negone_one_zero(int x, int y) {
>   if (x < y) return -1;
>   if (x > y) return 1;
>   return 0;
> }
>
> define i32 @negone_one_zero(i32, i32)  {
>   %3 = icmp slt i32 %0, %1
>   %4 = icmp sgt i32 %0, %1
>   %5 = zext i1 %4 to i32
>   %6 = select i1 %3, i32 -1, i32 %5
>   ret i32 %6
> }
>
>
> 4. Select and sext
> int negone_zero_one(int x, int y) {
>   int sel = x < y ? -1 : 0;
>   if (x > y) return 1;
>   return sel;
> }
>
> define i32 @negone_zero_one(i32, i32) {
>   %3 = icmp sgt i32 %0, %1
>   %4 = icmp slt i32 %0, %1
>   %5 = sext i1 %4 to i32
>   %6 = select i1 %3, i32 1, i32 %5
>   ret i32 %6
> }
>
>
> 5. Subs and shifts
> int neg101_sub_shifty(int x, int y) {
>   int r = (x - y) >> 31;
>   r += (unsigned)(y - x) >> 31;
>   return r;
> }
>
> define i32 @neg101_sub_shifty(i32, i32) {
>   %3 = sub nsw i32 %0, %1
>   %4 = ashr i32 %3, 31
>   %5 = sub nsw i32 %1, %0
>   %6 = lshr i32 %5, 31
>   %7 = add nsw i32 %4, %6
>   ret i32 %7
> }
>
>
> 6. Zexts and sub
> int neg101_cmp_sub(int x, int y) {
>   return (x>y) - (x<y);
> }
>
> define i32 @neg101_cmp_sub(i32, i32) {
>   %3 = icmp sgt i32 %0, %1
>   %4 = zext i1 %3 to i32
>   %5 = icmp slt i32 %0, %1
>   %6 = zext i1 %5 to i32
>   %7 = sub nsw i32 %4, %6
>   ret i32 %7
> }
>
>
> https://godbolt.org/g/UnM9H7
>
> Show these are logically equivalent:
> http://rise4fun.com/Alive/b4D
>
> Recent patch related to this pattern:
> https://reviews.llvm.org/D34278
>
> _______________________________________________
> 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/20170710/8029972d/attachment.html>