[llvm-bugs] [Bug 51983] New: [x86-64] Inefficient codegen for __builtin_mul_overflow

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=51983

            Bug ID: 51983
           Summary: [x86-64] Inefficient codegen for
                    __builtin_mul_overflow
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Backend: X86
          Assignee: unassignedbugs at nondot.org
          Reporter: ianloic at google.com
                CC: craig.topper at gmail.com, llvm-bugs at lists.llvm.org,
                    llvm-dev at redking.me.uk, pengfei.wang at intel.com,
                    spatel+llvm at rotateright.com

(I largely worked this out on godbolt: https://godbolt.org/z/zGWWx51a1)

I was looking at catching integer overflow in arithmetic without introducing
additional branches so I wrote:
int square_and_subtract(int x, int y) {
    int square;
    bool overflowed = __builtin_mul_overflow(x, x, &square);
    int difference;
    overflowed |= __builtin_sub_overflow(square, y, &difference);
    if (overflowed) {
        abort();
    }
    return difference;
}
which squares x then subtracts y and either returns the result or aborts if
either operation overflowed.

GCC 11.2's codegen is fairly straightforward with one IMUL, one SUB, one branch
and some bit shuffling:
square_and_subtract(int, int):
        xor     edx, edx
        imul    edi, edi
        mov     eax, edi
        seto    dl
        xor     ecx, ecx
        sub     eax, esi
        seto    cl
        or      edx, ecx
        jne     .L7
        ret
square_and_subtract(int, int) [clone .cold]:
.L7:
        push    rax
        call    abort

Clang trunk (on godbolt on 2021-09-27: https://github.com/llvm/llvm-project.git
9c2cd6e7c803eabbee652f9477c23aeda8ce02c8) surprised me with two IMUL, one sub,
two branches and the requisite bit shuffles:
square_and_subtract(int, int):
        mov     eax, edi
        imul    eax, edi
        sub     eax, esi
        seto    cl
        imul    edi, edi
        jo      .LBB0_3
        test    cl, cl
        jne     .LBB0_3
        ret
.LBB0_3:
        push    rax
        call    abort

My assembly language knowledge is about 30 years out of date but my sense is
that multiplies and branches are expensive though I understand that in modern
processors everything is instruction scheduling.

The AArch64 codegen didn't seem to multiply twice and the bitcode didn't
either:
define dso_local i32 @_Z19square_and_subtractii(i32 %0, i32 %1)
local_unnamed_addr #0 {
  %3 = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %0, i32 %0)
  %4 = extractvalue { i32, i1 } %3, 1
  %5 = extractvalue { i32, i1 } %3, 0
  %6 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %5, i32 %1)
  %7 = extractvalue { i32, i1 } %6, 1
  %8 = or i1 %4, %7
  br i1 %8, label %9, label %10
9:                                                ; preds = %2
  tail call void @abort() #3
  unreachable
10:                                               ; preds = %2
  %11 = extractvalue { i32, i1 } %6, 0
  ret i32 %11
}


Is something going awry with the codegen or is it just more efficient to
multiply twice on modern processors?

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20210927/75e7e011/attachment.html>