[llvm-bugs] [Bug 40090] New: [x86-64] missed optimization: can use the zero flag which is set by BSR

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=40090

            Bug ID: 40090
           Summary: [x86-64] missed optimization: can use the zero flag
                    which is set by BSR
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: arthur.j.odwyer at gmail.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

I was trying to trick Clang into generating optimal code for a 128-bit "count
leading zeros" function. I started with the most naive version:

    using u128 = __uint128_t;
    using u64 = uint64_t;
    int countleadingzerosA(u128 x)
    {
        return (x >> 64) ? __builtin_clzll(u64(x >> 64)) + 64
                         : __builtin_clzll(u64(x));
    }

      testq %rsi, %rsi
      je .LBB1_2
      bsrq %rsi, %rax
      xorl $63, %eax
      orl $64, %eax
      retq
    .LBB1_2:
      bsrq %rdi, %rax
      xorl $63, %eax
      retq

By examining the generated code (-O3), I was able to produce this version:

    int countleadingzerosB(u128 x)
    {
        int lo = 63 - __builtin_clzll(u64(x)) + 64;
        int hi = 63 - __builtin_clzll(u64(x >> 64));
        return 63 - ((x >> 64) ? hi : lo);
    }

    bsrq %rdi, %rax
    xorl $64, %eax
    bsrq %rsi, %rcx
    testq %rsi, %rsi
    cmovel %eax, %ecx
    movl $63, %eax
    subl %ecx, %eax
    retq

I believe there are two missed optimizations here that MIGHT be relatively
straightforward to implement.
Number 1: According to https://www.felixcloutier.com/x86/BSR.html the
instruction `bsrq %rsi, %rcx` sets ZF in exactly the same way as `testq %rsi,
%rsi`, so the `testq` instruction is redundant.
Number 2: If dataflow can remember that the value in %rax is in the range
[0..63], then it should be able to apply the same SUB-to-XOR strength reduction
that it did in countleadingzerosA: we can replace the final two instructions
with `xorl $63, %ecx; movl %ecx, %eax` and then the `movl` can be eliminated by
register allocation.

I can easily work around number 2 by just doing `return 63 ^ ...` instead of
`return 63 - ...`; I was just surprised that the compiler would do SUB-to-XOR
in some places but then seemingly miss it in others.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20181218/d4add4eb/attachment.html>