https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128834

            Bug ID: 128834
           Summary: 128-bit carry idiom "acc += p; top += acc < p;"
                    expands to a branch instead of adc since GCC 13 (PR
                    93141 testcase regressed)
           Product: gcc
           Version: 16.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jdh863 at gmail dot com
  Target Milestone: ---

The carry-out of an unsigned __int128 addition written in the usual way

    acc += p;
    top += acc < p;

has been compiled to a conditional jump, a 128-bit 0/1 temporary, or, setne and
movzbl since GCC 13.1. GCC 10.1 through 12.4 compile it to a single "adc $0",
as clang does, and as GCC still does for the same idiom on uint64_t and for
__builtin_add_overflow on unsigned __int128.

This is the testcase of PR 93141 (addressed by r279887 for GCC 10; that PR is
still ASSIGNED). It regressed
between 12.4 and 13.1 and is still wrong on trunk (gcc version 17.0.0 20261105,
checked on Compiler Explorer). The tests added for PR 93141 (pr93141-1.c,
pr93141-2.c) only use __builtin_add_overflow, so they do not catch it.

PR 107564 is related but different: it is about "m += n; return m < n;" giving
cmp/sbb/setc on GCC 12.2, where the carry is returned rather than added. The
case here was optimal on GCC 12 and the idiom is recognized as .ADD_OVERFLOW;
what fails is the expansion.

$ cat carry.c
typedef unsigned long u64;
typedef unsigned __int128 u128;

void add_carry(u128 *acc, u64 *top, u64 a, u64 b) {
  u128 p = (u128)a * b;
  *acc += p;
  *top += *acc < p;
}

void add_carry_builtin(u128 *acc, u64 *top, u64 a, u64 b) {
  u128 p = (u128)a * b;
  *top += __builtin_add_overflow(*acc, p, acc);
}

GCC 12.4, -O2 (both functions identical):

add_carry:
        movq    %rdx, %rax
        mulq    %rcx
        addq    (%rdi), %rax
        adcq    8(%rdi), %rdx
        movq    %rax, (%rdi)
        movq    %rdx, 8(%rdi)
        adcq    $0, (%rsi)
        ret

GCC 13.1, 14.3, 15.3.1, 16.2.1 and trunk, -O2:

add_carry:
        movq    %rdx, %rax
        movq    %rsi, %r8
        xorl    %esi, %esi
        mulq    %rcx
        xorl    %ecx, %ecx
        addq    (%rdi), %rax
        adcq    8(%rdi), %rdx
        jc      .L5
.L2:
        movq    %rax, (%rdi)
        movq    %rcx, %rax
        orq     %rsi, %rax
        movq    %rdx, 8(%rdi)
        setne   %al
        movzbl  %al, %eax
        addq    %rax, (%r8)
        ret
.L5:
        movl    $1, %ecx
        jmp     .L2

add_carry_builtin is still the good 8-instruction sequence on all these
versions, and so is add_carry with u64 in place of u128.

At -fdump-tree-optimized both functions have been turned into .ADD_OVERFLOW.
The only difference is that the idiom form keeps an explicit "!= 0" test on the
TImode IMAGPART before the conversion:

  add_carry:                                add_carry_builtin:
  _17 = .ADD_OVERFLOW (_3, p_11);           _14 = .ADD_OVERFLOW (_3, p_11);
  _4 = REALPART_EXPR <_17>;                 _4 = REALPART_EXPR <_14>;
  _18 = IMAGPART_EXPR <_17>;                *acc_13(D) = _4;
  *acc_13(D) = _4;                          _5 = IMAGPART_EXPR <_14>;
  _5 = *top_15(D);                          _6 = *top_16(D);
  _6 = _18 != 0;                            _7 = (long unsigned int) _5;
  _7 = (long unsigned int) _6;              _8 = _6 + _7;
  _8 = _5 + _7;                             *top_16(D) = _8;
  *top_15(D) = _8;

At expand, both forms produce the overflow flag as a TImode pseudo set to 0 or
1 around a conditional jump; only the builtin form is later folded into adc.

The original PR 93141 loop shows the same regression. With
-O3 -march=broadwell -fno-unroll-loops the loop body is

GCC 12.4:                                 GCC 13.1 and later:
.L4:                                      .L4:
        movq    b(%rcx), %rax                     movq    b(%rbx), %rdx
        mulq    a(%rcx)                           xorl    %eax, %eax
        addq    %rax, %rsi                        xorl    %ecx, %ecx
        adcq    %rdx, %rdi                        mulx    a(%rbx), %rsi, %rdi
        adcq    $0, %r8                           addq    %r8, %rsi
        addq    $8, %rcx                          adcq    %r9, %rdi
        cmpq    $16384, %rcx                      jc      .L8
        jne     .L4                       .L2:
                                                  orq     %rcx, %rax
                                                  movq    %rsi, %r8
                                                  movq    %rdi, %r9
                                                  setne   %al
                                                  addq    $8, %rbx
                                                  movzbl  %al, %eax
                                                  addq    %rax, %r10
                                                  cmpq    $16384, %rbx
                                                  jne     .L4
                                                  ...
                                          .L8:
                                                  movl    $1, %eax
                                                  jmp     .L2

Real-world impact: the accurate path of the CORE-MATH binary128 tangent
(https://gitlab.inria.fr/core-math/core-math/-/blob/master/src/binary128/tan/tanq.c,
function mul_hi_320) accumulates a 320x320-bit product by columns with this
idiom, 19 carries per product. For that function alone, compiled with
-O3 -march=x86-64-v3 and timed with rdtsc on random inputs (Ryzen 7 8700F):

  GCC 16.2.1, idiom as written:                 98.6 ticks/call, 34 branches
  GCC 16.2.1, idiom replaced by the builtin:    51.4 ticks/call,  0 branches
  clang 22.1.8, idiom as written:               58.6 ticks/call,  0 branches

The whole accurate path, which calls this product 13 times per input, runs at
about 4950 ticks/call with GCC 16.2.1 against 2350 with clang 22.1.8.

Reply via email to