Load-Store Ordering and Memory Disambiguation in a Speculative Machine

Renaming solves the register namespace problem by giving every written value a private name. Memory has no such luxury. There is exactly one address space, and a store to 0x1000 is visible to any later load from 0x1000 regardless of which instruction happened to execute first. The hardware therefore cannot rename memory in the same sense it renames registers; it must instead reason about whether two memory operations can touch the same bytes.

That reasoning is the entire job of the load-store unit’s ordering machinery, and it runs under a handicap no register scheme faces: at the time a load is issued, the address of a store ahead of it may not be known, because that store’s address is itself the result of a computation that has not finished.

The four memory hazards

Using the same classification as registers, with read meaning load and write meaning store:

Hazard	Pattern	Real?
RAW	load after store to same address	yes
WAR	store after load from same address	no, if the load already read
WAW	store after store to same address	no, if the later store wins
RAR	load after load	no, both may proceed together

A load that runs ahead of an older store to the same address reads stale data — a RAW violation, which is a correctness bug. A store that runs ahead of an older load to the same address is a WAR, and it is harmless provided the load has already obtained its value; if the load has not yet read, the store must not pass it. A store that passes an older store to the same address is a WAW, harmless if the older store is not yet visible and the program order of the writes is preserved in the cache. Loads never conflict with loads.

Memory ordering therefore reduces to one hard case, load-versus-older-store, and one bookkeeping case, store-versus-older-store (which is handled by a store queue that commits in order).

The load path, step by step

A load is issued to the address generation unit, which computes the effective address from its renamed operands. Then:

1. Look up the store queue. Every pending store whose address is known is compared against the load’s address. A match with an older store to overlapping bytes means the load must either take the value from the store queue (store-to-load forwarding) or wait. Forwarding is possible only when the load is fully contained within the store, at the same alignment; partially overlapping or misaligned cases usually force a stall or a replay.
2. Check against stores with unknown addresses. If any older store has not yet computed its address, the load cannot be proven safe. The design either stalls the load or speculates that no conflict exists and records the possibility of a violation.
3. Access the data cache. The L1 is virtually indexed in most designs so the index can be computed before translation completes; the tag and physical address are checked after translation.
4. Record the load in the load queue. The entry retains the address and the load’s position in program order so later checks can reference it.

Step 2 is where the interesting designs differ.

Speculating past unknown addresses

Stalling on every older store with an unknown address would be prohibitively expensive: store addresses depend on loads (pointer chasing writes), so the dependency is cyclic in ordinary code. The standard answer is to let the load proceed, then verify.

Verification happens in two places. When an older store’s address finally becomes known, the store compares against the load queue; if it matches an already-executed younger load, that load was incorrectly ordered and must be replayed. Separately, when a load is retired or when it is issued, the hardware may consult a predictor that says whether this load has historically conflicted with an older store.

Two prediction strategies have been used:

• Store sets. A per-load predictor records which stores have conflicted with it before, and forces the load to wait for exactly those stores rather than for all of them. This preserves the dangerous cases while removing the serialization that an “all loads wait for all stores” policy would impose.
• No speculation at all. Loads wait for older stores’ addresses. Simple, safe, and poor for pointer-chasing workloads.

The cost of getting it wrong is a pipeline replay: the load and every instruction depending on it re-execute. Because a replay can cascade — a load that is replayed late may have already propagated a wrong value into dependent arithmetic — the recovery is generally a squash to the load’s ROB entry, not a local fix.

The store queue as an in-order write buffer

Stores cannot be performed speculatively because their effect is externally visible. Instead a store is “executed” when it has its address and data, and enters the store queue, where it stays until retirement. At retirement the store leaves the queue and is written to the data cache, in program order. This is why the store buffer in an out-of-order machine is architecturally the same construct as in an in-order one: it is the mechanism for deferring writes without reordering them.

The queue is sized independently of the reorder buffer and is typically much smaller, which matters for store-heavy code as noted in The Reorder Buffer and In-Order Retirement. A store that cannot enter the queue blocks allocation, and the effect propagates backward to fetch.

