[RFC] Universal Profile-Guided Automatic Software Loop Data Prefetcher for LLVM

[SergeyShch01]

[RFC] Universal Profile-Guided Automatic Software Loop Data Prefetcher for LLVM

Full design document
Initial related LLVM PR: PR #166553

Summary

This RFC proposes upstreaming the current implementation of a profile-guided automatic software loop data prefetcher for LLVM. The implementation is an LLVM function pass for AArch64 platforms that support SPE, consumes collected load profiles, and addresses our current motivating workloads and engineering needs.

The prefetcher is called universal because the complete design is not restricted to a fixed set of address-expression templates. Its target model is any load whose memory address can be computed ahead of time, regardless of whether the address-producing slice contains multiple PHI nodes, control flow, recurrences such as pointer-chasing loops, inner computations, or cross-call dependencies. The current implementation covers a practical subset of this design; the additional full-design scope is summarized near the end of this RFC and described in detail in the linked document.

The core of the framework — the per-loop pipeline, dependency DAG, distance scheduling, profitability and overhead budgeting, and hoisting of original instructions — is architecture-neutral and can be reused as-is on other targets. Porting to a new target still requires target-specific work: wiring up an equivalent precise event-based sampling source (for example, PEBS on x86) as a profile provider, tuning the heuristics for the target’s microarchitectural characteristics, and configuring the prefetch safety machinery to the instruction set actually available on that target.

The proposed prefetcher includes the existing LoopDataPrefetch functionality as a subset: it covers SCEV-expressible single-induction-variable access patterns and can be configured to behave equivalently. The current implementation already goes beyond that subset with profile-driven per-load distance selection, dependency-aware scheduling, safety handling, overhead budgeting, and hoisting of original instructions. The full design further broadens the supported address-computation space, as summarized below. The intended end state is for the new prefetcher to subsume and replace LoopDataPrefetch.

Motivation

Memory latency remains a major performance limiter. Loads that miss in the last-level cache, or incur expensive address-translation behavior such as DTLB misses, can stall dependent execution for hundreds of cycles. These delinquent loads are often irregular and data-dependent, which makes them difficult for hardware prefetchers and existing compiler prefetch passes to handle.

LLVM’s existing LoopDataPrefetch pass is fully static. It targets affine, single-induction-variable address expressions expressible by SCEV as {base, +, stride}, and its prefetch distance comes from a target-provided constant rather than from workload behavior.

Recent academic systems extend the scope but remain narrow. APT-GET is profile-guided, but every PHI in the address slice must be a loop induction variable, so non-IV recurrences such as pointer-chasing loops are out of scope. RPG2 recognizes only three fixed address pattern templates tied to an inner/outer induction-variable structure. In both systems, analysis and placement are confined to the two innermost loop levels, and outer-loop hoisting is limited to a single immediately enclosing loop.

The proposed framework addresses these limitations with a profile-guided, latency-ranked, safety-aware, and overhead-aware prefetching pipeline.

Profiling

The current implementation uses two profile inputs:

• a load profile, collected through precise event-based sampling, describing the memory behavior of individual load instructions;
• an optional branch profile, used to estimate loop trip counts, per-load hotness relative to the loop header, and average instruction count per loop iteration.

Load-profile collection is integrated into llvm-profgen. Load-latency information is extracted from SPE profiling samples, recorded in an extended profile format, and attached to LLVM IR load instructions through MD_prof.

The optional branch profile may be collected together with the load profile or in a separate profiling run. It is used to estimate the loop trip count, the load hotness relative to the loop header, and the average instruction count per loop iteration; when absent, the pass falls back to static estimates.

Current Implementation Overview

The current prefetcher is an LLVM function pass for AArch64 platforms that support SPE.

For every loop, the current implementation performs the following high-level pipeline:

1. Identify candidate delinquent loads from the load profile.
2. Deduplicate loads that access the same cache line.
3. Compute the address-producing predecessor slice for each candidate.
4. Build a dependency DAG between prefetches when one prefetch’s address computation depends on another prefetched load.
5. Compute prefetch distances recursively over that DAG.
6. Apply per-load profitability and global overhead budgeting.
7. Generate prefetch code by cloning the address computation and hoisting it a selected number of loop iterations ahead, so it prefetches data for a future iteration.
8. Apply safety mechanisms for potentially unsafe speculative execution.
9. When profitable, hoist original instructions to replace duplicated cloned computation with pipelined original computation communicated through ring buffers.

