Resource assignment apparatus

Abstract

A resource assignment apparatus for use with a software compiler or translator for compiling or translating a high-level source program into a machine language program, wherein the resource assignment apparatus assigns the variables in the high-level source program to system resources consisting of registers, memory, and the like. The resource assignment apparatus generates assignments consisting of the variables and their live ranges and finds the interference cost incurred when assigning these various assignments to each of the various resources, consisting of data registers, address registers, memory, and the like. The apparatus sorts the assignments into groups whereby these interference costs will be the lowest. The resource element minority assignment unit then carries out the assigning of each of these groups of sorted assignment. The various assignments with live ranges which interfere are assigned to different resource elements. When there are a number of resource elements to which an assignment can be assigned, the apparatus determines which is the most appropriate resource element, and assigns the assignment to this most appropriate resource element. When there is no resource element for which assigning is possible, the assignment is then moved to another resource group.

Claims

What is claimed is:

1. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means for each of the resource elements determined by the same resource remaining resource element determination means;

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the priority values of the assignments determined by the coherent assignment determination means and, moreover, whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the first loss occurring resource element determination means being set at 0.

2. The resource assignment apparatus of claim 1, wherein

the second resource element assigning means comprises:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists.

3. The resource assignment apparatus of claim 2, further comprising:

profit value calculation means for calculating the profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating the loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means; and

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means.

4. The resource assignment apparatus of claim 3, wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the priority values of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

5. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means, the second resource element assigning means comprising:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference,

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means, and

wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the priority values of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0;

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means,

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the priority values of the assignments determined by the coherent assignment determination means and, moreover, whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the first loss occurring resource element determination means being set at 0.

6. The resource assignment apparatus of claim 5, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned,

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which is assigned to the resource element to the loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

7. The resource assignment apparatus of claim 5, further comprising:

non-commutative operation operand determination means for determining whether the assignment taken by the assignment retrieval means is on a right side of an operator of a non-commutative operation such as subtraction and division; and

third loss occurring resource element retrieval means for retrieving a resource element to which the assignment defined by the non-commutative operation is assigned, once the non-commutative operation operand determination means has determined that the assignment is on the right side;

wherein, once the third loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which are assigned to the resource element to the loss value of the resource element which is the retrieved result of the third loss occurring resource element retrieval means.

8. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means:

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means, the second resource element assigning means comprising:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists;

control means for repeatedly having the assignment retrieval means activated until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means:

greatest difference resource element determination means for calculating difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means; and

loop-nesting depth level retrieval means for retrieving a loop-nesting depth level of each of the loops in the program;

wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the loop-nesting depth levels of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

9. The resource assignment apparatus of claim 8, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means,

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the loop-nesting depth levels of each of the assignments determined by the coherent assignment determination unit and, moreover, whose live range interferes with the live range of the assignment which are assigned to the resource element, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

10. The resource assignment apparatus of claim 9, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned;

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the loop-nesting depth levels of the assignments which are assigned to the resource elements to the loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

11. The resource assignment apparatus of claim 10, further comprising:

non-commutative operation operand determination means for determining whether the assignment taken by the assignment retrieval means is on a right side of an operator of a non-commutative operation such as subtraction and division; and

third loss occurring resource element retrieval means for retrieving a resource element to which the assignment defined by the non-commutative operation is assigned, once the non-commutative operation operand determination means has determined that the assignment is on the right side;

wherein, once the third loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the loop-nesting depth levels of the assignments which are assigned to the resource element to the loss value of the resource element which is the retrieved result of the third loss occurring resource element retrieval means.

12. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means, the second resource element assigning means comprising:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means;

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means; and

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means; and

wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means, based on a number of assignments out of the retrieved results of the coherent assignment retrieval means which are assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

13. The resource assignment apparatus of claim 12, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the number of assignments which are assigned determined by the coherent assignment determination unit and, moreover, whose live range interferes with the live ranges of the assignments which are assigned to the resource element, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

14. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means:

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means, the second resource element assigning means comprising:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means; and

execution frequency storage means for storing a frequency which shows how often each step in the program is executed corresponding to every step in the program; and execution frequency totalling means for totalling the frequencies of steps in the program for every assignment stored in the assignment storage means, setting the corresponding totalled values as the execution frequency of every assignment;

wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the execution frequencies of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

15. The resource assignment apparatus of claim 14, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means,

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the execution frequencies of each of the assignments determined by the coherent assignment determination means and whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

16. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval means;

succession resource element determination means for determining the resource element to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means, the second resource element assigning means comprising:

first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

profit value calculation means for calculating a profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating a loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means.;

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means;

global group creation means for retrieving a plurality of assignments whose live ranges are connected one after another, out of the assignments stored in the assignment storage means, and setting the retrieved assignments as a global group;

global group retrieval means for retrieving a global group which contains the assignment retrieved by the assignment retrieval means, when there are a plurality of resource elements determined by the greatest resource element determination means; and

global profit value calculation means for calculating a global profit value which shows how memory size and/or execution time are reduced if an as yet unassigned assignment is assigned to a common resource element, for each of the resource elements determined by the same resource remaining resource element determination means; and global loss calculation means for calculating a global loss value which shows how memory size and/or execution time are increased if an as yet unassigned assignment is assigned to a common resource element, for each of the resource elements determined by the same resource remaining resource element determination means;

wherein for a case when a plurality of resource elements are determined by the greatest difference resource element determination means, the third assigning means calculates a difference between the global profit value and the global loss value, and then assigns the taken assignment to a resource element for which the difference is greatest.

