Resource assignment apparatus

• US 5,684,994 A
• Filed: 10/19/1994
• Issued: 11/04/1997
• Est. Priority Date: 10/20/1993
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Irimajiri, Junko, Tanaka, Akira, Tominaga, Nobuki
• Primary Examiner(s): Oberley, Alvin E.
• Assistant Examiner(s): Park, Alice Y.
• Application Number:
  US08/325,998
• Time in Patent Office: 1,112 Days
• Field of Search: 395/650, 395/700, 395/800, 395/705, 395/674
• US Class Current: 717/153
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/443 Optimisation

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

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.

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.

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.

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.