Ring buffers are used when an original loop instruction is hoisted into an earlier prefetch pipeline stage. The moved instruction produces a value for a future iteration, while its original consumers still execute later. A small per-value circular buffer stores the produced values until the corresponding later iteration consumes them; indexing is derived from the loop induction variable and wraps with a power-of-two mask. A prologue initializes the entries needed by the first steady-state iterations.

Safety

Prefetch address computation executes ahead of its original program point, so it can encounter inputs that the original program would not have produced at that point. The framework handles this explicitly instead of assuming that generated prefetch code is always safe.

The safety logic focuses on two main sources of risk:

• post-exit iteration execution, where prefetch code computes values for iterations beyond the loop exit;
• store-load aliasing, where an early load in the prefetch address computation may observe a value different from the original execution order.

The current implementation provides operand sanitization and bypass branches. It can also use target-provided non-faulting load variants as a safety mechanism; on AArch64, this is implemented with ldnf1d.

Performance Notes

The current performance tuning was done on NVIDIA Grace CPU systems, based on Arm Neoverse V2 cores. Software prefetching is highly sensitive to microarchitectural details, so thresholds and conclusions may be CPU-specific.

On internal workloads, the current implementation has shown speedups of up to +56%. Among open and publicly known benchmarks, representative results obtained on serial (single-threaded) benchmark versions include (links to the benchmark sources are provided in the full design document):

• graph500/bfs: +31%
• gapbs/sssp: +11%
• gapbs/bc: +10%
• hashjoin-ph-2: +22%

These benchmarks cover different forms of indirect memory access patterns.

The loads that benefited most consistently were those with frequent DRAM or DTLB misses. A key limiting case is when the original demand misses are already too frequent: they can saturate memory-system throughput and leave little room for software prefetches, which are often deprioritized or dropped in such situations. Another limiting factor was small loop trip count, especially because promotion of prefetches into enclosing loops is not yet implemented. This is a trade-off rather than a hard cutoff; we observed useful cases around trip count 32.

Proposed Patch Plan

We currently expect the work to be split into the following patch sequence. This sequence describes the proposed review order, not the current internal implementation status; some later patches correspond to functionality that already exists internally but will be posted separately to keep reviews manageable.

1. ExtBinary format extension. Extend the ExtBinary format used by the profile toolchain. This work is already ongoing: PR #166553. Review comments are welcome.
2. AArch64 SPE branch profiling. Add SPE-based branch profiling and enable an llvm-profgen-based profiling toolchain for AArch64.
3. AArch64 SPE load profiling. Add SPE-based load profiling and load-profile propagation into LLVM IR.
4. Basic Universal Loop Data Prefetcher. Land a simplified reviewable subset of the pass without non-trivial CFG support, memory aliasing checks, non-faulting loads, hoisting of original instructions, or recurrence support.
5. Non-trivial CFG support. Add support for address computations involving non-trivial control flow.
6. Memory aliasing checks. Add memory alias analysis and checks needed by the prefetch safety machinery.
7. Non-faulting load support. Add support for using non-faulting load variants in prefetch address computation where the target supports them.
8. Recurrence support. Add support for non-IV recurrences in address computations.
9. Hoisting of original instructions. Add hoisting of original instructions and the corresponding ring-buffer pipeline machinery.

Full Design Extensions

The full design is structured to accommodate several extensions beyond the current implementation. These extensions are not required for the initial upstream version and can be implemented incrementally when there is sufficient motivation:

• direct latency sampling as an additional profiling mode on targets where accurate load-latency samples are available;
• loop preheader prefetching for early iterations;
• recursive promotion of prefetches through enclosing loops;
• function-call handling, including partial inlining of callee address-computation slices;
• loop versioning for pre-loop safety checks;
• richer control-flow support in address computations, including switch instructions and inner loops;
• inter-stage clone deduplication for non-relocatable instructions.

Request for Guidance