17. The resource assignment apparatus of claim 16, wherein

the global profit value calculation means comprises:

a first global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, a global group to which the retrieved assignment belongs;

a global profit value storage unit for storing a total of the profit values for every resource element corresponding to a global group as the global profit value; and

a first total value managing unit for adding, once the profit value calculation means has calculated the profit value of a resource element for the assignment, the profit value to the global profit value of the resource element.

18. The resource assignment apparatus of claim 17, wherein

the global loss calculation means comprises:

an interfering global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, global groups which contain the assignments which are the retrieval results of the interfering assignment retrieval means in regard to the taken assignment;

a second total storage unit for storing the total of the priority values of the assignments belonging to the global group as the global loss value corresponding to every resource element; and

a second total managing unit for adding, once the profit value calculation means has calculated the profit value of the resource element for the assignment retrieved by the assignment retrieval means, the priority value of assignment for the resource element which is the retrieval result of the interfering assignment retrieval means to the total of the global loss value for the resource element.

19. The resource assignment apparatus of claim 16, wherein

the global profit value calculation means comprise:

a first global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, the global group to which the assignment belongs;

a first total storage unit for storing the number of assignments in a global group assigned to a resource element as the global profit value corresponding to each of the resource elements; and

a first total managing unit for adding, once the profit value calculation means has calculated the profit value of a resource element for an assignment, 1 to the global profit value of the resource element.

20. The resource assignment apparatus of claim 19, wherein

the global loss value calculation means comprises:

an interfering global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, the global groups which contain the assignments which are the retrieval result of the interfering assignment retrieval means in regard to the taken assignment;

a second total storage unit for storing a number of assignments assigned to resource elements belonging to a global group as the global loss value corresponding to every resource element; and

a second total managing unit for adding 1 to the global loss value of the resource element, once the profit value calculation means has calculated the profit value of a resource element for an assignment retrieved by the assignment retrieval means.

21. The resource assignment apparatus of claim 18, wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the priority values of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

22. The resource assignment apparatus of claim 21, further comprising:

secondary interfering assignment retrieval means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment retrieval means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the priority values of each of the assignments determined by the coherent assignment determination unit and, moreover, whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

23. The resource assignment apparatus of claim 22, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned;

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which are assigned to the resource element to the loss value and the global loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

24. The resource assignment apparatus of claim 23, further comprising:

non-commutative operation operand determination means for determining whether the assignment taken by the assignment retrieval means is on a right side of an operator of a non-commutative operation such as subtraction and division; and

third loss occurring resource element retrieval means for retrieving a resource element to which the assignment defined by the non-commutative operation is defined, once the non-commutative operation operand determination means has determined that the assignment is on the right side;

wherein, once the third loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which are assigned to the resource element to the loss value and global loss value of the resource element which is the retrieved result of the third loss occurring resource element retrieval means.

25. The resource assignment apparatus of claim 18, further comprising:

loop-nesting depth level retrieval means for retrieving a loop-nesting depth level of each of the loops in the program;

wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the loop-nesting depth levels of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

26. The resource assignment apparatus of claim 25, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the loop-nesting depth levels of each of the assignments determined by the coherent assignment determination unit and, moreover, whose live range interferes with the live range of the assignment which are assigned to the resource element, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

27. The resource assignment apparatus of claim 26, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned;

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the loop-nesting depth levels of the assignments which are assigned to the resource elements to the loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

28. The resource assignment apparatus of claim 27, further comprising:

non-commutative operation operand determination means for determining whether the assignment taken by the assignment retrieval means is on a right side of an operator of a non-commutative operation such as subtraction and division; and

third loss occurring resource element retrieval means for retrieving a resource element to which the assignment defined by the non-commutative operation is assigned, once the non-commutative operation operand determination means has determined that the assignment is on the right side;

wherein, once the third loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the loop-nesting depth levels of the assignments which are assigned to the resource element to the loss value of the resource element which is the retrieved result of the third loss occurring resource element retrieval means.

29. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program written in programming language to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

cost storage means for storing for every resource a cost which shows code size and/or execution time of every instruction used by the resource;

cost retrieval means for retrieving the cost for every resource by referring to the cost storage means, for each of the instructions in a program which are used in the live range of a variable in one assignment;

cost totalling means for totalling the costs retrieved by the cost retrieval means of each of the assignments for each resource;

priority value calculation means for calculating the priority value based on the cost total value calculated for each of the assignments and the live ranges of the various assignments;

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform the same function as each of the resource elements to which the assignment extracted by the interfering assignment extraction means has been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment taken by the assignment retrieval means and assignments for which an end point is coincident with the same starting point of the assignment taken by the assignment retrieval means;

succession resource element determination means for determining the resource elements to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the succession resource element determination means and, moreover, the determination result of the same resource remaining resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means; and

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned.

30. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program written in programming language to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

cost storage means for storing for every resource a cost which shows code size and/or execution time of every instruction used by the resource;

cost retrieval means for retrieving the cost for every resource by referring to the cost storage means, for each of the instructions in a program which are used in the live range of a variable in one assignment;

cost totalling means for totalling the costs retrieved by the cost retrieval means of each of the assignments for each resource;

priority value calculation means for calculating the priority value based on the cost total value calculated for each of the assignments and the live ranges of the various assignments;

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning the assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform the same function as each of the resource elements to which the assignment extracted by the interfering assignment extraction means has been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment taken by the assignment retrieval means and assignments for which an end point is coincident with the same starting point of the assignment taken by the assignment retrieval means;

