PARTICLE: An Automatic Program Specialization System for Imperative and Low-Level Languages

This document describes the design and implementation of PARTICLE, a fully automatic program specialization system for imperative and low-level languages. PARTICLE performs source-to-source specialization of programs written in the C programming language based on knowledge of program behavior acquired through extensible, high-quality program analysis. PARTICLE supports a unique two-phase specialization strategy that permits careful balancing between the time benefits and space costs of specialization and permits the user to avoid the huge space expansion that has traditionally accompanied program specialization. During the first phase of PARTICLE operation, an input program in the C programming language is analyzed using an extensibly precise form of symbolic evaluation in order to discover opportunities for low-level specialization. The symbolic evaluation manipulates explicit approximations to program values and states and the compile time flow of analysis in the program represents a..