We would appreciate community input on the following items:

1. Community interest. Does the community see this direction - a profile-guided, latency-ranked, safety-aware universal software prefetcher - as a useful direction for LLVM to pursue upstream?

2. Patch-series ordering. Is the patch sequence above reviewable as proposed, or should some pieces be split further, reordered, or grouped differently?

3. Pass placement. Our current proposal is to run the new pass from the same pipeline location that currently invokes LoopDataPrefetch; this placement works for both the regular optimization pipeline and LTO. We would still appreciate feedback on this choice.

4. IPO ownership. The complete design includes function-call handling, where address-computation slices may cross call boundaries or require partial inlining of the relevant callee slice. The current implementation does not include this piece yet. Should the pass source live under IPO from the beginning to reflect this future direction, or should the initial upstream version remain organized as a function pass and move toward IPO only when function-call handling is implemented?

5. Replacement plan for LoopDataPrefetch. The new prefetcher is intended to subsume and replace LoopDataPrefetch, with a compatibility mode that mimics the existing static SCEV-based behavior. We would appreciate guidance on transition strategy, default enablement policy, and criteria for retiring or disabling the old pass.

6. Cross-cutting concerns. Anything we should pre-empt or discuss before posting patches rather than discovering only during review.

Thanks in advance for any guidance the community can offer.

[flyahead]

Thanks for sharing this RFC. We are actually exploring a very similar direction internally as well.

Do you have an estimated timeline for when more details of the implementation will be available? We’d be very interested in reviewing the proposal once it is published.

Our goal is to avoid duplicating effort and instead build on top of existing work where possible. If your approach already covers some of the areas we’re investigating, we’d prefer to focus on complementary improvements, validation, and identifying any remaining gaps rather than independently developing a parallel solution.

Looking forward to seeing more details, and thanks again for driving this work.

[SergeyShch01]

Hello @flyahead, thank you for your interest in the proposal.

Actually we didn’t plan to publish extra description of the prefetcher implementation (the detailed description is already published as a part of the full design document).

However if you have additional questions which aren’t covered there we would be happy to answer them here or in a new article.

[snehasish]

Prefetching is very platform-specific. Replacement policies, hardware prefetcher effectiveness, prefetch faulting semantics, and bandwidth-constrained prefetch behavior directly dictate the design and tuning of prefetch insertion (as noted in the RFC). Furthermore, this proposal requires advanced profiling features (e.g., SPE on ARM, PEBS/IBS on Intel and AMD) that are unavailable on all platforms.

Because this introduces a new pass, I recommend implementing it as a generic backend pass. This provides access to target-specific information, allowing -march=XYZ flags to drive thresholds and heuristics. As the safety section notes, using ARM-specific instructions simplifies the heuristic, which reinforces the backend approach.

Moving this implementation to the backend allows it to cleanly co-exist with the current IR pass. Alternatively, if this remains in the IR, it should subsume the current implementation, since it is a subset. What are your thoughts on the tradeoffs for this?

Questions about the implementation

Load profile: How do you rank and prioritize delinquent loads?

Address producing predecessor: How do you handle indirection?

Prefetch distance: What is the metric? How do you measure effectiveness for an inserted prefetch (for example, handling a partial reduction in latency of the target delinquent load)?

Ring buffers: How is this implemented, and what is the size? By design, these must be thread-local, which introduces more overhead per access. How many values are tracked, and how do you ensure the safety of accessing intermediate values (e.g., from pointer indirection)?

Performance notes (for the benchmarks):

1. How many unique software prefetches were inserted?
2. How many unique delinquent load locations are present?
3. Which features from the patch plan (bullets 5-9) were implemented for these benchmarks?

[SergeyShch01]

@snehasish,
Thank you for the thoughtful comments and questions. Please find our answers below. The response is somewhat long, but we hope the examples make the implementation clearer.

