|
The University of Washington Dynamic
Compilation Group is exploring the technique of automatic dynamic compilation, generating code at run time
with the goal of improving application performance. More
specifically, we have been investigating run-time specialization --
dynamic optimization using program data values. Our work targets
general-purpose, imperative programming languages, initially C.
Run-time specialization enables
applications to adapt to particular program inputs and actual
run-time behavior. Run-time specialization holds the promise of
tremendous performance improvements for some applications; however, a
number of challenges still need to be addressed before the technology
can be widely deployed. First, the run-time cost of the run-time
optimizations can be significant; the challenge is to reduce the cost
of dynamic optimizations without overly decreasing their
effectiveness. Second, the performance impact of the optimizations is
highly variable. Together with cost considerations, one easily
concludes that it is usually not beneficial to apply all available
optimizations to all potential targets. However, the number of
potential optimization configurations is large, so automatic selection
of optimizations and their targets is non-trivial.
We are working towards addressing these two challenges: low-cost
run-time optimization and automatic application of run-time
specialization. To that end, we have designed and built a dynamic-compilation system, dubbed DyC (pronounced dicey). DyC is
based on a principled extension of
partial evaluation and is currently driven by user annotations.
DyC has good potential for producing speedups for larger, more complex
C programs than previous general-purpose run-time-specialization
systems have achieved. Our results for a few medium-sized programs
are encouraging. The best speedup we obtained, 4.6, was for mipsi,
an instruction-level simulator for the MIPS R3000. Dynamic-compilation
overhead is low, averaging 10-1000 cycles per instruction generated on
the DEC Alpha
21164, depending on what optimizations are performed. DyC's design is
described in our expanded
journal publication, and our most recent performance results are described in our paper in PLDI `99.
Since the completion of DyC we have worked on making the dynamic
compilation process fully automatic by generating the
annotations that drive DyC with a separate tool named Calpa
. Calpa uses static program analysis to identify computations
that might benefit from specialization. It then uses the results of
detailed value-profiling to estimate the dynamic compilation costs and
benefits associated with candidate annotations identified by the
analysis. Calpa has been able annotations of the same quality as we
had previously found by hand -- but at a fraction of the time, minutes
or hours of machine time versus days and weeks of human time. Calpa
is described in more detail in our MICRO 2000 paper.
|