Method and apparatus for an improved optimizing compiler

• US 5,659,754 A
• Filed: 03/31/1995
• Issued: 08/19/1997
• Est. Priority Date: 03/31/1995
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Schwartz, David C., Grove, Daniel D.
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): CORCORAN, PETER JOSEPH
• Application Number:
  US08/414,267
• Time in Patent Office: 872 Days
• Field of Search: 395/700, 395/705, 395/707, 395/709, 395/800, 395/377, 395/395, 395/392
• US Class Current: 717/158
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

An optimizing compiler process and apparatus is disclosed for more accurately and efficiently identifying live variable sets in a portion of a target computer program, so as to more efficiently allocate registers in a computer central processing unit. The process of the invention includes the steps of performing a static single assignment transform to a computer program, including the addition of phi functions to a control flow graph. Basic blocks representing a use of a variable are further added to the control flow graph between the phi functions and definitions of the variables converging at the phi functions. A backward dataflow analysis is then performed to identify the live variable sets. The variables in the argument of phi functions are not included as a use of those variables in this dataflow analysis. The dataflow analysis may be iteratively performed until the live variable sets remain constant between iterations. The apparatus of the present invention includes a computer system having a memory storing a set of variables that are live during the execution of a portion of a computer program. This memory may include CPU registers, cache memory, conventional RAM and other types of memory.

Claims

1. A computer system having a central processing unit (CPU) and random access memory (RAM) coupled to said CPU, for use in compiling a target program to run on a target computer architecture having a fixed number of CPU registers, said target program having at least one basic block and wherein "use" blocks are inserted in a control flow graph which inhibit needless variable spilling to memory, said computer system comprising:

a compiler system resident in said computer system having a front end compiler, a code optimizer and a back end code generator; and

said code optimizer configured to determine a set of live variables for said basic block in said target program, wherein said fixed number of CPU registers in said target computer architecture can be allocated to said set of live variables in a manner which minimizes a number of variables in said set of live variables that must be stored in said memory instead of in said fixed number of CPU registers,

wherein said code optimizer inserts, in at least a portion of a control flow graph, a dummy block representing usage of a variable in said control flow graph prior to a phi-function node and determines said set of live variables by considering said dummy block, and wherein said code optimizer is further configured to perform a static single assignment transform on said target program and to add said phi function node to said control flow graph representation of said target program, and wherein said dummy block is a use block.

2. The computer system of claim 1 wherein said code optimizer is further configured to determine said set of live variables by using a backward dataflow analysis in which said variable is an argument in said phi function node and said variable is not considered as a use within said phi function node.

3. The computer system of claim 2 wherein said backward dataflow analysis is performed by beginning at an end of said basic block and adding to said set of live variables those variables live at a beginning of one or more children blocks of said basic block and adding to said set of live variables each usage instance of said variable and deleting from said set of live variables each subsequent definition of said variable.

4. The computer system of claim 3 wherein said backward dataflow analysis is iteratively performed until said set of live variables for said basic block remains constant between successive iterations.

5. The computer system of claim 1 wherein said phi function is added to said control flow graph representation of said target program by said code optimizer whenever multiple definitions of said variable reach a use of that variable.

6. The computer system of claim 5 wherein said dummy block is inserted into said control flow graph between said phi function having said variable in its argument and a preceding block containing a definition of said variable.

7. A compiler system for compiling a target program to run on a target computer architecture having a memory and a plurality of CPU registers, said compiler system comprising:

a front end portion configured to accept source code of said target program as input and to output a corresponding intermediate code set;

a code optimizer portion coupled to said front end portion and configured to accept said intermediate code set as input and to output a second intermediate code set,

wherein said second intermediate code set comprises code for said target program that allocates said plurality of CPU registers of said target computer architecture to a set of live variables for basic blocks in said target program in a manner which minimizes a number of variables in said set of live variables that must be stored in said memory instead of in said plurality of CPU registers,

wherein said code optimizer inserts, in at least a portion of a control flow graph, a dummy block representing usage of a variable in said control flow graph prior to a phi-function node and determines said set of live variables by considering said dummy block;

wherein said code optimizer is further configured to perform a static single assignment transform on said target program, and to add said phi function node to said control flow graph representation of said target program and wherein said dummy block is a use block; and

a back end code generator portion coupled to said code optimizer configured to accept said second intermediate code set as input and to generate binary code which will run on said target computer architecture.

8. The compiler system of claim 7 wherein said code optimizer is further configured to determine said set of five variables by using a backward dataflow analysis in which said variable is an argument in said phi function node and said variable is not considered as a use within said phi function node.

9. The compiler system of claim 8 wherein said backward dataflow analysis is performed by beginning at an end of said basic block and adding to said set of live variables those variables live at a beginning of one or more children blocks of said basic block and adding to said set of live variables each usage instance of said variable and deleting from said set of live variables each subsequent definition of said variable.

10. The compiler system of claim 9 wherein said backward dataflow analysis is to be iteratively performed until said set of live variables for said basic block remains constant between successive iterations.

