[JIT] X64 - Recognize patterns to emit `bextr` and `bzhi`

[TIHan]

public class C 
{
    static uint bextr(uint bits)
    {
        return (bits >> 2) & 0x3u;;
    }
    
    static uint bextr_field(ref uint bits)
    {
        return (bits >> 2) & 0x3u;;
    }
    
    static uint bzhi(int position, uint bits)
    {
        return ((1u << position) - 1) & bits; // bmi2
    }
    
    static uint bzhi_field(int position, ref uint bits)
    {
        return ((1u << position) - 1) & bits; // bmi2
    }
}

Currently emits:

C.bextr(UInt32)
    mov eax, ecx
    shr eax, 2
    and eax, 3
    ret

C.bextr_field(UInt32 ByRef)
    mov eax, [rcx]
    shr eax, 2
    and eax, 3
    ret

C.bzhi(Int32, UInt32)
    mov eax, 1
    shlx eax, eax, ecx
    dec eax
    and eax, edx
    ret

C.bzhi_field(Int32, UInt32 ByRef)
    mov eax, 1
    shlx eax, eax, ecx
    dec eax
    and eax, [rdx]
    ret

Instead, it could emit:

#include <stdint.h>

uint32_t bextr(uint32_t bits)
{
    return (bits >> 2) & 0x3u;;
}

uint32_t bextr_field(uint32_t& bits)
{
    return (bits >> 2) & 0x3u;
}

uint32_t bzhi(int32_t position, uint32_t bits)
{
    return ((1 << position) - 1) & bits; // bmi2
}

uint32_t bzhi_field(int32_t position, uint32_t& bits)
{
    return ((1 << position) - 1) & bits; // bmi2
}

bextr(unsigned int):                              # @bextr(unsigned int)
        mov     eax, 514
        bextr   eax, edi, eax
        ret
bextr_field(unsigned int&):                      # @bextr_field(unsigned int&)
        mov     eax, 514
        bextr   eax, dword ptr [rdi], eax
        ret
bzhi(int, unsigned int):                              # @bzhi(int, unsigned int)
        bzhi    eax, esi, edi
        ret
bzhi_field(int, unsigned int&):                      # @bzhi_field(int, unsigned int&)
        bzhi    eax, dword ptr [rsi], edi
        ret

We already handle transformations to blsi, blsmsk, and blsr in lowering, we just need to handle bextr and bzhi in the same way.

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch, @kunalspathak
See info in area-owners.md if you want to be subscribed.

Issue Details

---

public class C 
{
    public uint _bitfield;
    
    uint bextr(uint bits)
    {
        return (bits >> 2) & 0x3u;;
    }
    
    uint bextr_field()
    {
        return (_bitfield >> 2) & 0x3u;;
    }
    
    uint bzhi(int position, uint bits)
    {
        return ((1u << position) - 1) & bits; // bmi2
    }
    
    uint bzhi_field(int position)
    {
        return ((1u << position) - 1) & _bitfield; // bmi2
    }
}

Currently emits:

C.bextr(UInt32)
    mov eax, edx
    shr eax, 2
    and eax, 3
    ret

C.bextr_field()
    mov eax, [rcx+8]
    shr eax, 2
    and eax, 3
    ret
    
C.bzhi(Int32, UInt32)
    mov eax, 1
    shlx eax, eax, edx
    dec eax
    and eax, r8d
    ret

C.bzhi_field(Int32)
    mov eax, 1
    shlx eax, eax, edx
    dec eax
    and eax, [rcx+8]
    ret

Instead, it could emit:

// bextr
mov   eax, 514
bextr eax, edx, eax
ret

// bextr_field
mov     eax, 514
bextr   eax, dword ptr [rip + _bitfield], eax
ret

// bzhi
bzhi    eax, ecx, edx
ret

// bzhi field
bzhi    eax, dword ptr [rip + _bitfield], edx
ret

We already handle transformations to blsi, blsmsk, and blsr in lowering, we just need to handle bextr and bzhi in the same way.

