Description
When the result of a umul.with.overflow
by a constant is only needed when it didn't overflow and the result passes a comparison check, that comparison can be moved before the checked multiplication so that it can be replaced with a normal multiplication.
Alive2 proof for an example case: https://alive2.llvm.org/ce/z/XdagRK
define i64 @src(i64 noundef %x) denormal-fp-math=ieee,ieee {
%start:
%0 = umul_overflow i64 noundef %x, 5
%1 = extractvalue {i64, i1, i24} %0, 1
%2 = extractvalue {i64, i1, i24} %0, 0
%_8.i = icmp ugt i64 %2, 9223372036854775807
%3 = or i1 %1, %_8.i
%.0.i = select i1 %3, i64 -1, i64 %2
ret i64 %.0.i
}
=>
define i64 @tgt(i64 noundef %x) denormal-fp-math=ieee,ieee {
%start:
%is_bigger = icmp ugt i64 noundef %x, 1844674407370955161
%product = mul nsw nuw i64 noundef %x, 5
%r = select i1 %is_bigger, i64 -1, i64 %product
ret i64 %r
}
Transformation seems to be correct!
This is highly advantageous as actually emitting the overflow check needs a full x86 mul
, whereas without it a lea
can be used, and since it collapsed the two conditions into the one check it saves the second conditional move too:
src: # @src
mov rax, rdi
mov ecx, 5
mul rcx
seto cl
test rax, rax
mov rdx, -1
cmovs rax, rdx
test cl, cl
cmovne rax, rdx
ret
tgt: # @tgt
movabs rax, 1844674407370955161
cmp rdi, rax
lea rcx, [rdi + 4*rdi]
mov rax, -1
cmovbe rax, rcx
ret
Motivation: after rust-lang/rust#95295, we're hitting this a bunch in Rust. rust-lang/rust#99174 does it manually for some cases, but it would be much nicer for LLVM to do it everywhere.
Minimized demonstration of the code pattern: https://rust.godbolt.org/z/7KWh5j5Mz