System and method for performing selective dynamic compilation using run-time information

• US 6,427,234 B1
• Filed: 06/11/1999
• Issued: 07/30/2002
• Est. Priority Date: 06/11/1998
• Status: Expired due to Fees

• Current Assignee: University of Washington, Washington University In St Louis
• Original Assignee: University of Washington
• Inventors: Philipose, Matthai, Eggers, Susan J., Mock, Markus, Grant, Brian K., Chambers, Craig
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US09/330,359
• Time in Patent Office: 1,145 Days
• Field of Search: 717/5, 717/6, 717/8, 717/9, 717/140, 717/143, 717/148, 717/151, 717/153, 717/155, 708/200, 709/100, 340/825, 702/60, 714/707
• US Class Current: 717/140
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

Selective dynamic compilation of source code is performed using run-time information. A system is disclosed that implements a declarative, annotation based dynamic compilation of the source code, employing a partial evaluation, binding-time analysis (BTA), and including program-point-specific polyvariant division and specialization and dynamic versions of traditional global and peephole optimizations. The system allows programmers to declaratively specify policies that govern the aggressiveness of specialization and caching, providing fine control over the dynamic compilation process. The policies include directions for controlling specialization at promotion points and merge points, and further define caching policies, and speculative-specialization policies. The system also enables programmers to specialize programs across arbitrary edges, both at traditional locations, such as procedure boundaries, but also within procedures. Programmers are enabled to conditionally specialize programs based on evaluation of arbitrary compile-time and run-time conditions.

Claims

1. A method for automatically processing source code for a computer program to produce machine-executable instructions comprising statically-compiled code portions and specialized code portions, said specialized code portions including dynamically-compiled instructions that are generated at run time when the machine-executable instructions are executed by a processor, comprising the steps of:

(a) defining policies having associated program statements and values for generating said specialized code portions and for integrating said specialized code portions with said statically-compiled code portions;

(b) identifying program points where said specialized code portions may be implemented at run time;

(c) applying the policies to the program points by entering annotations in the source code in proximity to said program points, using the associated program statements;

(d) binding the values to variables; and

(e) processing the source code to generate the statically-compiled code portions and to create run-time specializers that dynamically compile the specialized code portions when the specialized code portions are requested to be executed at run-time, based on the values bound to the variables.

2. The method of claim 1, wherein the source code comprises a plurality of procedures, and wherein the step of binding the values to the variables comprises the steps of:

(a) generating a control flow graph representation of each of the plurality of procedures; and

(b) iteratively performing a data flow analysis over the control flow graph representation for each procedure to propagate a set of divisions, said divisions mapping the variables to the values in accord with the annotations entered in the source code.

3. The method of claim 2, wherein the data flow analysis produces information associated with each program point that is used to produce the run-time specializers.

4. The method of claim 1, wherein the policies specify parameters for controlling a level of aggressiveness of specialization of said specialized code portions, the level of aggressiveness controlling the extent to which code is duplicated in order to create the specialized code portions.

5. The method of claim 1, wherein the policies specify parameters for controlling caching of said specialized code portions.

6. The method of claim 1, wherein the source code comprises variables that may be static or dynamic at run time, and wherein the step of identifying the program points comprises performing a binding-time analysis based on the policies to identify static variables and dynamic variables at run time.

7. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

8. A method for automatically conditionally specializing source code for a computer program to generate machine-executable instructions that comprise statically-compiled code portions and specialized code portions, said specialized code portions including dynamically-compiled instructions that are generated at run time when the machine-executable instructions are executed by a processor, comprising the steps of:

(a) identifying one or more program points in the source code for implementing the specialized code portions;

(b) annotating the source code in proximity to said one or more program points by entering at least one conditional statement at each program point; and

(c) processing each conditional statement so as to direct the generation of a corresponding specialized code portion based on evaluation of the conditional statement.

9. The method of claim 8, wherein the generation of said specialized code portion comprises the steps of:

(a) copying a portion of the source code to be specialized;

(b) apply a binding-time analysis to said portion;

(c) creating a run-time specializer from the copy of the source code portion that was analyzed, said run-time specializer being used to produce a specialized version of the copy at run time; and

(d) creating a specializer stub that is prepended to the run-time specializer to control execution of said specialized version of the copy at run time.