Author:	TIHan
Assignees:	-
Labels:	area-CodeGen-coreclr
Milestone:	-

[hopperpl]

From my experience, bextr is slower than a shr/and sequence for compiler time constant masks ((1 << bits) - 1). This seems to agree with the latest gcc and clang compilers which also avoid to emit bextr.

https://gcc.godbolt.org/z/GGe5W5xWc

The replacement code is to emit shrx before bzhi for bextr use cases

I will try to confirm this with a real performance test.

[tannergooding]

From my experience, bextr is slower than a shr/and sequence for compiler time constant masks ((1 << bits) - 1).

This one is slightly dependent on micro-architecture and Clang does emit it for AMD Zen (znver1/2/3/4) (because AMD explicitly added the timing tables to indicate its profitable there): https://gcc.godbolt.org/z/9s4GEEbhf -- It is 1 latency, 0.3-0.5 reciprocal throughput, and 1 micro-op for AMD.

For Intel based CPUs, bextr has classically been 2 latency, 0.5 reciprocal throughput, and 2 micro-ops (Haswell through Rocket Lake). Alder Lake regressed this to 4-6 latency.

shr r32, i8 is 1 cycle on all of these platforms with and r32, i8 being the same. Since they're dependent there is roughly an even split between bextr and shr/and on most Intel based CPUs. With the main consideration being that you have 2-3 instructions taking 2 micro-ops for [mov]/shr/and costing ~6-8 bytes of codegen and 1-2 instructions (but still 2 micro-ops) for [mov]/bextr where the cost is ~5-10 bytes of codegen.

For non-constant it depends on the desired behavior around "overshifting" (do you mask the shift, zero the output, or in the case of signed shift do you potentially return all bits set).

[hopperpl]

indeed, I just benchmarked it on a Zen1, Zen2 and Zen3. I will find an old and a new Intel to check there.

00007FF603511790 0F 31                rdtsc  
00007FF603511792 48 C1 E2 20          shl         rdx,20h  
00007FF603511796 48 09 D0             or          rax,rdx  
00007FF603511799 48 89 C3             mov         rbx,rax  
00007FF60351179C 48 C7 C1 48 E8 01 00 mov         rcx,1E848h  ; 125000
00007FF6035117A3 66 66 66 66 2E 0F 1F 84 00 00 00 00 00 nop         word ptr cs:[rax+rax]  

00007FF6035117B0 C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117B5 C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117BA C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117BF C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117C4 C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117C9 C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117CE C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117D3 C4 E2 C8 F7 C7       bextr       rax,rdi,rsi  
00007FF6035117D8 48 FF C9             dec         rcx  
00007FF6035117DB 75 D3                jne         perf_bextr+20h (07FF6035117B0h)  

00007FF6035117DD 0F 31                rdtsc  
00007FF6035117DF 48 C1 E2 20          shl         rdx,20h  
00007FF6035117E3 48 09 D0             or          rax,rdx  
00007FF6035117E6 48 29 D8             sub         rax,rbx  
00007FF6035117E9 C3                   ret  

executes 125000 * 8 or 1 million times bextr

bextr: min 525622 ticks for 1000000 executions; avg 557647 ticks

Therefore it can execute two bextr per clock cycle. Similar result with bzhi.

bzhi: min 525622 ticks for 1000000 executions; avg 576476 ticks

The 5% overhead is within my expectation for the loop and the instruction decoder choking with so many VEX.

---

double the time needed due to rax dependency for shrx followed by bzhi

00007FF6DB2F1850 C4 E2 F3 F7 C3       shrx        rax,rbx,rcx  
00007FF6DB2F1855 C4 E2 C8 F5 C7       bzhi        rax,rdi,rsi  
(8 times)

shrx/bzhi: min 946090 ticks for 1000000 executions; avg 1002733 ticks

this only measured the minimum execution time to test what the CPU at best can do; average removed all runs over 2 million ticks (thread switches, interrupts, CPU power level switching etc).