Value Prediction and the Limits of Speculating on Data

Every mechanism in this cluster so far removes an obstacle that is not fundamental: renaming removes name dependencies, the window removes the constraint of issue order, the front end removes supply limits, and checkpoints remove the cost of being wrong about control flow. What none of them removes is the true data dependency. If instruction n adds one to the result of instruction n-1, the machine must wait, and no amount of scheduling helps.

Value prediction proposes to break that too. If the result of an instruction can be guessed before it executes, its dependants can proceed on the guess and the correctness check can happen at the same time. The idea is almost thirty years old and has never reached a general-purpose shipping core, and the reasons are worth understanding because they are about the structure of the problem, not about a lack of effort.

The dataflow limit, precisely

Consider a recurrence: x[i] = x[i-1] + 1 in a loop. The loop’s iterations are independent in every respect except that each needs the previous value. A machine with an infinite window executes them one add at a time, and the throughput limit is the latency of the add, not the width of the machine.

Wall’s analysis of achievable ILP quantified this: even with unbounded resources, the parallelism a program exposes is bounded by its dependency graph’s critical path. For general-purpose integer code the bound is modest; for code with long recurrences it approaches one instruction per latency.

Branch prediction breaks a control dependency by guessing the next address. Value prediction breaks a data dependency by guessing the next value. The analogy is exact in the abstract and breaks in three concrete places.

How a value predictor would work

The mechanism mirrors a branch predictor’s structure. An instruction is identified by its program counter, and a table indexed by that program counter (or by a history of recent values, or by a combination) returns a predicted result. Several predictors have been proposed:

• Last value. Predict that the instruction produces the same value it produced last time. Works for loop counters that change slowly relative to execution, and for constants loaded repeatedly.
• Stride. Predict v + d where d is the last difference, generalizing the last-value scheme to arithmetic sequences.
• Context-based. Index on a history of the values of the instruction’s sources, so the prediction is a function of the inputs rather than of the instruction’s identity.
• Computational. Predict the result of a simple operation from a predicted source value, so a short chain of dependent adds can be covered by predicting only the head.

Verification happens at execution: the functional unit computes the real value, compares it against the prediction, and either confirms or signals a mismatch. Dependants that already consumed the prediction must be replayed, and any whose result already retired must not have retired — so the check must occur before any dependant commits. That constraint has a direct design consequence: verification must be fast, because otherwise the machine commits speculation it cannot undo.

The correctness argument is identical to branch prediction’s: a predictor may be wrong, provided architecture and memory never observe the wrong result. Retirement order and the checkpoint machinery do the rest.

Where it differs from branch prediction

The cost of a wrong guess is larger. A mispredicted branch discards everything younger. A mispredicted value discards every instruction that used the value, which need not be younger in program order — it is younger in the dataflow graph. If the machine has already used the value to compute a store address, the store’s ordering relative to other stores is compromised, and the recovery must handle memory operations, not just registers. Branch misprediction never corrupts the memory ordering machinery, because the branch is a control operation with no data effect.

The verification latency is on the critical path. A branch’s outcome is known when the branch executes, and its dependants’ addresses are already known. A predicted value’s verification depends on the producer’s own operands being available, which for a long chain means the verification is late by construction. It is easy to build a scheme where the predictor is right and the machine is still no faster, because the check could not complete in time for the dependants to be confirmed.

The distribution of values is not the distribution of outcomes. Branch outcomes have strong structure — a small number of patterns repeated — which is why two-level and history-based predictors work so well. Values have enormous dynamic range, and the fraction of instructions whose result is predictable from their identity alone is modest. The classic results on value prediction showed a large fraction of dynamic instructions produce a value that repeats, but the repeats concentrate in a few instruction classes: constants, stack-pointer updates, and a small set of loop counters. The instructions that make up a dependency chain — the ones actually limiting throughput — are the least predictable.

The last point is the fundamental objection. The chain that limits an out-of-order machine is a sequence of data computations, and those are exactly the values least amenable to prediction. Predicting the trivially predictable ones costs hardware and buys nothing, because they were not on the critical path.

The security problem

The more recent obstacle is not about performance. Speculating on data means the machine may compute with values that were never architecturally produced, and any channel that leaks information about the speculation — cache state, branch-predictor state, timing — leaks information about real data. The whole family of attacks that exploit speculative execution applies with more force here, because the speculated quantity is the data rather than an address.