succession resource element determination means for determining the resource elements to which the assignments retrieved by the coherent assignment retrieval means are assigned, by referring to the assigning result storage means;

second resource element assigning means for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the succession resource element determination means and, moreover, the determination result of the same resource remaining resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means;

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned; and

resource classified assignment supply means for supplying all of the assignments which can be assigned to the same resource to the assignment storage means, wherein

the resource classified assignment supply means comprises:

resource determination means for determining which resource has a lowest total cost, out of the totalled costs for the various assignments calculated by the cost totalling means;

resource classified group conversion means for referring to the various assignments and the resources which correspond to the assignments determined by the resource determination means and converting into groups the assignments obtained as having the same determination results to form resource classified groups;

resource classified group selection means for selecting one group out of the several resource classified groups formed by the resource classified group conversion means;

resource classified group writing means for writing the resource classified group selected by the resource classified group selection means into the assignment storage means; and

control means for indicating a selection of a next resource classified group, when all the assignments stored in the assignment storage means have been taken by the assignment retrieval means.

31. The resource assignment apparatus of claim 30, further comprising:

resource classified group cost totalling means for totalling the total cost values of the assignments found by the cost totalling means for each of the resource classified groups formed by the resource classified group conversion means;

wherein the resource classified group selection means selects a resource classified group with a highest total cost totalled by the group cost totalling means, out of as yet unselected resource classified groups.

32. The resource assignment apparatus of claim 31, wherein

the same resource remaining resource element determination means further comprises:

first resource classified group determination means for determining the resource classified group to which the assignment retrieved by the assignment retrieval means belongs;

second resource classified group determination means for determining, when all of the resource elements of the resource corresponding to the resource classified group have been assigned assignments retrieved by the interfering assignment retrieval means, the resource classified group for an assignment with a higher cost value total for the assignment than the first determined resource but, moreover, with a lowest total cost value; and

first transference means for transferring, once the second resource classified group determination means has determined a resource classified group, an assignment retrieved by the assignment retrieval means from the resource classified group determined by the first resource classified group determination means to the resource classified group determined by the second resource classified group determination means.

33. The resource assignment apparatus of claim 32, wherein

the cost totalling means further comprises:

loop-nesting depth level retrieval means for retrieving the loop-nesting depth level of the loop processes for the various instructions using the variable in one assignment;

wherein the cost totalling means adds the loop-nesting depth level to the cost retrieved by the cost retrieval means.

34. The resource assignment apparatus of claim 30, further comprising:

group element count retrieval means for retrieving a number of the assignments belonging to one resource classified group;

wherein the resource classified group selection means selects the resource classified group with a highest number of assignments retrieved by the group element count retrieval means, out of the as yet unselected resource classified groups.

35. The resource assignment apparatus of claim 34, wherein

the same resource remaining resource element determination means further comprises:

first resource classified group determination means for determining the resource classified group to which the assignment retrieved by the resource retrieval means belongs;

second resource classified group determination means for determining the resource classified group with a next highest number of assignments, when all of the resource elements of the resource corresponding to the resource classified group which is the determination result of the first resource classified group determination means have been assigned assignments retrieved by the interfering assignment retrieval means; and

a first transference means for transferring, once the second resource classified group determination means has determined a resource classified group, an assignment retrieved by the assignment retrieval means from the resource classified group determined by the first resource classified group determination means to the resource classified group determined by the second resource classified group determination means.

36. The resource assignment apparatus of claim 30, further comprising:

resource element number retrieval means for retrieving a number of resource elements in a resource corresponding to a resource classified group;

wherein the resource classified group selection means selects the resource classified groups in order of the number of resource elements retrieved by the resource element number retrieval means starting with a lowest number.

37. The resource assignment apparatus of claim 36, wherein

the same resource remaining resource element determination means further comprises:

first resource classified group determination means for determining the resource classified group to which an assignment retrieved by the assignment retrieval means belongs;

second resource classified group determination means for determining the resource classified group with a next lowest number of resource elements, when all of the resource elements of the resource corresponding to a resource classified group have been assigned assignments retrieved by the interfering assignment retrieval means; and

a first transference means for transferring, once the second resource classified group determination means has determined a resource classified group, an assignment retrieved by the assignment retrieval means from the resource classified group determined by the first resource classified group determination means to the resource classified group determined by the second resource classified group determination means.

38. The resource assignment apparatus of claim 29, further comprising:

resource element number determination means for referring to the assigning result storage means and finding a number of resource elements which have already been assigned, out of the retrieval result of the interfering assignment retrieval means in regard to the assignment retrieved by the assignment retrieval means, wherein

the priority value calculation means recalculates the priority value of the assignments stored by the assignment storage means, based on the determination results of the resource element number determination means.

39. The resource assignment apparatus of claim 29, further comprising:

resource element number determination means for referring to the assigning result storage means and finding a number of resource elements which have already been assigned, out of the retrieval results of the coherent assignment retrieval means in regard to the assignment extracted by the assignment extraction means, wherein

the priority value calculation means recalculates the priority value of the assignments stored by the assignment storage means, based on the determination results of the resource element number determination means.

40. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program written in programming language to resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

reserved assignment extraction means for extracting assignments in the program which should be assigned to a previously determined resource element;

reserved resource element storage means for storing the resource elements to which the assignments extracted by the reserved assignment extraction means should be assigned;

reserved assigning means for assigning the assignments extracted by the reserved assignment extraction means to the corresponding resource elements out of the resource elements stored by the reserved resource element storage means, and having the assigning results stored by the assigning result storage means;

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning an assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment taken by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment taken by the assignment retrieval means;

