Benefits and costs of staged run-time specialization

Run-time specialization denotes dynamic optimizations that exploit program data values to produce faster code than is possible using purely static optimizations. However, because the optimizations are performed at run time, the cost of applying them must be recovered before any net benefit from specialization can be realized. Hence, one of the most significant challenges is to reduce the run-time cost of the dynamic optimizations without overly decreasing their effectiveness. This is the main problem that I investigated.; My work was done within DyC, a run-time specialization system for C programs developed by myself and others at the University of Washington. DyC extends previous work by (1) demonstrating several novel capabilities that are important for producing speedups on larger, more complex programs written in a widely used imperative language (C) and by (2) achieving extremely low overhead despite its many features and optimizations. This dissertation assesses the benefits, costs and applicability of DyC's optimizations, both individually and when applied together, with considerable attention devoted to the two main methods I applied to achieve DyC's low run-time cost. The first method creates dynamic compilers customized for each application and for the dynamic optimizations applied. This approach reduced dynamic compilation overhead up to a factor of 10 compared to our previous approach. The second method provides a suite of dispatching techniques, each designed to exploit particular patterns of change in the run-time values used for specialization. We found that a variety of techniques is needed to achieve good performance when dynamically specializing a range of applications.