Why the pipeline hates branches: static prediction and the delay slot

A branch answers two questions, and both come late

You know from your first architecture course what a conditional branch does: BNE R1, R2, LOOP compares two registers and continues at the label if they differ, at PC + 4 otherwise. The notes write RISC-V beq x1, x3, L1; this notebook writes branches as the exam papers do, without the dollar sign of the older papers ($R1, $F2). Here is the loop of the June 2025 paper in that spelling (the paper prints ADDI.U for ADDUI and ADDI.D for FADD):

INIT: ADDUI R1, R0, 0
      ADDUI R2, R0, 20
LOOP: LD    F0, 0(R1)
      FADD  F2, F0, F0
      SD    F2, 0(R1)
      ADDUI R1, R1, 4
      BNE   R1, R2, LOOP

What makes a branch special is who is waiting for its answer: the fetch unit needs the next PC every cycle, and a branch delivers it in two parts, both late.

In the basic pipeline of the notes (pp. 30–31) the ALU compares the registers and adds PC + offset in EX, and the PC is written at the end of ME: for three cycles after the branch is fetched, fetch does not know where to go. That gap is the control hazard, a "pipeline hazard due to uncertainty in branch outcome during instruction fetch" in the notes' summary box (p. 32), caused by every instruction that modifies the PC, jumps included. Fetch can only stall until the PC is known, or fetch and flush: guess, keep going, throw the guessed instructions away if the guess was wrong.

Read the penalty off the figure: the next PC is known at the end of stage r of the branch (ME is stage 4, ID is 2), so the fetch slots of cycles 2 … r are lost.

Branch penalty = (stage at whose end the PC is written) − 1: three cycles with the PC written in ME, one cycle with the branch solved in ID.

On the notes' four-instruction sequence (p. 34), counted as the formula sheet counts, cycles = IC + 4 + stalls:

Early branch evaluation: move the comparison into ID

Nothing forces the comparison to wait for EX: BNE needs an equality test, a cheap tree of XOR gates, and its target is PC-relative, so an adder can produce PC + offset right after decoding. The notes (p. 35) list what the ID stage gains — comparison and addition logic, a multiplexer with control signals to write the PC, wider data paths for the offset and the register values — and both answers are ready at the end of ID: the right panel of Fig. 1.

The price: a branch that is hungry for its operands

The comparator in ID wants its operands one stage earlier than an ALU would. If the instruction right before the branch produces one of them, forwarding cannot help — the producer is still in EX when the branch asks in ID — so the branch waits one cycle, two after a load. Hence the sentence of every VLIW exercise of the three papers, "1 Integer ALU with 1 cycle latency to next Int/FP/L/S & 2 cycle latency to next Branch": the loop counter must be updated at least one instruction before the branch that tests it.

      ADDUI R1, R1, 4      # produces R1 in EX
      BNE   R1, R2, LOOP   # needs R1 in ID: one stall cycle

One independent instruction between them removes the stall. Early resolution buys a short penalty and a hungrier branch: both halves are exam material.

Stall or flush: the CPI formula

Stalling pays the penalty on every branch; a guessed fetch pays it only when wrong. The derivation turns that into the one formula of this lesson that is not on the formula sheet.

1. The formula sheet's cycle count for IC instructions on the 5-stage pipeline (4 = the pipeline fill):

   \[ \text{cycles} = \text{IC} + 4 + \text{stalls} . \]

2. A fraction \(f_b\) of the instructions are branches; each costs \(r - 1\) cycles when fetch guessed wrong, with probability \(p_{\text{mis}}\):

   \[ \text{stalls}_b = \text{IC} \cdot f_b \,(r - 1)\, p_{\text{mis}} . \]

3. Divide by IC; for a long program the fill term \(4 / \text{IC}\) vanishes:

   \[ \text{CPI} = 1 + f_b\,(r - 1)\,p_{\text{mis}} . \]

4. Stalling is "always wrong", \(p_{\text{mis}} = 1\). A predictor pays only when wrong: always not taken has \(p_{\text{mis}} = p_T\), the taken fraction; always taken has \(1 - p_T\).

5. With \(f_b = 0.2\), \(p_T = 0.6\) and the branch solved in ID: stall 1.20, always not taken 1.12, always taken 1.08. With the PC written in ME: 1.60, 1.36, 1.24 — a machine built for CPI = 1 runs at 1.6 before a single cache miss.

Guessing with no memory: the four static schemes

Branch prediction is speculation: guess the outcome, fetch along the guessed path, flush and restart if the guess was wrong. One rule keeps it safe (p. 37): "the processor must avoid updating its internal state (registers, memory, etc.) until the branch outcome is known with certainty". With the branch solved in ID that is free, since the wrongly fetched instruction is still in IF; the out-of-order machines of lesson 17 need a reorder buffer for it.