succession resource element determination means for determining the resource elements to which the assignments retrieved by the coherent assignment retrieval means can be assigned, by referring to the assigning result storage means;

second resource element assigning means

for assigning, when there is only one resource element determined by the same resource remaining element determination means, the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means; and

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned.

41. A resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program written in programming language to resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising:

reserved assignment extraction means for extracting assignments in the program which should be assigned to a previously determined resource element;

reserved resource element storage means for storing the resource elements to which the assignments extracted by the reserved assignment extraction means should be assigned;

reserved assigning means for assigning the assignments extracted by the reserved assignment extraction means to the corresponding resource elements out of the resource elements stored by the reserved resource element storage means, and having the assigning results stored by the assigning result storage means;

assignment storage means for storing the assignments in a program and their priority values;

first resource element assigning means for taking an assignment with a highest priority value from the assignment storage means and assigning an assignment with the highest priority value to a resource element;

assigning result storage means for storing assigning results;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned;

interfering assignment extraction means for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval means;

same resource remaining resource element determination means for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction means have been assigned by referring to the assigning result storage means;

coherent assignment retrieval means for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment taken by the assignment retrieval means and assignments for which an end point is coincident with the starting point of the assignment taken by the assignment retrieval means;

succession resource element determination means for determining the resource elements to which the assignments retrieved by the coherent assignment retrieval means can be assigned, by referring to the assigning result storage means;

second resource element assigning means for assigning, when there is only one resource element determined by the same resource remaining element determination means the assignment retrieved by the assignment retrieval means to the resource element,

for assigning the assignment taken by the assignment retrieval means to any resource element which is the determination result of the same resource remaining resource element determination means and, moreover, the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists,

and for storing the assigning result in the assigning result storage means; and

control means for repeatedly having the assignment retrieval means activated, until all of the assignments have been assigned;

the second resource element assigning means comprising: first assigning means for assigning, when there is only one resource element determined by the same resource remaining resource element determination means, the assignment taken by the assignment retrieval means to the resource element;

second assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined by the same resource remaining resource element determination means when there is a plurality of resource elements determined by the same resource remaining resource element determination means and there is no corresponding resource element determined by the succession resource element determination means; and

third assigning means for assigning the assignment taken by the assignment retrieval means to any of the resource elements determined as the determination result of the same resource remaining resource element determination means and, moreover, determined as the determination result of the succession resource element determination means, when there is a plurality of resource elements determined by the same resource remaining resource element determination means and a resource element determined by the succession resource element determination means exists.

42. The resource assignment apparatus of claim 41, further comprising:

profit value calculation means for calculating the profit value which shows how memory size and/or execution time are reduced for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means;

loss value calculation means for calculating the loss value which shows how memory size and/or execution time are increased for a machine language program after compiling if an assignment is assigned to one of the resource elements determined by the same resource remaining resource element determination means, for each of the resource elements determined by the same resource remaining resource element determination means; and

greatest difference resource element determination means for calculating a difference between the profit value and the loss value and determining which resource elements have a greatest difference;

wherein the third assigning means assigns the assignments retrieved by the assignment retrieval means to one of the resource elements determined by the greatest difference resource element determination means.

43. The resource assignment apparatus of claim 42, wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the priority values of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

44. The resource assignment apparatus of claim 43, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the priority values of the assignments determined by the coherent assignment determination means and, moreover, whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

45. The resource assignment apparatus of claim 44, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned;

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which is assigned to the resource element to the loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

46. The resource assignment apparatus of claim 45, further comprising:

secondary interfering assignment extraction means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment extraction means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the execution frequencies of each of the assignments determined by the coherent assignment determination means and whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

47. The resource assignment apparatus of claim 46, further comprising:

global group creation means for retrieving a plurality of assignments whose live ranges are connected one after another, out of the assignments stored in the assignment storage means, and setting the retrieved assignments as a global group;

global group retrieval means for retrieving a global group which contains the assignment retrieved by the assignment retrieval means, when there are a plurality of resource elements determined by the greatest resource element determination means;

global profit value calculation means for calculating a global profit value which shows how memory size and/or execution time are reduced if an as yet unassigned assignment is assigned to a common resource element, for each of the resource elements determined by the same resource remaining resource element determination means; and

global loss calculation means for calculating a global loss value which shows how memory size and/or execution time are increased if an as yet unassigned assignment is assigned to a common resource element, for each of the resource elements determined by the same resource remaining resource element determination means;

wherein for a case when a plurality of resource elements are determined by the greatest difference resource element determination means, the third assigning means calculates a difference between the global profit value and the global loss value, and then assigns the taken assignment to a resource element for which the difference is greatest.

48. The resource assignment apparatus of claim 47, wherein

the global profit value calculation means comprises:

a first global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, a global group to which the retrieved assignment belongs;

a global profit value storage unit for storing a total of the profit values for every resource element corresponding to a global group as the global profit value; and

a first total value managing unit for adding, once the profit value calculation means has calculated the profit value of a resource element for the assignment, the profit value to the global profit value of the resource element.

49. The resource assignment apparatus of claim 48, wherein

the global loss calculation means comprises:

an interfering global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, global groups which contain the assignments which are the retrieval results of the interfering assignment retrieval means in regard to the taken assignment;

a second total storage unit for storing the total of the priority values of the assignments belonging to the global group as the global loss value corresponding to every resource element; and

