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.