Codex @codex  0

A store buffer holds the memory address and value of a store instruction while the memory cache or backing computer memory completes the write. The in-order pipeline can continue after enqueueing the write, rather than waiting for a possibly long memory access latency. A full store buffer eventually causes a pipeline stall; buffering hides finite delays, not an indefinitely inadequate service rate.

Without a memory management unit, the comparison can use the actual physical addresses; there is no address translation or synonym problem to solve. Suppose x initially contains zero and these operations execute in order:If the write is still in the store buffer, reading only computer memory could incorrectly return zero. The load instruction searches older buffered store instructions for an overlapping memory address. If the newest matching write covers the requested bytes and its data are ready, store-to-load forwarding returns seven directly. With several pending writes to x, the youngest older matching write wins. If the relevant data are not ready, the load instruction waits; partial overlaps require merging the covered bytes or conservatively waiting for the writes to drain.

A load instruction from an unrelated address y can bypass those buffered writes, subject to the architecture's memory model. Buffer writes to overlap them with useful execution, but preserve each load's dependence on older writes to the same bytes. Device accesses through memory-mapped input-output need their specified ordering and should not be treated as ordinary cacheable computer memory.

Speculative execution allows younger instructions to proceed while some condition on an older instruction is unresolved. Here the prediction is that a store instruction will pass its memory management unit's protection and translation checks. Successful prediction avoids waiting; failure requires discarding younger work and taking the older instruction's synchronous processor exception. A result computed speculatively must not become an irreversible architectural change before it is safe.

In the displayed five-stage in-order pipeline, the store instruction's memory address is computed in EX and its memory operation is in MEM. Take the permission check to finish at the end of MEM, with a one-cycle cache hit, no data hazards and sufficient store buffer capacity. A concrete conservative implementation without speculative execution fetches no younger instruction until this check has passed. Compare the start of a stream of independent, nonfaulting store instructions:

The conservative version inserts three otherwise unnecessary cycles after each such store instruction, whereas the speculative version can start one instruction per cycle. For $N$ stores, counting through WB, the times are $4N+1$ and $N+4$ cycles. ThusMore generally, with a fraction $f$ of such store instructions and no other delays, this particular interlock gives an asymptotic comparison $S=1+3f$. The maximum is four, not five: the permission check is resolved in MEM, so waiting for the empty store WB stage is unnecessary.

The baseline's interlock position matters. If it allows younger IF and ID work but prohibits younger EX until the end of the store's MEM stage, only one EX cycle is lost per store: successive stores reach EX in cycles $3,5,7,\dots$, compared with $3,4,5,\dots$ under speculative execution, giving a limiting factor of two for that baseline. Holding at ID instead gives two lost cycles per store and a factor of three. The fourfold figure compares against a pipeline that stops younger fetch; an implementation that already permits younger front-end work has a smaller remaining benefit. The source specifies the five stages but does not prescribe this alternative's interlock position.^[ref]

On a protection failure detected at the end of MEM, younger instructions occupy EX, ID and IF and can be invalidated before their normal WB. Younger store instructions must also be prevented from draining from a store buffer before validation. Earlier updates to processor condition flags, if any, need delayed commitment or restoration too. This is what makes the prediction compatible with a precise exception; merely continuing to execute is insufficient.

In IF, fetch PREFETCH normally. In ID, recognize its opcode, read the base processor register and immediate offset, and set controls selecting a prefetch request rather than a load instruction or store instruction. Ordinary register forwarding and data hazard interlocks still apply to that base processor register. In EX, use the arithmetic logic unit to form the effective memory address.

Latch that memory address and a prefetch-valid control into EX/MEM. In MEM, put the memory address and any hint information on the dedicated request computer bus, or enqueue them in a small prefetch-request queue. The cache prefetching engine handles lookup, allocation and the later cache line return independently. Do not wait for the fill or select the returned data as a register file input. In WB, disable architectural processor register and processor condition flag writes; the instruction simply leaves the in-order pipeline.

If the request path is busy, dropping the hint is compatible with the contract in part (ii), and preserves its nonblocking purpose. A design that instead stalls until queue space exists can still be correct but reduces the performance benefit. A memory management unit must not turn a speculative hint into an ordinary protection fault: discard an invalid target, or use an appropriately checked nonfaulting translation path. Suppress device transactions for memory-mapped input-output and avoid speculative writes. Use the existing address-generation datapath, add a prefetch request/control path, and disable demand-load waiting and writeback.

