Tuning LLVM's SLP Vectorizer Cost Model

Similar to my last post, this writeup covers how I solved a performance regression on LLVM by analyzing a benchmark from a RISCV target.

TLDR A recent LLVM patch introduced ordered vector reductions to replace a chain of scalar fadds, but it triggered a performance regression on a benchmark by failing to account for cost of building the initial vector per iteration. This in turned caused unprofitable code to be deemed “profitable.” PR, Issue

The Regression Looking at Igalia’s LNT instance for the BPI-F3, I noticed this particular benchmark with a delta of 89%. Specifically, there was an increase in ~26% issued instructions and a ~48% increase in cycles.

I have attached two more pictures right below, with the first one being the assembly of a basic block from the older build and the corresponding assembly from the newer build.

Info

Bn here refers to Billions of cycles. This basic block is basically taking twice as many cycles to execute.

We can see that that newer build of LLVM is performing a sequence of fsd instructions, also known as Float Store Double. It’s essentially storing the floating point values from those registers onto the stack. Specifically, it’s storing the value at the address s1 + 0x80. From a preceding basic block that I have not included here, I know that value of the register a5 to be equal to s1 + 0x80 from this instruction. addi a5, s1, 0x80 The Vector Load Instruction vle64.v is loading the values from memory at the address at a5 (s1 + 0x80) into the vector register v16. v16 = M[a5] Finally, it executes the vfredosum.vs instruction (Ordered floating-point sum), which performas the following for a vector register of size VL. \[ vd[0] = \left( \dots \left( \left( vs1[0] + vs2[0] \right) + vs2[1] \right) + \dots + vs2[VL-1] \right) \]The new codegen is basically trying to replace the ordered fadd instructions in the first basic block with this vector sum reduction instruction.

I hope this diagram may illustrate this better, with what was previously happening versus what is currently occurring. From the images above, it can be observed that the new code is significantly more expensive in terms of cycles.

graph LR %% Left-to-Right top level allows parallel tracks to scale height independently V_IN["Original Source Data<br/><i>(Residing in Scalar Registers)</i>"]

%% Link to Scalar Track V_IN -->|Old Execution| S1 %% Link to Vector Track V_IN -->|New Execution| FSD1

%% Left Side Track: Original Scalar Chain subgraph ScalarChain ["Original Intent: Ordered fadd Chain"] direction TB S1["fadd (START_VAL + SCALAR_VAL_0)"] --> S2["fadd (Result + SCALAR_VAL_1)"] S2 --> S3["fadd (Result + SCALAR_VAL_2)"] S3 --> S4["fadd (Result + SCALAR_VAL_3)<br/><code>FINAL_SCALAR_SUM</code>"] end

%% Right Side Track Part 1: Memory Gather (Now cleanly scales to its actual contents) subgraph Gather ["Memory Gather (Stack Spilling Penalty)"] direction TB FSD1["Store SCALAR_VAL_0 to s1 + 0x80"] FSD2["Store SCALAR_VAL_1 to s1 + 0x88"] FSD3["Store SCALAR_VAL_2 to s1 + 0x90"] FSD4["Store SCALAR_VAL_3 to s1 + 0x98"] end

subgraph VectorOps ["Vector Load & Reduction"] direction TB VLE["Vector Load<br/><i>(Loads from memory into vector register v16)</i>"] --> VFRED["Vector Ordered Sum Reduction<br/><i>(vfredosum)</i>"] end

%% Connect the two vector halves sequentially FSD4 -->VLE

%% --- STYLING BLOCK --- style ScalarChain

fill:none,stroke:#888888,stroke-dasharray: 5 5 %% Gather Penalty (Soft Red Glow) style Gather fill:#b71c1c18,stroke:#ef4444,stroke-width:2px,rx:8,ry:8 %% Vector Operations (Soft Blue Glow) style VectorOps fill:#0d47a118,stroke:#3b82f6,stroke-width:2px,rx:8,ry:8

Info

If you visit the link yourself, you may notice that there is also another basic block further down that also has a significant increase in cycles compared to its older counterpart. I chose not to include that as both of them are identical, so fixing one fixes the other.

The Where? To narrow down where these new fsd and vfredosum.vs instructions are introduced, I ran the command below to get emit the LLVM IR. The output of this commend will give us the intermediate representation produced by the middle-end. If we can observe IR code that would result in those instructions, we can rule out the backend. $lbd/bin/clang -O3 \ --target=riscv64-unknown-linux-gnu \ -march=rva22u64_v \ --gcc-toolchain=/usr \ --sysroot=/usr/riscv64-linux-gnu \ -I. \ -DFP_ABSTOLERANCE=1e-5 \ -S -emit-llvm seidel-2d.c \ -o seidel-2d.ll for.body8.i: ; preds = %for.body8.i, %for.cond5.preheader.i %18 = phi double [ %.pre117.i, %for.cond5.preheader.i ], [ %26, %for.body8.i ] %19 = phi double [ %.pre116.i, %for.cond5.preheader.i ], [ %18, %for.body8.i ] %20 = phi double [ %.pre115.i, %for.cond5.preheader.i ], [ %25, %for.body8.i ] %21 =

