rust-lang / rust-lang/rust

Missed optimization: Redundant move instruction in `.count()` loop termination

Open
#156,996 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-bug needs-triage
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

[Godbolt] Appologies for the long source code. I could not replicate this missed-opt with something shorter. But thankfully, we only have to focus on the .scan() and .count().

struct TrieNode {
    children: [Option<Box<TrieNode>>; 10],
}

#[inline(always)]
fn decompose_num(mut num: i32) -> ([u8; 9], usize) {
    // Implementation is not important
}

#[unsafe(no_mangle)]
fn longest_prefix(root: &TrieNode, num: i32) -> i32 {
    let (num_stack, idx) = decompose_num(num);
    unsafe { std::hint::assert_unchecked(idx > 0); }
    unsafe { num_stack.get_unchecked(..idx) }
        .iter()
        .rev()
        .scan(root, |node: &mut &TrieNode, &digit: &u8| {
            let entry = unsafe { node.children.get_unchecked(digit as usize) };
            if let Some(child_ref) = entry.as_ref() {
                *node = child_ref;
                Some(())
            } else {
                None
            }
        })
        .count() as i32
}

The truncated assembly output:

; Irrelevant assembly output is omitted
                                                ; num_stack is from address [rsp - 16] to [rsp - 8], inclusive
                                                ; rcx = idx
        lea     rdx, [rsp - 17]                 ; rdx = base address of num_stack - 1
        xor     eax, eax                        ; .count()'s internal counter
.LBB0_3:
        movzx   esi, byte ptr [rdx + rcx]       ; load an u8 from num_stack into rsi
        mov     rdi, qword ptr [rdi + 8*rsi]    ; rdi = entry, rdi = node.children[rsi]
        test    rdi, rdi                        ; check if entry is None
        je      .LBB0_6                         ; return (counter already in eax)
        inc     rax                             ; increment counter
        dec     rdx                             ; decrement num_stack's u8 index
        cmp     rcx, rax                        ; check if num_stack[..idx]'s reverse iteration is done
        jne     .LBB0_3                         ; loop if not
        mov     rax, rcx                        ; REDUNDANT (unnecessary inst.: already rax = rcx b/c previous jne instruction fails)
.LBB0_6:
        ret

Because rax is mathematically guaranteed to equal rcx upon natural loop termination, that last mov is unnecessary. What is interesting about this bug is that this might be an issue that completely resides in LLVM (Take a look at the last 3 LLVM IR basic blocks. They seem optimal - according to my limited experience). But, I was encouraged to first report here so that if it can be escalated to the relevant maintainers if it really is a LLVM bug.

bug exists in 1.95.0 stable, nightly, and beta
--edition 2024
-C target-cpu=znver4 // AMD Zen 4 architecture
bug exists for -C opt-level=2 and opt-level=3

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 Godbolt reproducer for longest_prefix and inspect the truncated assembly around the final mov, then compare it with the last three LLVM IR basic blocks mentioned in the report. Reproduce on Rust 1.95.0 stable, nightly, and beta with opt-level=2 and 3 and target-cpu=znver4; done means determining whether the redundant move is introduced by Rust or LLVM and documenting the relevant escalation.

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
Quiet
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.