Our current implementation uses the following separation. The transformation operates on LLVM IR so that its core remains generic across architectures and can use the richer analysis and transformation infrastructure available at that level, including ScalarEvolution, alias and dependence analysis, and structured loop and control-flow information.
At the same time, the pass is scheduled from the target (AArch64) CodeGen pipeline, in the same way as the existing LoopDataPrefetch pass. Target-specific policy is provided through TTI and subtarget parameters, allowing the selected CPU and target features to control thresholds, cost and distance heuristics, and the available safety mechanisms. Target-specific operations, such as non-faulting loads, are then lowered by the backend.
We believe this separation provides both a target-independent transformation and target-specific configurability. It also allows the new pass to subsume and eventually replace the existing prefetcher, rather than requiring a separate MachinIR implementation.

Load profile: How do you rank and prioritize delinquent loads?

The load profile provides the estimated average memory-access latency for each load. We combine this latency with execution hotness derived from the branch profile. We also consider the L1 hit probability separately: loads with a high L1 hit rate receive a stricter profitability budget. These metrics form the basis for candidate selection and prioritization.

Address producing predecessor: How do you handle indirection?

We handle indirection by cloning the complete data-flow and control-flow slice that produces the target address, including intermediate loads. If an intermediate load is itself selected for prefetching, we represent it as a predecessor in the prefetch dependency DAG and schedule it farther ahead, so its value is expected to be available in cache before computing the dependent address. This is applied recursively to support multi-level indirection.
Here’s an example for clarity:

// Original loop: accesses to f[], b[], e[], d[] miss cache
for (i = 0; i < N; i++) 
    a += f[c[i] & 1 ? b[e[c[i]]] : d[c[i]]];

// -------------------------------------------------------

// Prefetching pipeline: each prerequisite stage is issued D iterations earlier than its dependent stage (the same own prefetching distance is used for all delinquent loads for simplicity in this example) 
for (i = 0; i < N; i++) {
    if (i+D < N) {
       prefetch(&f[c[i+D] & 1 ? b[e[c[i+D]]] : d[c[i+D]]]) ;         // stage #3
       if (i+2 * D < N) {
          prefetch(c[i+2*D] & 1 ? &b[e[c[i+2*D]]] : &d[c[i+2*D]]);   // stage #2
          if (i+3*D < N && c[i+3*D] & 1)
             prefetch(&e[c[i+3*D]]);                                 // stage #1  
       }
    }
    a += f[c[i] & 1 ? b[e[c[i]]] : d[c[i]]];    // targeted demand accesses are expected to hit after the pipeline warm-up
 }

Prefetch distance

Prefetch distance is measured in loop iterations. For each prefetch candidate, the desired distance is proportional to its profiled average memory-access latency divided by the profile-weighted dynamic instruction count per loop iteration, which is used as a proxy for iteration execution time. The distance limit is derived from the estimated trip count together with target-specific coefficients and limits.
For profitability, the scheduler first estimates the maximum allowable prefetch overhead assuming the full desired distance. It then scales this budget down to account for factors that reduce the expected benefit, including cold execution paths, small loops, uncovered initial iterations, and a selected distance shorter than the desired one. Consequently, a shorter-distance prefetch is accepted only under a stricter overhead threshold, accounting for partial latency hiding.
At present, actual effectiveness of prefetching is evaluated only from the resulting application performance. The current tuning was performed using a single profile-and-compile iteration; iterative feedback based on re-profiling the transformed binary is not currently used, but could be explored in the future.

Ring buffers

Ring buffers are used only when semantic hoisting moves an original SSA-producing instruction into an earlier prefetch stage. One buffer is created for each moved value that must be consumed at a later stage or in the original loop body. If the value is produced at distance Ddef and its minimum consumer distance is Duse, the buffer contains the smallest power-of-two number of slots greater than or equal to Ddef - Duse + 1. The buffers are packed into stack allocations in the function entry block, making them private to each function invocation and therefore thread-safe. The number of tracked values is determined statically for each loop and is not fixed, while the maximum ring-buffer storage is controlled by th option, which defaults to 32 KiB. If this limit is exceeded, the least profitable semantic-hoisting candidates are removed and scheduling is repeated.
The spill, fill, and indexing overhead is included in the profitability model. The most interesting cases for semantic hoisting are large or costly DFG subgraphs whose results contribute only to the target load’s address-calculation slice. Such cases are relatively uncommon, so ring buffers are not emitted frequently; however, when applicable, moving the subgraph instead of duplicating it can provide a substantial gain.
Ring indices are derived from a loop induction variable and masked by the power-of-two buffer size. A spin-up loop initializes the entries required by the first main-loop iterations. Safety of intermediate pointer-producing values is ensured by the mechanisms described in the RFC’s Safety section. If an intermediate load cannot be semantically relocated, the original load remains in place; the result of its speculative copy may still be reused by another prefetch stage, but it is not used to replace the original load.