phi double [ %.pre114.i, %for.cond5.preheader.i ], [ %div.i40, %for.body8.i ] %22 = phi double [ %.pre113.i, %for.cond5.preheader.i ], [ %24, %for.body8.i ] %23 = phi double [ %.pre.i, %for.cond5.preheader.i ], [ %22, %for.body8.i ] %indvars.iv.i38 = phi i64 [ 1, %for.cond5.preheader.i ], [ %indvars.iv.next.i39, %for.body8.i ] %add.i = fadd double %22, %23 %indvars.iv.next.i39 = add nuw nsw i64 %indvars.iv.i38, 1 %arrayidx23.i = getelementptr inbounds nuw [8 x i8], ptr %arrayidx.i37, i64 %indvars.iv.next.i39 %24 = load double, ptr %arrayidx23.i, align 8, !tbaa !14 %arrayidx34.i = getelementptr inbounds nuw [8 x i8], ptr %17, i64 %indvars.iv.i38 %arrayidx40.i = getelementptr inbounds nuw [8 x i8], ptr %17, i64 %indvars.iv.next.i39 %25 = load double, ptr %arrayidx40.i, align 8, !tbaa !14 %arrayidx60.i = getelementptr inbounds nuw [8 x i8], ptr %arrayidx44.i, i64 %indvars.iv.next.i39 %26 = load double, ptr %arrayidx60.i, align 8, !

tbaa !14 %27 = insertelement <8 x double> poison, double %24, i32 0 %28 = insertelement <8 x double> %27, double %add.i, i32 1 %29 = insertelement <8 x double> %28, double %21, i32 2 %30 = insertelement <8 x double> %29, double %20, i32 3 %31 = insertelement <8 x double> %30, double %25, i32 4 %32 = insertelement <8 x double> %31, double %19, i32 5 %33 = insertelement <8 x double> %32, double %18, i32 6 %34 = insertelement <8 x double> %33, double %26, i32 7 %35 = call double @llvm.vector.reduce.fadd.v8f64(double -0.000000e+00, <8 x double> %34) %div.i40 = fdiv double %35, 9.000000e+00 store double %div.i40, ptr %arrayidx34.i, align 8, !tbaa !14 %exitcond.not.i41 = icmp eq i64 %indvars.iv.next.i39, 1999 br i1 %exitcond.not.i41, label %for.inc66.i, label %for.body8.i, !llvm.loop !25 We can observe here a chain of insertelement instructions building an <8 x double> vector. The instruction follows this format: %result = insertelement <vector_type> <source_vector>, <scalar_value>, <index> Using the snippet above, we can see that %27 is the initial vector. Because there is no prior value, the source is marked as poison, the scalar value it’s inserting is the value %24, and the index is 0.

From there, each subsequent instruction feeds the result of the previous line its source vector operand. Once the vector is completely packed at %34, it serves as an operand to the vector.reduce.fadd intrinsic (maps to vfredosum). The LLVM LangRef explains how this intrinsic sums up the elements in the second operand (34%), and adds the first operand (0.0), and stores the result (%35). The pseudocode provided by the LangRef probably explains this better. float sequential_fadd(start_value, input_vector) result = start_value // This is -0.00000 for i = 0 to length(input_vector) // Traverses every element in %34 result = result + input_vector[i] return result

Intrinsic

LLVM intrinsics are built-in functions that map directly to low-level architecture instructions, but can be hard to express in normal LLVM IR semantics. They give the compiler a better understanding of a hardware operation, allowing it to generate more efficient assembly.

Since the behaviour is already introduced by the middle-end, we can rule out the RISCV backend. I can confidently say that it was some middle-end pass causing this behaviour. This gives us a better idea of what to isolate. I ran git log on the dates of when the builds were ran, and grepped for keywords. After hitting a couple of dead-ends, I found a promising lead when I filtered specifically for reduction. git log --since="2026-05-19 00:00:00 +0000" --until="2026-05-20 00:13:39 +0000" --oneline | grep reduc

e28e7ec30357 Reland [VectorCombine] foldShuffleChainsToReduce - add support for partial vector reductions (#197659) dfa05b675eee [VectorCombine] Fold reduce.add == 0 into

reduce.[or,umax] == 0 (#180001) 230980947083 [SLP] Support ordered fadd reduction via reduction intrinsics 2d9407bb56b7 [X86] Add handling for sub-128bit minmax reductions (#198319) The third commit immediately stood out, as its description would perfectly explain the new codegen. After building LLVM locally before and with this commit, I was able to determine that the commit was the culprit. The Why? For some reason, the SLP Vectorizer thinks it more profitable to performed the fadd reduction here when we know from the benchmark that its not. The key things that author added in that commit were the following:

matchOrderedReduction

Responsible for finding possible instructions for ordered reduction.

tryToReduceOrdered

This is the function that actually checks if its profitable, and commits to the ordered reduction if it is.

SLP Vectorizer I think the LLVM docs does a decent job at a high-level overview of what the SLPVectorizer does. LLVM has two vectorizers, and the SLP Vectorizer is one of them. The pass’ main goal is to combine independent instructions into vector instructions. This is a pretty important in terms of performance. By vectorizing what was previously scalar instructions, you can perform the same operations on multiple values at once. This is especially beneficial when operations within a loop can be vectorized, as these tend to be the hotspots within a program. In this case though, the SLP Vectorizer was vectorizing a sequence of ordered instructions. I think the commit message itself will elucidate the goal of this commit better.

Previously, the SLP vectorizer could only vectorize ordered reductions by keeping the original scalar chain and emitting extractelement instructions. The new path replaces the scalar chain with a vector ordered reduction intrinsic (where profitable), which allows the backend to lower it more efficiently.

The following test case from the PR further illustrates the goal of the commit. - ; CHECK-NEXT: [[TMP28:%.*]] = extractelement <4 x float> [[TMP17]], i32 0 - ; CHECK-NEXT: [[TMP32:%.*]]