| Issue |
244246
|
| Summary |
[X86][LV] LLVM 23 regression: strided i16 loads scalarized at VF 8 without SSE4.1, ~15x slower
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
wasade
|
Since LLVM 23 this loop is about 15x slower at the default x86-64 target. It counts, for each of 16 `i16` lanes, the mismatches between `a` and `b`, one 16-element chunk at a time. That is the shape of a Rust kernel once its inner lane loop is unrolled.
```
opt -passes=loop-vectorize -pass-remarks=loop-vectorize -pass-remarks-missed=loop-vectorize -disable-output lanes16.ll
```
- **22.1.8:** `the cost-model indicates that vectorization is not beneficial`
- **23.1.6 and main:** `vectorized loop (vectorization width: 8, interleaved count: 1)`
| `clang -O3 lanes16.ll driver.c` | ns per call |
|---|---|
| 22.1.8 | 51 |
| 23.1.6 | 770 |
| main + #<PR> | 402 |
The machine is a Ryzen 9 9950X3D, on one core.
LLVM 22 leaves the loop to SLP, which loads each chunk as whole vectors. LLVM 23 scalarizes the strided loads instead: each `<8 x i16>` is built from 8 `movzwl`, 8 `movd` and 7 `punpckl`.
**Bisected to 497a6d672263.** Lane 0's loads use the pointer IV directly, not a GEP.
- **Before that commit,** they got no address SCEV, so `X86TTIImpl::getAddressComputationCost` charged them the pre-AVX2 non-strided penalty: 96 each at VF 8 instead of 16.
- **That penalty was what kept the loop scalar.** The commit itself looks right.
**What is actually wrong:**
1. **X86 costs each insert as a PINSRW** (cost 1), but without SSE4.1 `LowerBuildVectorv8i16` only uses PINSRW up to 4 elements, and emits MOVD+PUNPCK above that. #<PR> corrects the cost. VF 8 is then rejected, LV picks VF 4, and the time drops from 770 to 402 ns.
2. **The rest is LV comparing against the scalar loop,** 81 against 82 per lane at VF 4, rather than against what SLP makes of it (51 ns). That is #234596.
Related: #234596 (the same shape at AVX2) and #186979 (an earlier `getAddressAccessSCEV` change, on AArch64). Found through rust-lang/rust#166207, with real impact on the kernel of [DartUniFrac](https://github.com/jianshu93/DartUniFrac) (count_mismatches in crates/dartunifrac-core). Its default 16-bit distance runs about 12× slower when built with Rust 1.99+: about 800 ns per pair against 66 ns, single-threaded, k = 2048. The results are identical; only the speed changes.
<details><summary>lanes16.ll</summary>
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; n = number of 16-element chunks, n > 0
define i64 @count(ptr noalias %a, ptr noalias %b, i64 %n) {
entry:
br label %loop
loop:
%i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
%pa = phi ptr [ %a, %entry ], [ %pa.next, %loop ]
%pb = phi ptr [ %b, %entry ], [ %pb.next, %loop ]
%acc0 = phi i16 [ 0, %entry ], [ %acc0.next, %loop ]
%acc1 = phi i16 [ 0, %entry ], [ %acc1.next, %loop ]
%acc2 = phi i16 [ 0, %entry ], [ %acc2.next, %loop ]
%acc3 = phi i16 [ 0, %entry ], [ %acc3.next, %loop ]
%acc4 = phi i16 [ 0, %entry ], [ %acc4.next, %loop ]
%acc5 = phi i16 [ 0, %entry ], [ %acc5.next, %loop ]
%acc6 = phi i16 [ 0, %entry ], [ %acc6.next, %loop ]
%acc7 = phi i16 [ 0, %entry ], [ %acc7.next, %loop ]
%acc8 = phi i16 [ 0, %entry ], [ %acc8.next, %loop ]
%acc9 = phi i16 [ 0, %entry ], [ %acc9.next, %loop ]
%acc10 = phi i16 [ 0, %entry ], [ %acc10.next, %loop ]
%acc11 = phi i16 [ 0, %entry ], [ %acc11.next, %loop ]
%acc12 = phi i16 [ 0, %entry ], [ %acc12.next, %loop ]
%acc13 = phi i16 [ 0, %entry ], [ %acc13.next, %loop ]
%acc14 = phi i16 [ 0, %entry ], [ %acc14.next, %loop ]
%acc15 = phi i16 [ 0, %entry ], [ %acc15.next, %loop ]
%la0 = load i16, ptr %pa, align 2
%lb0 = load i16, ptr %pb, align 2
%ne0 = icmp ne i16 %la0, %lb0
%z0 = zext i1 %ne0 to i16
%acc0.next = add i16 %acc0, %z0
%ga1 = getelementptr inbounds i8, ptr %pa, i64 2
%gb1 = getelementptr inbounds i8, ptr %pb, i64 2
%la1 = load i16, ptr %ga1, align 2
%lb1 = load i16, ptr %gb1, align 2
%ne1 = icmp ne i16 %la1, %lb1
%z1 = zext i1 %ne1 to i16
%acc1.next = add i16 %acc1, %z1
%ga2 = getelementptr inbounds i8, ptr %pa, i64 4
%gb2 = getelementptr inbounds i8, ptr %pb, i64 4
%la2 = load i16, ptr %ga2, align 2
%lb2 = load i16, ptr %gb2, align 2
%ne2 = icmp ne i16 %la2, %lb2
%z2 = zext i1 %ne2 to i16
%acc2.next = add i16 %acc2, %z2
%ga3 = getelementptr inbounds i8, ptr %pa, i64 6
%gb3 = getelementptr inbounds i8, ptr %pb, i64 6
%la3 = load i16, ptr %ga3, align 2
%lb3 = load i16, ptr %gb3, align 2
%ne3 = icmp ne i16 %la3, %lb3
%z3 = zext i1 %ne3 to i16
%acc3.next = add i16 %acc3, %z3
%ga4 = getelementptr inbounds i8, ptr %pa, i64 8
%gb4 = getelementptr inbounds i8, ptr %pb, i64 8
%la4 = load i16, ptr %ga4, align 2
%lb4 = load i16, ptr %gb4, align 2
%ne4 = icmp ne i16 %la4, %lb4
%z4 = zext i1 %ne4 to i16
%acc4.next = add i16 %acc4, %z4
%ga5 = getelementptr inbounds i8, ptr %pa, i64 10
%gb5 = getelementptr inbounds i8, ptr %pb, i64 10
%la5 = load i16, ptr %ga5, align 2
%lb5 = load i16, ptr %gb5, align 2
%ne5 = icmp ne i16 %la5, %lb5
%z5 = zext i1 %ne5 to i16
%acc5.next = add i16 %acc5, %z5
%ga6 = getelementptr inbounds i8, ptr %pa, i64 12
%gb6 = getelementptr inbounds i8, ptr %pb, i64 12
%la6 = load i16, ptr %ga6, align 2
%lb6 = load i16, ptr %gb6, align 2
%ne6 = icmp ne i16 %la6, %lb6
%z6 = zext i1 %ne6 to i16
%acc6.next = add i16 %acc6, %z6
%ga7 = getelementptr inbounds i8, ptr %pa, i64 14
%gb7 = getelementptr inbounds i8, ptr %pb, i64 14
%la7 = load i16, ptr %ga7, align 2
%lb7 = load i16, ptr %gb7, align 2
%ne7 = icmp ne i16 %la7, %lb7
%z7 = zext i1 %ne7 to i16
%acc7.next = add i16 %acc7, %z7
%ga8 = getelementptr inbounds i8, ptr %pa, i64 16
%gb8 = getelementptr inbounds i8, ptr %pb, i64 16
%la8 = load i16, ptr %ga8, align 2
%lb8 = load i16, ptr %gb8, align 2
%ne8 = icmp ne i16 %la8, %lb8
%z8 = zext i1 %ne8 to i16
%acc8.next = add i16 %acc8, %z8
%ga9 = getelementptr inbounds i8, ptr %pa, i64 18
%gb9 = getelementptr inbounds i8, ptr %pb, i64 18
%la9 = load i16, ptr %ga9, align 2
%lb9 = load i16, ptr %gb9, align 2
%ne9 = icmp ne i16 %la9, %lb9
%z9 = zext i1 %ne9 to i16
%acc9.next = add i16 %acc9, %z9
%ga10 = getelementptr inbounds i8, ptr %pa, i64 20
%gb10 = getelementptr inbounds i8, ptr %pb, i64 20
%la10 = load i16, ptr %ga10, align 2
%lb10 = load i16, ptr %gb10, align 2
%ne10 = icmp ne i16 %la10, %lb10
%z10 = zext i1 %ne10 to i16
%acc10.next = add i16 %acc10, %z10
%ga11 = getelementptr inbounds i8, ptr %pa, i64 22
%gb11 = getelementptr inbounds i8, ptr %pb, i64 22
%la11 = load i16, ptr %ga11, align 2
%lb11 = load i16, ptr %gb11, align 2
%ne11 = icmp ne i16 %la11, %lb11
%z11 = zext i1 %ne11 to i16
%acc11.next = add i16 %acc11, %z11
%ga12 = getelementptr inbounds i8, ptr %pa, i64 24
%gb12 = getelementptr inbounds i8, ptr %pb, i64 24
%la12 = load i16, ptr %ga12, align 2
%lb12 = load i16, ptr %gb12, align 2
%ne12 = icmp ne i16 %la12, %lb12
%z12 = zext i1 %ne12 to i16
%acc12.next = add i16 %acc12, %z12
%ga13 = getelementptr inbounds i8, ptr %pa, i64 26
%gb13 = getelementptr inbounds i8, ptr %pb, i64 26
%la13 = load i16, ptr %ga13, align 2
%lb13 = load i16, ptr %gb13, align 2
%ne13 = icmp ne i16 %la13, %lb13
%z13 = zext i1 %ne13 to i16
%acc13.next = add i16 %acc13, %z13
%ga14 = getelementptr inbounds i8, ptr %pa, i64 28
%gb14 = getelementptr inbounds i8, ptr %pb, i64 28
%la14 = load i16, ptr %ga14, align 2
%lb14 = load i16, ptr %gb14, align 2
%ne14 = icmp ne i16 %la14, %lb14
%z14 = zext i1 %ne14 to i16
%acc14.next = add i16 %acc14, %z14
%ga15 = getelementptr inbounds i8, ptr %pa, i64 30
%gb15 = getelementptr inbounds i8, ptr %pb, i64 30
%la15 = load i16, ptr %ga15, align 2
%lb15 = load i16, ptr %gb15, align 2
%ne15 = icmp ne i16 %la15, %lb15
%z15 = zext i1 %ne15 to i16
%acc15.next = add i16 %acc15, %z15
%pa.next = getelementptr inbounds i8, ptr %pa, i64 32
%pb.next = getelementptr inbounds i8, ptr %pb, i64 32
%i.next = add nuw i64 %i, 1
%done = icmp eq i64 %i.next, %n
br i1 %done, label %exit, label %loop
exit:
%w0 = zext i16 %acc0.next to i64
%w1 = zext i16 %acc1.next to i64
%w2 = zext i16 %acc2.next to i64
%w3 = zext i16 %acc3.next to i64
%w4 = zext i16 %acc4.next to i64
%w5 = zext i16 %acc5.next to i64
%w6 = zext i16 %acc6.next to i64
%w7 = zext i16 %acc7.next to i64
%w8 = zext i16 %acc8.next to i64
%w9 = zext i16 %acc9.next to i64
%w10 = zext i16 %acc10.next to i64
%w11 = zext i16 %acc11.next to i64
%w12 = zext i16 %acc12.next to i64
%w13 = zext i16 %acc13.next to i64
%w14 = zext i16 %acc14.next to i64
%w15 = zext i16 %acc15.next to i64
%s1 = add i64 %w0, %w1
%s2 = add i64 %s1, %w2
%s3 = add i64 %s2, %w3
%s4 = add i64 %s3, %w4
%s5 = add i64 %s4, %w5
%s6 = add i64 %s5, %w6
%s7 = add i64 %s6, %w7
%s8 = add i64 %s7, %w8
%s9 = add i64 %s8, %w9
%s10 = add i64 %s9, %w10
%s11 = add i64 %s10, %w11
%s12 = add i64 %s11, %w12
%s13 = add i64 %s12, %w13
%s14 = add i64 %s13, %w14
%s15 = add i64 %s14, %w15
ret i64 %s15
}
```
</details>
<details><summary>driver.c</summary>
```c
/* driver.c: time count() from lanesK.ll. ns per call over k = 2048 u16 (2048/K chunks). */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#ifndef K
#error define K
#endif
uint64_t count(const uint16_t *a, const uint16_t *b, uint64_t n);
int main(void) {
enum { N = 2048, ROWS = 1000 };
uint16_t *s = malloc(sizeof(uint16_t) * N * ROWS);
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < N; j++) s[i * N + j] = (uint16_t)((i * 31 + j * 7 + (i ^ j) * 3) % 13);
volatile uint64_t chk = 0;
for (int i = 0; i < ROWS; i++) chk += count(s, s + i * N, N / K); /* warm up */
struct timespec t0, t1;
clock_gettime(CLOCK_MONOTONIC, &t0);
for (int r = 0; r < 200; r++)
for (int i = 0; i < ROWS; i++) chk += count(s + (r % ROWS) * N, s + i * N, N / K);
clock_gettime(CLOCK_MONOTONIC, &t1);
double ns = ((t1.tv_sec - t0.tv_sec) * 1e9 + (t1.tv_nsec - t0.tv_nsec)) / (200.0 * ROWS);
printf("%.1f ns/call (checksum %llu)\n", ns, (unsigned long long)chk);
return 0;
}
```
</details>
This issue was isolated with the help of @claude.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs