| Issue |
243053
|
| Summary |
[Reassociate] Top-word additions of two carry chains are reordered, so a carry is saved with setb
|
| Labels |
missed-optimization,
llvm:transforms
|
| Assignees |
|
| Reporter |
chfast
|
Two consecutive 3-word additions, `w = a + b + c` (mod 2^192), each written as an add-with-carry chain where the top word's carry-out is unused:
```c
typedef unsigned long long u64;
// w = a + b + c (mod 2^192): two add-with-carry chains, the top carries unused.
void acc3(u64 w[3], const u64 a[3], const u64 b[3], const u64 c[3])
{
u64 k, z;
u64 w0 = __builtin_addcll(a[0], b[0], 0, &k);
u64 w1 = __builtin_addcll(a[1], b[1], k, &k);
u64 w2 = __builtin_addcll(a[2], b[2], k, &z);
w0 = __builtin_addcll(w0, c[0], 0, &k);
w1 = __builtin_addcll(w1, c[1], k, &k);
w2 = __builtin_addcll(w2, c[2], k, &z);
w[0] = w0; w[1] = w1; w[2] = w2;
}
// The same with the x86 builtin.
void acc3_x86(u64 w[3], const u64 a[3], const u64 b[3], const u64 c[3])
{
u64 w0, w1, w2;
unsigned char k = __builtin_ia32_addcarryx_u64(0, a[0], b[0], &w0);
k = __builtin_ia32_addcarryx_u64(k, a[1], b[1], &w1);
(void)__builtin_ia32_addcarryx_u64(k, a[2], b[2], &w2);
k = __builtin_ia32_addcarryx_u64(0, w0, c[0], &w0);
k = __builtin_ia32_addcarryx_u64(k, w1, c[1], &w1);
(void)__builtin_ia32_addcarryx_u64(k, w2, c[2], &w2);
w[0] = w0; w[1] = w1; w[2] = w2;
}
```
`clang -O2` (x86-64), https://godbolt.org/z/T7a6Ev6dx:
```asm
acc3:
movq (%rsi), %rax
addq (%rdx), %rax
movq 8(%rsi), %r8
adcq 8(%rdx), %r8
setb %r9b
movq 16(%rdx), %rdx
addq 16(%rsi), %rdx
addq 16(%rcx), %rdx
addq (%rcx), %rax
adcq 8(%rcx), %r8
movzbl %r9b, %ecx
adcq %rcx, %rdx
movq %rax, (%rdi)
movq %r8, 8(%rdi)
movq %rdx, 16(%rdi)
retq
acc3_x86:
movq (%rsi), %rax
addq (%rdx), %rax
movq 8(%rsi), %r8
adcq 8(%rdx), %r8
movq 16(%rsi), %rsi
adcq 16(%rdx), %rsi
addq (%rcx), %rax
adcq 8(%rcx), %r8
adcq 16(%rcx), %rsi
movq %rax, (%rdi)
movq %r8, 8(%rdi)
movq %rsi, 16(%rdi)
retq
```
Expected: `acc3` should be the same as `acc3_x86`, two `add`/`adc`/`adc` chains without `setb`/`movzbl`. llc gives that for the IR in source order (https://godbolt.org/z/Mdv1hcGWK):
```llvm
define void @src_order(ptr %w, i64 %a0, i64 %a1, i64 %a2, i64 %b0, i64 %b1, i64 %b2, i64 %c0, i64 %c1, i64 %c2) {
; first chain: s = a + b
%p0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a0, i64 %b0)
%s0 = extractvalue { i64, i1 } %p0, 0
%k0 = extractvalue { i64, i1 } %p0, 1
%k0z = zext i1 %k0 to i64
%p1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a1, i64 %b1)
%t1 = extractvalue { i64, i1 } %p1, 0
%o1 = extractvalue { i64, i1 } %p1, 1
%q1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %t1, i64 %k0z)
%s1 = extractvalue { i64, i1 } %q1, 0
%o2 = extractvalue { i64, i1 } %q1, 1
%k1 = or i1 %o1, %o2
%k1z = zext i1 %k1 to i64
%t2 = add i64 %a2, %b2
%s2 = add i64 %t2, %k1z
; second chain: r = s + c
%r0p = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s0, i64 %c0)
%r0 = extractvalue { i64, i1 } %r0p, 0
%m0 = extractvalue { i64, i1 } %r0p, 1
%m0z = zext i1 %m0 to i64
%r1p = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %s1, i64 %c1)
%u1 = extractvalue { i64, i1 } %r1p, 0
%n1 = extractvalue { i64, i1 } %r1p, 1
%r1q = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %u1, i64 %m0z)
%r1 = extractvalue { i64, i1 } %r1q, 0
%n2 = extractvalue { i64, i1 } %r1q, 1
%m1 = or i1 %n1, %n2
%m1z = zext i1 %m1 to i64
%u2 = add i64 %s2, %c2
%r2 = add i64 %u2, %m1z
store i64 %r0, ptr %w
%w1 = getelementptr i8, ptr %w, i64 8
store i64 %r1, ptr %w1
%w2 = getelementptr i8, ptr %w, i64 16
store i64 %r2, ptr %w2
ret void
}
```
`llc -mtriple=x86_64`:
```asm
addq %r8, %rsi
adcq %r9, %rdx
adcq 8(%rsp), %rcx
addq 16(%rsp), %rsi
adcq 24(%rsp), %rdx
adcq 32(%rsp), %rcx
```
After `opt -passes=reassociate`, llc gives the `setb`/`movzbl` version again. Reassociate rewrites the top word `(((a2 + b2) + k1) + c2) + k2` as `(((a2 + b2) + c2) + k1) + k2`. The carry `k1` of the first chain is then added only after the second chain has started, so it has to be kept in a register.
The same happens with more rows: intx's (multi-precision integers) truncated 256-bit multiplication, written as rows of `x[i] * y` added with `__builtin_addcll`, is 58 instructions with clang 23, and 48 with `__builtin_ia32_addcarryx_u64`.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs