Delay Slots and the Burden They Move to the Compiler

A delay slot is a contract between the instruction set and the pipeline: the instruction at address PC+4 executes whether or not the branch at PC is taken. The hardware gets to keep fetching while the branch resolves, and the price is that every branch’s successor must be an instruction that is correct under both outcomes. On a machine with one delay slot, that price is a scheduling obligation incurred by every compiler and every assembly programmer; on a machine with two, as some early designs had, it is a harder obligation that the toolchain may not be able to meet at all.

The mechanism is worth understanding even for architectures that abandoned it, because the decision to expose or hide the branch penalty is the clearest example of a general architectural choice: whether a pipeline’s timing artefact becomes visible in the instruction set. The alternative, predicting the branch and recovering from a wrong guess, is covered in control hazards and branch penalties.

What the slot is, mechanically

The pipeline resolves a branch at the end of EX. In a machine without prediction, the front end has already fetched the two instructions behind the branch and must discard them. If the instruction set declares that the first of those two will execute unconditionally, the machine does not need to discard it: it can let it complete, and it only needs to squash the second. The branch penalty drops from two cycles to one, at the cost of one instruction’s worth of constraints on the software.

without delay slot          with one delay slot
beq  L1                     beq  L1
add  x3, x4, x5   (squashed) nop            <- executes either way
sub  x6, x7, x8   (squashed) sub  x6, x7, x8  (squashed)
L1: ...                     L1: ...

The slot instruction is architecturally committed. Its effects on registers and memory happen, its exceptions are taken, and it cannot be undone if the branch turns out taken. That last property is what makes slot filling hard: the instruction must be safe to execute on both paths, which is a semantic condition the compiler has to prove rather than a syntactic one it can check.

The slot must also be an instruction whose own execution does not depend on the branch outcome. The typical legal candidates are an instruction from before the branch whose result is not yet needed, an instruction from the taken target that is also correct on the fall-through path, or an instruction from the not-taken path that is idempotent with respect to the taken path. Anything else requires a no-operation, and a no-operation in the slot is exactly the bubble the slot was meant to remove.

The three ways to fill a slot

Compilers use three strategies, in increasing order of difficulty.

Fill from before the branch. Take an instruction that precedes the branch and whose operands are ready, and move it after the branch into the slot. This is safe whenever the moved instruction does not depend on the branch and is not the producer of a value the branch’s condition reads. It is the most common successful fill, and it works because most branches are preceded by independent work.

Fill from the target. Take the first instruction of the taken path and duplicate it into the slot, provided it is also correct when the branch is not taken. This requires that the instruction be safe on the fall-through path, which usually means it must not fault or must be guarded. A load from a pointer that is invalid on the fall-through path is not safe.

Fill from the fall-through. Take the first instruction of the not-taken path into the slot and replicate it at the target. This is the mirror image and has the mirror-image constraint.

In each case the compiler must also handle the case where no instruction qualifies, and it inserts a no-operation. Measurements of slot fill rates on early MIPS and SPARC compilers are the kind of number that varies enormously by benchmark, so the honest statement is that fill rates are high for straight-line numeric code and low for branch-dense control code, and the fraction of no-operations in slots is the measure of how much the mechanism actually bought.

/* Filling a delay slot: the move is independent of the branch condition and
   its destination is not read by the branch. */
int a[N], b[N], c[N];

for (int i = 0; i < N; i++) {
    if (a[i] != 0) {          /* branch on a[i] */
        c[i] = b[i] + 1;      /* taken path */
    }
    /* The loop increment is the natural delay-slot fill only when the
       compiler can prove c[i] is not read by the branch. */
}

The code above is the shape a scheduler reasons about, not a transformation it can always perform. The loop increment moves into the slot only if the branch reads nothing it writes, and if the increment itself cannot trap.

The interaction with exceptions

A delay slot that traps is a problem the architecture must define. If the slot instruction raises an exception, the saved PC points at the branch, and returning from the handler must not re-execute the branch as if the slot had not run. Architectures with delay slots specify this case explicitly: the exception’s return address is the branch, and the handler must know that the slot has already executed, or the architecture provides a separate restart mechanism.

The cleaner solution, adopted by later implementations of the same instruction sets, is to make the slot instruction’s exception restartable by recording enough state that re-execution is safe. This is easier when the slot instruction has no side effects other than its register write, and harder when it is a store, which is why stores in delay slots are frequently forbidden or handled by a special case.

A second interaction is with the branch itself. A branch whose condition depends on the instruction in its own delay slot is a defined hazard on most such architectures and produces an undefined result on some. The compiler must never place such a pair, and the assembler may not diagnose it.

Why the mechanism was abandoned

The delay slot solves a hardware problem by exporting it. That trade looked good when the alternative was a full pipeline drain, and it looked worse as pipelines deepened. On a machine that resolves branches later, the number of required slots grows, and the probability that a compiler can fill two or three consecutive slots with safe instructions falls quickly. A two-slot architecture with a low fill rate has simply moved the bubbles from hardware into the instruction stream, where they consume fetch bandwidth and instruction cache space.

Prediction offers the same benefit with no software obligation. A predicted branch lets the front end continue on a guessed path, and a correct guess costs nothing at all — better than a delay slot, which still consumes a slot. The wrong guess costs the same as the unpredicted case. Once branch prediction became cheap in area, the delay slot’s advantage over prediction disappeared, and the architectural cost of exposing the pipeline in the instruction set became pure loss.

The remaining argument for delay slots is compatibility and decode simplicity: a slot costs no hardware at all, whereas a predictor costs tables and recovery logic. That argument holds for small embedded cores, and it is why variants of delay-slot architectures remain in that space while high-performance designs from the same lineage dropped them.

What the slot taught about scheduling

The delay slot is the earliest systematic case of the compiler being asked to schedule for a specific pipeline. The techniques it forced into compilers — dependence analysis between the branch and its neighbours, the notion of a safe instruction that cannot trap, and the machinery for moving an instruction across a control-flow edge — are the same techniques that later became standard in instruction scheduling for wide and deeply pipelined machines. A scheduler that fills delay slots is a scheduler that has to reason about basic-block boundaries, and once a compiler can do that it can also schedule loads ahead of their uses to cover the load-use penalty.

The lesson for the pipeline designer is the inverse: any timing artefact that is exposed in the instruction set becomes a permanent constraint on every implementation that must remain compatible with it. A later machine with a different depth cannot reduce the slot count without breaking binaries, and cannot increase it without a new instruction set. Hiding the artefact behind an interlock keeps that freedom, at the cost of hardware that the compiler cannot see. The choice between the two is a bet on how much the pipeline will change, and the history of the 1990s is a long argument that pipelines changed a great deal.