A Framework for Fine-Grained Program Versioning

Static dependence analysis is critical for optimizations such as vectorization and loop-invariant code motion. However, traditional static dependence analysis is often imprecise, making these optimizations less effective. To address this issue, production compilers use loop versioning to rule out some categories of memory dependencies at run time. However, loop versioning is loop-centric and usually tied to specific optimizations (e.g., loop vectorization), making it less effective for nonloop optimizations such as superword-level parallelism (SLP) vectorization.

In this paper, we propose a fine-grained versioning framework to rule out program dependencies at run time. Our framework is general and not tailored to any specific optimizations. To use our system, a client optimization specifies groups of instructions (or loops) whose independence is desired but unprovable statically. In response, our system duplicates the appropriate instructions and guards the original ones with run-time checks to guarantee their independence; if the checks fail, the duplicated instructions execute instead.

In a case study, we extended an existing SLP vectorizer with minimal modifications using our framework, resulting in a 1.17× speedup over Clang's vectorizers on TSVC and a 1.51× speedup on PolyBench. In both benchmarks, we encountered programs that could not be vectorized with loop versioning alone.

In a second case study, we used our framework to implement a more aggressive variant of redundant load elimination than the one implemented by Clang. Our redundant load elimination results in a 1.012× speedup on the SPEC 2017 Floating Point benchmarks, with the maximum speedup being 1.064×.