Using a Swap Instruction to Coalesce Loads and Stores

Apan Qasem, David Whalley, Xin Yuan, Robert van EngelenLecture Notes in Computer Science 2001 · DOI · OpenAlex

Introduction

In computer architecture, data movement between registers and memory is a frequent and relatively expensive operation. Typically, reading a value from a memory address and subsequently writing a new value to that same address requires two distinct instructions: a load followed by a store. While many Instruction Set Architectures (ISAs) include a swap instruction—which atomically exchanges the contents of a register and a memory location—it is traditionally reserved for synchronization primitives like mutexes.

This paper investigates whether a compiler can automatically repurpose the swap instruction as a general-purpose performance optimizer. By coalescing separate load and store operations into a single atomic swap, the authors aim to reduce both executed instructions and total memory references across standard applications.

Coalescing load and store operations at different code levels.

Methodology

The researchers implemented a low-level code-improving transformation within the vpo (Very Portable Optimizer) compiler backend. The optimization process involves several key steps:

  1. Pattern Matching: The compiler identifies sequences where a load instruction is followed by a store instruction targeting the same memory address.
  2. Dependency Analysis: The transformation is only applied if the value to be stored is independent of the value just loaded. A direct data dependency (e.g., x = x + 1) would invalidate the use of a parallel swap.
  3. Instruction Rescheduling: If other instructions exist between the target load and store, the compiler attempts to reschedule them to make the load and store contiguous.
  4. Register Renaming: To facilitate the merge, the compiler renames registers to preserve data live ranges, which often has the secondary benefit of reducing overall register pressure.

Furthermore, high-level transformations like loop unrolling act as catalysts, exposing "cross-iteration" dependencies that can then be coalesced by the backend.

Experimental Setup

The transformation was evaluated using 16 benchmark programs, primarily from Numerical Recipes in C. These benchmarks cover a wide range of algorithmic domains:

  • Linear Algebra: bandec, elmhes, gaussj, ludcmp, transpose.
  • Sorting/Searching: bubblesort, indexx, select.
  • Signal Processing: fft, chebpc, mmid, predic, rtflsp.
  • General Algorithms: thresh (image processing), traverse (binary tree), and tsp (traveling salesman).

Key Results and Analysis

The experimental results demonstrate consistent performance gains across the benchmark suite. On average, the number of executed instructions decreased by 3.06%, with the transpose benchmark achieving a peak reduction of 11.54%.

The impact on memory system efficiency was even more significant. The average reduction in memory references was 8.52%. Benchmarks such as transpose (24.96%) and thresh (19.49%) showed substantial improvements, as detailed in the performance data below.

Performance improvements in instruction count and memory references across benchmarks.

Interestingly, while memory references decreased, data cache misses remained largely unaffected. This is expected, as the optimization reduces the frequency of memory access instructions but does not alter the set of memory addresses being accessed.

Discussion

The core insight of this work is viewing the swap instruction as a form of hardware-level parallelism. By executing a load and store simultaneously, the processor effectively hides the latency of one operation. Additionally, by merging instructions and renaming registers, the compiler can free up registers, potentially unblocking other optimizations.

However, the authors noted that the order of optimizations is crucial. For instance, Common Subexpression Elimination (CSE) can sometimes remove redundant loads too early, inadvertently destroying opportunities for swap coalescing.

Conclusion

While highly effective on architectures that support it (like SPARC), this optimization is hardware-dependent. Its utility is also limited to cases without direct data dependencies between the load and store. Future research could explore more aggressive rescheduling techniques or the application of similar coalescing strategies to other atomic instructions.

Summary updated

BibTeX
@inproceedings{qasem2001using,
  author = {Apan Qasem and David Whalley and Xin Yuan and Robert van Engelen},
  title = {{Using a Swap Instruction to Coalesce Loads and Stores}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2001},
  doi = {10.1007/3-540-44681-8\_35},
}

Loading related content...

Figure