a second total managing unit for adding, once the profit value calculation means has calculated the profit value of the resource element for the assignment retrieved by the assignment retrieval means, the priority value of assignment for the resource element which is the retrieval result of the interfering assignment retrieval means to the total of the global loss value for the resource element.

50. The resource assignment apparatus of claim 49, wherein

the global profit value calculation means comprises:

a first global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, the global group to which the assignment belongs;

a first total storage unit for storing the number of assignments in a global group assigned to a resource element as the global profit value corresponding to each of the resource elements; and

a first total managing unit for adding, once the profit value calculation means has calculated the profit value of a resource element for an assignment, 1 to the global profit value of the resource element.

51. The resource assignment apparatus of claim 50, wherein

the global loss value calculation means comprises:

an interfering global group retrieval unit for retrieving, once the assignment retrieval means has retrieved an assignment, the global groups which contain the assignments which are the retrieval result of the interfering assignment retrieval means in regard to the taken assignment;

a second total storage unit for storing a number of assignments assigned to resource elements belonging to a global group as the global loss value corresponding to every resource element; and

a second total managing unit for adding 1 to the global loss value of the resource element, once the profit value calculation means has calculated the profit value of a resource element for an assignment retrieved by the assignment retrieval means.

52. The resource assignment apparatus of claim 51, wherein the profit value calculation means calculates the profit value for the resource element determined by the succession resource element determination means based on the priority values of the assignments assigned to the resource element, with the profit values of the resource elements aside from the resource element determined by the succession resource element determination means being set to equal 0.

53. The resource assignment apparatus of claim 52, further comprising:

secondary interfering assignment retrieval means for retrieving assignments which have live ranges which interfere with the live ranges of the assignments retrieved by the coherent assignment retrieval means, but are not the retrieved results of the interfering assignment retrieval means; and

first loss occurring resource element determination means for determining to which resource elements the assignments which are the retrieval results of the secondary interfering assignment retrieval means are assigned, by referring to the assigning result storage means;

wherein the loss value calculation means calculates loss values of the resource elements determined by the first loss occurring resource element determination means based on the priority values of each of the assignments determined by the coherent assignment determination unit and, moreover, whose live range interferes with the live range of the assignment which is assigned to each of the resource elements, with the loss values of all of the resource elements aside from the resource element determined by the loss occurring resource element determination means being set at 0.

54. The resource assignment apparatus of claim 53, further comprising:

non-commutative operation definition determination means for determining whether the assignment taken by the assignment retrieval means is defined by a non-commutative operation such as subtraction and division; and

second loss occurring resource element retrieval means for retrieving, when the non-commutative operation definition determination means determines that the assignment is defined as a non-commutative operation, a resource element to which an assignment which is on a right side of an operator of the non-commutative operation is assigned;

wherein, once the second loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which are assigned to the resource element to the loss value and the global loss value of the resource element which is the determination result of the second loss occurring resource element retrieval means.

55. The resource assignment apparatus of claim 54, further comprising:

non-commutative operation operand determination means for determining whether the assignment taken by the assignment retrieval means is on a right side of an operator of a non-commutative operation such as subtraction and division; and

third loss occurring resource element retrieval means for retrieving a resource element to which the assignment defined by the non-commutative operation is defined, once the non-commutative operation operand determination means has determined that the assignment is on the right side;

wherein, once the third loss occurring resource element retrieval means has retrieved the resource element, the loss calculation means adds the priority values of the assignments which are assigned to the resource element to the loss value and global loss value of the resource element which is the retrieved result of the third loss occurring resource element retrieval means.

56. The resource assignment apparatus of claim 55, wherein the reserved assignment extraction means extracts assignments which store arguments for function calls from the program, and the reserved resource element storage means stores argument registers to which the assignments should be assigned.

57. The resource assignment apparatus of claim 55 wherein the reserved assignment extraction means extracts assignments which store return values for function calls from the program, and the reserved resource element storage means stores return value registers to which the assignments should be assigned.

58. The resource assignment apparatus of claim 55 wherein the reserved assignment extraction means extracts the assignments whose values may be changed from the program, and the reserved resource element storage means stores broken registers to which the assignments should be assigned.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a resource assignment apparatus which assigns the variables in a program to resources such as registers and memory, to be used by a compiler when compiling a program written in a high-level language into machine language.

2. Description of the Related Art

In recent years, there have been many improvements in the efficiency of program development by writing programs in high-level programming languages, such as C language.

By using high-level programming languages, the programmer can express such processes as the storage, operation and transmission of numerical values as operations (steps) taking the variables as operands. Since these variables are defined voluntarily by the programmer, and comprise of the necessary number of figures, the operator can describe the program freely. When compiled, these described programs (known as source programs) become machine language programs which can be understood by the computer. Operations in such machine language programs are expressed as machine language instructions, and since these machine language instructions take the registers and memory as operands, it becomes necessary to assign the above variables to the registers and memory. This assigning process is known as the resource assignment process.

Before describing the resource assignment process under the prior art, several of the terms to be used will be explained.

Live Range

The live range, in its widest sense, refers to the range for which the stored value of the variables is valid, while in its narrowest sense, it refers to the range of the program from the step in which values are substituted into the variable to the step in which these substituted values are used.

FIGS. 1A and 1B show one example of a source program and the corresponding live ranges. The live ranges are shown by lines s1, s2, and s3 in FIG. 1B. The defining step and final using step mentioned above are known respectively as the starting point and the end point and are expressed in the drawing by the points p1, p2, p3, p4, p5 etc. In FIG. 1B, there are two starting points for each of the variables c and d, but this is because variables c, d are defined in terms of the two processes p1 and p2 in the decision statement if (b.gtoreq.10) {process p1} else {process p2}.