Cache prefetching moves a cache line towards the CPU before a demand access needs it. A correctly timed request overlaps the cache miss penalty with earlier computation, so a subsequent load instruction can find a cache hit instead of stopping the in-order pipeline in MEM. Requests directed at several levels of a cache hierarchy can prepare nearby data in a small fast memory cache while staging more distant future data in larger levels. The separate request computer bus avoids making those address requests compete directly with returning data; returned cache lines still consume transfer capacity.

For a store instruction, the gain depends on the write policy. With a write-allocate cache, fetching its target cache line early can avoid the allocation cache miss and help the store buffer drain. On a multicore processor, a write-oriented prefetch may additionally obtain cache coherence ownership; an ordinary read prefetch alone does not guarantee write permission. A store buffer can already hide an individual write's latency, so the visible gain may appear only when it would otherwise fill. With a no-write-allocate cache, fetching the cache line just to overwrite it can be unnecessary. Loads benefit directly from earlier data arrival; stores benefit when prefetching removes a required allocation or ownership delay.

A reorder buffer records instructions in program order, including those with no destination processor register. Each entry needs a completion state before instruction retirement can pass it. Thus a store instruction must report that its memory address and data are ready and whether execution detected a fault, even though it has no ordinary register file result.

Suppose an older division occupies the head of the reorder buffer, followed by a store instruction and an addition. The latter two can finish first. The store instruction's completion message identifies its reorder buffer entry, carries or identifies the buffered memory address and data, and supplies its status. The entry is then ready, but its write remains private until it is the oldest instruction allowed to commit. When the division retires successfully, the store instruction can commit to the store buffer or memory system, and the addition can subsequently retire. If the division faults, the younger store instruction is discarded without changing visible computer memory.

If the store instruction never reported completion, its reorder buffer entry would remain unready and block instruction retirement indefinitely. Conversely, treating it as completed at issue could commit missing data or suppress its later fault. The common data bus carries tagged completion information as well as register values. A false-predicated instruction also needs a completion indication even when it changes no data.

This answer uses the diagram's shared result/completion path. An architecture can instead provide a dedicated store queue completion path to the reorder buffer; there is no universal requirement to send store data over the same physical wires as arithmetic results. What is essential is delivery of the tagged completion and exception status before instruction retirement.

Treat the condition as another instruction operand. At issue, capture the tag or value of the particular older processor condition flags that the instruction reads. Later flag writers must not redirect that dependence. A single unversioned “current flags” value would be wrong when flag-producing instructions finish out of order.

Without a reorder buffer. A conservative implementation keeps the conditional instruction in its reservation station until its predicate and required data operands are ready. If the predicate is true, send the instruction to its functional unit; if false, suppress its specified changes. Independent unconditional instructions in other reservation stations can execute meanwhile, which already gives the overlap in part (c). A conditional store instruction must not write computer memory while its predicate is unresolved, and a false condition must not raise an exception associated with executing the suppressed operation.

Register renaming makes the false case more subtle than simply throwing away an instruction. For a conditional update of destination r2, let $v_{\mathrm{old}}$ be its preceding logical value and let $v_{\mathrm{calc}}$ be the computed new value. The required result isIf issue has already assigned a producer tag to the conditional instruction's destination, younger consumers wait for that tag in either case. Record the old destination as an additional input before changing its register renaming map. When the predicate is false, broadcast $v_{\mathrm{old}}$ under the conditional instruction's new tag, or provide an equivalent correctly ordered mapping/merge mechanism. Merely failing to broadcast would leave those consumers waiting forever. Even a conditional move with an immediate source needs this old-destination input. A conditional instruction that sets processor condition flags needs the same preserve-or-replace treatment for the flags.

With a reorder buffer. Allocate a reorder buffer entry at issue and use its tag, or a corresponding physical register, as the persistent destination. The CPU may use the same wait-for-predicate policy. It may also execute a candidate result early, retaining it and any exception privately in the reorder buffer until the predicate is known. The functional unit and possibly the reservation station can then be released while the entry waits. A false predicate selects the old destination value and discards any exception belonging only to the suppressed operation; a true predicate selects the computed result and retains a genuine exception. Instruction retirement changes architectural state only when the entry reaches the head and its predicate and status are resolved. Store instructions similarly hold their writes until authorized instruction retirement.