Here’s an example for clarity:

// Original loop: accesses to b[] miss cache
 for (i = 0; i < N; i++) 
    a += b[c[i] + d[i] % M];

// -------------------------------------------------------

// Calculate b[] indices once and store them in the ring buffer for reuse
uint64_t temp[SIZE];                  // SIZE=2^N >= (D+1)
for (j = 0; j < min(D, N); j++) 
    temp[j] = c[j] + d[j] % M;

for (i = 0; i < N; i++) {
    if (i + D < N) {
         uint64_t idx = c[i + D] + d[i + D] % M; 
         prefetch(&b[idx]);
         temp[(i + D) & (SIZE - 1)] = idx;
    }
    a += b[temp[i & (SIZE - 1)]];     // targeted demand accesses are expected to hit after the pipeline warm-up
}

Performance notes

graph500/bfs
The measured BFS kernel contains a loop with a profiled average trip count of 32 and an average of 13 dynamic instructions per iteration. It contains one delinquent load with a profiled memory-access latency of 410 cycles. The prefetch address-calculation slice has an estimated cost of six instructions and is cloned for the iteration 16 iterations ahead. One static software prefetch is inserted. Of patch-plan items #5–#9, only #6 is exercised.

gapbs/sssp
The measured SSSP kernel contains a loop with a profiled average trip count of 7373 and an average of 377 dynamic instructions per iteration. It contains two delinquent loads with profiled memory-access latencies of 466 and 1106 cycles. The loads are dependent through control flow (the first one contributes to the predicate of the second one), so the scheduler places the dependent prefetch at distance 3 and its predecessor at distance 4. The two prefetch address-calculation slices have estimated costs of 7 and 16 instructions, respectively. Two static software prefetches are inserted in the measured kernel. This case exercises patch-plan items #5, #6, and #7.

gapbs/bc
The measured BC kernel contains four loops with seven unique delinquent load locations:
• The PBFS frontier loop has a profiled average trip count of 41,287 and 905 dynamic instructions per iteration. Its adjacency-index load has a profiled memory-access latency of 955 cycles and an estimated prefetch address-calculation slice size of 4 instructions. The prefetch is inserted at distance 1.
• The PBFS neighbor loop has an average trip count of 64 and 14 dynamic instructions per iteration. The depths[v] and path_counts[v] loads have latencies of 230 and 487 cycles and estimatedprefetch address-calculation slice sizes of 3 and 12 instructions, respectively. Both candidates are rejected by the profitability model.
• The reverse-propagation vertex loop has an average trip count of 41,188 and 847 dynamic instructions per iteration. Its adjacency-index and scores[u] loads have latencies of 936 and 847 cycles and prefetch address-calculation slice sizes of 4 and 3 instructions, respectively. Both prefetches are inserted at distance 1.
• The reverse-propagation neighbor loop has an average trip count of 64 and 13 dynamic instructions per iteration. Its deltas[v] and path_counts[v] loads have latencies of 563 and 791 cycles; both have an estimated prefetch address-calculation slice size of 11 instructions. Both candidates are rejected by the profitability model.
Thus, three unique static software prefetches are inserted for three of the seven delinquent load locations. From patch-plan items #5–#9, only #6 is exercised.

hashjoin/ph2
The hash-table build loop has a profiled average trip count of 8,000 and 19 dynamic instructions per iteration. It contains the benchmark’s only delinquent load, the bucket-occupancy load, with a profiled memory-access latency of 1,184 cycles and an estimated prefetch address-calculation slice size of 13 instructions. One software prefetch is inserted at distance 74. This case exercises patch-plan items #6 and #7.

[snehasish]

