Last updated May 12, 1999.Brian Grant (grant@cs.washington.edu)
University of Washington Technical Report UW-CSE-97-03-03. This report is an expanded version of Annotation-Directed Run-Time Specialization in C. To appear in Theoretical Computer Science. It was last updated May 12, 1999.
|
|
To save the paper to a file using Netscape Navigator, right click on one of the links at the left and select "Save Link As..." |
We present the design of DyC, a dynamic-compilation system for C based on run-time specialization. Directed by a few declarative user annotations that specify the variables and code on which dynamic compilation should take place, a binding-time analysis computes the set of run-time constants at each program point in the annotated procedure's control-flow graph; the analysis supports program- point-specific polyvariant division and specialization. The results of the analysis guide the construction of a run-time specializer for each dynamically compiled region; the specializer supports various caching strategies for managing dynamically generated code and mixes of speculative and demand-driven specialization of dynamic branch successors. Most of the key cost/benefit trade-offs in the binding-time analysis and the run-time specializer are open to user control through declarative policy annotations.
DyC has been implemented in the context of an optimizing compiler, and initial results have been promising. The speedups we have obtained are good, and the dynamic-compilation overhead is among the lowest of any dynamic-compilation system, typically 20-200 cycles per instruction generated on a Digital Alpha 21064. The majority of DyC's functionality has been used to dynamically compile an instruction-set simulator. Only three annotations were required, but a few other changes to the program had to be made due to DyC's lack of support for static global variables. This deficiency and DyC's rudimentary support for partially static data structures are the primary obstacles to making DyC easy to use.
Dynamic compilation, specialization, partial evaluation, constant folding, run-time code generation, program optimization, dataflow analysis, C language.
Last updated May 12, 1999.