| 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