Data Hazards: Stalling and Forwarding

PIPE keeps five instructions in flight, and that overlap creates its first hard problem. In SEQ each instruction finished (wrote its result into the register file) before the next one read its operands. In PIPE the next instruction reads its operands in Decode while the earlier one is still grinding through Execute or Memory, before it has written anything back. If the later instruction needs the value the earlier one is producing, it reads a stale register. This is a data hazard, and handling it is what separates a pipeline that is fast from one that is merely wrong.

The read-after-write hazard

Consider two Y86-64 instructions where the second uses what the first produces.

irmovq $10, %rax      # rax <- 10
addq   %rax, %rbx     # rbx <- rbx + rax   (reads rax)

The addq reads %rax in its Decode stage. But irmovq does not write %rax into the register file until its own write-back stage, several cycles later. Lay the two on the pipeline diagram and the conflict is geometric: the Decode that reads happens earlier in time than the write-back that writes.

The addq reads %rax in cycle 3 but irmovq writes it in cycle 5: the value is needed two cycles before the register file holds it. Something must give.

Which pairs are dangerous: the hazard taxonomy

Before fixing anything, map the problem's exact extent. Two questions decide whether a pair of instructions collides: who writes and reads registers, and how far apart they sit.

The writers are every instruction with a destination: OPq, rrmovq, irmovq, and cmovXX write a computed value through register port E; mrmovq and popq write a loaded value through port M; and pushq, popq, call, ret update %rsp through port E. The readers are every instruction that consumes register values in Decode: OPq, rrmovq, rmmovq, mrmovq, pushq read rA and/or rB, and the stack instructions read %rsp. Condition codes create no hazard at all: they are written in Execute and read in Execute, so a jump following an OPq always sees fresh codes one cycle later. The register file is the only point of conflict.

Distance is the sharper axis. The register file is written on the rising clock edge that ends the producer's write-back cycle, so a consumer's Decode read is safe only if it happens in a strictly later cycle. Count it out: a producer fetched in cycle 1 writes back in cycle 5; a consumer at distance $d$ decodes in cycle $d+2$. The read is safe when $d+2>5$, that is $d\ge 4$. Distances 1 through 3 are all hazardous, and each one leaves the needed value in a different place:

The table is the lesson's skeleton: every fix must cover exactly rows 1-3, and row 3 is a genuine hazard even though producer and consumer overlap in only one cycle — a Decode read concurrent with the write-back still sees the old value, because the write lands on the edge that ends the cycle.

Fix 1: stall (inject bubbles)

The blunt fix is to make the pipeline wait. Detection is cheap: the decode logic compares its source IDs d_srcA, d_srcB against the destination IDs of the instructions in Execute, Memory, and Write-back. On a match, the control logic holds the F and D registers in place (the consumer re-reads the register file each cycle) and injects a bubble into E so the stages ahead have harmless work.

Count the cost carefully, because the naive count is off by one. irmovq writes back in cycle 5, but a cycle-5 Decode still reads stale data; the first good read is cycle 6. So addq sits in Decode for cycles 3 through 6 and three bubbles flow through the pipeline, the same effect as the compiler inserting three nops between the two instructions. A third-of-the-pipeline penalty for one dependency, and adjacent dependent instructions are the most common pattern in compiled code. Stalling is always correct, but as the only tool it would erase most of pipelining's gain. We can do far better by noticing the value is not actually missing; it is just in the wrong place.

Fix 2: forward (bypass)

The value addq needs already exists inside the processor by cycle 3: the ALU computes it during that very cycle. It just has not made the round trip through the register file. Forwarding (bypassing) adds wires that route such values straight back to Decode, skipping the register file entirely.

Timing makes this legal: Decode only has to deliver valA/valB by the end of its cycle, when the E register latches, and the ALU output settles well before that. Nothing about the clock changes; the value simply takes a wire instead of a detour.

One path is not enough, though. The taxonomy said the needed value can be in three different places, and values come in two kinds (computed valE, loaded valM), so PIPE wires five forwarding sources into Decode:

Decode's two selection blocks (Sel+Fwd A for valA, Fwd B for valB) compare d_srcA and d_srcB against each source's destination ID and pick the first match; only if nothing matches do they fall through to the register-file read. In HCL, for valA:

word d_valA = [
    D_icode in { ICALL, IJXX } : D_valP;  # incremented PC, merged into valA
    d_srcA == e_dstE : e_valE;            # forward valE from execute
    d_srcA == M_dstM : m_valM;            # forward valM from memory
    d_srcA == M_dstE : M_valE;            # forward valE from memory
    d_srcA == W_dstM : W_valM;            # forward valM from write back
    d_srcA == W_dstE : W_valE;            # forward valE from write back
    1 : d_rvalA;                          # use value read from register file
];

With these five paths, every RAW hazard in the taxonomy is covered with zero stall cycles — except one case, coming below.

A worked trace: three distances at once

One program can carry all three hazard distances against a single producer, and tracing it shows each forwarding source firing in turn. Here irmovq writes %rax in cycle 5, and three later instructions each read it at a different distance:

