Missed optimization: bounds checking if index is both subtracted and divided
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 119k
- Forks
- 16.1k
- PR merge metrics
- PR metrics pending
Description
Take this code:
#[no_mangle]
pub fn example(arr: &[u32]) -> u32 {
let mut result = 0;
for i in 1..arr.len() {
result = arr[(i - 1) / 2];
}
result
}
If there was only a subtraction, the bounds check would be removed. Same if there was only a division (or a right shift).
But if there are both, it isn't:
example_1:
xor eax, eax
cmp rsi, 2
jb .LBB0_5
lea rcx, [rsi - 1]
xor edx, edx
.LBB0_2:
mov rax, rdx
shr rax
cmp rax, rsi
jae .LBB0_6
inc rdx
cmp rcx, rdx
jne .LBB0_2
mov eax, dword ptr [rdi + 4*rax]
.LBB0_5:
ret
.LBB0_6:
push rax
lea rdx, [rip + .L__unnamed_1]
mov rdi, rax
call qword ptr [rip + core::panicking::panic_bounds_check::he3703b517476def5@GOTPCREL]
Adding unsafe {assert_unchecked((i - 1) / 2 < i)}; fixes the issue.
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 Rust example and Godbolt reproduction in the issue, using rustc nightly with -C opt-level=3 to confirm the extra bounds check. Trace the compiler's bounds-check elimination for the (i - 1) / 2 index through the relevant optimization entry points. Done means the generated code no longer retains the redundant bounds check without assert_unchecked, with regression coverage for this pattern.
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
- 38/100