Run-Time Detection and Recovery From Incorrectly Reordered Memory Operations

We present a new approach for run-time detection of incorrectly reordered memory operations. This problem arises when a load operation is statically scheduled for execution earlier than sequentially preceding store operations, but the computer cannot prove whether the memory locations accessed by the operations are disjoint. Previous techniques for dealing with this problem compare the memory addresses referenced by the reordered load and store instructions; if the addresses overlap, the load instruction is regarded as incorrectly reordered, and a recovery sequence is invoked to correct the error. Instead, the approach described here compares the value loaded out-of-order with the value in the corresponding memory location at the original position of the load instruction in the program; a recovery sequence is invoked whenever the two values are not identical. In contrast to previous techniques, this approach is characterized by constant overhead independent of the type of interference among memory references (e.g. operands with different size, overlapping operands, multiple reordering) and handles special cases (e.g. asynchronous modifications, context switches). We have incorporated this technique in Chameleon, our research compiler for instruction-level parallelism, and have applied it to a VLIW processor. Simulation results have shown performance improvements up to 16% in some cases, and 4-7% in a wider sample, over scheduling without reordering ambiguous memory operations. The algorithm used selects load instructions for disambiguation in a way that causes negligible code expansion due to the recovery sequences, and very infrequent execution of such recovery sequences.