https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128290
Bug ID: 128290
Summary: x86: unsigned __int128 __builtin_sub_overflow computes
the borrow again with cmp/sbb
Product: gcc
Version: 16.2.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: normal
Priority: P3
Component: target
Assignee: unassigned at gcc dot gnu.org
Reporter: chfast at gmail dot com
CC: chfast at gmail dot com
Target Milestone: ---
Target: x86_64-pc-linux-gnu
typedef unsigned __int128 u128;
u128 submod(u128 x, u128 y, u128 m)
{
u128 d;
if (__builtin_sub_overflow(x, y, &d))
d += m;
return d;
}
u128 addmod(u128 x, u128 y, u128 m)
{
u128 s;
if (__builtin_add_overflow(x, y, &s))
s -= m;
return s;
}
GCC 16.2 -O2 (GCC 14, 15 and trunk are the same):
submod:
movq %rdi, %r10
movq %rsi, %r11
movq %rsi, %rax
pushq %rbx
subq %rdx, %r10
sbbq %rcx, %r11
cmpq %r10, %rdi
sbbq %r11, %rax
jc .L7
xorl %esi, %esi
xorl %edi, %edi
.L2:
negq %rsi
popq %rbx
adcq $0, %rdi
andq %r8, %rsi
negq %rdi
movq %rsi, %rax
andq %r9, %rdi
addq %r10, %rax
movq %rdi, %rdx
adcq %r11, %rdx
ret
.L7:
movl $1, %esi
xorl %edi, %edi
jmp .L2
addmod:
movq %rdx, %rax
xchgq %rdi, %rsi
movq %rcx, %rdx
addq %rsi, %rax
adcq %rdi, %rdx
jnc .L8
subq %r8, %rax
sbbq %r9, %rdx
.L8:
ret
In submod the difference is computed with sub/sbb, then d is compared with x
again (cmp/sbb) to get the borrow, which is turned into a 0/1 value through a
branch. addmod uses the carry of add/adc directly. On x86 uaddv<mode>4,
addv<mode>4 and subv<mode>4 accept SWIDWI, while usubv<mode>4 accepts only SWI.
The same happens for unsigned long long with -m32.
clang -O2:
submod:
xorl %eax, %eax
subq %rdx, %rdi
sbbq %rcx, %rsi
cmovaeq %rax, %r9
cmovbq %r8, %rax
addq %rdi, %rax
adcq %rsi, %r9
movq %r9, %rdx
retq
We hit this in intx (a multi-precision integer library): an unsigned __int128
version of its 3/2 division correction step gets the borrow with a second
cmp/sbb whether it is written as x - y and x < y (not recognized as
.SUB_OVERFLOW, PR99620) or with __builtin_sub_overflow.