11. The computer system of claim 7 wherein said phi function is added to said control flow graph representation of said target program by said code optimizer whenever multiple definitions of said variable reach a use of that variable.

12. The computer system of claim 11 wherein said dummy block is inserted into said control flow graph between said phi function having said variable in its argument and a preceding block containing a definition of said variable.

13. A code optimizer for use in an compiler system for compiling a target program to run on a target computer architecture having a memory and a plurality of CPU registers, said code optimizer comprising:

a first portion configured to accept as input an intermediate code representation of said target program;

a second portion, coupled to said first portion, configured to determine a set of live variables for at least one basic block of said target program; and

a third portion, coupled to said second portion, configured to allocate said plurality of CPU registers of said target computer architecture to said set of live variables for said basic blocks of said target program in a manner that minimizes a number of variables in said set of live variables that must be stored in said memory instead of in said plurality of CPU registers,

wherein said third portion inserts, in at least a portion of a control flow graph, a dummy block representing usage of a variable in said control flow graph prior to a phi-function node and determines said set of live variables by considering said dummy block, wherein the third portion is further configured to perform a static single assignment transform on said target program and to add said phi function node to said control flow graph representation of said target program, and wherein said dummy block is a use block.

14. The code optimizer of claim 13 wherein said third portion is further configured to determine said set of live variables by using a backward dataflow analysis in which said variable is an argument in said phi function node and said variable is not considered as a use within said phi function node.

15. The code optimizer of claim 14 wherein said backward dataflow analysis is performed by beginning at an end of said basic block and adding to said set of live variables those variables live at a beginning of one or more children blocks of said basic block and adding to said set of live variables each usage instance of said variable and deleting from said set of live variables each subsequent definition of said variable.

16. The code optimizer of claim 15 wherein said backward dataflow analysis is iteratively performed until said set of live variables for said basic block remains constant between successive iterations.

17. The computer system of claim 13 wherein said phi function is added to said control flow graph representation of said target program by said third portion whenever multiple definitions of said variable reach a use of that variable.

18. The computer system of claim 17 wherein said dummy block is inserted into said control flow graph between said phi function having said variable in its argument and a preceding block containing a definition of said variable.

19. A computer controlled method of allocating a live set of variables in a target program to a fixed number of CPU registers in a target computer architecture in a manner that minimizes a number of variables in said live set of variables that must be stored in a memory instead of in said fixed number of CPU registers;

said target program having at least one basic block said method comprising steps of;

a) constructing an interference graph representing a procedure of said target program;

b) determining said live set of variables for said target program by sub-steps of;

b1) performing a static single assignment transform of said procedure of said target program, including a step of adding a phi function to a control flow graph of said target program;

b2) inserting a use block representative of a use of a variable in said control flow graph between said phi function and a block containing a definition of said variable; and

b3) determining said live set of variables for said basic block in said target program by a backward dataflow analysis of said control flow graph without including arguments of said phi function wherein said backward dataflow analysis is performed beginning at an end of said basic block, initially adding to said live set of variables those variables live at a beginning of one or more children blocks of said basic block and adding to said live set of variables each instance of a use of a variable and deleting from said live set of variables each subsequent definition of said variable; and

c) mapping said live set of variables to said fixed number of CPU registers.

20. The method of claim 19 wherein the backward dataflow analysis is iteratively performed until said live set of variables remain constant between successive iterations.

21. The method of claim 19 wherein said phi function is added to said control flow graph where multiple definitions of said variable reach a use of that variable.

22. A computer controlled method of optimizing binary code of a target program which is compiled to run on a target computer architecture having a memory and a fixed number of CPU registers, said method comprising steps of:

a) providing a compiler system configured to accept source code of said target program and to output binary code representing said target program which is capable of being processed on said target computer architecture, said compiler system comprising a front end portion, a code optimizer portion and a back end code generator;

b) providing said code optimizer portion of said compiler system configured to accept intermediate code from said front end portion of said compiler system and to allocate a live set of variables in said intermediate code representing said target program to said fixed number of CPU registers in said target computer architecture in a manner that minimizes a number of variables in said live set of variables that must be stored in said memory instead of in said fixed number of CPU registers,

wherein allocation of said live set of variables in said intermediate code representing said target program to said fixed number of CPU registers is performed by sub-steps;

(b1) constructing an interference graph representing a procedure of said target program;

determining said live set of variables for said target program by sub-steps of;

(b1a) performing a static single assignment transform of said procedure of said target program, including adding a phi function to a control flow graph of said target program;

(b1b) inserting a use block representing usage of a variable in said control flow graph between said phi function and a defining block containing a definition of said variable; and

(b1c) determining said live set of variables for basic blocks in said target program by a backward dataflow analysis of said control flow graph;

(b2) mapping said live set of variables to said fixed number of CPU registers; and

(c) outputting a second intermediate code version of said target program to said back end code generator, said second intermediate code version of said target program containing the allocation of said live set of variables in said target program to said fixed number of CPU registers in said target computer architecture in a manner that minimizes a number of variables in said live set of variables that must be stored in said memory instead of in said fixed number of CPU registers, whereby said target program binary code is optimized.