MerceMay.Technical Library

Computer Architecture · Out-of-Order Execution

The Reorder Buffer and In-Order Retirement

How entries move through the reorder buffer from allocation to commit, why retirement order is what makes speculative and out-of-order execution safe, and what limits the buffer size.

Archive date May 13, 2026 · 8 min read · foundational

Execution order and architectural state are two different things. An out-of-order machine executes instructions in whatever order their operands become available, but the program it presents to the outside world must behave as if each instruction completed before the next one started. The reorder buffer is the structure that reconciles the two: it holds results out of order and publishes them in order.

A FIFO with a random-access middle

The reorder buffer (ROB) is a circular queue of entries, allocated in program order at the far end of the front end and released in program order at the retirement stage. Each entry typically carries:

  • the instruction’s program counter or an identifier that can produce it;
  • its destination, as a physical register number or a memory address, or a marker for neither;
  • a done bit and, in some designs, the result value itself;
  • a small amount of exception and branch bookkeeping.

The head of the queue is the oldest unretired instruction. Retirement — also called commit — examines the head each cycle and, if the entry is done and has not been squashed, makes its effect architecturally visible: the physical register it wrote becomes the architectural value of its destination, its store is released to memory, and its exceptions are raised if any. Then the head advances. A machine that can retire n instructions per cycle examines the oldest n contiguous done entries.

Everything between allocation and retirement is unordered. An entry can complete in any cycle; entries complete out of order, sit finished, and wait for the queue to drain to them.

Why retirement granularity is the safety property

The core argument for in-order retirement is that speculation requires a recovery point. A branch predicted taken may in fact not be taken; a load may be replayed because it raced a store. When that happens, all younger instructions must disappear without having changed anything anyone can observe. If architectural state could be updated as instructions execute, a squashed instruction’s writes would already be visible and would have to be undone — and undoing a store to memory is impossible without an undo log.

In-order retirement makes “younger” a well-defined boundary. At any moment the machine has an architectural state (everything up to the head) and a speculative state (everything after). A squash discards entries younger than the recovery point and rebuilds the rename table from a checkpoint; the architectural state was never touched. The mechanism for precise exceptions falls out of the same structure, since the head of the queue is by definition the oldest instruction and therefore the one whose exception must be taken first.

There is a second, less obvious benefit: in-order retirement is what makes the physical register file reclaimable. Because entries leave in order, the free pointer of a circular physical register file can advance with the head, as noted in Register Renaming and the Elimination of False Dependencies.

Allocation, and what happens when it fails

The ROB is allocated at rename, at the same rate and in the same order. If the queue is full, the front end stalls — but a stall is not a single condition. The instruction at the allocation point may be blocked by any of:

  • no free ROB entry;
  • no free physical register for its destination;
  • no free entry in the load or store queue if it is a memory operation;
  • no free slot in the issue queue for its class of instruction.

These are separate resources with separate sizes, and the smallest one determines the effective instruction window. A machine with 300 ROB entries, 200 floating-point issue queue entries, and a 64-entry store queue becomes a 64-entry machine for store-heavy code. This is why specifications of window size in terms of a single number are misleading, and why microarchitectural analyses probe with different instruction mixes.

The relation between ROB size and window size is subtle: the ROB holds all unretired instructions, including finished ones waiting for their turn to retire. If retirement is narrow, completed entries accumulate at the head and the buffer fills with instructions that have already done their work, throttling the fetch of new work. A wide machine therefore needs a retirement width comparable to its issue width, or the queue backs up from the wrong end.

Retirement is not just bookkeeping

Because retirement is the only point at which the machine knows an instruction is real, several functions attach to it.

Store visibility. Stores are held in the store queue from execution until retirement, then released to the memory order buffer in program order. This is what keeps the memory system from observing speculative stores. The details are in Load-Store Ordering and Memory Disambiguation.

Interrupt and exception delivery. When the head entry indicates a fault, retirement stops, younger entries are squashed, and control transfers to the handler with the architectural state of the instruction before the faulting one. Because the head is the oldest, the exception is precise by construction, which is the subject of Precise Exceptions from an Imprecise Machine.

Self-modifying code and serializing operations. Instructions that require ordering with respect to all preceding instructions — a fence, a cache invalidation, a write to a control register — must wait for the ROB to drain, or nearly drain. These operations are rare but extremely expensive, and their cost scales with the buffer size and with the latency of the pipeline behind it.

