Method and apparatus for an optimizing compiler

Claim 2

The computer system of claim 1 wherein the code optimizer is further configured to perform a static single assignment transform to the target program, and to add phi functions to a control flow graph representation of the target program.

Claim 3

The computer system of claim 2 wherein the code optimizer is further configured to insert use blocks representative of a use of a variable in the control flow graph.

Claim 4

The computer system of Claim 1 wherein the code optimizer is further configured to determine the set of live variables by a backward dataflow analysis in which the phi functions are not considered as a use of variables in an argument of the phi function.

Claim 5

The computer system of Claim 4 wherein said backward dataflow analysis is to be performed by beginning at an end of a basic block and adding to said live variable set each instance of a use of a variable and deleting from said live variable set each subsequent definition of said variable.

Claim 6

The computer system of Claim 5 wherein said backward dataflow analysis is further to be performed by beginning at an end of a basic block and adding to said live variable set those variables live at a beginning of children blocks of said basic block.

Claim 7

The computer system of Claim 6 wherein said backward dataflow analysis is to be iteratively performed until the live variable set for the basic blocks remain constant between successive iterations.

Claim 8

The computer system of Claim 1 wherein phi functions are to be added to a control flow graph representation of said target program by said code optimizer whenever multiple definitions of a variable reach a use of that variable.

Claim 9

The computer system of Claim 8 wherein use blocks representative of the use of a variable are to be inserted into the control flow graph between a phi function having a variable in its argument and a preceding block containing a definition of the variable.

Claim 10

A compiler system for compiling a target program to run on a target computer architecture having 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 which 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 computer memory instead of in said plurality of CPU registers, wherein said code optimizer inserts, in at least a portion of a control flow graph, dummy blocks representative of a use of a variable in said control flow graph prior to a phi-function node and determines the set of live variables by considering said dummy blocks; 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.

Claim 11

The compiler system of claim 10 wherein the code optimizer is further configured to perform a static single assignment transform to the target program, and to add phi functions to a control flow graph representation of the target program.

Claim 12

The compiler system of claim 11 wherein the code optimizer is further configured to insert use blocks representative of a use of a variable in the control flow graph.

Claim 13

The compiler system of Claim 10 wherein the code optimizer is further configured to determine the set of live variables by a backward dataflow analysis in which the phi functions are not considered as a use of variables in an argument of the phi function.

Claim 14

The compiler system of Claim 13 wherein said backward dataflow analysis is to be performed by beginning at an end of a basic block and adding to said live variable set each instance of a use of a variable and deleting from said live variable set each subsequent definition of said variable.

Claim 15

The compiler system of Claim 14 wherein said backward dataflow analysis is further to be performed by beginning at an end of a basic block and adding to said live variable set those variables live at a beginning of children blocks of said basic block.

Claim 16

The compiler system of Claim 15 wherein said backward dataflow analysis is to be iteratively performed until the live variable set for the basic blocks remain constant between successive iterations.

Claim 17

The compiler system of Claim 10 wherein phi functions are to be added to a control flow graph representation of said target program by said code optimizer whenever multiple definitions of a variable reach a use of that variable.

Claim 18

The compiler system of Claim 17 wherein use blocks representative of the use of a variable are to be inserted into the control flow graph between a phi function having a variable in its argument and a preceding block containing a definition of the variable.

Claim 19

A code optimizer for use in an compiler system for compiling a target program to run on a target computer architecture having 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 basic blocks 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 basic blocks of said target program in a manner which minimizes a number of variables in said set of live variables that must be stored in computer memory instead of in said plurality of CPU registers, wherein said third portion inserts, in at least a portion of a control flow graph, dummy blocks representative of a use of a variable in said control flow graph prior to a phi-function node and determines the set of live variables by considering said dummy blocks.

Claim 20

The code optimizer of claim 19 wherein the third portion is further configured to perform a static single assignment transform to the target program, and to add phi functions to a control flow graph representation of the target program.

