Issue 243062
Summary [LoopIdiom][SROA] Shifting a small local array in a loop becomes a memmove that keeps the array on the stack
Labels missed-optimization, llvm:transforms
Assignees
Reporter chfast
    ```c
typedef unsigned long long u64;

void f(u64 out[4], const u64* p, unsigned long n)
{
    u64 r[4] = {0, 0, 0, 0};
    for (unsigned long j = 0; j < n; ++j)
    {
        const u64 t = r[3];
        for (int i = 3; i != 0; --i)  // shift r up by one word
            r[i] = r[i - 1];
        r[0] = p[j] + t;
    }
    out[0] = r[0];
    out[1] = r[1];
    out[2] = r[2];
    out[3] = r[3];
}
```

`clang -O2` (x86-64), the remainder loop (https://godbolt.org/z/aacWv3vWT):

```asm
.LBB0_6:
        movq -16(%rsp), %r8
        movaps  -40(%rsp), %xmm0
        movq    -24(%rsp), %r9
        movq    %r9, 16(%rdx)
        movups  %xmm0, (%rdx)
 addq    (%rcx,%rsi,8), %r8
        movq    %r8, -40(%rsp)
        incq %rsi
        cmpq    %rsi, %rax
        jne     .LBB0_6
```

`r` stays on the stack. Each iteration stores `r[0]` with an 8-byte store and the next one reads it back with a 16-byte load, so store-to-load forwarding fails on the loop-carried chain. The unrolled main loop does the same 4 times per iteration.

Expected, as with `-mllvm -disable-loop-idiom-all`: `r` in registers.

```asm
.LBB0_6:
        movq    %r9, %r10
        movq %r8, %r9
        movq    %rax, %r8
        movq    %r11, %rax
        addq (%rdx,%rsi,8), %rax
        incq    %rsi
        movq    %r10, %r11
 cmpq    %rsi, %rcx
        jne     .LBB0_6
```

LoopIdiomRecognize turns the inner loop into `memmove(r + 1, r, 24)` before the loop is fully unrolled. The memmove's two sides, [0, 24) and [8, 32) of the same alloca, are unsplittable slices that cover all of `r`, so SROA keeps it as one `[4 x i64]` in memory. Without the memmove, the inner loop is unrolled into three loads and stores and SROA promotes `r`.

clang 21 gives the same code.

Found in a prototype of intx's (multi-precision integers) MULMOD, where the accumulator of a reduction loop is shifted by one word per iteration: MULMOD with a 3-word modulus went from 171 to 288 cycles. Writing the shifted words into a new array (`acc[i] = r[i - 1]`, then `r = acc`) avoids it.

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to