[Bug tree-optimization/128248] New: -O2 does not unroll a 4-iteration add-with-carry loop ("size would grow"), although the unrolled code is not larger

[chfast at gmail dot com via Gcc-bugs]

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

            Bug ID: 128248
           Summary: -O2 does not unroll a 4-iteration add-with-carry loop
                    ("size would grow"), although the unrolled code is not
                    larger
           Product: gcc
           Version: 16.2.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          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

At -O2 this loop is not unrolled:

struct u256 { unsigned long long w[4]; };

void add(struct u256 *r, const struct u256 *x, const struct u256 *y)
{
    unsigned long long k = 0;
    for (int i = 0; i < 4; ++i)
        r->w[i] = __builtin_addcll(x->w[i], y->w[i], k, &k);
}

-fdump-tree-cunroll-details:

  Loop size: 8
  Estimated size after unrolling: 16-6
Not unrolling loop 1: size would grow.

GCC 16.2 -O2 (GCC 14, 15 and trunk also keep the loop):

add:
        movq    %rdi, %r8
        xorl    %eax, %eax
        movq    %rsi, %rdi
        movq    %rdx, %rsi
        xorl    %edx, %edx
.L2:
        movq    (%rdi,%rdx), %rcx
        addb    $-1, %al
        adcq    (%rsi,%rdx), %rcx
        movq    %rcx, (%r8,%rdx)
        setc    %al
        addq    $8, %rdx
        cmpq    $32, %rdx
        jne     .L2
        ret

-O3 unrolls it into the same number of instructions, with the carry kept in the
flags:

add:
        movq    (%rsi), %rax
        addq    (%rdx), %rax
        movq    %rax, (%rdi)
        movq    8(%rsi), %rax
        adcq    8(%rdx), %rax
        movq    %rax, 8(%rdi)
        movq    16(%rsi), %rax
        adcq    16(%rdx), %rax
        movq    %rax, 16(%rdi)
        movq    24(%rdx), %rax
        adcq    24(%rsi), %rax
        movq    %rax, 24(%rdi)
        ret

The difference grows when the sum is used further, e.g. (x + y) mod m:

void addmod(struct u256 *r, const struct u256 *x, const struct u256 *y, const
struct u256 *m)
{
    struct u256 s, d;
    unsigned long long k = 0, b = 0;
    for (int i = 0; i < 4; ++i)
        s.w[i] = __builtin_addcll(x->w[i], y->w[i], k, &k);
    for (int i = 0; i < 4; ++i)
        d.w[i] = __builtin_subcll(s.w[i], m->w[i], b, &b);
    *r = (k || !b) ? d : s;
}

At -O2 this is 39 instructions and 10.7 ns per call. With #pragma GCC unroll 4
on both loops it is 38 instructions (s and d stay in registers) and 3.6 ns
(Ryzen 9 5950X, called in a loop). We found this in intx (a multi-precision
integer library), whose uint256 addition and subtraction are such loops.