Precise Exceptions and Restarting a Pipeline Mid-Stream

An exception is only useful if the machine can describe, exactly, the state of the program at the moment it occurred. “The page fault happened somewhere around this instruction, with some registers already updated” is not a description a handler can act on. The requirement is that all instructions before the faulting one have completed, none after it has begun, and the saved PC names the faulting instruction itself. A pipeline violates that requirement by construction: at any instant, five instructions are at five different points, and several of them may have already written registers or issued memory operations.

Making the pipeline appear sequential is the precise-exception problem, and its solutions determine much of a processor’s structure. The two families are the commit point, in which results are held until they can be released in order, and the checkpoint, in which the state is saved and the pipeline rolled back.

What “precise” rules out

Consider a load that faults in MEM while an older store is in WB and a younger add is in EX. The handler needs the register file to contain the store’s effect if the store precedes the load in program order, and not to contain the add’s result if the add follows the load. The add is younger, so its result must be absent. But in a plain five-stage pipeline the add reaches WB one cycle after the load reaches WB, and the fault is signalled at the end of MEM — before either write-back has occurred. That ordering happens to work for the add. It fails for a case where the younger instruction is closer to write-back than the faulting one, which is exactly what happens when a multi-cycle instruction sits between them.

The formal statement is: at the exception point, the architectural state equals the state produced by executing the program up to and including the instruction before the faulting one, and the PC is the faulting instruction’s address. Anything else is an imprecise exception, and the handler must either be written to cope or the machine must be flushed and restarted from a much earlier point.

Two consequences follow. First, the pipeline must have a well-defined single instruction that is allowed to commit its results in a given cycle; call it the commit point. Second, all results produced before that point must be either already committed or held in a form that can be committed in order, and all results produced after it must be discardable without a trace.

The commit point as a structural choice

The simplest commit point is write-back. A five-stage pipeline writes the register file only in WB, so the instruction in WB is the oldest, and everything younger is still in flight and has not yet changed architectural state. If an exception is detected in a younger instruction, the machine can squash everything younger than WB, wait for the instructions in EX and MEM to finish or be flushed, and take the exception with a PC that points at the faulting instruction.

This works because register writes are the only architectural side effect that can happen before WB. Memory writes are the exception: a store that has reached MEM has already written memory in a write-through design. The standard fix is to buffer stores and release them at the commit point, so that memory state also becomes precise. The store buffer holds the address and data of each committed- but-not-yet-written store, and the ordering guarantee is that stores leave the buffer in program order. This is where the commit point turns into a queue rather than a single stage, and it is why the interlock and bubble-injection machinery has to be able to hold a younger instruction indefinitely without losing its place in that order.

Deeper and wider machines push the commit point later and make it explicit. A reorder buffer holds every in-flight instruction’s result until retirement, and retirement happens in program order at a rate of the machine’s width. The commit point is then the head of the reorder buffer, and the exception logic is a matter of walking the buffer to find the oldest instruction with a pending fault and squashing everything behind it.

Why the restart PC is not just the faulting instruction’s address

The subtle part of restart is that the faulting instruction may have partially executed. A load that faults on its data access has already computed its address and may have written nothing; restarting it is safe. A store that faults after having updated a cache line is not safe to restart unless the write can be undone. A multi-cycle multiply that faults is not a real case, but an instruction that faults during a page-table walk has already modified the hardware page-table walker’s state.

The general requirement is that the machine expose a restart point at which re-executing the faulting instruction produces the same result as the original execution would have. For most instructions this is the instruction’s own PC. For instructions with partial side effects, the architecture must either guarantee that the side effect is invisible until the instruction commits, or define a different restart point.

A pipeline makes this harder than a serial machine because the fault may be detected in one stage while the instruction is already in another. The load that faults in MEM is, by that point, past EX; its address register has been read and its destination register has been reserved. Restarting it means re-reading the address, which is fine, and releasing the reservation, which the exception logic must do explicitly.

/* Squash everything younger than the faulting instruction and set the restart
   PC. `stages` is indexed from oldest (WB) to youngest (IF). */
void take_exception(struct pipeline *p, int fault_stage, unsigned long pc,
                    unsigned cause)
{
    for (int s = fault_stage; s <= IF; s++)
        p->stages[s].valid = 0;            /* the faulting insn and younger: discard */
    p->restart_pc = pc;                    /* re-execute the faulting insn */
    p->cause = cause;
    p->pc = p->handler_vector;
}

The loop’s direction is the whole point. The faulting instruction and everything younger than it is discarded, which means the stages from the fault forward to fetch, not the stages between the fault and write-back. Confusing the two produces a machine that discards the instructions that had already completed, which is a silent correctness failure rather than a crash.

Imprecise exceptions and why they were tolerated

Some early machines did not maintain precision. A floating-point exception raised by an operation in a long-latency unit might be reported several instructions after the operation issued, by which time the intervening instructions had committed. The handler then sees a state that corresponds to no program point: results from instructions after the faulting one are present.

The software workaround is to make the handler restart from a point before the faulting instruction and re-execute the intervening instructions, which requires that they be idempotent or that their effects be recoverable. That is expensive and error-prone, and it is why architectures converged on precision. The cost of precision in hardware is the reorder buffer or the store buffer plus the squash logic; the cost of imprecision in software is a class of bugs that appear only when a floating-point operation traps in the middle of a dependent sequence.

The interaction with speculation

Once the front end fetches past a predicted branch, the instructions in flight include ones that may never belong to the program. The exception machinery must therefore distinguish three categories: instructions that have committed, instructions that are in flight on a path that is still live, and instructions that are on a path that has been abandoned.

The commit point handles the first category by definition. The third category is handled by marking the pipeline registers invalid on a misprediction, exactly as the exception squash does. The second category is the one that requires care: a live instruction that faults must take its exception at the right program point even though younger instructions are present, and the branch that was predicted correctly must not be disturbed.

This is why the reorder buffer records, for each instruction, whether it has completed and what its exception status is. Retirement walks the buffer in order, and the first entry with a pending exception triggers the squash of everything behind it. Instructions ahead of it have already retired and cannot be undone, which is correct because they precede the fault in program order. The mechanism is the same one described in control hazards and branch penalties, applied to a different trigger, and it is why the two problems are usually solved by the same structure.

Cost, and the cases where precision is not needed

Precision is not free. A store buffer adds an associative lookup on every load to check for a matching pending store, and that lookup is on the load’s critical path. A reorder buffer adds a wide, deeply indexed structure with in-order allocation and in-order retirement, plus the logic to compare destination tags against every pending source. The area and the timing cost both scale with the number of in-flight instructions, which is why the reorder buffer’s size is one of the central parameters of an out-of-order design.

Some situations genuinely do not need precision. A debug trap that stops the machine can report an approximate state if the debugger is prepared to single-step from a known point. A fatal machine check does not need a restartable state at all, because the machine is not restarting. An asynchronous interrupt has no faulting instruction, so the “precise” requirement reduces to “commit everything that has already been fetched,” which is easier.

The interesting boundary is the one between an exception that the handler can fix and re-execute, such as a page fault, and one that terminates the instruction, such as an illegal opcode. Both need a precise PC; only the first needs the state to be restartable at that PC. Machines that get the first right and the second wrong produce handlers that work for demand paging and fail for emulation, which is a narrow enough failure to survive a long time in the field.