Memory disambiguation is a set of techniques employed by high-performance out-of-order execution microprocessors that execute memory access instructions (loads and stores) out of program order. The mechanisms for performing memory disambiguation, implemented using digital logic inside the microprocessor core, detect true dependencies between memory operations at execution time and allow the processor to recover when a dependence has been violated. They also eliminate spurious memory dependencies and allow for greater instruction-level parallelism by allowing safe out-of-order execution of loads and stores.

When attempting to execute instructions out of order, a microprocessor must respect true dependencies between instructions. For example, consider a simple true dependence:

In this example, the add instruction on line 2 is dependent on the add instruction on line 1 because the register R1 is a source operand of the addition operation on line 2. The add on line 2 cannot execute until the add on line 1 completes. In this case, the dependence is static and easily determined by a microprocessor, because the sources and destinations are registers. The destination register of the add instruction on line 1 (R1) is part of the instruction encoding, and so can be determined by the microprocessor early on, during the decode stage of the pipeline. Similarly, the source registers of the add instruction on line 2 (R1 and R4) are also encoded into the instruction itself and are determined in decode. To respect this true dependence, the microprocessor's scheduler logic will issue these instructions in the correct order (instruction 1 first, followed by instruction 2) so that the results of 1 are available when instruction 2 needs them.

Complications arise when the dependence is not statically determinable. Such non-static dependencies arise with memory instructions (loads and stores) because the location of the operand may be indirectly specified as a register operand rather than directly specified in the instruction encoding itself.

Here, the store instruction writes a value to the memory location specified by the value in the address (R2+2), and the load instruction reads the value at the memory location specified by the value in address (R4+4). The microprocessor cannot statically determine, prior to execution, if the memory locations specified in these two instructions are different, or are the same location, because the locations depend on the values in R2 and R4. If the locations are different, the instructions are independent and can be successfully executed out of order. However, if the locations are the same, then the load instruction is dependent on the store to produce its value. This is known as an ambiguous dependence.

Executing loads and stores out of order can produce incorrect results if a dependent load/store pair was executed out of order. Consider the following code snippet, given in MIPS assembly:

Assume that the scheduling logic will issue an instruction to the execution unit when all of its register operands are ready. Further, assume that registers $30 and $31 are ready: the values in $30 and $31 were computed a long time ago and have not changed. However, assume $27 is not ready: its value is still in the process of being computed by the mul instruction. Finally, assume that registers $30 and $31 hold the same value, and thus all the loads and stores in the snippet access the same memory word.

In this situation, the sw $27, 0($30) instruction on line 2 is not ready to execute, but the lw $08, 0($31) instruction on line 3 is ready. If the processor allows the lw instruction to execute before the sw, the load will read an old value from the memory system; however, it should have read the value that was just written there by the sw. The load and store were executed out of program order, but there was a memory dependence between them that was violated.