The Reorder Buffer and Precise State
Execution finishes in whatever order the data allows. Something has to put the results back in order before anyone can see them — and that same something is what lets a page fault, an interrupt or a mispredicted branch unwind cleanly instead of corrupting your program.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Execution is not commitment
The single most useful distinction in this module: executed means the result has been computed; retired means the result is part of the architectural state. Between the two, a result is real enough to be forwarded to dependent operations but provisional enough to be thrown away without trace.
The reorder buffer is a queue in program order. Operations enter it at dispatch, in order. They complete in whatever order the data allows, marking their entries as finished. Retirement examines the *oldest* entry only: if it is finished, its result is committed and it leaves; if it is not, retirement waits — even if every younger entry is finished and idle.
That in-order head is what produces the guarantee. Since nothing younger can retire before something older, the architectural state always corresponds to a clean prefix of the program. There is never a moment where instruction 41 has committed and instruction 39 has not.
Recovery is free because nothing younger has committed
When an instruction raises a fault, the machine does not have to reconstruct anything. Every younger operation is, by construction, unretired — so it discards all of them, points the program counter at the faulting instruction and hands control to the OS. The architectural state already reflects exactly the instructions before the fault. This is what "precise exception" means, and it is the reason a page fault can be serviced and the instruction transparently restarted (The Page-Table Walk: Dependent Loads All the Way Down).
Branch misprediction uses the same machinery. Speculatively executed work sits unretired in the buffer; when the branch resolves the wrong way, the younger entries are flushed and fetch restarts on the correct path. The cost is the discarded work and the time to refill the window, which is exactly the penalty Misprediction: What a Wrong Guess Costs quantifies.
The same property is what makes Speculative Execution: Doing Work Before You Know You Need It safe at the architectural level — and, crucially, what makes it *unsafe* at the microarchitectural level. Flushing removes the results, but it does not undo the side effects the speculative work left in caches and predictors. That gap is the entire basis of the speculative side-channel family (Side Channels: When Performance Optimisations Leak, Spectre and Meltdown: When Speculation Crossed a Boundary).
- Fault — flush younger entries, restart at the faulting instruction, let the OS handle it.
- Misprediction — flush younger entries, restart fetch on the correct path.
- Interrupt — retire up to a convenient boundary, flush the rest, take the handler.
- In every case — architectural state is a clean prefix; microarchitectural state is not restored.
The buffer is finite, and that has consequences
The reorder buffer has a fixed number of entries, and this creates a stall reason that surprises people. If the oldest entry is a load that missed all the way to DRAM, it cannot retire until the data arrives. Younger operations continue executing and filling entries — until the buffer is full. At that point dispatch stops, and the machine stalls even though execution ports are sitting idle.
This is why a single badly-placed cache miss can cost far more than its own latency. It is not just that dependents wait; it is that the whole window drains into the buffer behind it and then the front end is blocked. The effect scales with how long the miss takes and how quickly younger work fills the remaining entries.
It also explains why memory-level parallelism matters so much (Misses That Overlap Are Nearly Free). If several independent misses are outstanding simultaneously, their latencies overlap and the head of the buffer clears after roughly one miss latency rather than several. A pointer chase, which can only ever have one miss outstanding, pays them end to end — which is the deeper reason behind Pointer Chasing: The Address You Do Not Have Yet being so much worse than its instruction count suggests.
Key points
- Executed means computed; retired means it counts. Everything in between can be discarded without trace.
- Retirement is strictly in program order, so architectural state is always a clean prefix of the program.
- Precise exceptions, working debuggers and safe speculation all fall out of that single property.
- Flushing restores architectural state but not microarchitectural state — the basis of speculative side channels.
- The buffer is finite: a long-latency operation at its head eventually stalls the whole front end.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Dispatch → buffer entry: every operation allocates an entry in program order, whether or not it can execute yet.
- 2Execution → completion flag: results are written to physical registers and the entry is marked finished, in any order.
- 3Retirement → architectural state: the oldest entry, if finished, commits its result and frees its entry.
- 4Blocked head → capacity stall: an unfinished oldest entry holds the queue, and once entries run out, dispatch halts.
- 5Fault or misprediction → flush: all younger entries are discarded at once, since none of them have committed.
- • "The instruction faulted, so everything after it partially ran." Nothing after it retired; the state is clean.
- • "Speculation is fully undone on misprediction." Architecturally yes, microarchitecturally no — caches keep the evidence.
- • "A cache miss costs one memory latency." At the head of a full buffer it can cost considerably more.
- • "Out-of-order means results appear out of order." Results appear strictly in order; only execution is reordered.
- • "A bigger buffer would always be better." It costs area and power, and only helps if there is independent work to fill it.
Consequences, controls and cost
- • A debugger can stop at any instruction and see exactly the state the source implies.
- • A page fault can be taken mid-instruction-stream and the instruction restarted transparently.
- • Mispredicted work costs cycles and window refill, but never corrupts results.
- • One DRAM miss at the head of the buffer can stall a core far longer than the miss latency alone.
- • Speculative execution leaves cache and predictor traces that flushing does not remove.
- • Increase memory-level parallelism so independent misses overlap instead of serialising at the buffer head.
- • Avoid long dependent memory chains in hot paths where the data structure permits an indexed alternative.
- • Reduce miss frequency generally — locality work pays double here, once for the miss and once for the stall behind it.
- • Nothing directly: buffer capacity is not exposed or adjustable, so the control is always indirect.
- • Look for stalls attributed to reorder-buffer or dispatch resource exhaustion in top-down counter categories.
- • Compare a pointer-chasing loop against an indexed one over the same data: the gap includes both serialisation and buffer stalls.
- • Count outstanding memory requests during a traversal where counters expose it; a value near one indicates no overlap.
- • Observe that adding independent work to a miss-heavy loop is nearly free until the buffer fills, then abruptly is not.
- • Restructuring for memory-level parallelism usually means changing the data structure, which affects insertion and memory footprint.
- • Prefetching to overlap misses costs bandwidth and can evict useful data if the prediction is wrong ([[prefetching]]).
- • The hardware itself trades area and power for window depth, which is why efficiency cores are much shallower.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICBuffer capacity, retirement width and how many memory requests can be outstanding are design choices that differ per core and generation. Deep desktop cores and shallow embedded cores behave very differently on the same miss-heavy loop.
- SIMPLIFIEDPresented as a single in-order queue. Real designs separate the reorder buffer from load and store queues, retire several entries per cycle, and use additional structures for memory disambiguation.