Missed optimization(?): LLVM ignores carry flag after a 'shr'

[shelerr]

https://godbolt.org/z/zdhPve74e

unsigned int bar1();
unsigned int bar2();

int foo(unsigned int num) {
    unsigned int temp = num >> 12;
    if ((num >> 11) % 2 == 0) {
        return bar1() + temp;
    } else {
        return bar2() * temp;
    }
}

foo(unsigned int):
        push    rbx
        mov     ebx, edi
        shr     ebx, 12
        test    edi, 2048
        jne     .LBB0_2
        call    bar1()@PLT
        add     eax, ebx
        pop     rbx
        ret
.LBB0_2:
        call    bar2()@PLT
        imul    eax, ebx
        pop     rbx
        ret

On x86 64, 'shr' sets carry flag to the value of the last bit shifted out of the destination operand. So, I would expect the conditional jump to just be 'jc', instead of 'test'+'jne'. Am I missing something?

[topperc]

I think its possible, but not straightforward to implement in the compiler. The IR has two independent computation chains. The and with 2048 created from (num >> 11) % 2 and a lshr created by num >> 12.

Turning a branch on and with 2048 into a shift and carry flag probably isn't profitable by itself. So we would need to detect that the other computation chain exists and can be combined together into a single computation. Doing this combine profitably requires additional checks to make sure that the flag produced by the shift won't be clobbered by some other instruction that needs to occur between the shift and the branch. If we don't do this right we have to duplicate the shift and preserve its input so we can set the flag again. Effectively splitting back into 2 independent computations.

[shelerr]

Ok, I will try to explain my use case for this optimization. I have a string type with SSO (inline buffer, so that you don't have to allocate if it's small). Calculating its length goes something like this:

// string = { void* ptr, u64 length}
u64 inline_length = string.length >> 60;
if (string.is_inline()) {
    return inline_length;
} else {
    return string.length;
}

59th bit happens to be a pretty convinient place to put the flag that indicates whether string is inline. And what concerns me is that this missed optimization adds 5 extra bytes every time I want to get string's length (which happens a lot, especially considering that it is all actually in Rust). This noticably increases code size, which prevents additional inlining, pollutes icache, and in general is not great. I do not (yet) have great real-world benchmarks to back this up, but some dirty measurments suggest that it indeed has some small but non negligible impact.

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: shelerr (shelerr)

https://godbolt.org/z/zdhPve74e

unsigned int bar1();
unsigned int bar2();

int foo(unsigned int num) {
    unsigned int temp = num >> 12;
    if ((num >> 11) % 2 == 0) {
        return bar1() + temp;
    } else {
        return bar2() * temp;
    }
}

foo(unsigned int):
        push    rbx
        mov     ebx, edi
        shr     ebx, 12
        test    edi, 2048
        jne     .LBB0_2
        call    bar1()@<!-- -->PLT
        add     eax, ebx
        pop     rbx
        ret
.LBB0_2:
        call    bar2()@<!-- -->PLT
        imul    eax, ebx
        pop     rbx
        ret

On x86 64, 'shr' sets carry flag to the value of the last bit shifted out of the destination operand. So, I would expect the conditional jump to just be 'jc', instead of 'test'+'jne'. Am I missing something?

[Explorer09]

I thought this issue (reported by me) is related: #86788