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

[David Majnemer via llvm-dev]

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;
>

What if x is INT_MIN and y is greater than zero? Won't r be poison?


>   r += (unsigned)(y - x) >> 31;
>

Ditto with respect to y being INT_MIN and x greater than zero.


>   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/f59df652/attachment.html>