Assignment

The assignment of resources can be simply the taking of a variable, but, since the assignment can be to several separate resource elements for each respective live range, when there are several live ranges for one variable, this specification takes an assignment as the combination of a variable and live range.

Priority Value

This is the parameter for deciding the order of resource assignment. The following aspects of the program for each assignment; activity ratios, the loop-nesting depth level of loop processes, live ranges, and combinations of them are reflected in the priority value.

An example of a priority value calculation based on the activity ratio of the assignment is given below as {numerical equation 1}.

{Numerical Equation 1}

priority value=activity ratio=(number of def+number of use)/length of live range.

›def! and ›use! here refer respectively to the step whereby a value is substituted into the assignment, and to the step whereby this substituted value is used.

The loop-nesting depth level of a loop process may also be used in this calculation of priority value. Also, if there are other assignments whose live ranges interfere, then other assignment numbers may also be used in calculating assignment priority value.

Resource Element

This refers to the smallest unit among the elements in the computer hardware to which an assignment can be assigned. Buffers for temporarily storing a value, individual registers, memory elements of a single address in the memory are all examples of this. The number 0 register, the number 1 register, the memory at address 10 and the memory at address 101 are all different resource elements.

Resource

This refers to a group of resource elements which perform the same function.

For example, resources consist of memory and registers. Registers can be subdivided into address registers, data registers, global registers and local registers which all perform a given function. Additionally, memory can be subdivided in terms of fulfilling the functions of high-speed memory and low-speed memory. If it is possible to subdivide the resource elements in this way into groups which perform the same function, then each of these subdivisions becomes a resource.

Interference Graph

The interference graph is a graph to show pictorially the interference between the live ranges of two or more assignments. The interference graph has the assignments as its vertices, and shows the assignments (vertices) where the live ranges interfere as joined together as their edges.

Degree of Vertex

The number of edges joining one vertex in the interference graph.

FIG. 2 shows a construction of a compiler. This compiler is comprised of a syntax analysis apparatus 21, an optimizing apparatus 22, a resource assignment apparatus 23, and a code generation apparatus 24. The following is an explanation of the different components of this compiler with reference to the construction in FIG. 2, and to the tables FIGS. 3A, 3B and 3C.

The syntax analysis apparatus 21 executes the lexical analysis, the syntax analysis and the meaning analysis for the source program stored as a file in the storage apparatus (not shown in the figure), and converts the source program into an intermediate language program.

The optimizing apparatus 22 executes the optimizing of the intermediate language program with the object of minimizing the program size and the process execution time when finally generating the machine language program. Since the details of this optimizing are not the gist of this invention, they have been omitted, and only the aspects which are especially related to the resource assignment have been explained. The optimizing operation includes a basic block conversion operation, control flow analysis, and data flow analysis. Basic block conversion refers to the divided of the program to be processed into basic blocks.

This is a simplified explanation of this division process. First of all, the optimizing apparatus 22 refers to the first step in the intermediate language program, steps having a direction given by an either unconditional or a conditional jump, and steps coming directly after an unconditional or conditional jump and regards them as the leaders. Then the optimizing apparatus 22 extracts all of the program steps starting from the first leader and continues as far as the line coming before the next leader or the end of the program. The set of instructions obtained by this extraction process is known as a basic block, and becomes the unit of the following processes.

The control flow analysis analyzes the control flow within every basic block. The data flow analysis analyzes where each variable was substituted and where each variable was used within each separate block. By referring to the results of these analyses, the live ranges of the variables are obtained.

The resource assignment apparatus 23 is an algorithm for assigning resources, which assigns the registers and memory to the assignments in the intermediate language program by using a graph coloring method by means of graph degeneration. The graph coloring method by means of graph degeneration is an algorithm which executes the classification of every vertex in the interference graph with approximately the least number of colors, according to the principle where, in color classifying, every vertex which is joined to the edge is painted in a different color. The assignments in the program shown in FIG. 3A are assigned to the resource elements by the resource assignment process shown in FIG. 3B. In these drawings, the assignment a shown in FIG. 3A is shown as being assigned to resource element R0, while assignment b2 is shown as being assigned to resource element R2.

The code generation apparatus 24 executes the machine language instruction conversion for every step in the program in its intermediate language state shown in FIG. 3A, and converts this program in an intermediate language state into a machine language program (shown in FIG. 3C) that can be understood by the target machine. The machine code program which is the result of this conversion by the code generation apparatus 24 is called the object program. The machine language instructions in this object program and the corresponding instructions in the program of FIG. 3A are shown by the symbols (1), (2), (3), (4) etc.. In the above machine language instruction conversion, the resource assignment results shown in FIG. 3B are used as the machine language instruction operands. Also the transmission instructions in the drawing x11, x12, x13, x14, x15 etc. are generated by the code generation apparatus 24 so that the processing of every step in the program shown in FIG. 3A can be realized as machine language instructions. Also, depending on the results of the resource allocation, it can be that several of these transmission instructions become unnecessary. In FIG. 3C, since in (7) assignments b2 and c are both assigned to the same register, then this is an example of where transmission instruction generation becomes unnecessary.

The following is an explanation of the resource assignment apparatus 23. The details of the resource assignment process using the graph coloring method mention above are described by the following documents.

›1! A. V. Aho, R. Sethi, J. D. Ullman; "Compilers Principles, Techniques and Tools" Addison-Wesley, 1986

