Control Hazards
A pipelined processor fetches a new instruction every cycle. It does this long before the previous one finishes. This works beautifully until the processor meets a branch. The very next instruction to fetch depends on whether that branch is taken. It also depends on where it goes. But the branch's outcome is not known until it has traveled several stages down the pipeline. Meanwhile the fetch stage has already grabbed instructions from the fall-through path, purely as a guess. This is the control hazard: a hazard not over data values but over the identity of the next instruction. It is distinct from the Data Hazards and Forwarding problem, where the issue is a value not yet computed. It is also distinct from the Stalling and the Load-Use Hazard problem, where a specific known dependency forces a bubble. With control hazards, the processor does not even know which instruction comes next until the branch resolves. So it must either wait, guess, or restructure the pipeline to resolve branches earlier. Control hazards matter because branches are frequent. Roughly one in every five to seven instructions in typical code is a branch. A naive pipeline pays a penalty on every single one. In a five-stage pipeline where a branch resolves in the fourth stage, three wrong instructions may already be in flight. This happens before the mistake is discovered. Multiply that by billions of branches per second. The wasted work becomes a first-order performance problem, not a rare corner case. Understanding exactly when the penalty is paid is essential. So is knowing how many cycles it costs. And so is understanding how flushing repairs the pipeline state. All of this is essential to understanding real processor design. This article builds the mechanism from first principles. It covers how a pipeline detects that it fetched down the wrong path. It explains how flushing squashes the incorrect instructions before they can corrupt architectural state. It also shows how the "resolve early" and "predict and recover" strategies each shape the penalty. It sets up, without yet developing, the idea of Branch Prediction as the technique for cutting this penalty further. It previews how Exceptions and Interrupts reuse the exact same flush machinery to abort in-flight instructions when something goes wrong.
- A control hazard arises because the next instruction to fetch is unknown until a branch resolves.
- Every cycle the pipeline fetches speculatively before resolution is a chance to fetch the wrong instruction.
- Flushing converts wrongly-fetched instructions into no-ops (bubbles) so they cannot alter architectural state.
- The branch penalty equals the number of pipeline stages between fetch and the stage where the branch resolves.
- Moving branch resolution earlier in the pipeline (e.g., decode instead of execute) shrinks the penalty directly.
- These same mechanisms — detect wrong path, squash instructions, redirect fetch — underlie exception handling too.
A control hazard is paid for in flushed instructions, and the penalty is exactly the distance, in pipeline stages, between fetching an instruction and knowing where control flow actually goes.
The idea
A control hazard (also called a branch hazard) occurs when a pipeline cannot determine the address of the next instruction to fetch, because that address depends on the outcome of a branch, jump, or other control-flow instruction still working its way through the pipeline. Contrast this with a data hazard, where the identity of the next instruction is already known — only one of its operand values is missing. With a control hazard, the very fetch target is in question. Two quantities define the severity of a control hazard. The branch resolution stage is the pipeline stage in which the processor first learns definitively whether the branch is taken and, if so, its target address. The branch penalty is the number of cycles of useful work lost when a wrong guess is made — equivalently, the number of pipeline stages between instruction fetch and the resolution stage, since every instruction fetched during that window may need to be discarded.
Flushing (also called squashing) is the mechanism that discards those speculatively fetched instructions. When the branch resolves and the processor discovers it fetched down the wrong path, it converts every in-flight instruction from the wrong path into a pipeline bubble — a no-op that carries no register writes, no memory writes, and no control signals capable of altering architectural state. Flushing must happen at every pipeline stage that currently holds a wrong-path instruction, and it must happen in the same cycle the misprediction is detected, so that no wrong-path instruction is allowed to complete a state-changing action (a register write-back or a store) one cycle later. The simplest strategies for control hazards, in increasing sophistication, are: 1. Stall until resolved — freeze fetch until the branch outcome and target are known, paying the full penalty on every branch, always. 2. Predict not-taken (or a fixed default) and flush on misprediction — keep fetching down the fall-through path; pay the penalty only when the guess was wrong. 3. Resolve earlier in the pipeline — move branch comparison and target computation from a later stage (e.g., Execute) to an earlier one (e.g., Decode), shrinking the penalty for every branch, mispredicted or not. 4. Predict dynamically — use history-based prediction to guess correctly far more often, deferring the deeper mechanics to Branch Prediction. This article focuses on (1)–(3): the mechanics of detection, flushing, and moving resolution earlier — the load-bearing machinery that any predictor in (4) still depends on when it is wrong.
How it works
Consider a classic 5-stage RISC pipeline: IF (Instruction Fetch), ID (Instruction Decode / register read), EX (Execute / branch comparison), MEM (Memory access), WB (Write-back). Suppose branches are resolved in EX, as in an unoptimized MIPS-style design. When a branch instruction is fetched in cycle t, it will not tell the processor its outcome until it has passed through ID (cycle t+1) and reached EX (cycle t+2). Meanwhile, fetch has already speculatively grabbed instructions in cycles t+1 and t+2, guessing (by default) that the branch falls through to the next sequential address. If that guess is wrong, both of those instructions must be flushed — a 2-cycle penalty. If instead the datapath is redesigned so that branch comparison and target-address computation happen in ID (using a dedicated comparator rather than the full ALU, and computing the target with a separate adder in parallel with decode), the branch resolves one cycle earlier. Now only one wrong-path instruction has been fetched by the time the mistake is caught — a 1-cycle penalty. This is precisely the "resolve earlier" strategy, and it is why many real pipelines dedicate extra hardware in decode purely to make branches resolve faster, even though it does no other useful work. The general rule, and the reason the penalty formula holds exactly: ``` branch_penalty (cycles) = (index of resolution stage) − (index of fetch stage) = number of instructions fetched after the branch but before its outcome is known ``` Each of those fetched-but-not-yet-flushed instructions occupies one pipeline stage; when the misprediction is detected, all of them are simultaneously converted to bubbles.
Step-by-step mechanism
``` // Registers between pipeline stages: IF/ID, ID/EX, EX/MEM, MEM/WB // PC = program counter; each stage reads its input latch and writes its output latch every cycle: // ---- IF stage ---- instr = Memory[PC] IF_ID.instr = instr IF_ID.PC = PC if branch_predicted_taken: PC = predicted_target // speculative redirect (default: PC + 4) else: PC = PC + 4 // ---- ID stage ---- decode(IF_ID.instr) read_registers() if IS_BRANCH(IF_ID.instr) and RESOLVE_IN_ID: actual_taken = compare(rs1, rs2) // dedicated comparator actual_target = IF_ID.PC + immediate // dedicated adder if actual_taken != predicted_taken // misprediction detected HERE or actual_target != predicted_target: flush(IF_ID) // squash the one wrong-path instr in IF PC = actual_target if actual_taken else IF_ID.PC + 4 ID_EX.controls = control_signals ID_EX.operands = (rs1_val, rs2_val, ...) // ---- EX stage ---- result = ALU(ID_EX.operands) if IS_BRANCH(ID_EX.instr) and RESOLVE_IN_EX: actual_taken = compare(ID_EX.rs1_val, ID_EX.rs2_val) actual_target = ID_EX.PC + ID_EX.immediate if actual_taken != predicted_taken or actual_target != predicted_target: flush(IF_ID) // squash 2 wrong-path instrs: flush(ID_EX) // one in IF, one in ID PC = actual_target if actual_taken else ID_EX.PC + 4 EX_MEM.result = result // ---- MEM stage ---- access_memory(EX_MEM) MEM_WB.value = ... // ---- WB stage ---- write_register(MEM_WB.value) // flush(latch) sets every control signal in `latch` to a NOP encoding // (RegWrite = 0, MemWrite = 0, MemRead = 0, Branch = 0, ...) // so the instruction currently occupying that latch does no architectural work // as it drains harmlessly through the remaining stages. ``` The crucial correctness property is that `flush` happens in the same cycle the misprediction is discovered, not the next one. A one-cycle delay in flushing would let a wrong-path instruction's write-back (or store) commit — an unrecoverable error, since register files and memory have no notion of "undo."
Complexity & correctness
Time cost. Let the resolution stage be at pipeline depth (counting fetch as stage 1) and let branches be mispredicted with probability . Each misprediction costs exactly bubble cycles, because that many instructions were fetched, one per cycle, before the branch reached stage . If a fraction of all dynamic instructions are branches, the expected cycles-per-instruction (CPI) overhead attributable to control hazards is:
This is exact, not an approximation, given the "flush-on-misprediction" policy: every mispredicted branch injects precisely bubbles, no more (flushing removes exactly the wrong-path instructions already in the pipe) and no fewer (every stage between fetch and resolution necessarily holds a wrong-path instruction the cycle before resolution). If instead the processor always stalls until resolution (strategy 1 above), the cost becomes regardless of prediction accuracy — worse whenever , which is essentially always, so stall-always is strictly dominated once any reasonably-accurate default guess (like "not taken") is available. Reducing (resolving in ID instead of EX) reduces the penalty linearly and unconditionally — it helps on every branch, not just some fraction of them, which is why hardware designers treat "shrink " as a higher-leverage lever than clever prediction for a fixed pipeline depth, even though Branch Prediction ultimately provides the larger wins by reducing .
Space cost. Flushing costs no extra storage: it reuses the existing pipeline latches, merely overwriting their control fields with the NOP encoding. The only added hardware is the comparator/adder needed to resolve branches early (a constant, one-time area cost, independent of program size) — so control-hazard handling adds hardware, not something scaling with instruction count.
Correctness argument. The invariant that must hold at every cycle boundary is: > No instruction that lies on a mispredicted path may perform a state-changing action (register write-back, memory store, or PC redirect) after the misprediction has been detected. Flushing preserves this invariant by construction: the instant a mismatch between predicted and actual outcome is found (comparator output disagrees with the speculative PC choice), every latch currently holding a wrong-path instruction is overwritten with all-zero control signals in that same cycle. Since write-back, memory-write, and register-write enables are themselves control signals, a flushed instruction's `RegWrite`, `MemWrite`, and `Branch` lines are all forced to 0 as it continues (harmlessly) down the pipe. It behaves exactly like a `NOP`, which by definition alters no architectural state. Because this holds independent of which instructions were in flight, the invariant holds by induction over cycles — flushing is applied uniformly whenever a misprediction is detected, regardless of program point, so correctness does not depend on any property of the specific program being run.
Tradeoffs. Resolving branches earlier (in ID) requires duplicate comparison hardware separate from the main ALU, adds decode-stage complexity, and can create new forwarding hazards — if a branch's operand was produced by an instruction still in EX or MEM, ID now needs forwarding paths a cycle earlier than a normal ALU op would, which is more forwarding hardware, not less. Flushing itself is cheap, but every flushed instruction represents fetch bandwidth, decode work, and (in an in-order issue machine) power spent computing something ultimately discarded — a real energy cost even though it costs no extra cycles beyond the stall bound. Deeper pipelines (higher ) make this tradeoff worse, which is one reason very deep pipelines lean heavily on prediction accuracy rather than trying to resolve earlier.
Worked example
Take a 5-stage pipeline (IF, ID, EX, MEM, WB) with branch resolution in EX (so , penalty ), a "predict not-taken" default, and the instruction stream: ``` 100: ADD R1, R2, R3 104: BEQ R1, R0, 200 ; taken (R1 == R0) 108: SUB R4, R5, R6 ; wrong-path (fetched speculatively) 112: OR R7, R8, R9 ; wrong-path (fetched speculatively) 200: LW R10, 0(R11) ; correct target 204: ADDI R12, R10, 1 ``` Cycle-by-cycle:
| Cycle | IF | ID | EX | MEM | WB | Event |
|---|---|---|---|---|---|---|
| 1 | ADD | — | — | — | — | |
| 2 | BEQ | ADD | — | — | — | |
| 3 | SUB (spec.) | BEQ | ADD | — | — | fetched fall-through, guessing not-taken |
| 4 | OR (spec.) | SUB | BEQ | ADD | — | BEQ resolves in EX this cycle: taken, target = 200 |
| 5 | LW (correct) | flush→NOP | flush→NOP | BEQ | ADD | SUB and OR squashed; PC redirected to 200 |
| 6 | ADDI | LW | NOP | NOP | BEQ | pipeline now on correct path |
| 7 | ... | ADDI | LW | NOP | NOP |
`SUB` and `OR` each occupied one pipeline stage (ID and IF respectively) at the moment of resolution in cycle 4; both are converted to bubbles in cycle 5, matching the predicted penalty of cycles exactly. Crucially, `SUB`'s destination register `R4` is never written — its control signals were zeroed before it could reach WB — so architectural state after cycle 8 reflects only `ADD`, `BEQ`, `LW`, `ADDI`, exactly as if the pipeline had somehow known in advance that the branch would be taken. Now compare against resolving in ID (, penalty ): only `SUB` would ever be fetched speculatively; the misprediction would be caught one cycle sooner, `SUB` alone would be flushed, and `LW` would be fetched in cycle 4 instead of cycle 5 — one full cycle saved on this branch, and on every branch in the program, taken or not.
Common pitfalls & traps
| Pitfall | Why it happens | Consequence |
|---|---|---|
| Flushing one cycle too late | Detection and flush treated as separate pipeline stages instead of same-cycle combinational logic | A wrong-path instruction commits a register write or store — unrecoverable corruption |
| Forgetting to flush all in-flight wrong-path instructions | Only squashing the latch nearest fetch, not every stage between fetch and resolution | Deeper-in-pipeline wrong-path instructions slip through when |
| Confusing control hazards with data hazards | Both cause "stalls," so it's tempting to treat them with the same fix | Forwarding solves data hazards but does nothing for an unknown fetch target |
| Ignoring the target address mismatch, only checking taken/not-taken | Branch outcome (T/NT) and branch target are two separate quantities that can each be mispredicted | Indirect branches/jumps mispredict target even when "taken" was guessed correctly |
| Assuming penalty is fixed regardless of resolution stage | Treating "branch penalty = 2 cycles" as a hardware constant rather than | Wrong performance model when redesigning pipeline depth or moving resolution to ID |
Pioneers & history
The control hazard problem became a first-class design concern the moment pipelining moved from an academic idea to production silicon, because every pipelined machine has to decide, concretely, what to do about branches.
Origins · 1 minJohn L. Hennessy and how this was discovered
Where this matters
Every general-purpose CPU shipped today — from microcontrollers to server-class superscalar cores — implements some version of flush-on-misprediction, because it is the only mechanism that keeps pipelined execution correct under speculation. RISC-V, ARM, and x86 implementations all include dedicated hardware to detect branch mispredictions and squash in-flight instructions in the same cycle, even though their prediction strategies differ enormously in sophistication. Compilers exploit knowledge of the branch penalty directly: profile-guided optimization arranges "likely" code paths to fall through rather than jump, minimizing the chance of paying the penalty, and some ISAs historically exposed "delay slots" so the compiler could fill the penalty cycles with useful, non-speculative work instead of a wasted bubble. The flush mechanism itself is not limited to branches. Exactly the same squash-in-flight-instructions logic is reused whenever an exception or interrupt fires mid-pipeline: instructions younger than the faulting one must be discarded before they can commit, using the identical "zero the control signals in every affected latch, this cycle" technique developed for control hazards. Understanding control hazards is therefore a prerequisite not just for reasoning about branch performance, but for understanding precise exceptions, speculative execution more broadly, and the security-relevant machinery (e.g., protecting against speculative side-channel attacks) built on top of it.
Ask the tutor: How does dynamic branch prediction reduce the misprediction rate enough to make deep pipelines practical?
Is a control hazard the same thing as a branch misprediction?
Not quite. The control hazard is the structural problem — the pipeline doesn't know the next instruction's address until the branch resolves — which exists on every branch, taken or not, correctly guessed or not. A branch misprediction is the specific event where the guess made during that hazard turns out wrong. Even a correctly predicted branch still involved a control hazard in the sense that fetch had to guess; it just happened to guess right, so no flush was needed and no penalty was paid that cycle. The hazard is the risk; the misprediction is the realization of that risk.
Why not just always stall until every branch resolves, avoiding flush logic entirely?
Stalling always pays the branch penalty on every branch, whereas predict-and-flush only pays it on mispredicted branches. Since even a naive static predictor like "predict not-taken" is correct well over half the time in typical code, and modern dynamic predictors exceed 90–95% accuracy, flush-based speculation is strictly better in expectation. The cost is added complexity (detection logic, flush signals, redirect wiring) but that one-time hardware cost is paid once, while the stall-always penalty is paid on every single branch execution for the life of the program.
Does flushing waste power as well as cycles?
Yes. A flushed instruction still occupied fetch bandwidth, was decoded, and in many pipelines began executing before being squashed — all of that work consumes dynamic power for zero architectural benefit. This is one reason branch prediction accuracy matters even in embedded and mobile designs where cycle counts alone might seem tolerable: every misprediction is wasted energy, not just wasted time, which is why low-power cores still invest transistor budget in reasonably good predictors rather than accepting a simple stall-always policy.
How does delayed branching relate to control hazards?
Some early RISC ISAs (classic MIPS, SPARC) defined one or more "delay slots": instructions immediately after a branch that always execute, regardless of whether the branch is taken. The compiler tries to fill these slots with useful, branch-independent work, effectively hiding part of the penalty rather than wasting it on a flushed bubble. This only works when the penalty is small and fixed (typically one slot for a one-cycle-penalty pipeline); it becomes impractical as pipelines deepen and penalties grow, which is part of why modern deep-pipeline ISAs abandoned delay slots in favor of aggressive dynamic prediction instead.
Can control hazards be eliminated entirely rather than just mitigated?
Not without eliminating pipelining's core benefit or eliminating conditional control flow, neither of which is realistic. Any pipeline that overlaps fetch of instruction with earlier stages of instruction faces this hazard whenever instruction is a branch, because the fetch decision for must be made before 's outcome exists. What can be eliminated is the penalty, asymptotically, by predicting so accurately that mispredictions become vanishingly rare — the direction pursued by modern Branch Prediction hardware — but the structural hazard itself is inherent to pipelining, not a solvable bug.
How does this connect to precise exceptions?
Precise exception handling requires that, at the moment an exception is reported, all instructions before the faulting one have completed and none after it have altered state. That is exactly the invariant flushing already maintains for control hazards — discard/no-op every instruction that shouldn't have been allowed to commit. When an exception (e.g., a page fault or illegal instruction) is detected mid-pipeline, the processor flushes every younger in-flight instruction using the same latch-zeroing technique, then redirects the PC to the trap handler instead of a branch target. The mechanisms are so similar that hardware often reuses the branch-flush datapath for exception handling.
Why do deeper pipelines make control hazards worse?
The branch penalty is , where is the resolution stage's depth. Deeper pipelines (more stages before EX/branch-resolution, or resolution pushed even later for timing reasons) directly increase , so more instructions are speculatively fetched before any mistake can be caught, and more must be flushed per misprediction. This is precisely why deeply pipelined, high-clock-rate designs invest heavily in prediction accuracy: a 20-stage pipeline with a 15-cycle-deep branch resolution point pays an enormous penalty on any mispredict, so keeping the misprediction rate low becomes far more important than in a shallow 5-stage design.