x86 `bt` instruction emission can be improved

[TDecking]

The following four functions are examples where the bt instruction can be used during code generation:

LLVM

define noundef zeroext i1 @bit_test_0(i64 noundef %num, i64 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i64 1, %shift
  %bit = and i64 %mask, %num
  %bool = icmp eq i64 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @bit_test_1(i50 noundef %num, i50 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i50 1, %shift
  %bit = and i50 %mask, %num
  %bool = icmp eq i50 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @bit_test_2(i128 noundef %num, i128 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i128 1, %shift
  %bit = and i128 %mask, %num
  %bool = icmp eq i128 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @bit_test_3(i20 noundef %num, i20 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i20 1, %shift
  %bit = and i20 %mask, %num
  %bool = icmp eq i20 %bit, 0
  ret i1 %bool
}

Generated assembly

bit_test_0:                             # @bit_test_0
        bt      rdi, rsi
        setae   al
        ret
bit_test_1:                             # @bit_test_1
        mov     rcx, rsi
        mov     eax, 1
        shl     rax, cl
        and     rax, rdi
        shl     rax, 14
        sete    al
        ret
bit_test_2:                             # @bit_test_2
        mov     rcx, rdx
        xor     eax, eax
        mov     edx, 1
        xor     r8d, r8d
        shld    r8, rdx, cl
        shl     rdx, cl
        test    cl, 64
        cmovne  r8, rdx
        cmovne  rdx, rax
        and     r8, rsi
        and     rdx, rdi
        or      rdx, r8
        sete    al
        ret
bit_test_3:                             # @bit_test_3
        mov     ecx, esi
        mov     eax, 1
        shl     eax, cl
        and     eax, edi
        test    eax, 1048575
        sete    al
        ret

Currently, LLVM only emits bt if the integer bit width is exactly that of a register. Other integers do not get this treatment. The 128-bit integer example is particulary important since it can be easily created using Rust/C (u128, __int128) while being quite slow.

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Tobias Decking (TDecking)

The following four functions are examples where the `bt` instruction can be used during code generation:

<details>
<summary>LLVM</summary>

define noundef zeroext i1 @<!-- -->bit_test_0(i64 noundef %num, i64 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i64 1, %shift
  %bit = and i64 %mask, %num
  %bool = icmp eq i64 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @<!-- -->bit_test_1(i50 noundef %num, i50 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i50 1, %shift
  %bit = and i50 %mask, %num
  %bool = icmp eq i50 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @<!-- -->bit_test_2(i128 noundef %num, i128 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i128 1, %shift
  %bit = and i128 %mask, %num
  %bool = icmp eq i128 %bit, 0
  ret i1 %bool
}

define noundef zeroext i1 @<!-- -->bit_test_3(i20 noundef %num, i20 noundef %shift) unnamed_addr {
start:
  %mask = shl nuw i20 1, %shift
  %bit = and i20 %mask, %num
  %bool = icmp eq i20 %bit, 0
  ret i1 %bool
}

</details>

<details>
<summary>Generated assembly </summary>

bit_test_0:                             # @<!-- -->bit_test_0
        bt      rdi, rsi
        setae   al
        ret
bit_test_1:                             # @<!-- -->bit_test_1
        mov     rcx, rsi
        mov     eax, 1
        shl     rax, cl
        and     rax, rdi
        shl     rax, 14
        sete    al
        ret
bit_test_2:                             # @<!-- -->bit_test_2
        mov     rcx, rdx
        xor     eax, eax
        mov     edx, 1
        xor     r8d, r8d
        shld    r8, rdx, cl
        shl     rdx, cl
        test    cl, 64
        cmovne  r8, rdx
        cmovne  rdx, rax
        and     r8, rsi
        and     rdx, rdi
        or      rdx, r8
        sete    al
        ret
bit_test_3:                             # @<!-- -->bit_test_3
        mov     ecx, esi
        mov     eax, 1
        shl     eax, cl
        and     eax, edi
        test    eax, 1048575
        sete    al
        ret

</details>

Currently, LLVM only emits bt if the integer bit width is exactly that of a register. Other integers do not get this treatment. The 128-bit integer example is particulary important since it can be easily created using Rust/C (u128, __int128) while being quite slow.