[Polly] matmul pattern matching stopped firing on fixed size 2D arrays, works on 20.x
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Polly's BLIS matmul optimization used to fire on a normal matmul over `double (*)[N]` with a constant N. On trunk it doesn't. Polly itself looks unchanged to me, what changed is the IR it gets handed: instcombine now splits the two index GEP into a chain of byte typed GEPs as part of the ptradd work, `buildAccessMultiDimFixed` can't recover the array shape out of a chain, so the access ends up modelled flat 1D and `isMatMulOperandAcc` bails on its `dim(isl::dim::out) != 2` check. After that you just get generic tiling.
Two local trunk builds, `clang version 20.0.0git` good and `24.0.0git` bad, aarch64-unknown-linux-gnu. Neither binary has an llvmorg- string or a commit hash in it so I can't give exact revisions here.
repro (do not shrink N below 60, see below):
```c
#define N 64
void matmul(double (*restrict A)[N], double (*restrict B)[N], double (*restrict C)[N])
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
double sum = 0.0;
for (int k = 0; k < N; k++)
sum += A[i][k] * B[k][j];
C[i][j] = sum;
}
}
```
```
clang -O3 -mllvm -polly -mllvm -polly-optimized-scops -c mm.c -o /dev/null
```
20 gives `double MemRef1[*][64]` and `{ Stmt2[i0, i1, i2] -> MemRef1[i0, i2] }`, with Packed_A / Packed_B and CopyStmt_0/1 in the dump. 24 gives `double MemRef1[*]` and `MemRef1[64i0 + i2]`, no Packed_ anywhere.
The thing that convinced me this is a polly side problem: write the same nest with a runtime sized VLA (`double A[restrict n][n]`) and it **still fires on 24**, you get `double MemRef1[*][(zext i32 %0 to i64)]` and Packed_ back. Same binary, same flags. So there is already a shape recovery path that copes with the new IR, and it's only the fixed size one that got left behind.
Also worth knowing, `-mllvm -polly-pattern-matching-based-opts=false` on 20 gives you no Packed_ but the shape is still 2D. So the zero on 24 isn't the optimization being off, the shape is gone before it ever gets a look.
**Please don't shrink N.** Under 50 both versions give nothing (the loops unroll and the array degrades to scalar MemRefs). 50 to 56 is some other divergence where 24 forms no SCoP at all, which I didn't chase. 60 and up is this bug. If you drop it to 32 you'll conclude it doesn't repro.
I ablated a number of things that turned out not to matter: restrict, float vs double, C vs C++, `-mcpu` anything, `-fopenmp`, `-polly-parallel`, the vectorizer, and the opt level (O1/O2/O3/Ofast all show it). What does matter is the trailing dimension being a compile time constant. Writing it flat as `A[i*N+k]` gives 1D and no Packed_ on **20's own polly** too, so being modelled 1D is by itself enough to kill the kernel.
You can see the IR change with no polly involved, `opt -passes=instcombine` on a two index GEP: 20 keeps `getelementptr inbounds [2048 x double], ptr %A, i64 %i, i64 %k`, 24 turns it into `[16384 x i8]` then `[8 x i8]`. Both forms are correct, I'm not claiming instcombine is doing anything wrong here.
I wasn't able to bisect this. There's no intermediate toolchain on this machine, and I couldn't find a cl::opt that gates either fold. It's somewhere in the ptradd window, 2025-07-30 to 2026-03-06. 8a09adc22adb (#137297, split GEPs with multiple variable indices) is the earliest that would do it and a301e1a89529 (#151333) looks independently sufficient too, so even a clean bisect probably wouldn't land on one commit. I think 6ecbc0c96e56 (#180745) can be ruled out, it's guarded on `Indices.size() == 1`, and I can still reproduce the split with element types preserved and no i8 present.
Filing under polly rather than instcombine because the new IR is deliberate and correct, the commit messages say multi index GEPs are going away ahead of ptradd. The fragile bit is `buildAccessMultiDimFixed` pattern matching a single GetElementPtrInst with an ArrayType index chain and also wanting `GEP->getOperand(0)` to be the array base. Given the VLA case still works, the fix probably belongs in ScopBuilder, either walk a chain when accumulating subscripts and sizes, or send constant bounded arrays through the same SCEV delinearization the VLA path already uses. Happy to move this if you disagree.
Only tested aarch64, both my builds only register aarch64 and nvptx. I'd expect it to reproduce elsewhere but I haven't confirmed that.
For scale, a 2048x2048 double matmul went from about 0.7s to 5-6s for us. It doesn't look as bad as it is because the generic tiling fallback still parallelizes, so with -polly-parallel it just spreads worse code over every core. CPU time is the real tell, that went from around 0.7 CPU seconds to about 11.
Contributor guide
Research direction
Start with ScopBuilder's buildAccessMultiDimFixed and the fixed-size access handling, then compare the instcombine output and Polly dumps for the provided mm.c reproducer using the listed clang and opt commands. Done means fixed-size constant-dimension arrays retain a two-dimensional MemRef and Polly again produces Packed_A and Packed_B, while the VLA behavior remains intact.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100