Report Number: CS-TR-98-1608
Institution: Stanford University, Department of Computer Science
Title: A New Perspective on Partial Evaluation and Use Analysis
Author: Katz, Morris J.
Date: June 1998
Abstract: Partial evaluators are compile time optimizers achieving performance improvements through a program modification technique called specialization. Partial evaluators produce one or more copies, or specializations, of each procedure in a source program in the output program. Specializations are distinguished by being optimized for invocation from call sites with different characteristics, for example, placing certain constraints on argument values. Specializations are created by partially executing procedures, leaving only unexecutable portions as residual code. Symbolic execution can replace variable references by the referenced values, executed primitives by their computed results, and function applications by the bodies of the applied functions, yielding inlining. One core challenge of partial evaluation is selecting what specializations to create. Attempting to produce an infinite number of specializations results in divergence. The termination mechanism of a partial evaluator decides whether or not to symbolically execute a procedure in order to create a new specialization. Creating a termination mechanism that precludes divergence is not difficult. However, crafting a termination mechanism resulting in the production of a sufficient number of appropriate specializations to produce high quality residual code while still terminating all, or most, of the time is quite challenging. This dissertation presents a new type of analysis, called use analysis, forming the basis of a termination mechanism designed to yield a better combination of residual code quality and frequent termination than the current state-of-the-art.
http://i.stanford.edu/pub/cstr/reports/cs/tr/98/1608/CS-TR-98-1608.pdf