Patent ID: 8266603

Claim:
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, said method comprising: a first allocating step of selecting a 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 and said plurality of variables minus the replaced variables, in accordance with 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; 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; and a step of outputting said program having said registers allocated to said variables in said second allocating step.