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

[Sanjay Patel via llvm-dev]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170701/ee76109b/attachment.html>