Missed optimization: Redundant move instruction in `.count()` loop termination
Nobody has claimed this yet.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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