irmovq $7, %rax      # I1: writes rax (write-back in cycle 5)
addq   %rax, %rbx    # I2: distance 1
subq   %rax, %rcx    # I3: distance 2
andq   %rax, %rdx    # I4: distance 3

Walk the cycles. I2 decodes in cycle 3, when I1 is in Execute; the ALU output e_valE forwards straight down. I3 decodes in cycle 4, when I1 has moved to Memory; its result now sits in the M register as M_valE. I4 decodes in cycle 5, the same cycle I1 writes back; the value is in the W register as W_valE, and forwarding beats the register-file read (which would still be stale until the edge ends the cycle). Three consumers, three different sources, and the pipeline never stalls — every value was already inside the machine, just never in the register file yet.

Why the priority order matters

The HCL cases are tested top to bottom, and that order matters. Several instructions ahead of the consumer may all be writing the same register, one pending in each stage:

irmovq $10, %rdx     # older write to rdx
irmovq $3,  %rdx     # newer write to rdx
rrmovq %rdx, %rax    # must read 3, not 10

When rrmovq decodes in cycle 4, two pending writes to %rdx are in flight: the first irmovq is in Memory holding 10, the second in Execute computing 3. Sequential semantics is unambiguous (executed one at a time, rrmovq reads the most recent write, 3), so the forwarding logic must prefer the source from the earliest pipeline stage, which holds the latest instruction in program order. Execute beats Memory beats Write-back.

Swap any two cases in the HCL and some program breaks. If Memory were checked before Execute, rrmovq here would read 10, a value the ISA says was already overwritten. The within-stage order matters too: m_valM before M_valE because popq %rsp writes both ports at once and the ISA defines its result as the loaded value. Forwarding priority is one of those details that simulation rarely catches (the buggy order runs most programs correctly) and systematic analysis catches immediately — reason it out per stage, oldest to newest.

The load-use hazard: forwarding's one gap

Forwarding works whenever the needed value has been computed by the time the consumer's Decode ends. There is exactly one case where it has not: a load followed immediately by an instruction that uses the loaded value.

mrmovq 0(%rcx), %rax    # rax <- M[rcx]   (value read in Memory stage)
addq   %rax, %rbx       # uses rax one instruction later

The loaded value does not exist until mrmovq finishes its Memory stage. But addq reaches Decode one cycle earlier, when mrmovq is only in Execute and the value is not yet read. Forwarding cannot send a value backward in time. The diagram shows the path that would be needed pointing the wrong way:

The fix is a hybrid called a load interlock: stall the consumer for exactly one cycle, then forward. The control logic detects the pattern (a load in Execute whose E_dstM matches d_srcA or d_srcB), holds F and D, and injects a single bubble into E. Now addq decodes in cycle 4, when mrmovq is in its Memory stage and m_valM is available to forward. One stall, not three: the minimum the dependency forces.

Load interlocks plus forwarding handle every data hazard PIPE can encounter, and only the interlock costs anything. This single unavoidable stall is why compilers schedule a useful, independent instruction into the slot right after a load when they can, turning the mandatory bubble into real work.

Executing around the hazard

PIPE's answer to a load-use hazard is to stall: the consumer waits one cycle in Decode while the whole pipeline behind it freezes. That is correct but blunt — the frozen cycle is wasted even if there is other, independent work the processor could have done meanwhile. Out-of-order (dynamically scheduled) processors do not waste it. Instead of stalling the consumer and everything behind it, they let the stalled instruction step aside and run any later instruction whose operands are ready.

The mechanism is Tomasulo's algorithm (Tomasulo, 1967, IBM Journal of Research and Development), first shipped in the IBM System/360 Model 91's floating-point unit and standard in performance cores today. Decoded instructions wait in reservation stations rather than a rigid pipeline slot; each station holds an instruction and tags for the operands it still needs. When a functional unit produces a result, it broadcasts the value with its tag on a common data bus, and every waiting station listening for that tag grabs it at once — a forwarding network generalized from PIPE's five fixed wires to a fully associative match. An instruction fires the cycle its last operand arrives, regardless of program order, so a load miss no longer freezes the machine: independent instructions sail past the waiting consumer and keep the execution units busy.

The load-use hazard shows the contrast. In PIPE, addq %rax, %rbx after a load of %rax costs one guaranteed bubble. In an out-of-order core, if the instruction stream contains any independent work — and compiled code usually does — that work executes during the load's latency, and the addq fires the moment the loaded value broadcasts, with no idle cycle at all. The catch is enormous hardware cost: reservation stations, the reorder buffer that puts results back in program order, the register renaming from the previous lesson, and the associative wakeup logic. This is why the trade sits where it does — PIPE's in-order stall is a few gates, and dynamic scheduling is a large fraction of a modern core's area and power (Hennessy and Patterson, Computer Architecture: A Quantitative Approach, ch. 3). The principle, though, is a direct descendant of forwarding: route each value to whatever needs it the instant it exists.

Data hazards are about values flowing forward. The next lesson turns to a different break in the flow: not knowing which instruction comes next.