Two further constraints come from the memory system:

• Write-back caches with one write port. A retiring store that misses must allocate a line; if all miss buffers are full, retirement stalls even though the pipeline behind it is empty.
• Store-to-load forwarding across widths. Forwarding a 4-byte store into an 8-byte load requires merging with data from the cache or an older store, and implementations frequently decline, forcing a replay. Compilers that know about this align and size their stores accordingly.

Coherence and the ordering of a single store

The load-store machinery described so far operates within one core. Across cores, the observation order of stores matters, and that is governed by the memory model rather than by the queue.

A release store, or any store under a sequentially consistent model, must not become visible before the memory operations that precede it — which means the model’s ordering constraint imposes a serialization that a speculative machine would like to break. The mechanism that enforces it is usually a fence that waits for the store queue to drain, or a dependency-tracking scheme where stores carry ordering annotations checked at retirement. The consequence is that fences are much more expensive than they look: a fence is a demand that the out-of-order engine behave in order, and the cost is proportional to how far ahead the machine has run.

The memory consistency rules themselves are out of scope here; what matters is that the queue depth determines how long a fence can take, and that a machine which reorders aggressively pays more for the same fence.

A conformance test for the ordering rule

Specification test suites for these mechanisms are usually small litmus tests. The following C fragment is an adaptation of the standard message-passing shape, written as a plain function that a checking tool would examine under a given memory model.

/* Two-thread message-passing shape for the property the hardware must
   preserve: a consumer that observes the flag must also observe the data
   written before it. The assertion encodes the ordering requirement. */
#include <stdatomic.h>
#include <assert.h>

static _Atomic int flag;
static int data;

static void producer(void)
{
    data = 42;                        /* plain store */
    atomic_store_explicit(&flag, 1, memory_order_release);
}

static void consumer(void)
{
    if (atomic_load_explicit(&flag, memory_order_acquire) == 1)
        assert(data == 42);           /* must hold under release/acquire */
}

Under a release/acquire pair the assert cannot fail. If the store to data were allowed to become visible after the flag, a consumer could see the flag and read a stale data, which is exactly the failure mode that hardware disambiguation between an older store and a younger load must prevent within a single thread’s window. The out-of-order machinery and the memory model describe the same constraint at different granularities.

Where the mechanism degrades

Store queue full. Throughput of store-heavy scalar code such as memcpy or initialization loops is bounded by the store queue and the retirement rate, not by the load path. This is why wide store support — two stores per cycle, larger queues — is a recurring microarchitectural feature.

Mispredicted independence. A load that speculates past a conflicting store pays the replay cost for the whole dependent slice. Workloads with irregular aliasing, such as hash-table probing, show this frequently. Consolidation of pointer arithmetic into wider loads helps; so does eliminating redundant loads, which is a compiler duty.

4K aliasing. Two addresses that are congruent modulo a page size may collide in the cache’s set index or in an incremental address comparator even though they are distinct. Designs that compare only a subset of address bits for speed produce false dependencies and false replays; designs that compare full addresses take longer. Neither choice is free.

False wakeups for load consumers. Because a load’s latency is not fixed, the wakeup path in Issue Queue Wakeup and Select cannot know when its result will arrive. A consumer woken on the nominal latency reads a register that has not been written and must be replayed along with everything that depended on it. The load queue therefore holds both the address check for real conflicts and the timing information for this second, unrelated class of replay.

Self-modifying code. A store that modifies an instruction stream makes the contents of the front end’s fetch stage stale. Coherence does not track instruction fetches, so architectures specify that such a store requires an explicit synchronization — an instruction cacheflush or an architectural serializing event — before the new code may execute. On an out-of-order machine the flush has to wait for the store queue to drain and for the pipeline to be emptied.

What all these share is that the hardware is guessing about an address space it cannot rename. The load queue and store queue are the substitutes for a rename table, and every improvement in memory disambiguation buys throughput by accepting a bigger recovery cost when the guess is wrong.