llvm / llvm/llvm-project

[AArch64][LoopVectorize] Ordered reductions are slower than what SLP can generate

Open
#224,338 1 comment 0 reactions 0 assignees View on GitHub
backend:AArch64 missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

LoopVectorize takes a loop with two independent, non-reassociable floating-point
accumulators and a fully used stride-2 interleave group, and generates ordered
reductions at VF=2, IC=4. Leaving the loop to SLP instead packs the two
accumulators into a single two-lane vector and is substantially faster.

The LV generated code is around 25% slower than what SLP used to do. Originally found in [JuliaLang/julia#63165](https://github.com/JuliaLang/julia/issues/63165)

This used to be faster in clang-18 over clang-23 but disabling ordered reductions with -force-ordered-reductions=false restores the performance

[2f7ccaf4a856](https://github.com/llvm/llvm-project/commit/2f7ccaf4a8565628a4c7d2b5a49bb45478940be6)

kernel.c
```c
static inline double A(double i, double j) {
return (i + j - 2.0) * (i + j - 1.0) * 0.5 + i;
}

__attribute__((noinline))
double row(const double *restrict v, long i, long n) {
if (n <= 1) return 0.0;
long last = n - ((n & 1) ^ 1);
double even = 0.0, odd = 0.0;
for (long j = 1;; j += 2) {
even += v[j - 1] / A((double)i, (double)j);
odd += v[j] / A((double)i, (double)(j + 1));
if (j == last) break;
}
return even + odd;
}
```

The C flags are a bit odd to reproduce what Julia does.
```sh
clang -O2 -mcpu=apple-m1 -ffp-contract=off -fwrapv -fno-finite-loops \
-S -emit-llvm kernel.c -o lv.ll

clang -O2 -mcpu=apple-m1 -ffp-contract=off -fwrapv -fno-finite-loops \
-mllvm -force-ordered-reductions=false \
-S -emit-llvm kernel.c -o slp.ll
```

LV generated code
```llvm
...
; Loop block %21; preheader %15.
%23 = phi double [ 0.000000e+00, %15 ], [ %120, %21 ]
%24 = phi double [ 0.000000e+00, %15 ], [ %124, %21 ]
; ... address calculation ...
%37 = load <4 x double>, ptr %30, align 8, !tbaa !10
%38 = shufflevector <4 x double> %37, <4 x double> poison, <2 x i32>
%39 = shufflevector <4 x double> %37, <4 x double> poison, <2 x i32>
; ... three more loads with the same de-interleaving pattern ...
; ... denominator arithmetic ...
%77 = fdiv <2 x double> %38, %73
%78 = fdiv <2 x double> %41, %74
%79 = fdiv <2 x double> %44, %75
%80 = fdiv <2 x double> %47, %76
; ... denominator arithmetic for the other chain ...
%113 = fdiv <2 x double> %39, %109
%114 = fdiv <2 x double> %42, %110
%115 = fdiv <2 x double> %45, %111
%116 = fdiv <2 x double> %48, %112
%117 = tail call double @llvm.vector.reduce.fadd.v2f64(double %23, <2 x double> %77)
%118 = tail call double @llvm.vector.reduce.fadd.v2f64(double %117, <2 x double> %78)
%119 = tail call double @llvm.vector.reduce.fadd.v2f64(double %118, <2 x double> %79)
%120 = tail call double @llvm.vector.reduce.fadd.v2f64(double %119, <2 x double> %80)
%121 = tail call double @llvm.vector.reduce.fadd.v2f64(double %24, <2 x double> %113)
%122 = tail call double @llvm.vector.reduce.fadd.v2f64(double %121, <2 x double> %114)
%123 = tail call double @llvm.vector.reduce.fadd.v2f64(double %122, <2 x double> %115)
%124 = tail call double @llvm.vector.reduce.fadd.v2f64(double %123, <2 x double> %116)
...
```

SLP generated code

```llvm
%13 = phi i64 [ 1, %5 ], [ %31, %12 ]
%14 = phi <2 x double> [ zeroinitializer, %5 ], [ %29, %12 ]
%15 = getelementptr [8 x i8], ptr %0, i64 %13
%16 = getelementptr i8, ptr %15, i64 -8
%17 = load <2 x double>, ptr %16, align 8, !tbaa !10
; ... index conversion and denominator arithmetic ...
%28 = fdiv <2 x double> %17, %27
%29 = fadd <2 x double> %14, %28
%30 = icmp eq i64 %13, %8
%31 = add nuw i64 %13, 2
br i1 %30, label %32, label %12
```

Contributor guide

Open the contributing guide

Research direction

Start with kernel.c and reproduce both clang commands using -mcpu=apple-m1, then compare the LoopVectorize and SLP-generated LLVM IR. Investigate the ordered-reduction path and the effect of -force-ordered-reductions=false; done means the AArch64 case no longer produces the reported slowdown while preserving correct floating-point behavior.

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
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.