›2! Chaitin..; "Register allocation and spilling via graph coloring", proceeding of the ACM Symposium on Compiler Construction (June 1982), 98-105.

›3! Chaitin..; "Register allocation and spilling via graph coloring", U.S. Pat. No. 4,571,678, Feb. 18, 1986.

›4! Frederick Chow, John Hennessy; "Register Allocation by Priority-based Coloring", Computer Systems Laboratory, Stanford University.

›5! David Bernstein, . . . Ron Y. Pinter; "Spill code minimization techniques of optimizing compilers", SIGPLAN 1989, IBM Israel Science and Technology Technion City Haifa, Israel.

›6! Masataka Sasa; "Programming Gengo Shorikei", Register Assignment p420-p423, Iwanami Books.

The construction of the aforementioned resource assignment apparatus 23 is shown in FIG. 4. As shown in FIG. 4, the resource assignment apparatus 23 is comprised of an assignment generation unit 41 for generating the assignments in accordance with the process results of the optimizing apparatus 22, an assignment storage unit 42 for storing the assignments generated by the assignment generation unit 41, a priority value calculator 43 for calculating by means of the equation given above as {numerical equation 1}, and storing, the priority value of every assignment stored in the assignment storage unit 42, a live range information storage unit 44 for storing the information about the live ranges, as shown in FIG. 1B, for every assignment and the information as to how these live ranges interfere, a expansion unit 45 for expanding all of the assignments stored in the storage unit 42 in the interference graph, a buffer 46 for the expansion by the expansion unit 45, a stack 47 for piling up all the assignments once they have been expanded by the expansion unit 45, a control unit 40 for executing the resource assignment by means of the above method graph coloring method according to the graph degeneration, and a storage unit 48 for storing the assignment result in the form shown in FIG. 3B.

FIGS. 5A, 5B, and 6A through 6I are explanation tables for explaining the method graph coloring method according to the graph degeneration. The following is an explanation of the operational process of the resource assignment apparatus 23 with reference to these drawings. The number of registers for which assignment is possible is given as 3, with the assignments which cannot be assigned to these registers being assigned to the memory.

The aforementioned expansion unit 45 expresses the assignments shown in FIG. 3A and the interference between the live ranges between these assignments in the interference graph, as shown in FIG. 5A. In this kind of interference graph, the extent to which every assignment interferes with the live range of which other assignments is shown as the degree of vertex. Also, as is shown in FIG. 1B, when the starting point and end point of live ranges in one step are the same (assignments b2 and c in FIG. 1B), in order to regard them as one assignment, then the control unit 40 combines the corresponding vertices as shown in FIG. 5B, thus simplifying the interference graph. After accomplishing the simplification, then the modulation of the vertices is executed. The degree of vertex is referred to as being low for vertices with under 3 registers and as being high for vertices with 3 or more registers. This modulation of degree is used as the formation condition in the graph degeneration. The graph degeneration, as indicated by the arrows y11, y12, is carried out so that the vertices of low degree are removed in order of priority value as calculated in {numerical equation 1}, from lowest to highest priority value, with the assignment of the removed vertices being the piling up in the stack area in last in, first out order, with the result of the removal of e2 and d and the transformation of the interference graphs shown in FIGS. 5B and 6A being shown in FIG. 6B.

Since all the vertices in FIG. 6B are of high degree, the above formation condition is not satisfied. Therefore, from among these vertices, the assignment having the lowest priority value b1 is assigned to the memory and is removed, as shown by the arrow y13. By removing b1, the interference graph is transformed so as to equal the one shown in FIG. 6C, where once again, the above formation condition is satisfied. Graph degeneration is again repeated for the state shown in FIG. 6C, and all of the assignments are piled up in the stack, as shown in FIG. 6D. After this piling up process has been completed, then the resource assignment process is executed. First of all, as shown in FIG. 6E, assignment a is assigned to register R0. Next, as shown in FIGS. 6F and 6G, assignments e1 and b2c are assigned to registers R1 and R2. The following assignments e2 and d interfere with the live range of b2c, but, since they do not interfere with the live ranges of assignments a and e1, then e2 is assigned to the lowest number register R0 for which assignment is possible, as shown in FIG. 6H, while assignment d is assigned to register R1, as shown in FIG. 6I. By means of this kind of assignment process, sets of assignments whose live ranges interfere with each other can be assigned to different registers.

The above assignments a, b2, c, d, e1, e2, and b1 are all assigned to resource elements by the resource assignment process, but, for high-level languages such as C language, there are registers for which the combination with assignments is already decided. These are used to improve the efficiency of function call operations, and are known as argument registers, return value registers and broken registers.

Argument registers are registers for transferring arguments when there is a function call. Assignments used as arguments in the source program are assigned to these argument registers.

Return value registers are registers for returning the return value of the function call. Assignments used for returning the return value in the source program are allocated to these return value registers.

Broken registers are registers for assigning the assignments for which it is not necessary to save and restore the stored values at the start and end of the function call. The object of these broken registers is overhead reduction for the function call. When an above function call is executed, according to the process within the called function, there is the possibility that the content of every register will be changed, and that before or after the function call, it will be necessary to save and restore the content of the registers. However, since this saving and restoring function for every register will increase the overheads of the function call, then, by setting beforehand the broken registers for which saving and restoring are unnecessary, and assigning the assignments for which it is inconsequential whether the stored value is changed to the broken registers, the saving and restoring operations can be rationalized.

However, for resource assignment apparatuses constructed according to the prior art, there has been the problem that resource allocation can increase execution time and the memory size of the object program.

