Control Hazards and Branch Prediction

Data hazards were about a value not being ready in time. Control hazards are about the pipeline not knowing which instruction to fetch next. Fetch must launch something every cycle, but after a conditional jump the next address depends on a branch condition computed two stages later, and after a ret it depends on a return address read from memory. The pipeline cannot pause, so it guesses, runs ahead on the guess, and undoes the work if the guess turns out wrong.

The control hazard

In a straight-line program the next PC is trivially this instruction plus its length, known the moment the bytes are fetched. A conditional jump breaks that: the next instruction is either the jump target (if taken) or the fall-through (if not), and which one depends on the condition codes, which are not settled until the jump reaches Execute — two cycles after it was fetched. By then Fetch has already grabbed two more instructions on a guess about the outcome.

Predict taken, and why

PIPE's choice is predict-taken: when it fetches a conditional jump, it immediately starts fetching from the jump target, assuming the branch will be taken. Two facts justify this choice. First, the target address valC sits right in the instruction's encoding, so predicting taken costs no extra hardware: the fall-through valP and the target are both available in Fetch, and the mux just picks the target. Second, the prediction is right more often than wrong, because of loops. A conditional jump that closes a loop is taken on every iteration but the last: run the loop $n$ times and the branch goes taken $n-1$ times, fall-through once, $99\%$ taken for a 100-iteration loop. Averaged over real programs, always-taken predicts about 60% of conditional branches correctly, while the opposite strategy, never-taken, manages only about 40%.

There is a smarter static rule. Backward taken, forward not-taken (BTFNT) predicts taken only when the target address is lower than the jump instruction (a backward branch), and not-taken otherwise. Backward branches are almost always loop closers, hence taken; forward branches implement if/else and are closer to coin flips. BTFNT reaches roughly 65%, still far from the 90-plus percent of the dynamic predictors below, but respectable for a rule with no memory. PIPE sticks with always-taken for simplicity.

A loop, counted out

To quantify the loop argument, take a loop that runs its body $n$ times, closed by a conditional jump back to the top:

loop:
    # ... body ...
    subq %rax, %rcx     # decrement counter, set condition codes
    jne  loop           # taken n-1 times, falls through once (the exit)

The closing jne is taken on iterations 1 through $n-1$ (predict-taken: correct) and falls through on iteration $n$ to exit (predict-taken: wrong, 2-cycle penalty). So the loop pays the branch penalty exactly once, on exit, no matter how many times it spins — a miss rate of $1/n$ that vanishes for large $n$:

One misprediction amortized over the whole loop: a 100-iteration loop mispredicts $1\%$ of its branches, a 1000-iteration loop $0.1\%$. Never-taken would invert this exactly — right once, wrong $n-1$ times — turning a tight loop into a misprediction on nearly every iteration. This single asymmetry is why the cheap, memoryless predict-taken rule already beats a coin flip on real code: loops dominate the dynamic instruction count, and predict-taken gets every loop almost entirely right.

Detecting and recovering from a misprediction

The jump reaches Execute, the condition codes resolve into the signal e_Cnd, and PIPE compares the real outcome against its prediction. If they agree, nothing happens: the speculatively fetched instructions were the right ones, and no cycles were lost. If they disagree, the two instructions fetched after the jump are on the wrong path: at that moment one is in Decode and one is in Fetch. Neither may be allowed to change the machine's state. At the next clock edge PIPE squashes them, injecting bubbles into the D and E registers to annul both, and the PC selection logic redirects Fetch to the fall-through address, which is carried through the pipeline in M_valA (the jump's valP, merged into valA back in Decode).

Why exactly two squashed instructions, and why is squashing safe? The wrong path had exactly two cycles to run (the gap between fetching the jump and resolving it in Execute), so exactly two instructions entered from the wrong address, and by resolve time the furthest has only finished Decode. Nothing in Fetch or Decode touches programmer-visible state: the first write of any kind (condition codes) happens in Execute, and the wrong-path instructions are annulled before reaching it. So recovery needs no rollback, only bubbles. This is a designed invariant: PIPE resolves branches in Execute precisely so that no programmer-visible state is written before then.

The predict-verify-recover timeline

It helps to see the three phases as one timeline: predict at fetch, verify at execute, recover if wrong.

The gap between predict and verify is the speculation window: two cycles of speculative work. Predicting well keeps that work useful; predicting badly throws it away. Either way, correctness never depends on the prediction, only performance does. The window's width is why deep pipelines invest so heavily in prediction: a processor that resolves branches at stage 12 instead of stage 3 discards eleven instructions per misprediction, a cost the final lesson quantifies.

The ret hazard: nothing to predict

A ret is different. Its next PC is the return address, which sits on the stack and is not read until ret reaches its Memory stage. Unlike a conditional jump, there is no plausible address in the instruction bytes to guess: the target is data. So PIPE does not predict it; it waits. Mechanically the wait looks odd, because there is no way to inject a bubble into Fetch: the fetch stage always fetches something. So Fetch keeps refetching the instruction that follows the ret, and the control logic keeps replacing it with a bubble in Decode — three times. When ret reaches write-back, the return address is sitting in W_valM, the PC selection logic finally has a real answer, and the correct instruction is fetched.

The ret therefore costs a fixed three-cycle stall every time. Real processors avoid this cost: procedure calls and returns come in matched pairs, so the fetch unit keeps a small hardware stack of return addresses, pushed by call and popped as the prediction for ret, that predicts returns almost perfectly. It is speculation like any other, verified and repaired the same way, and it makes the otherwise-unpredictable control hazard nearly free.

A taste of dynamic prediction

Static strategies are fixed at design time and cannot adapt when a particular branch behaves differently from the average. Dynamic prediction lets the hardware learn per branch. Its simplest useful form is a table of 2-bit saturating counters indexed by the branch's address. Each counter is a four-state machine:

The two bits encode confidence: strongly/weakly not-taken (SN, WN) and weakly/strongly taken (WT, ST). Each actual outcome nudges the counter one step toward its direction, saturating at the ends, and the prediction is simply the counter's top bit. Trace a counter starting in ST (strongly taken) through the loop's per-iteration outcomes to watch hysteresis absorb the single exit surprise:

The exit's lone N drops the counter from ST to WT but does not flip the prediction — WT still predicts taken — so when the loop is re-entered the very next branch is predicted correctly and the counter climbs back to ST. A 1-bit predictor, having only the states taken and not-taken, would have flipped to not-taken on the exit and then mispredicted the re-entry too: two misses per loop instead of one. The extra bit of state pays for removing that second miss. The key property is hysteresis: one surprising outcome shifts confidence but does not flip the prediction; only two surprises in a row do. A loop branch shows why that single extra bit matters:

For a 5-iteration loop run repeatedly, the 1-bit scheme mispredicts 2 of every 5 branches (60% accuracy, no better than static predict-taken), while the 2-bit counter mispredicts 1 of 5 (80%). Longer loops push it higher: a 100-iteration loop is predicted at 99%. Modern predictors go much further, indexing tables by branch history rather than address alone and letting multiple predictors compete, to reach well above 95% on typical code. PIPE needs none of this machinery, but the principle scales: every point of prediction accuracy buys back squashed cycles, and the deeper the pipeline, the more each point is worth.

What accuracy is worth, in cycles

Prediction accuracy converts directly into cycles. With branch frequency $f_b$, miss rate $m$, and penalty $p$ cycles, the wasted cycles per instruction are

Suppose $f_b=0.20$ and $p=2$ (PIPE's penalty), and put different predictors head to head so $w=0.20m\times 2$:

Moving from PIPE's predict-taken to a good dynamic predictor cuts the branch tax from 0.160 to 0.016 cycles per instruction — a tenfold reduction, and on a five-stage pipe that alone would shave more than a tenth off CPI. Now imagine the branch resolves at stage 12 instead of stage 3, so each mispredict costs eleven cycles rather than two: every row's last column multiplies by $5.5\times$, and predict-taken's tax balloons to $0.20\times 0.40\times 11=0.88$ cycles per instruction, nearly doubling CPI. This arithmetic is why deep pipelines spend so many transistors on prediction: the deeper the pipe, the more each accuracy point is worth. The next lesson folds these numbers into the full CPI account.

Real branch predictors, and their dark side

The 2-bit counter is only the starting point for dynamic prediction. Its weakness is that it predicts each branch from its own recent history alone, missing correlations between branches (the outcome of one if often determines another). Two-level predictors (Yeh and Patt, 1991, ISCA) fix this by indexing the counter table with a global history register, a shifting record of the last several branch outcomes, so the same static branch gets different counters in different history contexts. The widely used gshare variant (McFarling, 1993, DEC WRL report) hashes the branch address with the global history by XOR before indexing, cheaply capturing correlation. State-of-the-art predictors like TAGE (Seznec and Michaud, 2006) keep several tables tagged with different history lengths and let the longest matching one win, reaching well above $95\%$ accuracy on typical code — accuracy that only matters more as pipelines deepen, since each mispredict now squashes a dozen-plus instructions.

The ret hazard has its own specialized fix, the return-address stack mentioned above: a small hardware stack that call pushes and ret pops as its prediction. Because calls and returns nest perfectly in well-behaved code, this predicts return targets almost perfectly, turning PIPE's hopeless three-cycle ret stall into a near-free branch.

Speculation also has a security cost. It runs wrong-path instructions and then annuls their architectural effects: PIPE squashes them before they write any register or condition code. But wrong-path instructions can still leave microarchitectural traces, the cache chief among them: a speculatively loaded line stays cached even after the instruction is squashed. The Spectre class of attacks (Kocher et al., 2019, IEEE S&P) exploits exactly this, training a branch predictor to mispredict on purpose so a victim speculatively touches secret-indexed memory, then reading the secret back out through cache timing. Meltdown (Lipp et al., 2018) is the sibling attack exploiting speculative execution past a fault. PIPE's guarantee that squashed instructions vanish is true architecturally and false microarchitecturally, and that gap remains an active security problem: the same speculation that buys throughput also leaks secrets.

We now have every mechanism PIPE needs — forwarding, stalling, prediction, squashing. The final lesson assembles them into the complete pipelined processor and counts the cost in CPI.