Topics in Online Partial Evaluation

Partial evaluation is a performance optimization technique for computer programs. When a program is run repeatedly with only small variations in its input, we can profit by taking the program and a description of the constant portion of the input, and producing a "specialized" program that computes the same input/output relation as the original program, but only for inputs satisfying the description. This program runs faster because computations depending only on constant inputs are performed only once, when the specialized program is constructed. This technique has not only proven useful for speeding up "interpretive" programs such as simulators, language interpreters, and pattern matchers, but also encompasses many "traditional" compiler optimizations. Contemporary work in partial evaluation has concentrated on "offline" methods, where high-speed specialization is achieved at the cost of slower specialized programs by limiting the sorts of decision-making that can occur at specialization time. This dissertation investigates "online" methods, which impose no such restrictions, and demonstrates the benefits of specialization-time decision-making in FUSE, a partial evaluator for a functional subset of Scheme. We describe two new methods, return value analysis and parameter value analysis, for computing more accurate estimates of runtime values at specialization time, enabling more optimizations, and yielding better specialized programs with less "hand-tweaking" of the source. We develop a re-use analysis mechanism for avoiding redundancies in specialized code, improving the efficiency of both the specializer and the programs it produces. Finally, we show how to produce efficient, optimizing program generators by using our techniques to specialize an online program specializer. Erik Ruf March 1993 Publication: Ph.D. Dissertation, Department of Electrical Engineering, Stanford University Notes: Also published as Stanford Computer Systems Laboratory Technical Report CSL-TR-93-563. This report supersedes Memos 90-3, 91-5, 92-7, 92-8, 92-9, 92-11, and 92-13. The figures in this document will break many printers with imperfect PostScript implementations. Printers with Rev. 2 Postscript (e.g. HPIIISi/4mx) seem to fare better. If you find yourself completely unable to print a copy, contact Erik Ruf (ruf@cs.stanford.edu) to see if he still has any spare copies. Partial evaluation is a performance optimization technique for computer programs. When a program is run repeatedly with only small variations in its input, we can profit by taking the program and a description of the constant portion of the input, and producing a "specialized" program that computes the same input/output relation as the original program, but only for inputs satisfying the description. This program runs faster because computations depending only on constant inputs are performed only once, when the specialized program is constructed. This technique has not only proven useful for speeding up "interpretive" programs such as simulators, language interpreters, and pattern matchers, but also encompasses many "traditional" compiler optimizations. Contemporary work in partial evaluation has concentrated on "offline" methods, where high-speed specialization is achieved at the cost of slower specialized programs by limiting the sorts of decision-making that can occur at specialization time. This dissertation investigates "online" methods, which impose no such restrictions, and demonstrates the benefits of specialization-time decision-making in FUSE, a partial evaluator for a functional subset of Scheme. We describe two new methods, return value analysis and parameter value analysis, for computing more accurate estimates of runtime values at specialization time, enabling more optimizations, and yielding better specialized programs with less "hand-tweaking" of the source. We develop a re-use analysis mechanism for avoiding redundancies in specialized code, improving the effici

thesis.ps
PostScript file

Details

TypeInproceedings
> Publications > Topics in Online Partial Evaluation