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

Reply via email to