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 latest 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, and an earlier FDO workshop paper .