llvm / llvm/llvm-project

[LoopVectorize][X86] Single-tier epilogue underperforms a cascading (multi-VF) remainder for runtime-trip-count copies on AVX2

Open
#215,535 5 comments 0 reactions 0 assignees View on GitHub
backend:X86 missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Test case
```c
// Geekbench 6 Object Detection pad::execute(): int8 copy into a padded row.
// The surrounding fill loops + shared running index are needed to reproduce
// (a plain out[c]=in[c] loop takes a different remainder path). Dominant N=64.
#include
#include
void pad_execute(int8_t *out, const int8_t *in, size_t pad_l, size_t N,
size_t pad_r, int8_t fill) {
size_t o = 0, i = 0;
for (size_t c = 0; c < pad_l; c++) out[o++] = fill;
for (size_t c = 0; c < N; c++) out[o++] = in[i++]; // hot
for (size_t c = 0; c < pad_r; c++) out[o++] = fill;
}
```
`clang -O3 -mavx2 -S` (trunk `ddd7b23`).

## Problem
Main loop is `VF=32, IC=4` → 128 B/iter, entered only if `N >= 128`. For mid-size
`N` it is skipped and the copy runs on a single **`VF=16` (XMM, 128-bit) epilogue**
— the 256-bit YMM width is never used.

`VF=32` (YMM) is a *legal* epilogue candidate (`VF <= MainLoopVF`) and forcing it
works, so this is purely a cost decision:

| build | epilogue |
|---|---|
| default | XMM `VF=16` (`ymm=8, xmm=2`) |
| `-mllvm -epilogue-vectorization-force-VF=32` | YMM `VF=32` (`ymm=10, xmm=0`) |

## Root cause
In `selectEpiloguePlan` (`LoopVectorize.cpp`), because the trip count is a runtime
value, `RemainingIterations = TC urem (VF*IC)` is unresolved, so the epilogue is
costed at the worst case `MaxTripCount = VF*IC-1 = 127` (~L3573). Under that,
`isMoreProfitable` (~L3619) prefers `VF=16` (tail `127%16=15`) over `VF=32` (tail
`127%32=31`).

With a **known** TC the problem vanishes — same kernel, `N` constant `64`: IC drops
to 2, main runs as `2×YMM`, no epilogue, no tail. Every worst-case choice (IC=4,
MaxTC=127, VF=16) stems from `N` being unknown.

## A single epilogue tier cannot win — the remainder needs to cascade
The core limitation is that LLVM emits **one** cost-selected epilogue VF, then goes
scalar. No single VF is good for all runtime sizes: a wide (YMM) tier is best when
the remainder is a multiple of the width, a narrow (XMM) tier is best for awkward
remainders. Forcing either shows the tension (intra-clang, `-O3 -mavx2`, isolated
copy, GB/s):

| N | default (XMM `VF=16`) | force-VF=32 (YMM) |
|---|--:|--:|
| 64 | 14.8 | 17.9 |
| 96 | 20.3 | 24.7 |
| 48 | 11.2 | 7.8 |
| 127 | 16.8 | 15.1 |

GCC avoids the tradeoff entirely with a **cascading, descending-width remainder** —
`YMM → XMM → 8B → byte`, each tier peeled once under a size guard:
```asm
.L6: vmovdqu %ymm ... ; main, 32 B/iter
.L5: cmpq $14,%r; jbe .L16 ; if >=16 left: one XMM (16 B)
vmovdqu %xmm ...
.L8: cmpq $6,%r; jbe .L10 ; if >=8 left: one 8-byte GPR move
movq ...
.L10: movzbl/movb ... ; <8 B: bytes
```
This gives **full width for the bulk and a bounded (<8 B) scalar tail for any
trip count** — which is why GCC is uniformly faster across the mid-size range.
Each tier is peeled once under a `remaining >= VF` guard (verified across
i8/i16/i32/i64), so a cascade only adds skipped branches on the small-remainder
path — no regression versus today's single-tier + scalar tail.

## Suggested direction — a cascading multi-VF epilogue
Extend epilogue vectorization from a single tier to a **cascade of descending VFs**
(`VF=32 → 16 → 8 → scalar`) rather than choosing one VF and dropping to scalar.
This is the general fix: it covers both the multiples-of-VF sizes (full width) and
the awkward remainders (bounded tail), independent of the runtime trip count. It
corresponds to the remainder-vectorization idea in **D88819** that was not adopted
in favor of the current single-epilogue design.

Smaller interim step: cost the single epilogue VF with an expected/best-known
remainder (e.g. `getSmallBestKnownTC`) instead of the worst-case `VF*IC-1`; this
recovers the multiples-of-VF sizes but not the awkward ones. (Raised on #108190.)

Neither requires changing the main-loop interleave factor.

## Reproduce
```
clang -O3 -mavx2 -S t.c
clang -O3 -mavx2 -mllvm -epilogue-vectorization-force-VF=32 -S t.c
```

Contributor guide

Open the contributing guide

Research direction

Start in LoopVectorize.cpp at selectEpiloguePlan and review the remainder-costing logic around the referenced locations. Reproduce the behavior with the provided t.c commands, including the forced VF=32 comparison. Done means supporting descending VF=32 → 16 → 8 → scalar epilogue tiers with bounded scalar remainder behavior, while checking the i8/i16/i32/i64 cases described.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.