Suboptimal codegen involving tzcnt

[tavianator]

Here is a simple loop to find the index of the first different bit in two arrays:

unsigned long crit_bit(unsigned long *a, unsigned long *b, unsigned long size) {
    unsigned long ret = 0;
#pragma nounroll
    for (unsigned long i = 0; i < size; ++i) {
        unsigned long diff = a[i] ^ b[i];
        int bits = 8 * sizeof(unsigned long);
        ret += __builtin_ctzg(diff, bits);
        if (diff) {
            break;
        }
    }
    return ret;
}

On x86-64 with -O3 -mbmi, the loop generates

.LBB0_4:
        mov     r9, rax
        mov     r10, qword ptr [rdi + 8*r8]
        mov     r11, qword ptr [rsi + 8*r8]
        mov     rax, r11
        xor     rax, r10
        tzcnt   rax, rax
        mov     rbx, r11
        xor     rbx, r10
        cmove   rax, rcx
        add     rax, r9
        xor     r11, r10
        jne     .LBB0_6
        lea     r9, [r8 + 1]
        cmp     rdx, r8
        mov     r8, r9
        jne     .LBB0_4

First, it's using cmove to get 64 in case the input was zero, but tzcnt already returns 64 in that case so that's redundant.

Second, it could use the flags after tzcnt to handle the if (diff) break, but instead it re-does the comparison.

Better code would look something like this:

        xor     rax, r10
        tzcnt   rax, rax
        lea     rax, [rax + r9]
        jc      .LBB0_6

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Tavian Barnes (tavianator)

Here is a simple loop to find the index of the first different bit in two arrays:

unsigned long crit_bit(unsigned long *a, unsigned long *b, unsigned long size) {
    unsigned long ret = 0;
#pragma nounroll
    for (unsigned long i = 0; i < size; ++i) {
        unsigned long diff = a[i] ^ b[i];
        int bits = 8 * sizeof(unsigned long);
        ret += __builtin_ctzg(diff, bits);
        if (diff) {
            break;
        }
    }
    return ret;
}

On x86-64 with -O3 -mbmi, the loop generates

.LBB0_4:
        mov     r9, rax
        mov     r10, qword ptr [rdi + 8*r8]
        mov     r11, qword ptr [rsi + 8*r8]
        mov     rax, r11
        xor     rax, r10
        tzcnt   rax, rax
        mov     rbx, r11
        xor     rbx, r10
        cmove   rax, rcx
        add     rax, r9
        xor     r11, r10
        jne     .LBB0_6
        lea     r9, [r8 + 1]
        cmp     rdx, r8
        mov     r8, r9
        jne     .LBB0_4

First, it's using cmove to get 64 in case the input was zero, but tzcnt already returns 64 in that case so that's redundant.

Second, it could use the flags after tzcnt to handle the if (diff) break, but instead it re-does the comparison.

Better code would look something like this:

        xor     rax, r10
        tzcnt   rax, rax
        lea     rax, [rax + r9]
        jc      .LBB0_6

[phoebewang]

First, it's using cmove to get 64 in case the input was zero, but tzcnt already returns 64 in that case so that's redundant.

__builtin_ctzg may be not optimal for this case. Why don't use __builtin_ctzl instead?

Second, it could use the flags after tzcnt to handle the if (diff) break, but instead it re-does the comparison.

We can't guarantee it since there's not data dependence between them. We may need to define a new builtin like __builtin_ctzl_zero or intrinsic like _BitScanReverse64 for this purpose.

[topperc]

__builtin_ctzg may be not optimal for this case. Why don't use __builtin_ctzl instead?

__builtin_ctzl doens't allow the input to be 0.

[phoebewang]

__builtin_ctzg may be not optimal for this case. Why don't use __builtin_ctzl instead?

__builtin_ctzl doens't allow the input to be 0.

Oh, right. Then we can use _tzcnt_u64 instead: https://godbolt.org/z/bsa44Gs6M

[topperc]

I think the problem is in instcombine.

It turned

select (icmp ne (xor x, y), 0), cttz((xor x, y), true), 64

into

select (icmp ne x, y), cttz((xor x, y), true), 64

The original pattern is optimizable to cttz((xor x, y), false), but the rewrite of the icmp to avoid the xor broke the pattern match.

CC: @dtcxzyw