Claim 21

The code optimizer of claim 20 wherein the third portion is further configured to insert use blocks representative of a use of a variable in the control flow graph.

Claim 22

The code optimizer of Claim 19 wherein the third portion is further configured to determine the set of live variables by a backward dataflow analysis in which the phi functions are not considered as a use of variables in an argument of the phi function.

Claim 23

The code optimizer of Claim 22 wherein said backward dataflow analysis is to be performed by beginning at an end of a basic block and adding to said live variable set each instance of a use of a variable and deleting from said live variable set each subsequent definition of said variable.

Claim 24

The code optimizer of Claim 23 wherein said backward dataflow analysis is further to be performed by beginning at an end of a basic block and adding to said live variable set those variables live at a beginning of children blocks of said basic block.

Claim 25

The code optimizer of Claim 24 wherein said backward dataflow analysis is to be iteratively performed until the live variable set for the basic blocks remain constant between successive iterations.

Claim 26

The code optimizer of Claim 19 wherein phi functions are to be added to a control flow graph representation of said target program by said third portion whenever multiple definitions of a variable reach a use of that variable.

Claim 27

The code optimizer of Claim 26 wherein use blocks representative of the use of a variable are to be inserted into the control flow graph between a phi function having a variable in its argument and a preceding block containing a definition of the variable.

Claim 28

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 memory instead of in said fixed number of CPU registers, said method comprising the steps of: constructing an interference graph representing a procedure of said target program; determining a live set of variables for the target program by the sub-steps of performing a static single assignment transform of said procedure of said target program, including a step of adding phi functions to a control flow graph of said target program; inserting use blocks representative of a use of a variable in the control flow graph between a phi function and a block containing a definition of said variable; and determining said live set of variables for basic blocks in the Target program by a backward dataflow analysis of the control flow graph; and mapping the live set of variables to the fixed number of CPU registers.

Claim 29

The method of Claim 28 wherein the step of determining the set of live variables by a backward dataflow analysis does not include arguments of the phi functions.

Claim 30

The method of claim 29 wherein the backward dataflow analysis is performed beginning at an end of a basic block, 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.

Claim 31

The method of Claim 30 wherein the backward dataflow analysis is further performed by initially adding to said live set of variables those variables live at a beginning of children blocks of said basic block.

Claim 32

The method of Claim 31 wherein the backward dataflow analysis is iteratively performed until the live set of variables remain constant between successive iterations.

Claim 33

The method of Claim 28 wherein phi functions are added to the control flow graph where multiple definitions of a variable reach a use of that variable.

Claim 34

A computer controlled method of optimizing binary code of a target program which is compiled to run on a target computer architecture having a fixed number of CPU registers, said method comprising the steps of: 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; providing a 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 memory instead of in said fixed number of CPU registers, wherein said 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 the following sub-steps constructing an interference graph representing a procedure of said target program; determining a live set of variables for the target program by the sub-steps of performing a static single assignment transform of said procedure of said target program, including a step of adding phi functions to a control flow graph of said target program; inserting use blocks representative of a use of a variable in the control flow graph between a phi function and a block containing a definition of said variable; and determining said live set of variables for basic blocks in the Target program by a backward dataflow analysis of the control flow graph; mapping the live set of variables to the fixed number of CPU registers; and 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 memory instead of in said fixed number of CPU registers, whereby said target program binary code is optimized.

Claim 35

A computer controlled method for an improved code optimizer portion of a compiler which determines a target program's set of live variables comprising the steps of: in at least a portion of a control flow graph, inserting dummy blocks representative of a use of a variable in said control flow graph prior to a phi-function node; and determining the set of live variables by considering said dummy blocks.

Claim 36

In the computer controlled method of claim 35 wherein the step of inserting dummy blocks representative of a use of a variable in said control flow graph prior to a phi-function node includes the step of inserting a dummy block in each edge of said control flow graph which touches a phi-function block.