Search papers, labs, and topics across Lattice.
This paper formalizes the concept of idempotent backward slices, which are maximal subprograms that compute a given value, and introduces a sound and efficient algorithm for extracting them from programs in Gated Static Single Assignment (GSA) form. The algorithm addresses limitations in previous approaches that were insufficient for general control-flow graphs. The authors demonstrate the practical application of idempotent slices for sparse code-size reduction, achieving reductions up to 7.24% on specific benchmarks in the LLVM test suite after aggressive optimization.
Achieve up to 7.24% code-size reduction by identifying and extracting idempotent backward slices, enabling the merging of non-contiguous instruction sequences within and across functions.
Given a value computed within a program, an idempotent backward slice with respect to this value is a maximal subprogram that computes it. An informal notion of an idempotent slice has previously been used by Guimaraes et al. to transform eager into strict evaluation in the LLVM intermediate representation. However, that algorithm is insufficient to be correctly applied to general control-flow graphs. This paper addresses these omissions by formalizing the notion of idempotent backward slices and presenting a sound and efficient algorithm for extracting them from programs in Gated Static Single Assignment (GSA) form. As an example of their practical use, the paper describes how identifying and extracting idempotent backward slices enables a sparse code-size reduction optimization; that is, one capable of merging non-contiguous sequences of instructions within the control-flow graph of a single function or across functions. Experiments with the LLVM test suite show that, in specific benchmarks, this new algorithm achieves code-size reductions up to -7.24% on programs highly optimized by the -Os sequence of passes from clang 17.