10. The method of claim 9, wherein the specializer stub either executes the run-time specializer or causes the previously created specialized version of the copy to be executed.

11. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 8.

12. A method for automatically positioning cache lookups within a specialized computer program, said specialized computer program including a plurality of procedures and comprising statically-compiled code portions and dynamically-compiled code portions, each dynamically compiled code portion being generated at run time when the specialized computer program is executed by a processor, comprising the steps of:

(a) identifying ranges within the dynamically-compiled code portions that include code potentially reusable during execution of the specialized computer program, each range corresponding to a run-time constant and spanning program points between which said run-time constant is in use;

(b) coalescing the ranges identified by forming intersections between ranges that span common program points; and

(c) placing the cache lookups within the ranges that have been coalesced.

13. The method of claim 12, further comprising the step of performing a binding-time analysis that identifies the dynamically-compiled code portions and implements the step of identifying the ranges within said dynamically-compiled code portions.

14. The method of claim 12, wherein the step of identifying the ranges comprises the steps of:

(a) identifying points in the dynamically-compiled code portions in which code may be reused, each identified point corresponding to a procedure and having a program-control dependency; and

(b) for each identified point, constructing a range over said point'"'"'s associated procedure in which said point can be moved while maintaining its program-control dependency.

15. The method of claim 12, further comprising the steps of:

(a) promoting a run-time constant if its value has changed since a previous execution of a code portion within a range corresponding to the run-time constant; and

(b) evicting a run-time constant after it is no longer used by a dynamically-compiled code portion, wherein the placement of a cache lookup is dependent on a relative mix of variables within a range that has been coalesced such that if a relative majority of the variables are promoted, the cache lookup is placed at an end of said range, and if a relative majority of the variables are evicted, the cache lookup is placed at a start of said range.

16. A method for automatically enabling on-demand specialization to be produced across arbitrary control flow edges in a computer program comprising source code processed to generate machine-executable instructions, said machine instructions comprising statically-compiled code portions and specialized code portions, said specialized code portions including dynamically-compiled instructions that are generated at run time when the machine instructions are executed by a processor, comprising the steps of:

(a) generating a control flow graph of the computer program, the control flow graph comprising pairs of blocks of code and edges, wherein each pair of blocks includes a source block connected by an edge to a destination block, and wherein the edge contains no source code;

(b) generating a specialized source block based on any variables expected to be constant during the run-time execution of said source block; and

(c) replacing an edge that connects the specialized source block to a destination block with code that generates a stub immediately after the specialized source block, the stub, when executed, gathering values for variables that comprise a context of specialization for the destination block, and invoking a routine to create a specialized destination block with respect to the context.

17. The method of claim 16, wherein the stub, when executed, provides a direct branch from the specialized source block to the specialized destination block so that the stub is bypassed during future run-time traversals of the edge connecting the specialized source block with the specialized destination block.

18. A system for automatically processing a computer program comprising source code to generate machine-executable instructions, said machine-executable instructions including statically-compiled code portions and specialized code portions, said specialized code portions including dynamically-compiled instructions that are generated at run time when the machine-executable instructions are executed, comprising:

(a) a memory in which a plurality of machine instructions are stored; and

(b) a processor, coupled to the memory and responsive to the machine instructions, the machine instructions, when executed by the processor, causing the processor to;

(i) enable a user to annotate the source code with program statements corresponding to predefined policies, which are stored in the memory, said policies having associated values that define directions for generating said specialized code portions and for integrating said specialized code portions with said statically-compiled code portions, the program statements being introduced in the source code so as to operate on associated run-time constant variables;

(ii) bind the associated values to variables; and

(iii) process the source code to generate the statically-compiled code portions and to create run-time specializers, said run-time specializers comprising extensions that dynamically compile the specialized code portions when said specialized code portions are requested to be executed at run time, based on the values bound to the variables.

19. The system of claim 18, wherein the source code comprises a plurality of procedures and wherein execution of said machine instructions causes the processor to propagate binding the values to the variables by:

(a) generating a control flow graph representation of each of the procedures; and

(b) iteratively performing a data flow analysis over each control flow graph representation to propagate a set of divisions, said divisions mapping the variables to the values based on the program statements introduced into the source code.

20. The system of claim 18, wherein the policies specify parameters for controlling caching of said specialized code portions.