[LoopFusion] Initiating a Cost Model for LoopFusion

IR & Optimizations Loop Optimizations
1

[LoopFusion] Add a Cost Model to LoopFusion

Co-authored by @madhur13490

Summary

This RFC proposes an initial cost model for LoopFusion, requiring either same-iteration read-after-write (RAW) reuse or exact same-address affine read-after-read (RAR) reuse before fusion.

This patch is intended as an initial, low-cost step rather than a complete cost model. The intention is to provide a foundation for incrementally adding heuristics for register pressure, vectorisation compatibility, the strength of memory-locality benefits, and others that would benefit LoopFusion’s cost model, provided that they reuse existing analyses or remain cheap enough to avoid significant compile-time overhead.

1. Problem

LoopFusion currently has legality checks but no implemented cost model (issue #189117). Because of this, when fusion is enabled, every legal candidate is fused regardless of whether fusion is expected to be beneficial. While fusion can improve locality, it can also combine unrelated loops, increase register pressure, or inhibit later optimisations.

To capture the impact of this behaviour, the full C/C++ LLVM Test Suite benchmark scope was run, with runtime measured for selected fusion-affected tests. Among those measurements, the Test Suite for Vectorizing Compilers (TSVC) provides the most significant results:

The current behaviour upstream (unrestricted fusion) does improve the LoopRestructuring kernels, which include loop-interchange cases, by ~8%, but regresses the Packing kernels by 13.54%. The former contains exact cross-loop memory reuse, while the latter fuses unrelated setup loops. This motivates demonstrated cross-loop reuse as a low-cost first profitability signal.

2. Proposal

To begin cost model work on LoopFusion with the following memory reuse heuristic as an initial step towards a more complete cost model:

  • Require at least one distinct value reused at corresponding iterations between two otherwise-legal fusion candidates.
  • Recognise same-iteration RAW reuse through the existing dependence analysis and exact same-address affine RAR reuse through SCEV.
    This accepts producer-consumer loops and exact corresponding-address shared reads while rejecting legal fusion pairs with no demonstrated memory reuse.
  • Use this as a foundation for incrementally adding other low-cost signals, such as vectorization compatibility, register pressure, and the strength of locality benefits.

3. Design and Implementation

  • RAW reuse is collected from the dependence queries already performed for legality. A producer instruction in the first loop is counted when DependenceAnalysis reports a non-confused flow dependence whose direction at the candidate-loop level is EQ, meaning the second loop reads its result at the corresponding iteration.
  • RAR reuse requires matching affine load keys (type, start, step), derived from the pointer recurrence reported by SCEV. Loads from the first loop are indexed in a SmallDenseMap; loads from the second loop perform direct lookups. For R0 and R1 reads in the first and second loops, this gives an average O(R0 + R1) collection instead of O(R0 × R1) pairwise read-read dependence queries. The intention is to keep compile time low as we build out the cost model.
  • A set of producer instructions tracks distinct reused values, and collection stops once the default threshold of one is met.
  • SCEV is used only to identify profitable reuse. The existing DependenceAnalysis checks continue to determine whether fusion is legal as before.

4. Evaluation

In order to evaluate the impact of this initial cost model, evaluation was conducted combining a full-suite analysis of fusion coverage with runtime measurements for selected fusion-affected tests across the C/C++ LLVM Test Suite

All measurements compare the same three configurations:

  • Fusion off: LoopFusion is disabled.
  • Unrestricted fusion: LoopFusion is enabled without the cost model (current upstream behaviour)
  • Cost model: LoopFusion is enabled with our proposed initial cost model.

4.1 Full C/C++ LLVM Test Suite fusion coverage

Fusion coverage was measured at three levels across the C/C++ LLVM Test Suite build:

  1. Successful fusion transformations count passed FuseCounter remarks, which are emitted once immediately before each fusion is performed.
  2. Unique reported fusion locations deduplicates successful remarks by their reported source file, line, and column.
  3. Benchmark directories with fusion counts build-tree benchmark directories containing at least one successful fusion.
Metric Fusion off Unrestricted fusion Cost model Cost-model reduction vs unrestricted
Successful fusion transformations 0 8,342 81 99.03%
Unique reported fusion locations 0 512 23 95.51%
Benchmark directories with fusion 0 58 13 77.59%

The proposed model is intentionally conservative and reduces fusion transformations by 99.03% and the benchmark directories containing fusion from 58 to 13. Section 4.2 examines whether this selectivity keeps useful fusions while avoiding clear regressions in the measured cases.

4.2 Application and TSVC runtime

Runtime was measured for 12 selected tests. The table presents the three TSVC executables with the clearest connection between fusion decisions and performance. Each executable contains a group of kernels, and the fusion columns count transformations performed while building the executable rather than runtime executions. The -dbl and -flt variants use double- and single-precision element types respectively. The first table reports the number of successful fusions performed while building each executable.

Benchmark Fusion off Unrestricted fusion Cost model
LoopRestructuring-dbl 0 227 1
LoopRestructuring-flt 0 227 1
Packing-dbl 0 225 0

The next table reports five-run median execution times in seconds. Fusion off is the baseline, and negative changes indicate improvements.

Benchmark Fusion off Unrestricted fusion Cost model Unrestricted change vs fusion off Cost-model change vs fusion off
LoopRestructuring-dbl 2.3153 s 2.1218 s 2.1610 s -8.36% -6.66%
LoopRestructuring-flt 2.0513 s 1.8802 s 1.9052 s -8.34% -7.12%
Packing-dbl 1.7037 s 1.9343 s 1.7110 s +13.54% +0.43%

For each LoopRestructuring variant, the cost model keeps one fusion in s233, where both loops read cc[j][i], which alone recovers most of unrestricted fusion’s improvement. It rejects s2233, where the second access is transposed. For Packing, the proposed model performs no fusions and remains close to fusion-off, while unrestricted fusion performs 225 transformations and regresses by 13.54%. The accepted transformations include unrelated setup loops with no cross-loop reuse. These results support demonstrated cross-loop reuse as a useful initial signal, while the broader excluded set still contains neutral changes and some small improvements that future heuristics may recover.

4.3 LoopVectorization microbenchmarks

Five selected LoopVectorization microbenchmarks were measured to test whether accepted reuse-driven fusions were consistently profitable. The first table reports fusion coverage across the complete LoopVectorization build.

Metric Fusion off Unrestricted fusion Cost model
Number of fusions 0 90 36

The cost model substantially reduces fusion in this benchmark group, but its kept set still includes the truncation/extension case below.

The next table shows the largest measured regression. Values are five-run median times in nanoseconds. ‘Fusion off’ is the baseline.

Microbenchmark Fusion off Unrestricted fusion Cost model Unrestricted change vs fusion off Cost-model change vs fusion off
trunc/zext VW16 uint64_t to uint8_t 996.766 ns 1,062.536 ns 1,061.759 ns +6.60% +6.52%

Both unrestricted fusion and the cost model fuse this case and regress by approximately 6.5%. This shows that exact RAR reuse is not sufficient by itself to guarantee profitable fusion and motivates further work on this such as the vectorisation-compatibility work described in the next sections.

4.4 Preliminary compile-time check

Compilation CPU time is summed user time from 2,014 matched object-file compilations.

Configuration Compilation CPU time Proposed model vs configuration
Fusion off 549.455 s +3.05%
Unrestricted fusion 766.333 s -26.11%
Proposed model 566.209 s -

This shows no large compile-time regression, but the 3.05% value is preliminary and will be re-ran with the compile time tracker

5. Next Steps:

Both unrestricted fusion and the proposed model fuse the LoopVectorization truncation/extension case, and both regress by approximately 6.5%. This is a reproducible weakness of accepting exact RAR without considering the effect on vectorisation. A potential follow-up could have us first investigate a cheap vectorisation-compatibility heuristic. More data-driven heuristics could also be used to address register pressure and also distinguish stronger from weaker locality benefits.

Disclaimer: Generation of this RFC was partly assisted by AI tools.

4 Likes
2

Looks like a good starting point to me. I will continue looking into the PR and potentially discuss a couple of points there. Thanks for the work.

1 Like
3

Thanks @amehsan. That will be really useful to keep pushing loop fusion ahead.

4

Thanks for the detailed analysis. Some remarks:

  • Is https://github.com/llvm/llvm-project/pull/224626 supposed to be a proof-of-concept to refine the heuristic or is it intended to be merged? The test transforms/LoopFusion/guard_skip_empty_block.ll is failing.

  • What ideas do you have for the vectorization-compatibility heuristic

-TSVC: Packing-dbl regresses +0.43% but according to the text no transformation is performed. So this noise? What is the variance of the 5 runs? For LoopRestructuring, is s2233 the remaining 1-2% that unrestricted loop fusion is ahead?

  • Did you measure any SPEC CPU benchmarks?

  • As loop fusion and loop distribution are the opposite of each other, did you consider having them share the same heuristic?

6

Intended to merge. The reuse cost model is enabled by default but I’ve added an opt-out flag for tests and incremental work.

guard_skip_empty_block.ll was added after my last green CI. Rebasing onto current main pulled it in. Since it tests fusion on store-only loops with no cross-loop reuse, the run line needs -loop-fusion-disable-cost-model, like the other similar fusion tests in the PR. That fix is in the latest commit

I was thinking that looking into the LoopAccessAnalysis would be a good start (since I was able to see how LoopDistribute uses it) alongside a light use of TTI. I want to be mindful of the ct regressions that these could introduce though and will factor that in when spiking the heuristic.

Yes, it is noise and no fusions were triggered. The range was from 1.6830 to 2.0444 s without fusion and from 1.6727 to 1.7154 s with the cost model. The reported +0.43% is only the gap between the medians (1.7037 s vs 1.7110 s), which is far smaller than that run-to-run scatter. I included it for completeness but I can remove the +0.43% from the table if it adds confusion.

For the point on s2233 no, afaiu it’s the opposite. Our cost model avoids fusing s2233 and when I reduced LoopRestructuring to just s2233, fused runs were ~48% slower over 15 run medians than unfused runs. So fusing s2233 isn’t why unrestricted wins on the full binary. Afaiu, the likely reason is due to the other fusion sites we reject on the cost model (mostly in the TSVC init setup).

Yes, though for this RFC I’ve focused only on the llvm-test-suite results instead given that it’s openly available for anyone to see and the discussion on the gh issue was leaning towards using that as a measure

I’ve looked at LoopDistribute for the vectorization-compatibility and am considering sharing analysis (e.g. LAA, and TTI) seems useful, but I’ve not considered a single shared heuristic.

7

If you have the data, it would still be good to share. It would also be good to include the CPU/system you used for your benchmarks (sorry if I missed it in the thread)

It is also not clear to me how you picked the subset of microbenchmarks you shared results for.

Please measure with the compile-time tracker. If it is indeed 3%, I think this is likely to be considered a notable compile-time regression.

9

If you have the data, it would still be good to share. It would also be good to include the CPU/system you used for your benchmarks.

Since the 2026 rate suite triggered no fusions, we mainly used the 2017 rate suite… unrestricted fusion performed 87 fusions across 12 workloads (52 unique benchmark-source locations), while the cost model kept 25 of them across 7 workloads (14 unique locations). The measurements were run on a Grace CPU

It is also not clear to me how you picked the subset of microbenchmarks you shared results for.

I first collected fusion counts across the full LLVM test suite and then selected the areas with the highest concentration of successful fusions. TSVC and the LoopVectorization microbenchmarks contained the most opportunities.

Please measure with the compile-time tracker. If it is indeed 3%, I think this is likely to be considered a notable compile-time regression.

Agreed. I reran this with the LLVM CT Tracker:

Configuration Transformations Unique locations Benchmarks
Unrestricted 8 7 2
Cost model 6 4 2

I also ran it locally to verify where the fusion sites were and all fusions occurred in the benchmarks ClamAV and mafft.

10

LAA only checks feasbility of innermost-loop vectorization, not whether LoopVectorize will actually do anything. Note that LoopDistribute skips when the loop is already vectorizable before applying the loop distribution. It still does not count as profitability heuristic for LoopDistribute which because of this doesn’t to anything by default. For loop fusion it could be a heuristic such as “don’t fuse a loop that is vectorizable with a loop that is not”.

1 Like
11

I think that is an interesting idea.

I am thinking aloud here. On sharing a heuristic with LoopDistribute: I think the two signals can be shared as predicates rather than one monolithic model. (1) Corresponding-iteration reuse, as in this RFC, is a benefit for fusion and a cost for distribution: splitting a loop throws away exactly this reuse. (2) Vectorization compatibility (LAA plus IVDescriptors): fusion avoids merging a vectorizable loop with a non-vectorizable one, and distribution only splits when it turns a non-vectorizable loop into at least one vectorizable part. Because distribution only creates pairs that the fusion rule refuses to merge, the two passes cannot undo each other.

Please have a look at new way of distributing the loop at RFC: Statement-Seeded Partitioning for Loop Distribution

I think we can develop on this thought incrementally…