Thanks for the details in your response! Overall I’m in favor of having a profile guided prefetching implementation that we can enhance over time. However, I am skeptical that the utility may not extend beyond simple kernels due to limitations of LLVM’s analysis, the complexity of larger workloads and rigid nature of software prefetches (unlike hardware prefetchers). It would be great to demonstrate the utility of this on a workload such as a database or SPEC2017 though for the latter hardware prefetchers are well-tuned so ymmv.

Some follow ups below –

the pass is scheduled from the target (AArch64) CodeGen pipeline, in the same way as the existing LoopDataPrefetch pass.

Makes sense to me.

We handle indirection by cloning the complete data-flow and control-flow slice that produces the target address, including intermediate loads.

Does this mean you need to prove that loop iterations are independent? Loop data dependence analysis becomes a bottleneck along with alias analysis. I’ve had some luck with polyhedral analysis before but that comes with it’s own set of caveats.

Another concern is how do you handle profile information updates for the cloned code? In particular I’m wondering about poor interactions with profile driven code layout. Since the benchmarks are simple kernels, the negative impact of poor layout may not manifest in a measurable manner.

The spill, fill, and indexing overhead is included in the profitability model.

Can you share more details about the cost model?

[SergeyShch01]

@snehasish,
Thank you for new interesting questions.

However, I am skeptical that the utility may not extend beyond simple kernels due to limitations of LLVM’s analysis, the complexity of larger workloads and rigid nature of software prefetches (unlike hardware prefetchers). It would be great to demonstrate the utility of this on a workload such as a database or SPEC2017 though for the latter hardware prefetchers are well-tuned so ymmv.

This is a fair concern, and broader evaluation would be useful. However, prefetch applicability is determined at the level of an individual hot loop rather than by the complexity of the complete workload. The main factors are the hotness and memory-access latency of its delinquent loads, the complexity and cost of their address-producing slices, trip count, achievable distance, and generated overhead.
Even when these primary indicators appear favorable, additional limiting factors may apply. The most common one we observed is excessive miss density: when a loop has many cache-missing loads relative to its computation, it is likely limited by memory-system throughput - bandwidth, outstanding-request queues, or other concurrency resources. Additional prefetches would then compete with demand accesses, so the current heuristic filters such loops.
It should also be considered that, as noted in the RFC, the implementation is not yet complete. Therefore, some potentially profitable cases may remain uncovered by the currently implemented mechanisms. Thus, both kernels and complete workloads can contain loops where prefetching helps and loops where it does not. On the other hand, kernels are naturally easier sources of illustrative examples because their hot execution and relevant dynamic events are concentrated in a small region of code rather than spread across the entire application.

We would of course prefer LLVM’s analyses to be as precise and powerful as possible. For ordinary clone-based prefetching, however, limited analysis precision is primarily a performance limitation rather than a semantic blocker. The generated prefetch computation does not contribute values to the original demand computation, so it may operate on stale or otherwise incorrect data and issue a useless prefetch without affecting program semantics, provided that it cannot fault or introduce observable side effects. Fault avoidance is handled explicitly by the dedicated safety mechanisms described below. Semantic hoisting is treated more strictly because values produced by prefetch stages may replace original computations.

Software prefetches are indeed less flexible once compiled. However, sample-based profiling provides a path toward adapting them to current application behavior: low-overhead profiles can be collected during normal production execution, and an ideal deployment model could periodically reprofile and recompile the application in the background as its behavior changes. This iterative model is a possible future extension rather than part of the current implementation. Hardware and software prefetchers have different strengths and weaknesses, but in the proposed approach they are complementary rather than competing mechanisms. The profile reflects execution with the hardware prefetcher operating, so software prefetching targets loads that remain delinquent despite it - typically accesses that hardware cannot predict from memory streams alone. Hardware prefetching handles the patterns it recognizes dynamically, while software prefetching uses program data-flow and control-flow information to cover the remaining cases.

We examined broader workloads, including SPEC CPU2017 on NVIDIA Grace CPUs. In the SPEC benchmarks we evaluated, we did not find hot, non-recurrent delinquent loads with a sufficiently large performance contribution. This is consistent with your observation about well-tuned hardware prefetchers.
We also examined several database cases. A common pattern was a delinquent load whose address-producing slice itself contained a loop, often involving a volatile or atomic load. Inner loops in address-producing slices are not yet supported by the current implementation. Moreover, speculatively cloning volatile or atomic loads cannot generally be assumed to be semantically invisible and may introduce observable effects, so supporting these cases requires a separate safety and design discussion. They therefore remain potentially profitable but currently uncovered cases.

