초록 ▼

Assigns suitable registers to a plurality of variables. A compiler converts a source program into instructions for a processor having: a simultaneously used variable acquisition section which obtains, with respect to each of a plurality of variables used in the source program, some of the other vari

Assigns suitable registers to a plurality of variables. A compiler converts a source program into instructions for a processor having: a simultaneously used variable acquisition section which obtains, with respect to each of a plurality of variables used in the source program, some of the other variables used simultaneously with the variable; an allocation sequence generation section which generates a plurality of allocation sequences between the plurality of variables to allocate each variable to one of the plurality of registers different from those to which some of the other variables used simultaneously with the variable are allocated; an allocation priority acquisition section which obtains allocation priorities indicating to which one of the plurality of registers each variable is allocated with priority; and a register allocation section which allocates the variables to registers in accordance with an allocation sequence selected on the basis of the allocation priorities.

대표청구항 ▼

We claim: 1. A computer apparatus having a storage medium, for compiling a source program comprising: a simultaneously used variable acquisition means, said apparatus converts a source program into instructions for a processor, said simultaneously used variable acquisition means obtains, with respe

We claim: 1. A computer apparatus having a storage medium, for compiling a source program comprising: a simultaneously used variable acquisition means, said apparatus converts a source program into instructions for a processor, said simultaneously used variable acquisition means obtains, with respect to each of a plurality of variables used in the source program, one or more other variables used simultaneously with the variable; an allocation sequence generation means which generates a plurality of allocation sequences between a plurality of variables to allocate each variable to one of the plurality of registers different from registers to which said one or more other variables used simultaneously with said each variable are allocated; an allocation priority acquisition means which obtains allocation priorities indicating to which one register from the plurality of registers each variable is allocated with priority, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a register allocation means which allocates the plurality of variables to registers in accordance with one of the allocation sequences selected on the basis of allocation priorities. 2. The apparatus as recited on claim 1, wherein said allocation sequence generation means generates a partial order of allocation between the plurality of variables to allocate each variable to one of the plurality of registers different from those to which said one or more other variables used simultaneously with the variable are allocated, and said register allocation means allocates the plurality of variables to the plurality of registers in accordance with an allocation sequence selected on the basis of certain allocation priorities while maintaining the partial order. 3. The apparatus as recited on claim 2, wherein said allocation sequence generation means includes: a first selection means which selects one or more of the variables used simultaneously only with a number of the variables smaller than the total number of a registers; a second selection means which selects one or more of the variables used simultaneously only with the number of the variables smaller than the total number of the registers among the variables excluding variables already selected; and a sequence determination means which generates a partial order in such a manner that when processing by said second selection means is applied to each variable, said each variable is set subsequent in the partial order to one or more of the other variables made selectable by excluding the variable. 4. The apparatus as recited on claim 2, further comprising a register allocation possibility determination means which generates new variables by dividing at least one of the variables into at least two variables if it determines that each variable can not be allocated to the register different from those to which said one or more other variables used simultaneously with the variable are allocated, wherein said register allocation possibility determination means repeating the execution with the new variables by said simultaneously used variable acquisition means, said allocation sequence generation means, and said register allocation means. 5. The apparatus as recited on claim 2, wherein said register allocation means includes: a storage means which stores at least one simultaneously allocation candidate variable in a top position in the partial order; an allocation selection means which selects one simultaneously allocation candidate variable among said at least one simultaneously allocation candidate variables on the basis of the allocation priorities; an allocation execution means which removes the one simultaneously allocation candidate variable from said storage means, and allocates the candidate variable to a register selected on the basis of the allocation priorities; and an allocation repeating means which newly stores in the storage means one or more of the variables that have no preceding variables not allocated to any of the registers among those lower in position in the partial order than the one simultaneously allocation candidate variable, and which repeats processing by said allocation execution means until said storage means becomes empty. 6. The apparatus as recited on claim 5, wherein said allocation execution means selects, as said simultaneously allocation candidate variable in the at least one simultaneously allocation candidate variables, one of the variables having a maximum of the difference between the highest allocation priority and the lowest allocation priority in the allocation priorities with respect to the register not assigned the variable simultaneously used, and assigns the selected variable to the available register that has the highest allocation priority. 7. The apparatus as recited on claim 1, further comprising an allocation priority generation means which generates, as the allocation priorities for allocation of each variable to one of the plurality of registers, at least one portion of register preference information indicating to which kind of register the variable should be allocated and variable relation information which is information indicating the relationship between the variable and the other variables on the source program, on the basis of the way in which the variable is used in the source program. 8. A computer apparatus having a storage medium, for compiling a source program comprising: an allocation priority generation means, said compiler converts a source program into instructions for a processor, said allocation priority generation means generates, as allocation priorities for allocation of each of a plurality of variables to one of a plurality of registers, at least one portion of register preference information indicating to which kind of register the variable should be allocated and variable relation information which is information indicating the relationship between the variable and the other variables on the source program, on the basis of the way in which the variable is used in the source program, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a register allocation means which allocates the plurality of variables to the plurality of registers on the basis of the allocation priorities. 9. The apparatus as recited on claim 8, wherein said register allocation means allocates to the register, with priority, particular variables having a maximum of the difference between the highest allocation priority and the lowest allocation priority among the plurality of variables. 10. The apparatus as recited on claim 8, wherein said allocation priority generation means generates register preference information indicating that the variables should be allocated with priority to some of the registers not used in the function if it is determined that the variable is used before a call for the function and after the call for the function. 11. The apparatus as recited on claim 8, wherein said allocation priority generation means generates register preference information indicating that a particular variable should be allocated with priority to an argument register or a return value register prescribed in a function call procedure of instructions if it is determined that the particular variable is used for handover of values between functions. 12. The apparatus as recited on claim 8, further comprising an execution record information acquisition means which obtains execution record information which can be obtained in advance when the processing in accordance with the source program is executed, wherein said allocation priority generation means generates, on the basis of the execution record information, register preference information indicating that one of the variables used in a portion of the source program executed with higher frequency should be allocated to the register with priority over the variables used only in other portions. 13. The apparatus as recited on claim 8, further comprising a loop analysis means which analyzes a loop portion repeatedly executed in the source program, wherein said allocation priority generation means generates register preference information indicating that one of the variables used in the loop portion should be allocated to the register with priority over the variables used in portions other than the loop portion. 14. The apparatus as recited on claim 8, wherein the compiler converts the source program into the instructions having a memory access instruction for transfer of data between the plurality of registers and a memory at consecutive addresses, and wherein said allocation priority generation means generates variable relation information which enables the plurality of variables in the source program transferring data to or from the memory at consecutive addresses to be allocated to the plurality of registers to which the combined memory access instruction can be applied. 15. The apparatus as recited on claim 8, further comprising an identical register allocation detection means which detects a combination of one or more of the plurality of variables such that if the variables in the combination are allocated to the same register, the speed of execution of the instructions is increased, wherein said allocation priority generation means generates variable relation information of the variables in the combination detected by said identical register allocation detection means to be applied to the one register. 16. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform functions for a compiler, said functions comprising the functions of the elements in claim 1. 17. A computer apparatus having a processor, for register allocation comprising: a simultaneously used variable acquisition means, said apparatus allocates a plurality of variables used in a source program to registers used in instructions for a processor, said simultaneously used variable acquisition means obtains, with respect to each variable, one or more of the other variables used simultaneously with the variable; an allocation sequence generation means which generates a plurality of allocation sequences between the plurality of variables to allocate each variable to one of the plurality of registers different from those to which one or more of the other variables used simultaneously with the variable are allocated; an allocation priority acquisition means which obtains allocation priorities indicating to which one of the plurality of registers each variable is allocated with priority, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a register allocation means which allocates the plurality of variables to the registers in accordance with one of the allocation sequences selected on the basis of the allocation priorities. 18. A computer apparatus having a processor, for register allocation comprising: an allocation priority generation means, said apparatus converts a plurality of variables used in a source program into registers used in instructions for a processor, said allocation priority generation means generates, as allocation priorities for allocation of each variable to one of the plurality of registers, at least one of register preference information indicating to which kind of register the variable should be allocated and variable relation information which is information indicating the relationship between the variable and the other variables on the source program, on the basis of the way in which the variable is used in the source program, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a register allocation means which allocates the plurality of variables to the plurality of registers on the basis of the allocation priorities. 19. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a register allocation apparatus, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 17. 20. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to operate as a compiler for converting a source program into instructions for a processor, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 1. 21. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a computer to operate as a compiler for converting a source program into instructions for a processor, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 8. 22. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing register allocation, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 17. 23. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing register allocation, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 18. 24. A compilation method of converting a source program into instructions for a processor, said method comprising: a step of obtaining, with respect to each of a plurality of variables used in the source program, one or more other variables used simultaneously with the variable; a step of generating a plurality of allocation sequences between the plurality of variables to allocate each variable to one of the plurality of registers different from those to which said one or more of the other variables used simultaneously with the variable are allocated; a step of obtaining allocation priorities indicating to which one of the plurality of registers each variable is allocated with priority, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a step of allocating the plurality of variables to the registers in accordance with one of the allocation sequences selected on the basis of the allocation priorities. 25. A compilation method of converting a source program into instructions for a processor, said method comprising: a step of generating, as allocation priorities for allocation of each of a plurality of variables used in the source program to one of a plurality of registers, at least one of register preference information indicating to which kind of register the variable should be allocated and variable relation information which is information indicating the relationship between the variable and the other variables on the source program, on the basis of the way in which the variable is used in the source program, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a step of allocating the plurality of variables to the plurality of registers on the basis of the allocation priorities. 26. A register allocation method of allocating a plurality of variables used in a source program to registers used in instructions for a processor, said method comprising: a step of obtaining, with respect to each variable, one or more other variables used simultaneously with the variable; a step of generating a plurality of allocation sequences between the plurality of variables to allocate each variable to one of the plurality of registers different from those to which said one or more other variables used simultaneously with the variable are allocated; a step of obtaining allocation priorities indicating to which one of the plurality of registers each variable is allocated with priority, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a step of allocating the plurality of variables to the registers in accordance with one of the allocation sequences selected on the basis of the allocation priorities. 27. A register allocation method of converting a plurality of variables used in a source program into registers used in instructions for a processor, said method comprising: a step of generating, as allocation priorities for allocation of each variable to one of the plurality of registers, at least one of register preference information indicating to which kind of register the variable should be allocated and variable relation information which is information indicating the relationship between the variable and the other variables on the source program, on the basis of the way in which the variable is used in the source program, the allocation priorities obtained at least from using variable combination information including at least information indicating relationship between the plurality of variables, information on loop portion of the source program and execution record information; and a step of allocating the plurality of variables to the plurality of registers on the basis of the allocation priorities. 28. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a register allocation apparatus, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 18. 29. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing compilation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 24. 30. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing compilation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 25. 31. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing register allocation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 26. 32. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compilation, said method steps comprising the steps of claim 25. 33. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for register allocation, said method steps comprising the steps of claim 26.