Two separate compilers are involved in our approach to dynamic compilation: a static compiler and a dynamic compiler. The static compiler compiles code outside of regions of code to be dynamically compiled, called dynamic regions, and partially compiles and otherwise prepares dynamic regions to be compiled at run time. The dynamic compiler uses the partially compiled dynamic regions and other information generated by the static compiler to generate executable code for the dynamic regions.
For our first-generation dynamic compilation system, designed and built by Joel Auslander and Matthai Philipose, we have enhanced the Multiflow compiler to act as the static compiler, and built a dynamic compiler that is automatically invoked at run time. Dynamic regions are identified by the programmer through a set of source-code annotations. For each dynamic region, the programmer also specifies on which variables the region should be specialized. A new version of the region is compiled at run-time for each set of values these variables have at the beginning of the dynamic region. Furthermore, these annotated variables must be invariant throughout the dynamic region, and are called run-time constants.
The static compiler automatically identifies all values in the region that are derived from this programmer-specified set of run-time constants, which can then be considered run-time constants (and can be used as the basis for specialization) as well. In particular, if the arguments to an arithmetic operation, a comparison, or even a memory load are compile-time and run-time constants, then the result is assumed to be a run-time constant.
The static compiler then splits each dynamic region into two pieces of code, set-up code and machine-code templates. Set-up code includes all computations in the region that depend, directly or indirectly, solely on compile-time and run-time constants. Machine-code templates include all computations in the region that depend at least in part on run-time varying data. References in the machine-code templates to run-time constants cannot be resolved at static compile time, since their values are not determined until run time; therefore the machine-code templates contain holes in place of these values. The static compiler also outputs a series of directives to the dynamic compiler that indicate how to turn the machine-code templates into correct executable code, given the static values computed by the set-up code.
At run time, when a dynamic region is first entered, the dynamic compiler is invoked. The dynamic compiler first executes the region's set-up code to calculate the values of the run-time constants. It then executes the directives, selecting and copying the desired machine-code templates and filling in the holes based on the values computed by the set-up code, to produce the final optimized machine code for the dynamic region. This machine code is then run to continue the program's execution. For all future executions of the dynamic region with the same run-time-constant values, the generated machine code is executed directly without invoking the dynamic compiler or the set-up code.
Generally, the more time spent optimizing code at run-time, the higher the quality of code generated. However, the time spent optimizing code at run-time must be recovered through the speedups gained through the optimizations. So, it is desirable to make the dynamic compiler as fast as possible while still achieving significant benefits from the optimizations.
Our dynamic compiler only manipulates "nearly compiled" templates, and so is designed to be very fast. Even so, it can perform a number of optimizations, thus producing fast code. The dynamic compiler can complete the constant propagation and folding planned by the static compiler, eliminate memory loads of the run-time constants, perform peephole optimizations based on their values, remove branches they determine, and fully unroll loops they bound. Full unrolling of a loop causes the loop-induction variables to become run-time constants within each iteration, creating more opportunities for optimization.
However, even if the dynamic compiler is very fast and the code generated is very efficient, the code that is dynamically compiled will generally have to be executed many times in order to recoup the cost of dynamic compilation through enhanced performance. For this reason, the regions of code to be specialized at run-time and the variables on which the dynamic compiler is to specialize must be carefully selected. If not much improvement can be achieved by dynamically compiling an annotated region, or if the annotated run-time constants take on new values too frequently, then performance will be worse than purely statically compiled code. So, selecting dynamic regions and run-time constants is a delicate task, which is why we elected to use annotations with our system, rather than selecting regions and run-time constants automatically.
For more detailed information about our prototype, please see our PLDI `96 paper.
Last updated April 7, 1997.