Hazards & Branch Prediction

Before hazards make sense, the pipeline needs to be crisp in your mind. A classic RISC pipeline has five stages:

1. IF — Instruction Fetch: read the instruction from memory (or cache) at the program counter.
2. ID — Instruction Decode / Register Read: figure out what the instruction does, read source registers.
3. EX — Execute: the ALU does the arithmetic, or the branch condition is evaluated.
4. MEM — Memory Access: loads read from data cache; stores write to it.
5. WB — Write-Back: results are written into the register file.

Think of it as a car wash with five bays. At any clock cycle, five different cars (instructions) are in five different bays simultaneously. The throughput goal is one car (instruction) out per cycle. Hazards are the moments when a car can't move forward — because the next bay is busy, or because we don't know which car to let in next.

Each stage is separated by a pipeline register (also called a latch or buffer). At each clock edge, the outputs of every stage are captured into these registers, so the stages can all work in parallel on independent state. The pipeline registers between stages are conventionally named IF/ID, ID/EX, EX/MEM, and MEM/WB.

# Observe pipeline depth on x86 using perf
# Run a tight loop and look at branch-mispredict cost
perf stat -e cycles,instructions,branch-misses,branches \
  -- python3 -c "x=0
  for i in range(10_000_000): x += i
  print(x)"

A structural hazard occurs when two instructions in different pipeline stages need the same hardware resource at the same time, and there is only one copy of it.

Classic example — single memory port: In a naive design, instruction fetch (IF stage) and data memory access (MEM stage) both need to read memory. If there is only one memory port, an lw (load word) instruction in MEM conflicts with the next instruction trying to do IF. The pipeline must stall.

Solution — Harvard architecture / split caches: Almost all modern processors solve this by maintaining separate instruction caches (I-cache) and data caches (D-cache). They are distinct physical banks, so IF and MEM can proceed simultaneously. This is why you'll see references to 'Harvard-style' L1 caches even in what are logically von Neumann machines.

Another example — single write port: If many instructions try to write to the register file in the same cycle and there is only one write port, that's a structural hazard. Modern designs solve this with multi-ported register files.

Structural hazards are primarily a design-time problem. Once the hardware ships, they are fixed. The CPU designer chose how many ports, caches, and execution units to include based on cost/area/power tradeoffs. As a software engineer, you rarely need to think about structural hazards explicitly — they were resolved before the chip was taped out. However, they resurface in FPGA designs or when studying simple educational processors like MIPS R2000.

A data hazard occurs when an instruction depends on a result that hasn't been produced yet by a prior instruction still in the pipeline.

There are three types, named by the order of the conflicting accesses:

RAW — Read After Write (true dependence): Instruction J reads a register that instruction I is still computing. This is the most common and most important type.

add  x1, x2, x3    # I: writes x1 in WB (cycle 5)
sub  x4, x1, x5    # J: reads x1 in ID (cycle 3) — STALE!

Here, J reads x1 in its ID stage (cycle 3), but I doesn't write x1 until its WB stage (cycle 5). J gets the old value — this is a real bug if not handled.

WAR — Write After Read (anti-dependence): Instruction J writes a register that instruction I needs to read first. In a purely in-order pipeline this cannot happen (I is ahead of J), but it matters in out-of-order processors where J might execute early.

WAW — Write After Write (output dependence): Two instructions both write the same register; the second write must 'win'. Again, mostly relevant for out-of-order.

For our in-order 5-stage pipeline, RAW hazards are the central problem. Without any mitigation, the pipeline must insert stalls (do-nothing cycles) to wait for the result to be written back before it's read.

# Compile this and inspect the assembly.
# Without optimisation, the compiler may generate dependent instructions.
# With -O2, it may reorder to hide latency.
int example(int a, int b, int c) {
    int t = a + b;   // RAW: next line reads t
    return t * c;
}

Forwarding (also called bypassing) is the hardware technique that resolves most RAW hazards without stalling. The insight is simple: we don't need to wait for a result to be written into the register file. We can route it directly from wherever it is right now — a pipeline register — to wherever it's needed.

How it works: After instruction I finishes its EX stage, the computed result sits in the EX/MEM pipeline register. If the next instruction J needs that value in its EX stage, we can wire a multiplexer at the ALU input to select from EX/MEM instead of from the ID/EX register (which holds the stale register-file value).