Does this mean you need to prove that loop iterations are independent?

We do not require a global proof that all loop iterations are independent. LLVM alias and dependence analyses are used as one method of static disambiguation, limited to memory operations relevant to the address-producing slice.
If static disambiguation is inconclusive, this does not necessarily cause immediate rejection. This is possible because ordinary prefetch code carries no semantic value: it is purely a performance feature and does not feed the original demand computation. Therefore, operating on stale or incorrect data may make a prefetch ineffective but does not change program results, provided that the speculative code cannot fault or introduce observable side effects.
Dynamic disambiguation, such as loop versioning with runtime alias checks, may be used; alternatively, faults can be suppressed through operand sanitization or a non-faulting instruction variant. When applicable, these mechanisms turn what would otherwise be a semantic obstacle into additional runtime overhead. That overhead is included in profitability estimation and may indirectly cause rejection if the prefetch becomes too expensive. Sanitization and non-faulting loads are currently implemented, while loop versioning remains part of the planned design. Semantic hoisting is handled more conservatively because its values may replace original computations.

Here’s an example of operand sanitization:

 uint32_t *c = malloc(CSIZE * 4);
 uint32_t *d = malloc(DSIZE * 4); 
 // accesses to b[] miss cache
 for (i = 0; i < N; i++) {
    a += b[c[d[i]]];
    if (f[i]) *ptr = e[i];         // may alias with c[] and d[]
 }
--------------------------------------------------------------
// Sanitization: clamp address of unsafe load to safe bounds
for (i = 0; i < N; i++) {
    if (i + D < N) {
        uint32_t d_val = d[i + D]; // can be incorrect!
        uint32_t c_val = c[(d_val < CSIZE) ? d_val : 0]; // always safe
        prefetch(&b[c_val]) ;     // can be imprecise but safe
    }
    a += b[c[d[i]]];                    
    if (f[i]) *ptr = e[i];     
}

Another concern is how do you handle profile information updates for the cloned code? In particular I’m wondering about poor interactions with profile driven code layout.

Profile metadata is preserved automatically for instructions created through LLVM’s cloning interface, and we propagate the original branch weights to the corresponding branches when reconstructing the cloned control flow. The profile metadata of the original code remains unchanged.
The amount of duplicated code is also typically small at the scale of the complete application. Prefetch code is generated only for the small number of profile-selected delinquent loads, and the profitability model rejects address-producing slices whose cloning cost exceeds the per-load or aggregate overhead budget. We therefore expect the whole-program layout impact to be limited.

Can you share more details about the cost model?

The cost model is deliberately straightforward. For each candidate prefetch, it estimates the transformation overhead in terms of the cost of the added instructions. This includes clones in the address-producing slice, the prefetch instruction itself, safety guards or sanitization, recurrence and spin-up work, and ring-buffer operations. If semantic hoisting removes computation from the original loop, the corresponding cost reduction is credited.
This estimated overhead is compared with the maximum affordable cost derived from the loop and load profiles. The scheduler progressively reduces the prefetch distance until the estimated cost fits the budget; if no feasible distance fits, the prefetch is rejected. The aggregate cost of all selected prefetches is then checked, with the least profitable ones removed.

[snehasish]

@SergeyShch01

However, prefetch applicability is determined at the level of an individual hot loop rather than by the complexity of the complete workload. The main factors are the hotness and memory-access latency of its delinquent loads, the complexity and cost of their address-producing slices, trip count, achievable distance, and generated overhead.

I agree with this in principle, but for net performance wins on larger workloads we have to consider the global optimum particularly since software prefetches once inserted cannot be changed. In practice I’ve found that in the scenarios where profile guided optimizations are useful - large benchmarks, frequently changing code - localized decisions for prefetching performs poorly. On smaller kernels, it is easier to take the insight from the tooling and make source modifications instead of incurring the overhead of maintaining the infrastructure.