Partial Evaluation for Constraint-Based Program Analyses

Torben Amtoft

December 1999


We report on a case study in the application of partial evaluation, initiated by the desire to speed up a constraint-based algorithm for control-flow analysis. We designed and implemented a dedicated partial evaluator, able to specialize the analysis wrt. a given constraint graph and thus remove the interpretive overhead, and measured it with Feeley's Scheme benchmarks. Even though the gain turned out to be pretty limited, our investigation yielded valuable feed back in that it provided a better understanding of the analysis, leading us to (re)invent an incremental version. We believe this phenomenon to be a quite frequent spin-off from using partial evaluation, since the removal of interpretive overhead will make the flow of control more explicit and hence pinpoint the sources of inefficiency. Finally, we observed that partial evaluation in our case yields such regular, low-level specialized programs that it begs for runtime code generation

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.