Similarly, a result in the MEM/WB register can be forwarded to an instruction two stages behind.

Forwarding paths in a 5-stage pipeline:

• EX/MEM → EX input: handles 1-cycle-apart RAW (most common)
• MEM/WB → EX input: handles 2-cycle-apart RAW
• MEM/WB → MEM input: needed for store instructions that depend on a recent load

Load-use hazard — the one stall forwarding can't avoid: Consider:

lw   x1, 0(x2)    # result available after MEM stage (cycle 4)
add  x3, x1, x4  # needs x1 in EX stage (cycle 3)

The lw result isn't available until after its MEM stage — but add needs it one cycle earlier in EX. You can't forward backwards in time. The hardware must insert exactly one stall (bubble) and then forward from MEM/WB. A compiler doing load scheduling tries to place an independent instruction between the load and its consumer to fill this slot.

// The compiler's view: reorder to hide load latency
// Version 1: dependent — forces a stall on most CPUs
int v1(int *a, int *b) {
    int x = *a;          // load
    return x + *b;       // immediately uses x: load-use hazard
}

// Version 2: independent instruction fills the slot
int v2(int *a, int *b, int c) {
    int x = *a;          // load
    int y = c * 2;       // independent: fills load-delay slot
    return x + y + *b;   // x is now safe to use
}

When forwarding is insufficient (like the load-use case), the pipeline inserts a stall, also called a bubble or NOP (no-operation).

Mechanically, what is a stall? The hazard detection unit (HDU) in the pipeline control logic detects that instruction J cannot proceed. It does three things simultaneously:

