Repository navigation
split_at fails to optimize bounds check #74938
Description
https://rust.godbolt.org/z/E1PnPj
const N: usize = 3;
const T = u8;
pub fn split_mutiple(slice: &[T]) -> (&[T], &[T]) {
let len = slice.len() / N;
slice.split_at(len * N)
}results in the following assembly
example::split_mutiple:
push rax
mov r8, rdx
mov rcx, rdi
movabs rdx, -6148914691236517205
mov rax, r8
mul rdx
shr rdx
lea rdx, [rdx + 2*rdx]
mov rax, r8
sub rax, rdx
mov rdi, r8
sub rdi, rax
jb .LBB0_1 ; Note that this check can never be actually hit
mov qword ptr [rcx], rsi
add rsi, rdi
mov qword ptr [rcx + 8], rdi
mov qword ptr [rcx + 16], rsi
mov qword ptr [rcx + 24], rax
mov rax, rcx
pop rcx
ret
.LBB0_1:
lea rdx, [rip + .L__unnamed_1]
mov rsi, r8
call qword ptr [rip + core::slice::slice_index_len_fail@GOTPCREL]
ud2When using const N: usize = 4 the check is correctly optimized away:
example::split_mutiple:
mov rax, rdi
mov rcx, rdx
and rcx, -4
and edx, 3
mov qword ptr [rdi], rsi
add rsi, rcx
mov qword ptr [rdi + 8], rcx
mov qword ptr [rdi + 16], rsi
mov qword ptr [rdi + 24], rdx
retThis happens both on all stable versions I have tested and on the most recent nightly.
Activity
bugadani commentedon Jul 31, 2020
In fact, this has nothing to do with slices: https://rust.godbolt.org/z/7oG6qE change from 3 to 4 (or other powers of 2) to see everything optimized away.
Edit: reduced it some more: https://rust.godbolt.org/z/bEoj8x
tesuji commentedon Jul 31, 2020
There are no optimization in GCC and Clang either: https://godbolt.org/z/M88ndP
Should
foobe optimized to only return true?tesuji commentedon Jul 31, 2020
So this is more as LLVM part: @rustbot modify labels: +A-LLVM +A-mir-opt
Of course this might be improved with MIR-opt. But how hard it would be? I don't know.
bugadani commentedon Jul 31, 2020
What's interesting is that the power of 2 optimization is done by rustc somewhere - the same MIR is translated to radically different LLVM-IR when N is 2^n.
Trying to find where this happens without knowledge of the compiler is rather difficult, though :)
tesuji commentedon Jul 31, 2020
Clang could do that, change
N=4in my snippet about to see. But still GCC doesn't do that.nikic commentedon Jul 31, 2020
https://github.com/llvm/llvm-project/blob/63d3aeb529a7b0fb95c2092ca38ad21c1f5cfd74/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp#L311 needs to set a nuw flag. Then it will probably fold.
bugadani commentedon Jul 31, 2020
Cool. So if I understand correctly, the following is happening:
The bounds check boils down to basically
(length / N) * N <= length.This can be transformed to
length - length % N <= length(fair enough)This is further transformed to (as the llvm ir shows)
length % N <= length;(I don't see how this transform is equivalent, but OK)And for some reason, LLVM can't seem to deduce that this comparison will always be false. Adding this as an assumption will make the check be optimized:
https://rust.godbolt.org/z/vM1KPM
xldenis commentedon Jul 31, 2020
@bugadani, what's weird is that if you feed this IR straight into llc it does optimize it away: https://rust.godbolt.org/z/o6d6nM. Are we not calling a magic pass on the IR in rustc?Ignore me, I missed that the assume caused the IR to have
ret trueHowever, it does optimize if a
udivis inserted instead of aurem,InstructionSimplifyhas the following opt:x udiv y <=u xI don't know why the same doesn't exist forurem? maybe no one considered it until now?LLVM doesn't know about this optimization but it is apparently valid (thanks John Regehr) so I'll submit a patch to LLVM.
xldenis commentedon Aug 2, 2020
I've submitted a patch to LLVM adding this optimization: https://reviews.llvm.org/D85092
tesuji commentedon Aug 2, 2020
Does anyone want to file a bug against GCC? I registered an account two days ago but they hasn't accepted my account yet.
[InstSimplify] Peephole optimization for icmp (urem X, Y), X
11 remaining items
[InstSimplify] Peephole optimization for icmp (urem X, Y), X
add codegen test for rust-lang#74938
add codegen test for rust-lang#74938
add codegen test for rust-lang#74938
add codegen test for rust-lang#74938
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
Auto merge of rust-lang#125347 - tesuji:needtests, r=nikic
[InstSimplify] Peephole optimization for icmp (urem X, Y), X