Skip to content

Move comparison before umul.with.overflow by a constant #56562

Open
@scottmcm

Description

@scottmcm

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions