--- title: Control Hazards and Branch Prediction module: Pipelining moduleNumber: 5 lessonNumber: 4 order: 504 summary: > A pipeline must fetch an instruction every cycle, but after a conditional jump or a ret the next address is not yet known: a control hazard. We measure the branch penalty, weigh predict-taken against its alternatives with real loop arithmetic, watch PIPE detect a misprediction in Execute and squash the two wrong-path instructions, and meet the ret hazard, which has nothing to predict and stalls three cycles. A 2-bit counter gives a taste of dynamic prediction. topics: [Pipelining] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §4.5 Pipelined Y86-64 Implementations" --- [Data hazards](/computer-architecture/pipelining/data-hazards-stalling-and-forwarding) 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. > **Definition (Control hazard).** A situation where the correct next PC is not > known at fetch time because it depends on an instruction (a conditional jump or a > `ret`) that is still in the pipeline. Fetching naively requires predicting the > outcome and recovering if the prediction is wrong. ## 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. > **Definition (Branch penalty).** The number of cycles wasted when a branch > prediction is wrong: the cycles spent fetching and partially executing > instructions from the wrong path, which must be discarded. In PIPE a > mispredicted conditional jump costs **two** cycles. ### 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: ```asm [loop.ys] 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$: | $n$ (iterations) | Taken (correct) | Fall-through (miss) | Wasted cycles | Miss rate | | --- | --- | --- | --- | --- | | 4 | 3 | 1 | 2 | 25% | | 10 | 9 | 1 | 2 | 10% | | 100 | 99 | 1 | 2 | 2% | | 1000 | 999 | 1 | 2 | 0.1% | 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). > **Definition (Squash / cancel).** To turn an already-fetched instruction into a > bubble before it can write any register, memory, or condition code — annulling > its effects so a wrongly predicted path leaves no trace. $$ % caption: A mispredicted jump. PIPE predicts taken and fetches the target path % caption: (T1, T2). The jump resolves not-taken in Execute (cycle 3); at the next % caption: edge T1 and T2 are squashed (they continue only as bubbles, gray) and % caption: the correct fall-through is fetched in cycle 4. Penalty: two cycles. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,8} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; % jne: F D E M W, resolves in Execute at cycle 3 \node[anchor=east] at (-0.15,0) {\texttt{jne} (not tak\/en)}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (j\c) at (\c*1.0-0.5,0) {\s}; % wrong-path T1: fetched cycle 2, decoded cycle 3, then bubbles through E M W \node[anchor=east] at (-0.15,-0.85) {\texttt{T1} (wrong path)}; \node[cell, fill=acc!8] at (1.5,-0.85) {F}; \node[cell, fill=acc!8] at (2.5,-0.85) {D}; \foreach \c/\s in {4/E, 5/M, 6/W} \node[cell, fill=black!8] at (\c*1.0-0.5,-0.85) {\s}; % wrong-path T2: fetched cycle 3, then bubbles through D E M W \node[anchor=east] at (-0.15,-1.7) {\texttt{T2} (wrong path)}; \node[cell, fill=acc!8] at (2.5,-1.7) {F}; \foreach \c/\s in {4/D, 5/E, 6/M, 7/W} \node[cell, fill=black!8] at (\c*1.0-0.5,-1.7) {\s}; % correct fall-through fetched from cycle 4 \node[anchor=east] at (-0.15,-2.55) {fall-through}; \foreach \c/\s in {4/F, 5/D, 6/E, 7/M, 8/W} \node[cell, fill=acc!8] at (\c*1.0-0.5,-2.55) {\s}; % note below: resolution in cycle 3, squash at the edge into cycle 4 \node[anchor=north, text=acc] at (4.0,-3.05) {\scriptsize \texttt{outcome known in cycle 3; gray cells = squashed slots}}; \end{tikzpicture} $$ 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. $$ % caption: The predict-verify-recover timeline. At fetch (cycle 1) PIPE predicts and % caption: speculatively fetches; the prediction is verified when the branch reaches % caption: Execute (cycle 3); on a misprediction it recovers in cycle 4 by squashing % caption: and redirecting Fetch. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % timeline axis \draw[->] (0,0) -- (9.2,0) node[anchor=north] {cycles}; \foreach \x/\c in {1/1, 3/2, 5/3, 7/4} { \draw (\x,0.08) -- (\x,-0.08); \node[anchor=north] at (\x,-0.1) {\scriptsize \c}; } % phase markers above the line, well clear \node[draw, fill=acc!8, anchor=south, minimum height=7mm, inner sep=3pt] (p) at (1,0.5) {predict + fetch}; \node[draw, fill=acc!8, anchor=south, minimum height=7mm, inner sep=3pt] (v) at (5,0.5) {verify (Execute)}; \node[draw, fill=acc!8, anchor=south, minimum height=7mm, inner sep=3pt] (r) at (8,0.5) {recover (squash)}; \draw[acc, thick, ->] (p.east) -- (v.west); \draw[acc, thick, ->] (v.east) -- (r.west); \end{tikzpicture} $$ 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](/computer-architecture/pipelining/the-complete-pipe-processor) 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. $$ % caption: The ret hazard. The return address is read from the stack in ret's % caption: Memory stage (cycle 4) and latched into the W register; Fetch can use it % caption: only in cycle 5, so cycles 2-4 fetch nothing useful: three bubbles, no % caption: prediction possible. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=9mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \c in {1,...,7} \node at (\c*1.0-0.5,0.65) {\scriptsize \c}; \node[anchor=east] at (-0.15,0.65) {\scriptsize cycle}; % ret: F D E M W ; return addr read in Memory (cycle4), used from W (cycle5) \node[anchor=east] at (-0.15,0) {\texttt{ret}}; \foreach \c/\s in {1/F, 2/D, 3/E, 4/M, 5/W} \node[cell, fill=acc!8] (r\c) at (\c*1.0-0.5,0) {\s}; % bubbles while waiting (cycles 2,3,4) \node[anchor=east] at (-0.15,-0.85) {bubbles}; \foreach \c in {2,3,4} \node[cell, fill=black!8] at (\c*1.0-0.5,-0.85) {bb}; % correct target fetched from cycle5 \node[anchor=east] at (-0.15,-1.7) {return target}; \foreach \c/\s in {5/F, 6/D, 7/E} \node[cell, fill=acc!8] at (\c*1.0-0.5,-1.7) {\s}; % arrow: ret Memory provides the address, used by fetch next cycle \draw[acc, thick, ->] (r4.south) .. controls (3.98,-0.7) and (4.2,-1.0) .. (4.45,-1.28); \node[anchor=north, text=acc] at (3.5,-2.5) {\scriptsize \texttt{return address read in Memory, used by Fetch in cycle 5}}; \end{tikzpicture} $$ 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: $$ % caption: The 2-bit saturating counter. Taken outcomes (top edges) move right, % caption: not-taken (bottom edges) move left, and the ends saturate. The left two % caption: states predict not-taken; the right two predict taken. One surprise % caption: nudges the state; only two in a row flip the prediction. \begin{tikzpicture}[font=\footnotesize,>=stealth, st/.style={draw, fill=acc!8, minimum width=13mm, minimum height=8mm, inner sep=1pt}] \definecolor{acc}{HTML}{2348F2} \node[st] (sn) at (0,0) {SN}; \node[st] (wn) at (2.6,0) {WN}; \node[st] (wt) at (5.2,0) {WT}; \node[st] (st) at (7.8,0) {ST}; % taken edges: rightward, arcs above \draw[acc, thick, ->] (sn.north) .. controls (0.8,0.85) and (1.8,0.85) .. (wn.north); \draw[acc, thick, ->] (wn.north) .. controls (3.4,0.85) and (4.4,0.85) .. (wt.north); \draw[acc, thick, ->] (wt.north) .. controls (6.0,0.85) and (7.0,0.85) .. (st.north); \node[text=acc] at (1.3,0.95) {\scriptsize T}; \node[text=acc] at (3.9,0.95) {\scriptsize T}; \node[text=acc] at (6.5,0.95) {\scriptsize T}; % taken self-loop at ST \draw[acc, thick, ->] (st.10) .. controls (9.0,0.5) and (9.0,-0.5) .. (st.350); \node[text=acc] at (9.15,0) {\scriptsize T}; % not-taken edges: leftward, arcs below \draw[black, thick, ->] (st.south) .. controls (7.0,-0.85) and (6.0,-0.85) .. (wt.south); \draw[black, thick, ->] (wt.south) .. controls (4.4,-0.85) and (3.4,-0.85) .. (wn.south); \draw[black, thick, ->] (wn.south) .. controls (1.8,-0.85) and (0.8,-0.85) .. (sn.south); \node[black] at (6.5,-0.95) {\scriptsize N}; \node[black] at (3.9,-0.95) {\scriptsize N}; \node[black] at (1.3,-0.95) {\scriptsize N}; % not-taken self-loop at SN \draw[black, thick, ->] (sn.170) .. controls (-1.2,0.5) and (-1.2,-0.5) .. (sn.190); \node[black] at (-1.35,0) {\scriptsize N}; % prediction regions \node[black] at (1.3,-1.6) {\scriptsize predict not-tak\/en}; \node[text=acc] at (6.5,-1.6) {\scriptsize predict tak\/en}; \end{tikzpicture} $$ 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: | Outcome | State before | Prediction | Correct? | State after | | --- | --- | --- | --- | --- | | T | ST | taken | yes | ST | | T | ST | taken | yes | ST | | N (exit) | ST | taken | **no** | WT | | T (re-enter) | WT | taken | yes | ST | | T | ST | taken | yes | ST | 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: $$ % caption: A loop branch over two runs of the loop (outcomes T T T T N, twice). % caption: A 1-bit predictor flips state on every miss, so it misses twice per % caption: run: at the exit and again at the next run's first iteration. The 2-bit % caption: counter absorbs the exit and misses only once per run. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum width=8mm, minimum height=6.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.3,0) {outcome}; \foreach \i/\o in {1/T,2/T,3/T,4/T,5/N,6/T,7/T,8/T,9/T,10/N}{ \node[cell, fill=acc!8] at (\i*0.9-0.45,0) {\o}; } \node[anchor=east] at (-0.3,-0.9) {1-bit misses}; \foreach \i in {5,6,10} \node[cell, fill=black!12] at (\i*0.9-0.45,-0.9) {x}; \foreach \i in {1,2,3,4,7,8,9} \node[cell] at (\i*0.9-0.45,-0.9) {}; \node[anchor=east] at (-0.3,-1.8) {2-bit misses}; \foreach \i in {5,10} \node[cell, fill=black!12] at (\i*0.9-0.45,-1.8) {x}; \foreach \i in {1,2,3,4,6,7,8,9} \node[cell] at (\i*0.9-0.45,-1.8) {}; \end{tikzpicture} $$ 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 $$ w = f_b \cdot m \cdot p. $$ Suppose $f_b = 0.20$ and $p = 2$ (PIPE's penalty), and put different predictors head to head so $w = 0.20 \, m \times 2$: | Predictor | Accuracy | Miss rate | Wasted cycles / instr | | --- | --- | --- | --- | | Never-taken | 40% | 0.60 | 0.240 | | Predict-taken (PIPE) | 60% | 0.40 | 0.160 | | BTFNT (static) | 65% | 0.35 | 0.140 | | 2-bit counter | 85% | 0.15 | 0.060 | | gshare / TAGE (dynamic) | 96% | 0.04 | 0.016 | 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. > **Takeaway.** A **control hazard** is not knowing the next PC at fetch time. > PIPE **predicts taken** (~60% right; never-taken ~40%, BTFNT ~65%, and loops > make taken the majority), **verifies** in Execute via `e_Cnd`, and on a miss > **squashes** the two wrong-path instructions (safe because nothing writes > state before Execute) for a **two-cycle** penalty. A **`ret`** has no address > to guess: Fetch stalls for **three cycles** until the return address > emerges in `W_valM` (real processors instead predict it with a return-address > stack). Dynamic **2-bit saturating counters** add hysteresis, so a lone > surprise nudges confidence without flipping the prediction. We now have every mechanism PIPE needs — forwarding, stalling, prediction, squashing. The [final lesson](/computer-architecture/pipelining/the-complete-pipe-processor) assembles them into the complete pipelined processor and counts the cost in CPI.