Idempotent backward slices: a gsa-based approach to code-size reduction

Abstract

Compiler optimizations are critical for enhancing the efficiency of programs, particularly for software deployed on resource-constrained systems where code size is a primary concern. This thesis introduces a novel technique for code-size reduction by identifying and outlining recurrent program slices. Our approach leverages the Gated Single Assignment (GSA) form, an intermediate representation that makes both data and control dependencies explicit, to enable the precise extraction of self-contained, executable program logic, which we term Idempotent Backward Slices. The proposed algorithm is implemented as a complete, functional, and open-source, out-of-tree pass for the LLVM compiler infrastructure. To evaluate its effectiveness, we conducted a rigorous empirical study, compiling 2007 programs from the LLVM Test Suite. The results demonstrates that our technique achieves significant code-size reductions in specific, targeted cases where other optimizers fail. We conclude that GSA-based slicing is a viable but specialized tool, best suited for domains where code footprint is paramount and code bases contain the recurrent computational patterns our slicer is designed to identify.