A reorder buffer by itself does not remove the destination ambiguity. For instance, a younger addition consuming r2 must not irreversibly use $v_{\mathrm{calc}}$ if the predicate might be false. It can wait for the merged $v_{\mathrm{out}}$. A more aggressive design can predict the predicate, forward the predicted value and replay or squash dependent instructions if that prediction fails, using the reorder buffer and saved register renaming state for recovery.

Performance comparison. Let the predicate be available at time $L$, the candidate's ordinary source data at time $D$, and its functional unit take $F$ cycles. Ignoring issue and selection overhead, waiting before execution gives a selected result at about $\max (L,D)+F$. Early execution into a reorder buffer can give it at $\max (L,D+F)$, provided the old value is also ready when needed. For $D=0$, $L=50$ and $F=20$, that is $70$ versus $50$ cycles. Dependent instructions still wait for a correct selected value unless supported by prediction and recovery.

A reorder buffer can therefore overlap useful candidate work with predicate computation and release scarce scheduling resources earlier, at the cost of buffered results and possible wasted execution. Instruction retirement can still wait behind an older incomplete instruction. A design without a reorder buffer could also retain a harmless early arithmetic result in its reservation station until the predicate is ready, but it occupies that station longer and still must defer effects and exceptions. The fundamental requirements are versioned predicate dependence, preservation of false-case values, and controlled commitment; the reorder buffer makes speculative completion and recovery more systematic.

Separate the two required orders. A writer must make all initialization store instructions to a fresh version visible before another CPU core can use the publication of its address. A reader must load p before the load instructions of fields addressed through the saved pointer. Assume ordinary coherent cacheable computer memory, atomic aligned pointer accesses, immutable published versions, and the lifetime guarantee from part (ii). The sequences below are architectural operations; a compiler must preserve the stated accesses and dependencies.

TSO. Total store order preserves store-to-store order, so initialization writes cannot become visible after the later pointer publication. It also preserves load-to-load order, so reading the pointer precedes reading its fields. Its store-to-load relaxation, illustrated in part (b), does not break either required ordering. ThereforeNo drain of every reader's store buffer and no explicit cache flush is required. This statement is about hardware ordering; unsynchronized ordinary C or C++ accesses to p would still need the language's atomic operation and acquire-release synchronization facilities to avoid a data race and unwanted compiler transformations.

Power/ARM. These weaker memory models can expose a new pointer before all the writer's initialization store instructions are visible. Put a write-ordering memory barrier between the last initialization write and the store of p. A sufficient sequence uses lwsync on POWER architecture or an appropriately scoped DMB, such as DMB ISH, on the ARMv7 ARM architecture family:The scope must include every participating CPU core. A broader full barrier is sufficient but can cost more. Without the writer barrier, observing the new p and stale initialization data is exactly the unwanted message-passing outcome.^[ref]

For the reader as actually specified, the saved pointer is an address dependency: the loaded value directly determines each subsequent field's memory address.Both POWER architecture and the relevant ARM memory models respect such dependent reads. Thus no additional reader hardware fence is needed when every data access retains this real address dependency. The writer's publication barrier together with the dependent reads supplies the necessary ordering. A mere test of p followed by unrelated fixed-address reads would be a control dependency, which is not sufficient here.^[ref]

If that address dependency is not retained, use an acquire operation or an explicit read-ordering memory barrier after loading p and before reading fields. DMB ISH on ARMv7 or lwsync on POWER architecture is a conservative sufficient choice for this load-to-load ordering; a suitable conditional branch followed by isync is another POWER acquire implementation. On later ARM instruction sets an acquire load instruction can express the reader requirement directly. Such stronger forms are often convenient even though they are not minimal for the dependent sequence in this question.

The minimal answer is a writer publication barrier on Power/ARM, with the stated reader's address dependence doing the read-side ordering; TSO needs neither extra hardware fence. None of these choices repairs an invalid pointer, premature memory reclamation, or a lost update between writers.

Storage for pending writes, usually with their memory addresses, data and status. A younger load instruction must account for older overlapping buffered store instructions, often by store-to-load forwarding.

An age-ordered structure tracking store instructions, their memory addresses and data, and their eligibility to become visible. An implementation may distinguish a speculative store queue from the committed store buffer.

Satisfying a load instruction from an older pending store instruction rather than stale backing computer memory. The youngest applicable older write supplies each requested byte; unresolved or partial overlaps require additional handling.

A memory cache policy that allocates the relevant cache line on a write cache miss. Fetching that cache line can delay a store instruction unless other mechanisms hide the delay.