|
Partial Evaluation for Constraint-Based Program Analyses
Torben Amtoft December 1999 |
Abstract:
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. |