Forwarding and Stalls: Paying for Dependencies
When one instruction needs another's result, the hardware has two options: route the value directly to where it is needed, or wait. Forwarding covers most cases at no cost. The case it cannot cover — a load feeding the very next instruction — is the shape of every serious memory performance problem.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Forwarding: the value before it is filed
Consider ADD r1, r2, r3 followed by ADD r4, r1, r5. The second instruction needs r1. Naively it would read the register file, but the first instruction has not written r1 yet — it is still in the pipeline.
The fix is a direct wire. The ALU's output is routed back to the ALU's input for the following cycle, so the second add receives the value as soon as it is computed, before it is architecturally written. The register file write still happens; it just is not on the critical path.
With a full forwarding network, back-to-back dependent arithmetic runs without any stall at all. This is why dependency chains of simple arithmetic are limited by *operation latency* rather than by pipeline structure — the machinery to avoid structural delay is already there, and what remains is the irreducible time the operation takes (Execute: Not All Operations Cost the Same).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| I1 ADD r1, r2, r3 | I | I | E | M | W | ||
| I2 ADD r4, r1, r5 | I | I | E | M | W | ||
| I3 SUB r6, r4, r7 | I | I | E | M | W |
The case forwarding cannot fix
Now consider LOAD r1, [r9] followed immediately by ADD r4, r1, r5. The consumer needs r1 one cycle after the load enters execute — but the load does not *have* the value until the cache responds, which in this model is the MEM stage.
There is nothing to forward. The value does not exist. The consumer must stall until it does. On an L1 hit this is a single-cycle bubble — small, and on an out-of-order core usually filled by other independent work. This is the origin of the compiler heuristic of scheduling a load one or two instructions before its use.
On a cache miss the same structure costs hundreds of cycles instead of one. And when the loaded value is *itself the address of the next load*, the machine cannot even begin the next access until this one completes. That is Pointer Chasing: The Address You Do Not Have Yet: a chain of load-use dependencies where every mechanism the CPU has for hiding latency is simultaneously defeated, because there is nothing independent to run and nothing to prefetch.
1node = head;2while (node) {3 sum += node->value;4 node = node->next; // address of next load5} // depends on THIS load's result6// Nothing can be prefetched. Nothing independent to overlap.7// Every iteration pays full memory latency, serially.1for (i = 0; i < n; i++) {2 sum += values[i]; // address is base + i*size3} // computable without loading anything4// The prefetcher can run ahead; several loads are in flight5// at once; latency overlaps instead of accumulating.Both traverse n elements and do n additions. The difference is entirely whether the address of the next access depends on the result of the current one. In the array version the CPU knows every future address immediately and can have many loads outstanding; in the list version it can have exactly one. This single structural property, not the instruction count, is why the two differ so much in practice.
What this means for how you write loops
The actionable rule is short: prefer dependencies the machine can see through. Arithmetic dependencies are cheap because forwarding handles them. Address dependencies are expensive because they serialise memory access. Restructuring data so that addresses are computable rather than loaded is the single highest-leverage change available in this whole area, and it is what Both Are O(n). One Is Far Slower. is really about.
The second rule is to give the machine independent work near expensive operations. An out-of-order core stalls only when it runs out of things to do; a load-use pair with fifty independent instructions around it costs nothing at all. This is why unrolling and multiple accumulators help — not because they reduce work, but because they supply overlap.
The honest limit: on an in-order core (many embedded and some efficiency cores) none of this hiding happens, and every stall is paid in full. Code tuned for a big out-of-order core can behave quite differently there, which is a specific and common instance of ISA vs Microarchitecture: The Distinction Everything Depends On mattering more than the ISA.
| Dependency shape | Handled by | Typical cost |
|---|---|---|
| Arithmetic result → arithmetic operand | Forwarding | None beyond the operation's own latency |
| Load result → arithmetic operand (cache hit) | Short stall, hidden if independent work exists | Small |
| Load result → arithmetic operand (cache miss) | Out-of-order execution, if there is other work | Large; hidden only with real parallelism |
| Load result → address of next load | Nothing — fundamentally serial | Full memory latency per link, every time |
Key points
- Forwarding routes a result directly from producer to consumer, making back-to-back arithmetic dependencies essentially free.
- Load-use dependencies cannot be forwarded away, because the value does not exist until the cache responds.
- A one-cycle load-use bubble on a hit becomes hundreds of cycles on a miss.
- When a load's result is the next load's address, latency serialises and every latency-hiding mechanism fails at once.
- The lever is data structure, not instruction selection: make addresses computable rather than loaded.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Producer EX → forwarding network: the result is made available on a bypass path in the cycle it is computed.
- 2Forwarding network → consumer EX: the dependent instruction reads the operand from the bypass instead of the register file.
- 3Load → cache lookup: for a load, the value is unavailable until the data cache responds, so no bypass path can supply it early.
- 4Consumer → stall: the dependent instruction waits, inserting a bubble; an out-of-order core fills it with independent work if any exists.
- 5Load result → next address: when the loaded value is the next access's address, no subsequent load can even be issued until it returns.
- • "Dependencies are always expensive" — forwarding makes arithmetic dependencies free; only memory dependencies really cost.
- • "A cache miss costs the same wherever it appears" — a miss with independent work around it can be almost fully hidden; one in a dependent chain cannot be hidden at all.
- • "Both are O(n), so they perform similarly" — the array and list traversals differ in whether latency overlaps, which is not visible in the complexity.
Consequences, controls and cost
- • Chained arithmetic runs at operation latency, not at pipeline-structure cost.
- • Pointer-based traversals run at memory latency per element and do not benefit from wider or faster cores.
- • Loops with a load immediately followed by its use lose throughput on in-order cores, where nothing hides the bubble.
- • Restructure data so addresses are computed rather than loaded — contiguous arrays over pointer graphs where the access pattern allows.
- • Separate a load from its use by unrolling or interleaving, giving the machine independent work to overlap.
- • Where a pointer structure is required, consider storing indices into a contiguous array instead of raw pointers, keeping locality while preserving the shape.
- • On out-of-order cores, ensure there is genuinely independent work available; the hardware can only hide latency it has something to hide it with.
- • Compare an array traversal against a pointer traversal over the same data volume; the ratio measures how much latency your machine was able to hide.
- • Read cache miss counters alongside IPC — many misses with low IPC and no branch misses is the pointer-chasing signature.
- • Where available, read a counter for outstanding memory requests; a value pinned near one indicates a serialised chain rather than parallel misses.
- • Converting pointer structures to index-based contiguous ones costs flexibility in insertion and deletion, which may be the reason the structure was chosen.
- • Unrolling to separate loads from uses costs code size and can hurt the instruction cache.
- • These optimisations assume an out-of-order core with real memory-level parallelism; on small in-order cores the payoff differs substantially.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDThe one-cycle load-use penalty comes from the five-stage model. Real cores have deeper load pipelines and longer penalties, which out-of-order execution frequently hides; in-order cores pay them in full.
- MICROARCH-SPECIFICHow many outstanding misses a core supports determines how much of a chain's latency can overlap; this differs per design and is the difference between a costly array traversal and a cheap one.