Technique for allocating register to variable for compiling

A compiler apparatus configured to allocate registers to variables used in a program to be compiled, comprising:

• a storage device configured to store interference information indicating whether or not a certain variable and another variable used in said program have an interference relationship in which said variables concurrently hold effective values at any time point during an execution of said program, and assignment information in which a variable of an assignment source of an assignment instruction in said program is associated with a variable of an assignment destination of said assignment instruction;
• a first allocation section configured to select each variable used in said program, in accordance with a predetermined procedure and to allocate the variable to a respective register of a predetermined base number of registers, without allocating any two of a set of variables having said interference relationship to the same register of the predetermined base number of registers;
• an update section that is configured to reduce the number of said variables by replacing at least two of said variables with a new variable on condition that said replaced variables have the same said register allocated thereto by said first allocation section and are associated with each other in said assignment information, to read from a memory device said interference relationship concerning each of said plurality of variables, to merge said read interference relationships to generate an new interference relationship concerning said new variable, and to update said interference information according to said generated new interference relationship;
• a second allocation section that is configured to select each variable used in said program using said new variable and said plurality of variables minus the replaced variables, in accordance with said procedure of said first allocation section and to allocate the variable to a respective register of a predetermined base number of registers, without allocating to any two of a set of variables having said interference relationship based on said updated interference information to the same register of the predetermined base number of registers;
• a spill generator configured to select at least one of said plurality of variables and to generate instructions to store the selected variable in memory based upon a cost of storage determined by dividing the frequency of use of the variable in the program by the number of interference relationships of the at least one variable;
• and
• an output section that is configured to output said program having said registers allocated to each said variable used by said second allocation section.

A computer program product comprising a non-transitory computer useable medium including a computer readable program, wherein said computer readable program when executed on a computer causes said computer to perform the method steps for a compiling method for causing a computer to allocate registers to variables used in a program to be compiled, wherein said computer includes a storage device that stores interference information indicating whether or not a certain variable and another variable used in said program have an interference relationship in which these variables concurrently hold effective values at any time point during execution of the program, and assignment information in which a variable of an assignment source of an assignment instruction in said program is associated with a variable of an assignment destination of said assignment instruction, the method comprising the steps of:

• a first allocating step of selecting each variable used in said program, in accordance with a predetermined procedure and allocating the variable to a respective register of a predetermined base number of registers, without allocating any two of a set of variables having said interference relationship to the same register of the predetermined base number of registers;
• a step of replacing a plurality of aforementioned variables with a new variable on condition that said plurality of variables have same said register allocated thereto in said first allocating step and are associated with each other in said assignment information, reading from said memory device said interference relationship concerning each of said plurality of variables, merging said read interference relationships to generate an interference relationship concerning said new variable, and updating said interference information according to said generated interference relationship;
• a second allocating step of selecting each variable used in said program using said new variable instead of said plurality of variables, in accordance with same said predetermined procedure as that in said first allocating step and allocating the variable to a respective register of a predetermined base number of registers, without allocating any two of a set of variables having said interference relationship based on said updated interference information to the same register of the predetermined base number of registers;
• and
• a step of storing in memory at least one of the variables used in said program based upon a cost of storing said at least one variable determined by dividing the frequency of use of the variable in the program by the number of interference relationships of the at least one variable;
• a step of outputting said program having said registers allocated to said variables in said second allocating step.