This has moved the design space’s centre of gravity: modern cores add barriers that restrict what may speculate and when, which is the opposite direction from value prediction’s. A feature whose benefit depends on speculating further on data is a feature that a security-motivated design will constrain, and the constraints are architectural (they must hold for existing binaries) rather than microarchitectural hints.

The safer relatives

Three techniques achieve part of value prediction’s effect without guessing at arbitrary values.

Memory renaming / store-to-load forwarding across a window. A load whose address matches a pending store takes the store’s data without accessing the cache, effectively “predicting” the load’s value with certainty. This is not speculation at all, just a correctness-preserving shortcut, and it is what the load-store machinery in Load-Store Ordering and Memory Disambiguation already does. Its benefit is limited by how often a load can be shown to match.

Trace- or slice-based re-execution. Rather than predicting a value, the machine can keep a chain in flight by executing several dependent operations in immediate succession — a chained or “dependency-bypassing” execution unit — reducing the per-link latency without changing semantics. This is a latency optimization, not a speculation, and it is bounded by the unit’s depth.

Software-level parallelization. The compiler breaks a recurrence explicitly: unrolling with multiple accumulators, reassociation under fast-math rules, or transformation to a prefix-sum form. The last is particularly relevant because it converts a linear chain into a logarithmic-depth tree, and it is exact for associative operations. The cost is numerical reassociation, which the source language may not permit.

Each of these attacks the same limit from a direction that does not require the machine to be wrong. The third is the most portable, because it changes the dependency graph rather than the machine: a loop restructured to expose independent iterations fits the existing window better, as the sizing analysis in Sizing the Window: Why More Entries Stop Paying explains — the window’s value comes from the distribution of dependency distances, and shortening those distances is equivalent to enlarging the window for that loop.

A quantitative frame

The trade is simple to state, which is why it is a useful closing subject. Let a dependency chain have per-link latency L and let the predictor’s accuracy be p with a fixed cost C cycles to detect and recover from a misprediction. If the predictor is correct, the chain issues at the machine’s width; if wrong, the chain restarts. The expected throughput per link of a chain whose links each depend on the previous prediction is

$$c = p \cdot 1 + (1 - p) \cdot C$$

cycles per link (a crude model: a correct prediction retires one link per cycle, a wrong one wastes the recovery). For the predictor to beat the unpredicted case of L cycles per link, the requirement is p·1 + (1-p)·C < L, which for a large recovery cost C demands an accuracy very close to one. With C = 15 and L = 3, accuracy must exceed about 0.86; with L = 1 (a single-cycle operation with no prediction benefit at all), the predictor cannot help. This arithmetic is why value prediction research focused on the read-modify-write and load classes where L is large and accuracy is high, rather than on the ALU chains.

def break_even_accuracy(link_latency, recovery_cost):
    """Accuracy p needed for prediction to beat plain execution on a chain."""
    # p + (1 - p) * C < L  =>  p > (C - L) / (C - 1)
    if recovery_cost <= 1 or link_latency >= recovery_cost:
        return 0.0          # chain already no faster than recovery: any accuracy works
    return (recovery_cost - link_latency) / (recovery_cost - 1)

for lat in (1, 2, 3, 5, 10):
    for rec in (5, 15, 40):
        p = break_even_accuracy(lat, rec)
        print(f"L={lat:2d} recovery={rec:2d}: need p > {p:.2f}")

The model’s point is not any particular threshold but the shape: the required accuracy rises toward one as recovery cost grows relative to the chain’s own latency. Since recovery cost in a wide machine grows with the window — more instructions must be invalidated when a value is wrong — the two parameters are coupled in the wrong direction. That coupling is the structural reason value prediction remains a research topic rather than a design feature, and why the mechanisms in this cluster that merely reorder computation have proved durable while those that replace it have not.

Where the real gains remain

The cluster’s mechanisms each removed a specific structural limit and each paid in complexity. The remaining limits are narrower: memory latency that no scheduling can hide, dependency chains that no reordering can shorten, and supply that no width can provide. The techniques that address them are incremental — better prefetching, more accurate predictors, deeper memory-level parallelism, and attempts to expose parallelism at the source level. Value prediction sits at the boundary between reordering and replacing, and no design has crossed that boundary in a way that survives both the accuracy arithmetic and the constraints that speculation now carries.