Performance counters and profiling. Retiring an instruction is the natural point to attribute an architectural event, which is why retired-instruction counts are the canonical denominator for IPC figures.

Sizing: the queueing argument

The ROB is a queue with a service rate equal to the retirement width and an arrival rate equal to the issue width, in the absence of stalls. To sustain issue, the queue must absorb bursts. In steady state with the head always ready, the queue depth equals the number of instructions in flight, which is the product of instructions per cycle and cycles of latency being hidden — Little’s law applied to the window as a whole.

Two design pressures pull in opposite directions:

  • Larger is better for finding parallelism and hiding latency, because a larger window covers more code and therefore more independent work.
  • Larger is worse for cycle time and energy, because allocation, tag comparison, squash, and head-pointer management all touch the whole structure. Squashing on a misprediction typically invalidates every entry younger than the recovery point, and a wider buffer makes that a bigger operation unless it is organized hierarchically.

The standard mitigation is to make squash a pointer operation rather than a per-entry sweep: entries younger than the recovery point are simply not examined, and the free pointers are restored to saved values, which is exactly what the checkpoint mechanism in Checkpointing and Recovery from Misprediction does.

A model of the queue

The following model in C makes the accounting explicit: allocation, out-of-order completion, and in-order retirement, with a fixed buffer and a retirement width.

#include <stdio.h>
#include <stdbool.h>

#define ROB_SIZE 16
#define RETIRE_WIDTH 2

struct entry { int seq; int cycles_left; bool done; };

int simulate(int *out, int n, int issue_width)
{
    struct entry rob[ROB_SIZE];
    int head = 0, count = 0, next = 0, cycle = 0;

    while (next < n || count > 0) {
        int allotted = ROB_SIZE - count;
        int dispatched = 0;

        /* allocation in program order, bounded by buffer space and width */
        while (dispatched < issue_width && next < n && allotted > 0) {
            int slot = (head + count) % ROB_SIZE;
            rob[slot] = (struct entry){ .seq = next, .cycles_left = out[next], .done = false };
            count++; allotted--; dispatched++; next++;
        }

        /* execution: every unfinished entry advances independently */
        for (int i = 0; i < count; i++) {
            struct entry *e = &rob[(head + i) % ROB_SIZE];
            if (!e->done && --e->cycles_left <= 0) e->done = true;
        }

        /* retirement: only contiguous done entries from the head */
        int retired = 0;
        while (retired < RETIRE_WIDTH && count > 0 && rob[head].done) {
            head = (head + 1) % ROB_SIZE;
            count--; retired++;
        }
        cycle++;
    }
    return cycle;
}

Two properties are visible in the code. Retirement stops at the first incomplete entry even if later entries are done, which is the definition of in-order. And allotted couples allocation to retirement: a machine that retires slowly starves its own allocation, which is why retirement bandwidth matters as much as issue bandwidth.

With a latency profile where one instruction in five takes many cycles, the buffer fills and the head stalls on that instruction while entries behind it are complete — the signature of head-of-line blocking. The queue must be large enough that the stalled head is not blocking a nearly empty buffer; the classic result is that throughput degrades sharply once the buffer is smaller than the product of latency and width.

Edge cases that shape real designs

Partial retirement. A misaligned instruction or an entry whose result is not yet available can prevent retirement of a group that otherwise could commit. Designs either allow the group to shrink or hold the whole group, with different costs on the next cycle.

Microcoded instructions. Instructions that expand into many micro-operations occupy far more ROB space than their count in the binary suggests. A single string operation can consume dozens of entries, collapsing the window for surrounding code.

Long-latency completion after squash. A floating-point divide or a cache-missing load can take hundreds of cycles. Squashing the instruction does not cancel the work; the result arrives later and must be discarded without writing anything. Designs tag results with the ROB identifier of their instruction so a late result for a dead entry is simply dropped.

Retirement under a store that misses. A store that misses in the cache at retirement may need a miss-status holding register before it can be released, and retirement stalls if none is free. This turns a cache-miss cost into a retirement stall that is invisible in the issue-stage statistics.

References

  1. Computer Architecture: A Quantitative Approach, 6th edition — Chapter 3 — Hennessy & Patterson; Morgan Kaufmann
  2. The Microarchitecture of the Pentium 4 Processor — Intel Technology Journal, Q1 2001
  3. Modern Processor Design: Fundamentals of Superscalar Processors — Shen & Lipasti; McGraw-Hill