The root of this problem has been that the results of the assignment process have not correctly reflected the priority value of the assignments. In order that the number of def and use instructions and the loop-nesting depth level be properly reflected in the priority value, it is desirable to have high priority value assignments assigned to the registers. However, taking an assignment a of the lowest degree but of the highest priority value, and an assignment b of the highest degree but of the lowest priority value as a combined single vertex for the assignment ab, it can be seen by calculating the priority value according to (no. of def+no. of use)/length of live range for this combined vertex for assignment ab that the priority value will be of an intermediate value and the degree will be the highest, meaning that assignment ab can become an assignment which will be forcibly removed. By forcibly removing ab, then the assignment of the highest priority value a which should be assigned to the first register will end up being assigned to the memory. If a high priority value assignment is assigned to the memory, then the steps which use these assignments as operands will all be changed into machine language instructions which take the memory as operands. Operands used as machine language memory instructions are usually of low operational speed and take up a large amount of memory space, increasing the execution time and memory size of the object program.

Additionally, when the resources are split up into 3 or more functions, then there is the problem in that resource assignment cannot be achieved in accordance with the functions of the resources.

For example, for a target machine which is attempting to execute resource assignment, there are an equal number of data registers and address registers. Under the prior art, assignment is only separated into registers and memory used only when there is an insufficient number of registers, so that this second set of registers, the address registers, cannot be used. That is to say, under the prior art, resource assignment executed when considering several kinds of resource is incomplete.

There has also been the problem of not be able to execute resource assignment using the stored values of the argument registers, the return value registers and the broken registers as they are. These registers are originally set so that function calls can be executed efficiently.

The graph coloring method is an approximate algorithm for executing the most suitable color classification of the vertices in the interference graph. Since the argument registers, the return value registers and the broken registers are resource elements to which assignments are assigned before the execution of the algorithm, then these registers are regarded as colored vertices in the interference graph. In order to realize resource assignment which can use the stored values of the argument registers, return value registers and the broken registers as they are, then it becomes necessary to build the colored vertices into the interference graph and to execute a coloring process using that color for other vertices if it is valid, but this will deviate the limits of the graph coloring method. For the above reason, it is normally necessary to prepare separately the argument registers, the return value registers and the broken registers as assignable registers so that they may be used. Therefore, to use the stored values of the argument registers, the return value registers and the broken registers then a transmission instruction for assignable register use becomes necessary. If this kind of transmission instruction becomes necessary, then the necessary memory size and the execution time of the object program are increased by the amount used by this instruction.

The effect of the aforementioned problems can be disregarded as being of an insignificant level when there is an abundant supply of registers. However, when there are a only limited number of registers, such as with many built-in microprocessors, or when there are a small number of registers of several different kinds which fulfill different functions, then the effect of these problems becomes significant.

SUMMARY OF THE INVENTION

The first object of the present invention is to provide a resource assignment apparatus which is able to assign assignments to resource elements in order of priority ranking and, by limiting as much as possible the generation of transmission instructions, can restrict as far as possible the memory size and execution time needed by an object program.

The second object of the present invention is to provide a resource assignment apparatus which can use resources distinguishing between the functions that they perform, when there are 2 or more kinds of resource.

The third object of the present invention is to provide a resource assignment apparatus which can minimize the necessary amount of generated transmissions.

The first object of the invention can be achieved by a resource assignment apparatus used by a compiler which compiles programs written in a high-level language into programs written in machine language for assigning assignments which are a pairing of variables and live ranges in a program to separate resource elements which make up resources, divided up according to function, such as registers and memory, according to a priority value of the assignment, comprising: an assignment storage unit for storing the assignments in a program and their priority values; a first resource element assigning unit for taking an assignment with a highest priority value from the assignment storage unit and assigning the assignment with the highest priority value to a resource element; an assigning result storage unit for storing assigning results; an assignment retrieval unit for retrieving from the assignment storage unit an assignment which has a next highest priority value after a priority value of an assignment which has just been assigned; an interfering assignment extraction unit for extracting assignments whose live ranges interfere with a live range of the assignment retrieved by the assignment retrieval unit; a same resource remaining resource element determination unit for determining whether there are any resource elements of resources which perform a same function as each of the resource elements to which the assignments extracted by the interfering assignment extraction unit have been assigned by referring to the assigning result storage unit; a coherent assignment retrieval unit for retrieving the assignments for which, by referring to the starting point and end point of the live range, a starting point is coincident with the end point of the assignment retrieved by the assignment retrieval unit and assignments for which an end point is coincident with the starting point of the assignment retrieved by the assignment retrieval unit; a succession resource element determination unit for determining the resource element to which the assignments retrieved by the coherent assignment retrieval unit are assigned, by referring to the assigning result storage unit; a second resource assigning unit for assigning, when there is only one resource element determined by the same resource remaining element determination unit, the assignment retrieved by the assignment retrieval unit to the resource element, for assigning the assignment taken by the assignment retrieval unit to any resource element which is the determination result of the same resource remaining resource element determination unit and, moreover, the determination result of the succession resource element determination unit, when there is a plurality of resource elements determined by the same resource remaining resource element determination unit and a resource element determined by the succession resource element determination unit exists, and for storing the assignment result in the assignment result storage unit; and a control unit for repeatedly having the assignment retrieval unit activated, until all of the assignments have been assigned.

The second resource element assigning unit may comprise: a first assigning unit for assigning, when there is only one resource element determined by the same resource remaining resource element determination unit, the assignment taken by the assignment retrieval unit to the resource element; a second assigning