A CPU works on several instructions at once
A splits an instruction’s work into steps, and works on a different instruction in each step at the same time. The classic MIPS pipeline has five :
| stage | does |
|---|---|
| IF | fetch the word at the PC; PC + 4 |
| ID | decode it; read the registers it names |
| EX | compute: the sum, the address, the branch decision |
| MEM | read or write memory (loads and stores only) |
| WB | write the result into the destination register |
Every cycle, each instruction moves one stage to the right and a new one is fetched. Five instructions can be in flight at once.
What has already happened when a branch decides
Follow a taken beq through the pipeline. It is fetched in cycle 1. In
cycle 2 it is decoded, and that is when the CPU learns it is a branch and
decides it is taken. But in that same cycle 2, the fetch stage has already
fetched the next word. It is in the pipeline. What now?
What MIPS does: the slot completes, then the target enters
When the branch decides in cycle 2, what is already in the pipeline?
| instruction | cycle 1 | cycle 2 ★ | cycle 3 | cycle 4 | cycle 5 | cycle 6 | cycle 7 |
|---|---|---|---|---|---|---|---|
| beq $t0,$t1,targetthe branch | IF | ID | EX | MEM | WB | ||
| addiu $t0,$t0,1the delay slot | IF | ID | EX | MEM | WB | ||
| addiu $t0,$zero,99never fetched: the PC had already moved | |||||||
| sw $t0,4($t9)the target | IF | ID | EX | MEM | WB |
- IF
- ID
- EX
- MEM
- WB
- killed (hatched): never writes back
- ★ the cycle the branch decides
Cycle 1: the branch is fetched (IF). The pipeline does not yet know it is a branch.
What to notice
In cycle 2 the branch decides (★) while the orange slot is already in IF. MIPS lets it continue: it goes on to ID, EX, MEM, WB like any instruction. The target enters IF in cycle 3, right behind it. The third instruction is never fetched at all: the PC had already moved.
MIPS’s answer was: let it run, and make that a rule. The architecture defines that the instruction after a branch or jump always executes, and only then does the PC move. That instruction’s position is the delay slot.
The other choice: squash it
A CPU could instead throw the fetched instruction away. That is called a . The same branch, on a core that squashes:
What a squashing core does: the slot is killed
What does the squash cost, and what does it save?
| instruction | cycle 1 | cycle 2 ★ | cycle 3 | cycle 4 | cycle 5 | cycle 6 | cycle 7 |
|---|---|---|---|---|---|---|---|
| beq $t0,$t1,targetthe branch | IF | ID | EX | MEM | WB | ||
| addiu $t0,$t0,1the delay slot | IF | ||||||
| addiu $t0,$zero,99never fetched: the PC had already moved | |||||||
| sw $t0,4($t9)the target | IF | ID | EX | MEM | WB |
- IF
- ID
- EX
- MEM
- WB
- killed (hatched): never writes back
- ★ the cycle the branch decides
Cycle 1: the branch is fetched (IF). The pipeline does not yet know it is a branch.
What to notice
Same cycles, one difference: after the decision, the slot’s remaining stages are hatched. It never writes back. The target still enters in cycle 3, so the cost is one empty cycle per taken branch. The gain is that the program need not know the pipeline exists. RISC-V and almost every other ISA chose this.
What the rule costs, and what it gives
Because the slot always runs, four things follow:
- A useful instruction can be moved into the slot. An optimising compiler puts the instruction before the branch there, or one from the target, and the branch costs nothing. This was the whole point in 1985.
- When nothing fits, the slot holds a
nop. That is a wasted cycle, and a wasted word in memory. - A branch inside a delay slot is undefined. Two branches would each claim the same next instruction. MIPS calls the result unpredictable, and the site’s simulator halts on it.
$ra= jal + 8. The slot has already run when the call takes effect, so the return must land past it (§5.3).
Watch a real instruction in a slot do its work before the target runs:
A real instruction in the delay slot: it runs, and its effect lands before the target
If the instruction after a taken branch is not a nop, what happens to it?
program (address · word · instruction)
| PC → | 0xbfc00000 | 0x3c191000 | _start:lui $t9,0x1000 |
| 0xbfc00004 | 0x37390ff0 | ori $t9,$t9,0xff0 | |
| 0xbfc00008 | 0x24080001 | li $t0,1 | |
| 0xbfc0000c | 0x10000002 | b 0xbfc00018 | |
| 0xbfc00010 | 0x25080001 | addiu $t0,$t0,1 | |
| 0xbfc00014 | 0x24080063 | li $t0,99 | |
| 0xbfc00018 | 0xaf280004 | target:sw $t0,4($t9) | |
| 0xbfc0001c | 0xaf200008 | sw $zero,8($t9) |
registers — read · written this tick
console (what the doors printed)
▮tick 0 of 7
Nothing has run yet. The PC (program counter) points at the first instruction.
Tick 4 takes the branch. Tick 5 is the orange slot, addiu $t0,$t0,1, and $t0 turns green: 1 becomes 2. Only then does the PC jump to target. The instruction after the slot (99) is skipped. The console prints 2.
What to notice
Tick 4 takes the branch. Tick 5 is the orange slot, and $t0 turns green:
1 becomes 2. Then the PC jumps. The 99 after the slot is skipped, exactly
like everything between a branch and its target. The console prints 2.
Before reading on, decide:
An epilogue ends `addiu $sp,$sp,8` then `jr $ra` then `nop`. An optimiser moves the addiu into the slot: `jr $ra` then `addiu $sp,$sp,8`. Is the program still correct?
The nops in your dumps
Your toolchain compiles with -fno-delayed-branch. GCC is told not to fill
slots. It writes a nop under every branch and jump. Count them in the
fourteen reference dumps:
| in the 14 dumps | count |
|---|---|
| instructions | 1956 |
| branches and jumps | 211 |
nop | 230 |
slots holding anything but nop | 0 |
Across the full 34-build census, 1164 nops. Every one is a delay slot the
compiler could have filled, spent on purpose. The reason is your core. It
predicts every branch not taken and books its speculation on the branch
itself. So everything after a taken branch is squashed, slot included. A
squashed nop costs nothing; a squashed real instruction would lose its
effect. The compile tool checks that every slot is 0x00000000. The
engine’s “phase B” is the plan to let it run the slot properly.
The assembler has a say too. In crt0_mips.S, line 13 is
:
crt0 writes its own slots, so the nop after jal main at bfc00090 was
typed by hand. Without that directive GAS would move instructions or insert
nops itself.
Go deeper: why the slot was a mistake in the long run, and how Carolyne will learn it (phase B)
The delay slot bakes one fact about the 1985 pipeline into the instruction set: “exactly one instruction is fetched before a branch decides”. A deeper pipeline fetches two or three; a superscalar core fetches four per cycle; an out-of-order core fetches dozens ahead. Every later MIPS implementation had to keep the one-slot rule anyway, with extra hardware, for programs that were written for the old pipeline. Release 6 (2014) finally added branches without slots. RISC-V, designed in 2010, learned the lesson and left slots out from the start. That is what “delay slots leak the pipeline depth into the ISA” means.
Carolyne’s engine today squashes everything younger than a mispredicted
branch, slot included, so the compile tool holds every slot to nop. The
recorded phase B design: decode marks the lane after a branch as
is_delay_slot; the speculation tag is booked on the slot, while the
branch carries the tag its slot will book; the reorder buffer rolls back by
one more entry; and the branch station holds a branch’s issue until its
slot’s entry exists. The slot then survives every squash by construction,
and -fno-delayed-branch can go. The point of the design is that it is one
µop feature, delay_slot, read by the engine, with no MIPS name inside it.
Can you now explain it?
A pipeline fetches the next instruction before a branch decides. MIPS made that instruction part of the branch: it always executes, then the PC moves. Fill the slot with work or with a nop, never with a branch; links are +8; your core needs nops until phase B.
If you remember only three things
- Run it or squash it: MIPS chose run. Cheaper hardware in 1985, and a rule every MIPS core must keep since. RISC-V chose squash.
- Three consequences. A nop when nothing fits, no branch in a slot, and $ra = jal + 8 because the slot has already run.
- Your nops are deliberate. -fno-delayed-branch fills every slot with nop because your core squashes the slot; the compile tool checks it; phase B removes the need.
Now try to explain this one yourself: a MIPS core with a deeper pipeline decides branches in cycle 4 instead of cycle 2. How many instructions has it fetched when the branch decides? What must it do with them to stay a MIPS?
Go deeper: a model answer, once you have tried
Three: the slot and two more. The architecture says exactly one of them, the slot, executes; the other two must be squashed, because a MIPS program was written expecting only one instruction to run before the jump. So the deeper core needs the squash hardware after all, and must keep the slot alive: the worst of both choices. That is the cost of putting the 1985 pipeline into the ISA, and why Carolyne’s engine, which fetches far ahead, treats the slot as a special case rather than a free lunch.
Check your understanding
0/5 answered1.$t0 = 5. A taken `b` has `addiu $t0,$t0,3` in its delay slot. What does $t0 hold at the target?
2.Why did the original MIPS define the instruction after a branch as always executing?
3.The reader's toolchain compiles with -fno-delayed-branch, and every slot in the dumps is a nop. Why?
4.What does MIPS say about a branch placed in another branch's delay slot?
5.RISC-V has no delay slot. What does a RISC-V core do with the instruction it fetched after a taken branch, and what does that cost?