1. Freezes the IF and ID stage registers (PC and IF/ID don't update — the same instructions stay in those stages).
2. Inserts a bubble into the ID/EX register (sets all control signals to zero — no register writes, no memory access, ALU output ignored).
3. Lets everything ahead of ID/EX continue normally.

The result is that the pipeline now has a slot of empty work flowing through it — like a gap in the car wash. The instruction that was stalled gets a second (or third) chance to enter the EX stage on the next cycle.

Visualizing a stall:

Cycle:     1    2    3    4    5    6    7
lw x1      IF   ID   EX   MEM  WB
add x3         IF   ID   **   EX   MEM  WB   (** = stall)
or x5               IF   IF   ID   EX   MEM  WB

Note how or repeats its IF stage — the PC was frozen. The stall costs exactly one cycle of throughput per bubble.

CPI impact: A pipeline running perfectly has CPI (cycles per instruction) = 1. Each stall adds 1 to the CPI of the affected instruction. A program with a 20% load-use rate and no scheduling might have CPI ≈ 1.2. Compilers and out-of-order hardware both work hard to minimize this.

# Measure the effect of load-use hazards with perf
# Compare a tight dependent loop vs an unrolled/independent one
# On modern x86 this is mostly hidden by out-of-order execution,
# but on in-order ARM Cortex-A53 or RISC-V you'll see it clearly.

# Dependent version: each iteration depends on the previous load
gcc -O1 -o dep dep.c && perf stat -e cycles,instructions ./dep

# Independent (unrolled): 4 loads before any use
gcc -O1 -o indep indep.c && perf stat -e cycles,instructions ./indep

A control hazard (also called a branch hazard) arises because the pipeline fetches instructions sequentially, but branch and jump instructions change the PC to some other address. The pipeline doesn't know the correct next PC until the branch is resolved — often not until the EX or even MEM stage.

The problem in numbers: In a 5-stage pipeline resolving branches in EX (stage 3), by the time we know the branch outcome, we've already fetched two more instructions after the branch. If the branch was taken, those two instructions are wrong — we've done wasted work and must flush them (turn them into bubbles). This is a 2-cycle branch penalty per mispredicted/taken branch.

In a modern deep pipeline (15-20 stages) where branch resolution happens late, the penalty can be 15-20 cycles per mispredicted branch. With branches occurring roughly every 5-8 instructions in typical code, an unmitigated branch penalty would be catastrophic.

Three naive strategies:

1. Stall until resolved: Insert bubbles until we know the branch target. Simple but expensive.
2. Predict not-taken: Always fetch the fall-through. If the branch isn't taken, no penalty. If it is taken, flush the wrongly fetched instructions. Works well for loop exit conditions (which are not taken most iterations).
3. Delayed branching: The ISA defines that the N instructions after a branch (the 'delay slot') always execute, regardless of branch outcome. The compiler fills these slots with useful work. MIPS used this; modern ISAs avoid it because it complicates everything.

None of these is satisfactory for a modern high-performance core. The real solution is prediction.

// How the Linux kernel annotates branch likelihood
// From include/linux/compiler.h
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

// Usage in kernel code:
if (unlikely(error_condition)) {
    // cold path — compiler puts this far away
    handle_error();
}
// The common path falls through — no taken branch needed

Static prediction means the prediction is fixed at compile time (or by the hardware based on a simple rule), without any runtime feedback.

Backward-taken / Forward-not-taken (BTFNT): The simplest and most effective static heuristic:

• A branch whose target address is lower than the branch instruction itself (backward branch) is predicted taken — these are almost always loop back-edges.
• A branch whose target is higher (forward branch) is predicted not-taken — these are often error-handling or rare conditions.

This rule alone gets about 65-70% accuracy on typical workloads, which is remarkable for something with zero runtime cost.

Compiler hints — __builtin_expect: The GCC/Clang intrinsic __builtin_expect(expr, expected_value) tells the compiler which branch is hot. The compiler uses this to:

1. Lay out the hot path as fall-through (no branch instruction needed in the common case).
2. Move cold code to a different section (.text.unlikely).
3. On architectures with branch-hint prefixes (like PowerPC's bc instruction), emit the hint directly.

Profile-guided optimization (PGO): When you compile with -fprofile-generate, run the program, then recompile with -fprofile-use, the compiler has real branch frequency data and can make optimal static layout decisions. The Linux kernel's CONFIG_AUTOFDO uses this approach with hardware performance counters.

Static prediction has a fundamental ceiling: it can't adapt to runtime data. A branch that's 90% taken for one dataset might be 30% taken for another. That's where dynamic prediction comes in.

// Compile and inspect the assembly to see layout effect
// gcc -O2 -S -o - branch_hint.c | grep -A5 'likely_path\|unlikely'

#include <stdio.h>

void process(int x) {
    if (__builtin_expect(x > 0, 1)) {  // likely
        // hot path: compiler makes this fall-through
        printf("positive: %d\n", x);
    } else {
        // cold path: compiler emits a jump here
        printf("non-positive: %d\n", x);
    }
}

Dynamic prediction uses the history of past branch outcomes to predict future ones. The hardware maintains a small table of state machines, indexed by (part of) the branch's PC.

1-bit predictor (single flip-flop): For each branch, store a single bit: 0 = predict not-taken, 1 = predict taken. After each branch resolves, update the bit to reflect the actual outcome. This gives 100% accuracy on a loop that always iterates many times — except for the last iteration (exit misprediction) and first entry. For a loop running N times, accuracy = (N-2)/N.

Problem with 1-bit: Consider a nested loop where the inner branch alternates taken/not-taken. The 1-bit predictor will mispredict on every single iteration because it's always one step behind.

2-bit saturating counter (the classic): Store 2 bits per branch, forming a 4-state saturating counter:

00 (Strongly Not-Taken) → 01 (Weakly Not-Taken) → 10 (Weakly Taken) → 11 (Strongly Taken)

Both Not-Taken states predict not-taken; both Taken states predict taken. A single misprediction only moves one state; two mispredictions in a row are needed to flip the prediction. This is hysteresis — the prediction is sticky.

Why 2-bit is much better: For the nested loop, the inner branch exits once per outer iteration, then immediately re-enters. With a 2-bit counter in Strongly Taken, the one exit mispredicts, moves to Weakly Taken, then immediately snaps back to Strongly Taken on re-entry. Only 1 misprediction per outer loop, not 2.

The Branch History Table (BHT) / Branch Predictor Table (BPT): In hardware, these counters are stored in a table indexed by the low-order bits of the PC. A table with 4096 entries (12-bit index) takes only 1 KB of storage (2 bits × 4096 entries) and achieves over 90% accuracy on typical integer code. This is the design used in the original Pentium Pro (P6) architecture.

// Demonstrate predictor-friendly vs predictor-hostile loop
// The branch predictor LOVES this: branch always taken until last
void sum_array_friendly(int *a, int n) {
    int s = 0;
    for (int i = 0; i < n; i++)   // back-edge: almost always taken
        s += a[i];                 // no conditional inside
}

// Predictor-hostile: branch outcome depends on data
void count_positives(int *a, int n) {
    int count = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > 0)              // outcome depends on data — hard to predict
            count++;
    // If data is random, expect ~50% misprediction here
}

Predicting direction (taken or not-taken) is only half the problem. For a taken branch, the processor also needs to know where to jump — the branch target address — to fetch instructions from the right place immediately.

Why this is hard: The branch instruction hasn't even been decoded yet during IF. We don't know it's a branch, let alone where it goes. If we wait until after decode to find the target, we've already wasted a cycle.

The Branch Target Buffer (BTB): The BTB is a small, fast cache that maps recent branch PCs to their targets. It is looked up in parallel with (or just before) instruction fetch, using the current PC.

BTB lookup process:

1. During IF, index into the BTB using bits of the PC.
2. Check the tag (upper PC bits) for a valid hit.
3. If hit: use the stored target address to redirect the PC this cycle. Simultaneously, the direction predictor says whether to take it.
4. If miss: proceed sequentially; update the BTB when the branch resolves.

BTB entry fields:

• Tag: upper bits of branch PC (for validation)
• Target: the destination address
• Type: branch type (conditional, unconditional, return, indirect)
• Sometimes: direction prediction state (merges BHT and BTB)

Return Address Stack (RAS): Function call and return instructions are a special case. The return address is pushed/popped at runtime — each call site has a different return address. The BTB handles this poorly. Modern processors use a separate Return Address Stack (RAS) — a small hardware stack that mirrors the call stack. When a call is fetched, the return address is pushed onto the RAS. When a ret is fetched, the RAS predicts the return target by popping. This achieves near-100% accuracy for returns.

// Indirect branch: target computed at runtime — hardest for BTB
// This is why virtual dispatch (vtables) has a small cost
struct Animal {
    void (*speak)(struct Animal *self);  // function pointer
};

void make_noise(struct Animal *a) {
    a->speak(a);  // indirect call: target = *a->speak
                  // BTB must track each call-site/target pair
}

A single 2-bit counter indexed by PC works well for simple loops, but real programs have correlated branches — the outcome of one branch depends on the outcome of a previous branch. Example:

if (x > 5)     // branch A
    ...
if (x > 10)    // branch B — outcome correlates with A!
    ...

If branch A was not-taken (x ≤ 5), branch B is always not-taken. The 2-bit counter can't see this — it indexes only by branch B's own PC.

Two-level adaptive predictor (Yeh & Patt, 1991): Maintains a Branch History Register (BHR) — a shift register that records the outcomes (T/N) of the last k branches. The prediction table is indexed by the concatenation (or XOR) of the PC and the BHR contents. This way, the same branch can be predicted differently depending on what branches preceded it.

GShare predictor: A popular variant where the prediction table is indexed by PC XOR BHR. The XOR is clever: it doesn't require a wider index but mixes PC and history, reducing aliasing. GShare was used in the Alpha 21264.

Tournament/Hybrid predictor: Choose between two predictors (e.g., a global-history predictor and a local-history predictor) using a meta-predictor that tracks which one has been more accurate for each branch. The Pentium M and AMD K8 used tournament predictors.

TAGE (Tagged Geometric History Length): The state-of-the-art predictor (Seznec, 2006). Multiple tables with geometrically increasing history lengths (e.g., 4, 8, 16, 32, 64, 128 bits of history). Each table uses a tagged entry (partial PC + partial history XOR as tag). The longest-matching table wins. TAGE achieves >98% accuracy on SPECint benchmarks. Modern Intel and AMD processors use TAGE variants internally.

// Demonstrate correlated branch pattern
// A good predictor will learn that after 'if (flag)' is false,
// 'if (flag && extra)' is always false too.
void correlated(int *a, int n, int flag) {
    for (int i = 0; i < n; i++) {
        if (flag)              // Branch A
            a[i] *= 2;
        if (flag && a[i] > 0)  // Branch B: correlated with A
            a[i]++;
        // A two-level predictor captures this; a 2-bit counter does not
    }
}

When a branch prediction turns out to be wrong, the processor must:

1. Detect the misprediction (when the branch resolves, usually in EX or later).
2. Flush all instructions that were fetched along the wrong path (they are in the pipeline but their results must be discarded).
3. Redirect the PC to the correct target.
4. Restart fetching from the correct path.

Steps 1-3 cost cycles proportional to how far into the pipeline the branch has traveled before resolution. This is the misprediction penalty — the number of wasted cycles.

Typical penalties:

• Simple 5-stage pipeline (branch resolves in EX): 2 cycles penalty
• Intel Pentium 4 (Netburst, 20+ stages): 20 cycle penalty — catastrophic for branch-heavy code
• Modern Intel Core (10-15 stages): 14-17 cycle penalty
• ARM Cortex-A72: 15 cycle penalty
• RISC-V in-order core: 2-3 cycles

Speculative fetch (speculative execution): Rather than stalling on every branch, the processor speculatively fetches and executes instructions along the predicted path. Results are held in a reorder buffer (ROB) and not committed to architectural state until the branch is confirmed correct. This is the foundation of all modern out-of-order cores.

Speculative execution is also the root cause of Spectre (CVE-2017-5753). By speculatively executing code past a bounds check, the processor can read out-of-bounds memory. Even though the results are never committed, the memory access changes the cache state — and that cache-timing side channel is observable. The fix (series barriers, retpoline, LFENCE) all work by preventing speculation at sensitive points, deliberately taking a performance hit to close the side channel.

// The kernel's LFENCE-based Spectre barrier
// From arch/x86/include/asm/barrier.h
// LFENCE is a serializing instruction on the load port —
// no speculation can cross it.

// In kernel source:
#define barrier_nospec() __asm__ __volatile__("lfence" ::: "memory")

// Usage: prevent speculative array access past a bounds check
static inline int safe_array_read(int *array, unsigned int idx,
                                   unsigned int array_size) {
    if (idx < array_size) {
        barrier_nospec();  // speculation stops here
        return array[idx]; // only reached if idx is genuinely safe
    }
    return 0;
}

Retpoline is a software-only Spectre variant 2 mitigation invented by Google (Paul Turner, 2018). It cleverly exploits the Return Address Stack predictor to prevent the CPU from speculatively executing code at an attacker-controlled indirect branch target.

The problem Retpoline solves: Spectre variant 2 poisons the BTB so that an indirect branch in the kernel speculatively jumps to attacker-chosen gadgets, leaking privileged data via cache timing.

The retpoline trick: Instead of an indirect jmp [rax], the compiler emits:

call    load_label      ; push return address, CPU predicts return here
loop:                   ; <-- CPU speculates here (infinite loop = safe)
pause
lfence
jmp     loop
load_label:
    mov     [rsp], rax  ; overwrite stacked return address with actual target
    ret                 ; CPU mispredicts (predicted loop), then corrects

The ret will actually jump to wherever rax points (the real indirect target). But the CPU's RAS predicts it will return to loop — an infinite pause+lfence loop that leaks nothing. When the misprediction is detected, the CPU discards the speculative work and redirects to rax. No gadget was executed speculatively.

Performance cost: Retpoline costs ~1-3% on typical workloads, but can cost 10-15% on workloads with many indirect calls (virtual function calls, function pointers). This is why CONFIG_RETPOLINE exists as a kernel option, and why newer hardware (Skylake+, with IBRS/eIBRS) can provide hardware protection without the retpoline overhead.

This is a stunning example of how deep knowledge of the branch predictor leads to both the attack and the defense.

/* gcc -mindirect-branch=thunk generates retpoline
   You can see the output on godbolt.org:
   https://godbolt.org  — try: gcc -O2 -mindirect-branch=thunk

   Also: check your kernel's retpoline status */
grep RETPOLINE /boot/config-$(uname -r)  # check if enabled
cat /sys/devices/system/cpu/vulnerabilities/spectre_v2  # runtime status