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

Reply via email to