A static scheme guesses the same way for a given branch every time — a fixed hardware rule or a compiler hint; "static" means nothing is learned at run time, not "the compiler decides". Dynamic schemes (lessons 5 and 6) learn from the branch's history. The notes' four static rules, each with its cost and its failure case:

Always not taken, always taken — and why one of them needs a table

Branch always not taken costs nothing: keep fetching PC + 4 "without any need to determine or access the Branch Target Address" (p. 39). When the branch turns out taken, the one instruction fetched after it becomes a NOP and fetch restarts at the target — one cycle in the ID-resolved pipeline (the notes' Figure 12, left panel below). The right bet for an if whose else path is rare — the notes' example (p. 39) is if (z > 0) w = x; else w = y; with z usually positive, so the branch to the else part is usually not taken — and the wrong one for every loop-closing branch.

Branch always taken mirrors it in direction but not in cost: to fetch the target in the next cycle you must know it while the branch is still in IF, before decoding — and in IF nothing can be computed about a branch, only remembered, indexed by its PC. That memory is the Branch Target Buffer, "a specialized cache in the processor designed to predict the target address of a taken branch instruction before the branch condition is actually resolved" (p. 41): key, the address of the branch; value, the predicted target. In the notes' Example 1 (p. 42) the entry 0x100 → 0x80 sends fetch to 0x80 as soon as the branch at 0x100 is fetched; if the branch is then not taken, the instruction from 0x80 is flushed and fetch resumes at 0x104 — again one cycle. On a miss the processor "might default to sequential execution (PC + 4) or wait for the BTA to be calculated". The BTB is lesson 5; here, remember that without it always taken has nothing to fetch, since the target is known no earlier than the outcome.

Backward taken, forward not taken

The two uniform rules are each right on one kind of branch, so combine them with the one bit that tells the kinds apart: the direction. BTFNT predicts a backward branch (target below the current PC) as taken, because backward branches close loops and a loop of N iterations takes its bottom branch N − 1 times; a forward branch as not taken, because forward branches usually guard an else path or an error handler that is rarely entered. The notes (p. 44) call it "just a comparison of the target address vs the current PC"; in hardware it is the sign bit of the offset. It is not adaptive — a forward branch taken 90 % of the time is mispredicted 90 % of the time. And the sign bit is only known after decoding, when the ID-resolved pipeline knows the outcome anyway: in the course's pipeline the guess pays off only if it is stored, with the target, in the BTB entry of the branch, so that it is available in IF. The tables of this lesson assume that.

Profile-driven prediction

The fourth scheme lets the compiler decide per branch, from evidence: run the program on representative inputs, record how often each branch was taken, and encode the verdict as a hint bit in the instruction, 1 if usually taken, 0 if not. The notes' pattern (p. 45), T T T T T T T T NT NT NT, gives the hint "taken" and about 27 % mispredictions if future runs look like the profile. The processor only reads a bit; the costs are a profile-compile cycle, a profile that goes stale when the inputs change, and an instruction format with a spare bit — RISC-V has none, so compilers there lay the code out so that the frequent path falls through.

The notes' Table 2 (p. 47), with the delayed branch of section 4 included:

Putting numbers on it: the two exam loops

The exam asks for a table and a rate, so do both loops of the hook by hand once. The June 2025 BNE executes with R1 = 4, 8, 12, 16, 20 against R2 = 20: five executions, T T T T NT. The midterm BEQ executes with R1 = 0 … 100 against R2 = 100: 101 executions, NT 100 times, then T at the exit.

To turn a rate into cycles, count. The 2025 program executes 2 + 5 × 5 = 27 instructions; with branch stalls only (the body's load-use hazard is left out on purpose), stalling costs 27 + 4 + 5 = 36 cycles (CPI 1.33), always not taken 35 (1.30), always taken 32 (1.19). In the formula sheet's loop notation, m = 5 and k = 1 stall per iteration give CPI_∞ = (m + k) / m = 1.2 for the stalled loop; a correctly predicted branch has k = 0.

The delay slot: the bubble becomes a contract

The delayed branch stops guessing and changes the rules: the instruction right after the branch — the branch delay slot — "is always executed, regardless of whether the branch is taken or not" (p. 46), and the branch takes effect only after it. The bubble gets a meaning and the compiler gets the job of filling it; if it finds nothing it writes a NOP, which is exactly the stall you were trying to avoid.

The compiler's checklist (p. 46): the candidate must be independent of the branch decision — it must not produce a register the branch compares and must not be a branch itself — and safe to execute whether the branch is taken or not. It can come from three places.

From before: always a win

Take an instruction above the branch that the branch does not depend on and move it below. It had to execute on both paths, so the slot is useful whatever the outcome, with no safety condition beyond independence and no code growth. The notes' Example 2 (p. 48) in the papers' mnemonics: the ADD writes R1 and reads R2, R3; the branch reads R2 and R4; nothing links them.

ADD  R1, R2, R3
BEQ  R2, R4, L1
NOP              # delay slot

BEQ  R2, R4, L1
ADD  R1, R2, R3  # delay slot

From the target: a bet on "taken"

When nothing independent sits above the branch, copy the first instruction of the target into the slot and retarget the branch to the instruction after it. Taken, the slot did exactly what came next — for a loop, almost every time. Not taken, the slot instruction executes all the same, so it must be harmless on the fall-through path: typically it writes a register that path overwrites before reading. The notes' Example 3 (p. 49), with the loop made explicit:

L1:  SUB  R4, R5, R6
     ADD  R1, R2, R3
     BEQ  R1, R0, L1
     NOP              # delay slot

L1:  SUB  R4, R5, R6  # kept: first entry
L2:  ADD  R1, R2, R3  # new target
     BEQ  R1, R0, L2
     SUB  R4, R5, R6  # slot: the copy

The SUB now exists twice — the instruction duplication of p. 50. Only this branch is retargeted, to L2; the original stays at L1, because the first entry into the loop and any other branch that jumps to L1 still need it there. The price is code size and two copies to keep consistent; the gain is one cycle on every taken iteration — why the notes recommend it for loops, "particularly do-while constructs".

The example also hides the stall of section 1: ADD R1, R2, R3 produces R1 and BEQ R1, R0, L1 tests it in the very next cycle. Any instruction between the two would cure it; the quiz asks about this.

From the fall-through: a bet on "not taken"

The mirror bet moves the instruction that follows the branch on the sequential path into the slot. Not taken, the slot was needed anyway; taken, it still executes, so its result must be dead on the target path. The notes' Example 4 (p. 51): OR R7, R8, R9 is the fall-through instruction, SUB R4, R5, R6 at L1 the target.

     ADD  R1, R2, R3
     BEQ  R1, R0, L1
     NOP              # slot
     OR   R7, R8, R9  # not taken
L1:  SUB  R4, R5, R6  # taken

     ADD  R1, R2, R3
     BEQ  R1, R0, L1
     OR   R7, R8, R9  # slot
L1:  SUB  R4, R5, R6

The condition: R7 is not read at L1 or after it before being written again. Rarely-taken forward branches are the natural customers.

What the slot really costs, and why RISC-V has none

Two background facts complete the picture. A variant in which the slot is squashed exists — the cancelling branch (MIPS "branch likely"), whose slot executes only if the branch goes the predicted way: "from target" fills become safe, at the price of a flush when the prediction fails. And the slot writes the depth of one pipeline into the instruction set: a deeper pipeline has several bubbles and one slot hides only the first, a superscalar front end would need several slots, and an exception in the slot of a taken branch must restart at two non-adjacent addresses. Compilers fill a single slot usefully only about half of the time (Hennessy & Patterson: about 60 % filled, 80 % of those useful).

The exam's convention: "branch solved in ID stage, 1 cycle delay slot"

Now read the sentence every VLIW exercise of the 2024, 2025 and 2026 papers repeats: "The branch is completed with 1 cycle delay slot (branch solved in ID stage). No branch prediction." "Solved in ID" is early evaluation, hence the integer unit's "2 cycle latency to next Branch". "1 cycle delay slot" is the bubble of that pipeline, counted as a cycle of the iteration and written as "(delay slot)" in the row after the branch; nothing is scheduled in it, because the branch is the last instruction of the iteration and the exercise forbids the loop transformations that would move an instruction past it. "No branch prediction": the fetch after the slot waits for the ID-stage decision. The 2026 paper's LOOP1 (lesson 20 derives it):

In every exam table the delay slot is a cycle you count: the branch goes two cycles after the ADDUI that it tests, the slot is the next row, and the critical path ends there.

The puzzle, solved

The number in the hook is the branch offset. The June 2025 BNE points back to LOOP, its offset is negative, and a predictor that reads that bit says "taken": right on four iterations, wrong at the exit. The midterm BEQ points forward to DONE, its offset is positive, the same predictor says "not taken" and is right 100 times out of 101 — "always taken", blind to the sign, is the one wrong 100 times. The three lost cycles of the basic pipeline are the distance from IF to the end of ME; the course's pipeline moves the decision to ID, pays one, and the delayed branch gives even that cycle a job.