[LLVMdev] Missed optimization opportunity in 3-way integer comparison case

[Yuri]

On 05/13/2014 04:32, Bruce Hoult wrote:
> My copy only uses one cmp if you use int as in your C sample code. It 
> produces like your llvm and x86 code if you use unsigned. I don't 
> think it has any choice.
>

Bruce,

Yes, my original example had an unsigned comparison, and clang produces 
to 'cmp' instructions only in unsigned case. However, in both signed and 
unsigned cases it is possible to compare with only one 'cmp' instruction.

Here is the procedure that does such comparison with one 'cmp' in the 
case of unsigned arguments:
         .text
         .file   "cmp.c"
         .globl  mycmp
         .align  16, 0x90
         .type   mycmp, at function
mycmp:
         pushq   %rbp
         movq    %rsp, %rbp
         movl    $-1, %eax
         cmpl    %edi, %esi
         ja      .LBB0_2
         sbbl    %eax, %eax
         andl    $1, %eax
.LBB0_2:
         popq    %rbp
         retq
.Ltmp3:
         .size   mycmp, .Ltmp3-mycmp

So clang does miss this optimization opportunity, but only in unsigned case.

Yuri



On 05/13/2014 02:28, Yuri wrote:
> While looking at what llvm writes for this testcase, I noticed that 
> there is one redundant operation in resulting assembly. The second 
> 'cmp' operation there is essentially identical to the first one, with 
> reversed order of arguments. Therefore, it is not needed.
>
> This testcase is a simple integer comparison routine, similar to what 
> qsort would take to sort an integer array.
>
> I think llvm should be taking advantage of the preceding instruction 
> and not placing the similar instruction again.
>
> rev.208525, optimization level 3.
>
> Yuri
>
>
> --- C-style original code ---
> int mycmp (int i1, int i2) {
>     if (i1<i2) {
>       return -1;
>     } else if (i1>i2) {
>       return 1;
>     }
>     return 0;
> }
>
>
> --- llvm code ---
> define i32 @mycmp(i32, i32) #0 {
> lbl0:
>   %icmp.ULT = icmp ult i32 %0, %1
>   br i1 %icmp.ULT, label %lbl1, label %lbl2
>
> lbl1:
>   %merge = phi i32 [ -1, %lbl0 ], [ %., %lbl2 ]
>   ret i32 %merge
>
> lbl2:
>   %icmp.UGT = icmp ugt i32 %0, %1
>   %. = zext i1 %icmp.UGT to i32
>   br label %lbl1
> }
>
> --- intel assembly ---
> 0000000000000010 <mycmp>:
>   10:   55                      push   %rbp
>   11:   48 89 e5                mov    %rsp,%rbp
>   14:   b8 ff ff ff ff          mov    $0xffffffff,%eax
>   19:   39 f7                   cmp    %esi,%edi
>   1b:   72 07                   jb     24 <mycmp+0x14>
>   1d:   39 fe                   cmp    %edi,%esi   <==== !!! REDUNDANT 
> COMPARISON !!!
>   1f:   19 c0                   sbb    %eax,%eax
>   21:   83 e0 01                and    $0x1,%eax
>   24:   5d                      pop    %rbp
>   25:   c3                      retq
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>