rust-lang / rust-lang/rust

Bad codegen using `u8/u16::leading_ones`

Open
#126,661 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-LLVM C-optimization I-slow
Dominant language
Rust
Stars
119k
Forks
16.2k
PR merge metrics
PR metrics pending

Description

I wrote some utf-8 processing code recently and noticed that the codegen of u8::leading_ones is bad.
If I convert u8 into u32 or u64 first it produces better codegen.

pub fn u8_leading_ones(v: u8) -> usize {
    v.leading_ones() as _
}

pub fn u8_leading_ones_shift(v: u8) -> usize {
    ((v as u32) << (u32::BITS - u8::BITS)).leading_ones() as _
}

godbolt link.

on x86:

u8_leading_ones:
        xor     dil, -1
        je      .LBB0_1
        movzx   eax, dil
        bsr     eax, eax
        xor     eax, 7
        movzx   eax, al
        ret
.LBB0_1:
        mov     al, 8
        movzx   eax, al
        ret

u8_leading_ones_shift:
        shl     edi, 24
        not     edi
        bsr     eax, edi
        xor     eax, 31
        ret

on x86(BMI enable)

u8_leading_ones:
        not     dil
        movzx   eax, dil
        lzcnt   eax, eax
        add     eax, -24
        movzx   eax, al
        ret

u8_leading_ones_shift:
        shl     edi, 24
        not     edi
        lzcnt   eax, edi
        ret

on aarch64:

u8_leading_ones:
        mov     w8, #255
        bic     w8, w8, w0
        clz     w8, w8
        sub     w8, w8, #24
        and     x0, x8, #0xff
        ret

u8_leading_ones_shift:
        mov     w8, #-1
        eor     w8, w8, w0, lsl #24
        clz     w0, w8
        ret

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the Rust examples and Godbolt link in the issue, comparing u8/u16::leading_ones with the widened shift variant on x86 and aarch64. Trace the compiler codegen for these integer operations and identify why the narrow form produces extra instructions. Done means the narrow operations generate comparably efficient code without changing their results.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.