Resource assigning apparatus which assigns the variable in a program to resources

• US 5,790,862 A
• Filed: 03/14/1996
• Issued: 08/04/1998
• Est. Priority Date: 03/16/1995
• Status: Expired due to Term

• Current Assignee: Socionext Inc.
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Sayama, Junko, Yukawa, Hiroshi, Tanaka, Akira, Odani, Kensuke
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Nguyen, Cuong H.
• Application Number:
  US08/618,453
• Time in Patent Office: 873 Days
• Field of Search: 395/705, 395/708, 395/709, 395/674, 364/262.4, 364/280, 364/280.4, 364/259, 364/261.3, 364/280.5, 364/281.3
• US Class Current: 717/159
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

A resource assigning apparatus which generates assignments which are combinations of variables and their respective live ranges, which investigates, for each assignment, other assignments with live ranges which interfere or which are continuous and which calculates assigning priority levels. Next, the assigning resource element determination unit assigns each assignment to an assignable resource element starting with the assignment with the highest priority level, in doing so taking into account the use cost which is the cost incurred by the parts of the program which use an assignment and the resource succession relations, thereby calculating a profit value which standardizes an evaluation of a reduction in transfer instructions in the object code and assigning assignments to resource elements with a lowest use cost and highest profit value. In this way, by thoroughly investigating the relations between assignments which allow assigning to a same resource element, a more optimal assigning result is attained.

Claims

1. A resource assigning apparatus to be used by a compiler which compiles a program written in a high-level language into a machine language program, wherein the resource assigning apparatus generates a plurality of assignments, each of which is a combination of a variable in the program written in the high-level language and a live range, and assigns the generated assignments in order to resource elements of hardware resources such as registers and memory, the resource assigning apparatus comprising:

profit/loss value calculation means for calculating, for each resource element, a profit/loss value which shows a degree of suitability of a resource element for a next assignment to be assigned, based on a positional relationship between live ranges of any assignments which have already been assigned and a live range of the next assignment;

assigning means for assigning the next assignment to any of the resource elements based on a value of the profit/loss value calculated for each resource element; and

control means for repeatedly activating the profit/loss value calculation means and the assigning means until every assignment has been assigned.

2. The resource assigning apparatus of claim 1 further comprising positional relationship determination means for determining the positional relationships between all of the assignments in the program written in the high-level language, wherein the positional relationship determination means includes:

interfering relation determination means for determining whether the live range of the next assignment interferes with a live range of any assignment which has already been assigned to a resource element; and

assigned-next continuation determination means for determining whether the live range of the next assignment is continuous with a live range of any assignment which has already been assigned to a resource element,

wherein the profit/loss value calculation means includes a first increase unit for increasing, when the assigned-next continuation determination means determines that the live range of the next assignment is continuous with an assigned assignment, a profit/loss value of the resource element to which the assigned assignment has been assigned in accordance with an extent of a live range length from the assigned assignment to the next assignment,

and wherein the assigning means determines not to assign the next assignment to a resource element which has been assigned an assignment determined by the interfering relation determination means to have a live range which interferes with the live range of the next assignment, and instead determines to assign the next assignment to a resource element, out of all resource elements which have not been determined to have an interfering live range, which has a highest profit/loss value.

3. The resource assigning apparatus of claim 2, wherein the positional relationship determination means further includes:

first assigned assignment interference detection means for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment;

unassigned-next continuation determination means for determining whether the live range of the unassigned assignment detected by the first assigned assignment interference detection means is continuous with the live range of the next assignment; and

a first reduction unit for reducing, when it is determined by the unassigned-next continuation determination means that the live ranges are continuous, a profit/loss value of a resource element which has been assigned an assigned assignment detected as interfering with the unassigned assignment, in accordance with an extent of live range length from the unassigned assignment detected by the first assigned assignment interference detection means to the next assignment.

4. The resource assigning apparatus of claim 3, wherein, when a plurality of unassigned assignments are determined by the first assigned assignment interference detection means, the unassigned-next continuation determination means determines whether a live range of any of the plurality of unassigned assignments determined by the first assigned assignment interference detection means is continuous with the live range of the next assignment.

5. The resource assigning apparatus of claim 3, further including priority level storage means for storing a priority level corresponded to each assignment, the priority level reflecting at least one of a frequency of use of an assignment in the program and a loop-nesting depth level of a live range of an assignment, wherein the profit/loss value calculation means and the assigning means determine which assignment is a next assignment in order of priority levels stored in the priority level storage means.

6. The resource assigning apparatus of claim 5, wherein the positional relationship determination means further includes:

next assignment interfering assignment detection means for detecting, when there is a plurality of resource elements whose profit/loss values calculated by the profit/loss value calculation means are of a same value, any unassigned assignments whose live range interferes with the live range of the next assignment; and

unassigned-assigned continuation determination means for determining whether a live range of an assignment detected by the next assignment interfering assignment detection means is continuous with the live range of an assigned assignment,

wherein the profit/loss calculation means further includes;

a priority level detection unit for detecting a priority level of an assignment detected by the next assignment interfering assignment detection means;

a first extent calculation unit for calculating an extent of live range length from the unassigned assignment detected by the next assignment interfering assignment detection means to the assigned assignment determined by the unassigned-assigned continuation determination means to have a live range which continues with a live range of the detected unassigned assignment; and

a second reduction unit for multiplying the priority level detected by the priority level detection unit by the extent of live range length calculated by the first extent calculation unit and for reducing a profit/loss value of a resource element to which the determined assigned assignment is assigned in accordance with a multiplication result.

7. The resource assigning apparatus of claim 6, wherein the positional relationship determination means further includes:

second assigned assignment interference detection means for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment; and

unassigned-unassigned continuation determination means for determining whether a live range of an unassigned assignment detected by the next assignment interfering assignment detection means is continuous with a live range of an unassigned assignment detected by the second assigned assignment interference detection means,

and wherein the profit/loss value calculation means further includes;

a second extent calculation unit for calculating an extent of live range length from an unassigned assignment detected by the next assignment interfering assignment detection means to the unassigned assignment detected by the second assigned assignment interference detection means to have a live range which interferes with a live range of an assigned assignment; and

a second increase unit for multiplying the priority level detected by the priority level detection unit by the extent of live range length calculated by the second extent calculation unit and for increasing a profit/loss value of a resource element to which the detected assigned assignment is assigned in accordance with a multiplication result.

8. The resource assigning apparatus of claim 7, wherein, when a plurality of unassigned assignments are determined by the second assigned assignment interference detection means, the unassigned-unassigned continuation determination means determines whether any unassigned assignment, out of the determined plurality of unassigned assignments, has a live range which is continuous with the live range of the next assignment.

9. The resource assigning apparatus of claim 7, further including a profit/loss value storage unit for storing each resource element corresponded with an initial value of a profit/loss value, wherein the first and second increase units increase a profit/loss value of each resource element stored in the profit/loss value storage unit and the first and second reduction units reduce a profit/loss value of each resource element stored in the profit/loss value storage unit.

10. The resource assigning apparatus of claim 7, further including:

estimation means for estimating what will happen to a total value, which expresses at least one of a number of execution cycles and a code size of all definition instructions in which the next assignment is defined and use instructions in which the assignment is used, when assigning to resource elements belonging to each resource by calculating estimated values for the total value for pairings of the next assignment and each resource element; and

resource element singular/plural determination means for comparing estimated values which are a result of estimating for each resource element and determining whether a plurality of resource elements have a lowest estimated value or whether only one resource element has a lowest estimated value,

wherein, when the resource element singular/plural determination means determines that only one resource element has a lowest estimated value, the assigning means assigns the next assignment to the resource element determined to have the lowest estimated value, while when the resource element singular/plural determination means determines that a plurality of resource elements have a lowest estimated value, the assigning means assigns the next assignment to a resource element out of the plurality of resource elements with a lowest estimated value which has a highest profit/loss value.

11. The resource assigning apparatus of claim 10, wherein the estimation means includes:

an instruction pattern output unit for outputting an instruction pattern, which is information which uses an instruction format of machine language instructions and which expresses definition instructions and use instructions of an assignment in a program, for every definition instruction and use instruction of the assignment in the program;

a cost storage unit for storing a cost showing at least one of a number of execution cycles and a code size of definition instructions and use instructions when resource elements of each resource are used as each operand in a machine language instruction, corresponded to each instruction pattern obtained as an output from the instruction pattern output unit; and

a cost totalling unit for retrieving a cost from the cost storage unit corresponding to the output instruction pattern, for totalling retrieved costs for each resource element and for setting the totalled costs as estimated values.

12. The resource assigning apparatus of claim 10, further including prediction means for predicting, when a profit/loss value calculated by the profit/loss value calculation means for resource elements belonging to a plurality of resources have a same value, a resource element which when used for assigning the next assignment allows a most favorable assigning of all unassigned assignments which have a lower priority level than the next assignment,

wherein the assigning means assigns the next assignment to the resource element predicted by the prediction means.

13. The resource assigning apparatus of claim 12, wherein the prediction means includes:

first lower order assignment detection means for detecting all unassigned assignments which have a live range which is continuous with the live range of the next assignment and which also have a priority level lower than a priority level of the next assignment;

first estimation means for estimating what will happen to a total value, which expresses at least one of a number of execution cycles and a code size of all definition instructions in which the next assignment is defined and use instructions in which the assignment is used, when assigning each assignment detected by the first lower order assignment detection means to each resource element, by calculating estimated values for the total value for pairings of each assignment detected by the first lower order assignment detection means and each resource element;

first live range length calculation means for calculating a continuous length of live range for each assignment detected by the first lower order assignment detection means, the length of live range being between the next assignment and each assignment detected by the first lower order assignment detection means;

first weighting means for weighting the estimated value calculated by the first estimation means for pairings of each detected assignment and each resource element using the calculated length of live range;

first totalling means for totalling estimated values weighted by the first weighting means for each resource element; and

first optimal resource element determination means for determining that a resource element, which when used for assigning the next assignment allows a most favorable assigning of all unassigned assignments which have a lower priority level than the next assignment, is a resource element which has a lowest total value totalled by the first totalling means,

wherein a resource element determined as a determination result of the first optimal resource element determination means is set as a prediction result of the prediction means.

14. The resource assigning apparatus of claim 13, wherein the prediction means further includes:

second lower order assignment detection means for detecting, when a plurality of resource elements are determined by the first optimal resource element determination means to be most favorable, unassigned assignments which have a live range which interferes with the live range of next assignment and unassigned assignments which have a live range which is continuous with a live range of an assignment which has a live range which interferes with the live range of the next assignment;

second estimation means for estimating what will happen to a total value, which expresses at least one of a number of execution cycles and a code size of all definition instructions in which each detected assignment is defined and use instructions in which each assignment is used, when assigning each unassigned assignment detected by second lower order assignment detection means to each resource element, by calculating estimated values for the total value for pairings of each assignment detected by the second lower order assignment detection means and each resource element;

second live range length calculation means for calculating a continuous length of live range for each assignment detected by the second lower order assignment detection means, the length of live range being between an unassigned assignment whose live range interferes with the live range of the next assignment and an assignment which has a live range which is continuous with the live range of the unassigned assignment whose live range interferes with the live range of the next assignment;

second weighting means for weighting the estimated value calculated by the second estimation means for pairings of each unassigned assignment detected by the second lower order assignment detection means and each resource element using the length of live range calculated for each assignment by the second live range length calculation means and the priority value of each assignment;

second totalling means for totalling the estimated values of each assignment weighted by the second weighting means for each resource element; and

second optimal resource element determination means for determining that a resource element, which when used for assigning the next assignment allows a most favorable assigning of all unassigned assignments which have a lower priority level than the next assignment, is a resource element which has a highest total value totalled by the second totalling means.

15. The resource assigning apparatus of claim 14, wherein the first and second weighting means perform weighting using an extent of live range length of "1" when the live range lengths between assignments calculated by a respective one of the first live range length calculation means and the second live range length calculation means is "0", and the first and second weighting means calculate a reciprocal of a live range length and perform weighting using the calculated reciprocal as an extent of live range length when the lengths of live range between assignments calculated by a respective one of the first live range length calculation means and the second live range length calculation means is not "0".

16. The resource assigning apparatus of claim 15 further including cost storage means for storing a plurality of instruction patterns, each being information which uses an instruction format of machine language instructions and which expresses definition instructions and use instructions of an assignment in a program, and for storing a cost showing at least one of a number of execution cycles and a code size of definition instructions and use instructions of an assignment in the program when resource elements of each resource are used as each operand in a machine language instruction, corresponded to each instruction pattern,

wherein the first estimation means includes:

a first instruction pattern output unit for retrieving instruction patterns corresponding to all definition instructions and use instructions for an unassigned assignment detected by the first lower order assignment detection means and outputting the retrieved instruction patterns; and

a first cost totalling unit for retrieving a cost from the cost storage means corresponding to the output instruction patterns, for totalling the retrieved costs for each resource element and setting the totalled costs as estimated values,

wherein the second estimation means includes;

a second instruction pattern output unit for retrieving instruction patterns corresponding to all definition instructions and use instructions for an unassigned assignment detected by the second lower order assignment detection means and outputting the retrieved instruction patterns; and

a second cost totalling unit for retrieving a cost from the cost storage means corresponding to the output instruction patterns, for totalling the retrieved costs for each resource element and setting the totalled costs as estimated values.

17. The resource assigning apparatus of claim 16, wherein

an instruction pattern includes information showing whether a storage location of an operation result coincides with either operand in an operation or whether the storage location of an operation result is completely different,

and wherein a cost of instruction patterns where a storage location coincides with either operand is lower than a cost of instruction patterns where a storage location does not coincide with either operand.

18. The resource assigning apparatus of claim 16, wherein

an instruction pattern includes information showing whether or not a corresponding use instruction is an end point of a live range,

and a cost of instruction patterns where the corresponding use instruction is the end point of the live range is lower than a cost of instruction patterns where the corresponding use instruction is not the end point.

19. The resource assigning apparatus of claim 9, further including:

reserved assignment detection means for detecting assignments which are to be assigned to a predetermined resource element from the program; and

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

wherein the assigning means assigns the assignments detected by the reserved assignment detection means to the resource elements to which the assignments should be assigned, before assigning an assignment with a highest priority level to any of the resource elements.

20. The resource assigning apparatus of claim 19, wherein the reserved assignment detection means detects assignments which store arguments of function calls out of the program and the reserved resource element storage means stores that the detected assignments should be assigned to argument registers.

21. The resource assigning apparatus of claim 19, wherein the reserved assignment detection means detects assignments which store return values of function calls out of the program and the reserved resource element storage means stores that the detected assignments should be assigned to return value registers.

22. The resource assigning apparatus of claim 19, wherein the reserved assignment detection means detects assignments whose values may be rewritten out of the program and the reserved resource element storage means stores that the detected assignments should be assigned to broken registers.

23. The resource assigning apparatus of claim 9, further including live range continuation relation group storage means storing all assignments in the program corresponded to live range continuation relation groups made up of all assignments whose live range ends at start point of a live range of an arbitrary assignment in the program and all assignments whose live range starts at an end point of the arbitrary live range,

wherein the assigned-next continuation determination means includes:

a first determination unit for referring to the live range continuation relation group for the next assignment and determining whether there are any assigned assignments in the corresponding live range continuation relation group;

a second determination unit for retrieving, when the first determination unit determines that there are no assigned assignments, another assignment in the corresponding live range continuation relation group, for referring to a corresponding live range continuation relation group for the retrieved assignment and determining whether there are any assigned assignments in the corresponding live range continuation relation group; and

a control unit for repeatedly activating the second determination unit until the second determination unit determines that there is an assignment,

wherein the profit/loss calculation means includes;

a totalling unit for totalling a live range length of the assignments determined by the assigned-next continuation determination means; and

a reciprocal calculation unit for calculating a reciprocal of a total of a live range length of the next assignment and the live range length totalled by the totalling unit and for setting a calculation result as an extent of live range length.

24. The resource assigning apparatus of claim 23, wherein each live range of an assignment is expressed as instruction position information from a start point to an end point for a part of the program spanned by each live range, and the totalling unit totals a number of items of instruction position information and sets a total as an extent of live range length.

25. The resource assigning apparatus of claim 24, wherein a start point and an end point of a live range are expressed as instruction position information and the resource assigning apparatus further includes:

start/end point storage means for storing each assignment in the program corresponded with instruction position information for a start point of a live range and instruction position information for an end point of the live range;

first grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for a start point of a live range coincides with the instruction position information for an end point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group;

second grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for an end point of a live range coincides with the instruction position information for a start point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group; and

writing means for writing into the live range continuation relation group storage means an assignment in the program corresponded to any live range continuation relation groups to which the assignment belongs, the groups being grouped by one of the first grouping means and the second grouping means.

26. The resource assigning apparatus of claim 9, further including live range continuation relation group storage means storing all assignments in the program corresponded to live range continuation relation groups made up of all assignments whose live range ends at start point of a live range of an arbitrary assignment in the program and all assignments whose live range starts at an end point of the arbitrary live range,

wherein the unassigned-next continuation determination means includes:

a first determination unit for referring to the live range continuation relation group for the next assignment and determining whether there are any unassigned assignments detected by either assigned assignment interference detection means in the corresponding live range continuation relation group;

a second determination unit for retrieving, when the first determination unit determines that there is no such unassigned assignment, another assignment in the corresponding live range continuation relation group, for referring to a corresponding live range continuation relation group for the retrieved assignment and determining whether there are any unassigned assignments detected by either assigned assignment interference detection means in the corresponding live range continuation relation group; and

a control unit for repeatedly activating the second determination unit until the second determination unit determines that there is an assignment,

wherein the profit/loss calculation means includes;

a totalling unit for totalling a live range length of the assignments determined by the unassigned-next continuation determination means; and

a reciprocal calculation unit for calculating a reciprocal of a total of a live range length of the next assignment and the live range length totalled by the totalling unit and for setting a calculation result as an extent of live range length.

27. The resource assigning apparatus of claim 26, wherein each live range of an assignment is expressed as instruction position information from a start point to an end point for a part of the program spanned by each live range, and the totalling unit totals a number of items of instruction position information and sets a total as an extent of live range length.

28. The resource assigning apparatus of claim 27, wherein a start point and an end point of a live range are expressed as instruction position information and the resource assigning apparatus further includes:

start/end point storage means for storing each assignment in the program corresponded with instruction position information for a start point of a live range and instruction position information for an end point of the live range;

first grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for a start point of a live range coincides with the instruction position information for an end point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group;

second grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for an end point of a live range coincides with the instruction position information for a start point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group; and

writing means for writing into the live range continuation relation group storage means an assignment in the program corresponded to any live range continuation relation groups to which the assignment belongs, the groups being grouped by one of the first grouping means and the second grouping means.

29. The resource assigning apparatus of claim 9, further including live range continuation relation group storage means storing all assignments in the program corresponded to live range continuation relation groups made up of all assignments whose live range ends at start point of a live range of an arbitrary assignment in the program and all assignments whose live range starts at an end point of the arbitrary live range,

wherein the unassigned-assigned continuation determination means includes:

a first determination unit for referring to the live range continuation relation group for an unassigned assignment detected by the next assignment interfering assignment detection means and determining whether there are any assigned assignments in the corresponding live range continuation relation group;

a second determination unit for retrieving, when the first determination unit determines that there is no such assigned assignment, another assignment in the corresponding live range continuation relation group, for referring to a corresponding live range continuation relation group for the retrieved assignment and determining whether there are any assigned assignments in the corresponding live range continuation relation group; and

a control unit for repeatedly activating the second determination unit until the second determination unit determines that there is an assignment,

wherein the profit/loss calculation means includes;

a totalling unit for totalling a live range length of the assignments determined by the unassigned-assigned continuation determination means; and

a reciprocal calculation unit for calculating a reciprocal of a total of a live range length of the next assignment and the live range length totalled by the totalling unit and for setting a calculation result as an extent of live range length.

30. The resource assigning apparatus of claim 29, wherein each live range of an assignment is expressed as instruction position information from a start point to an end point for a part of the program spanned by each live range, and the totalling unit totals a number of items of instruction position information and sets a total as an extent of live range length.

31. The resource assigning apparatus of claim 30, wherein a start point and an end point of a live range are expressed as instruction position information and the resource assigning apparatus further includes:

start/end point storage means for storing each assignment in the program corresponded with instruction position information for a start point of a live range and instruction position information for an end point of the live range;

first grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for a start point of a live range coincides with the instruction position information for an end point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group;

second grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for an end point of a live range coincides with the instruction position information for a start point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group; and

writing means for writing into the live range continuation relation group storage means an assignment in the program corresponded to any live range continuation relation groups to which the assignment belongs, the groups being grouped by one of the first grouping means and the second grouping means.

32. The resource assigning apparatus of claim 9, further including live range continuation relation group storage means storing all assignments in the program corresponded to live range continuation relation groups made up of all assignments whose live range ends at start point of a live range of an arbitrary assignment in the program and all assignments whose live range starts at an end point of the arbitrary live range,

wherein the unassigned-unassigned continuation determination means includes:

a first determination unit for referring to the live range continuation relation group for an unassigned assignment detected by the next assignment interfering assignment detection means and determining whether there are any unassigned assignments detected by either assigned assignment interference detection means in the corresponding live range continuation relation group;

a second determination unit for retrieving, when the first determination unit determines that there is no such assigned assignment, another assignment in the corresponding live range continuation relation group, for referring to a corresponding live range continuation relation group for the retrieved assignment and determining whether there are any unassigned assignments detected by the either assigned assignment interference detection means in the corresponding live range continuation relation group; and

a control unit for repeatedly activating the second determination unit until the second determination unit determines that there is an assignment,

wherein the profit/loss calculation means includes;

a totalling unit for totalling a live range length of the assignments determined by the unassigned-unassigned continuation determination means; and

a reciprocal calculation unit for calculating a reciprocal of a total of a live range length of the next assignment and the live range length totalled by the totalling unit and for setting a calculation result as an extent of live range length.

33. The resource assigning apparatus of claim 32, wherein each live range of an assignment is expressed as instruction position information from a start point to an end point for a part of the program spanned by each live range, and the totalling unit totals a number of items of instruction position information and sets a total as an extent of live range length.

34. The resource assigning apparatus of claim 33, wherein a start point and an end point of a live range are expressed as instruction position information and the resource assigning apparatus further includes:

start/end point storage means for storing each assignment in the program corresponded with instruction position information for a start point of a live range and instruction position information for an end point of the live range;

first grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for a start point of a live range coincides with the instruction position information for an end point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group;

second grouping means for referring to the start/end point storage means, for detecting, out of all assignments, an assignment where the instruction position information for an end point of a live range coincides with the instruction position information for a start point of a live range of an arbitrary assignment in the program, and for setting a detected assignment and the arbitrary assignment in the program in a same live range continuation relation group; and

writing means for writing into the live range continuation relation group storage means an assignment in the program corresponded to any live range continuation relation groups to which the assignment belongs, the groups being grouped by one of the first grouping means and the second grouping means.

35. A resource assigning apparatus to be used by a compiler which compiles a program written in a high-level language into a machine language program, wherein the resource assigning apparatus generates a plurality of assignments, each of which is a combination of a variable in the program written in the high-level language and a live range, sets each generated assignment a priority level and assigns the generated assignments in order to resource elements of hardware resources such as registers and memory, the resource assigning apparatus comprising:

priority level setting means for detecting for each assignment in the program at least one of a frequency of use and a loop-nesting depth level from every part of the program and setting a priority level of each assignment based on a detection result;

profit/loss value calculation means for calculating, for each resource element, a profit/loss value which shows a degree of suitability of a resource element for a next assignment, based on a positional relationship between live ranges of any assignments which have already been assigned and a live range of the next assignment;

assigning means for assigning the next assignment to any of the resource elements based on the size of the profit/loss value calculated for each resource element;

control means for repeatedly activating the profit/loss value calculation means and the assigning means until every assignment has been assigned.

36. The resource assigning apparatus of claim 35, further including:

estimation means for estimating what will happen to a total value, which expresses at least one of a number of execution cycles and a code size of all definition instructions in which the next assignment is defined and use instructions in which the assignment is used, when assigning to resource elements belonging to each resource by calculating estimated values for the total value for pairings of the next assignment and each resource element; and

resource element singular/plural determination means for comparing estimated values which are a result of estimating for each resource element and determining whether a plurality of resource elements have a lowest estimated value or whether only one resource element has a lowest estimated value,

wherein, when the resource element singular/plural determination means determines that only one resource element has a lowest estimated value, the assigning means assigns the next assignment to the resource element determined to have the lowest estimated value, while when the resource element singular/plural determination means determines that a plurality of resource elements have a lowest estimated value, the assigning means assigns the next assignment to a resource element out of the plurality of resource elements with a lowest estimated value which has a highest profit/loss value.

37. The resource assigning apparatus of claim 36, wherein the estimation means includes:

an instruction pattern output unit for outputting an instruction pattern, which is information which uses an instruction format of machine language instructions and which expresses definition instructions and use instructions of an assignment in a program, for every definition instruction and use instruction of the assignment in the program;

a cost storage unit for storing a cost showing at least one of a number of execution cycles and a code size of definition instructions and use instructions when resource elements of each resource are used as each operand in a machine language instruction, corresponded to each instruction pattern obtained as an output from the instruction pattern output unit; and

a cost totalling unit for retrieving a cost from the cost storage unit corresponding to the output instruction pattern, for totalling retrieved costs for each resource element and for setting the totalled costs as estimated values.

38. The resource assigning apparatus of claim 36, wherein the positional relationship determination means further includes:

first assigned assignment interference detection means for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment;

unassigned-next continuation determination means for determining whether the live range of the unassigned assignment detected by the first assigned assignment interference detection means is continuous with the live range of the next assignment; and

a first reduction unit for reducing, when it is determined by the unassigned-next continuation determination means that the live ranges are continuous, a profit/loss value of a resource element which has been assigned an assigned assignment detected as interfering with the unassigned assignment, in accordance with an extent of live range length from the unassigned assignment detected by the first assigned assignment interference detection means to the next assignment.

39. The resource assigning apparatus of claim 38, wherein, when a plurality of unassigned assignments are determined by the first assigned assignment interference detection means, the unassigned-next continuation determination means determines whether a live range of any of the plurality of unassigned assignments determined by the first assigned assignment interference detection means is continuous with the live range of the next assignment.

40. The resource assigning apparatus of claim 39, wherein the positional relationship determination means further includes:

next assignment interfering assignment detection means for detecting, when there is a plurality of resource elements whose profit/loss values calculated by the profit/loss value calculation means are of a same value, any unassigned assignments whose live range interferes with the live range of the next assignment; and

unassigned-assigned continuation determination means for determining whether a live range of an assignment detected by the next assignment interfering assignment detection means is continuous with the live range of an assigned assignment,

wherein the profit/loss calculation means further includes;

a priority level detection unit for detecting a priority level set for an assignment;

a first extent calculation unit for calculating an extent of live range length from the unassigned assignment detected by the next assignment interfering assignment detection means to the assigned assignment determined by the unassigned-assigned continuation determination means to have a live range which continues with a live range of the detected unassigned assignment; and

a second reduction unit for multiplying the priority level detected by the priority level detection unit by the extent of live range length calculated by the first extent calculation unit and for reducing a profit/loss value of a resource element to which the determined assigned assignment is assigned in accordance with a multiplication result.

41. The resource assigning apparatus of claim 40, wherein the positional relationship determination means further includes:

second assigned assignment interference detection means for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment; and

unassigned-unassigned continuation determination means for determining whether a live range of an unassigned assignment detected by the next assignment interfering assignment detection means is continuous with a live range of an unassigned assignment detected by the second assigned assignment interference detection means,

and wherein the profit/loss value calculation means further includes;

a second extent calculation unit for calculating an extent of live range length from an unassigned assignment detected by the next assignment interfering assignment detection means to the unassigned assignment detected by the second assigned assignment interference detection means to have a live range which interferes with a live range of an assigned assignment; and

a second increase unit for multiplying the priority level detected by the priority level detection unit by the extent of live range length calculated by the second extent calculation unit and for increasing a profit/loss value of a resource element to which the detected assigned assignment is assigned in accordance with a multiplication result.

42. The resource assigning apparatus of claim 35, further including a profit/loss value storage unit for storing each resource element corresponded with an initial value of a profit/loss value, wherein the first and second increase units increase a profit/loss value of each resource element stored in the profit/loss value storage unit and the first and second reduction units reduce a profit/loss value of each resource element stored in the profit/loss value storage unit.

43. The resource assigning apparatus of claim 35, further including prediction means for predicting, when a profit/loss value calculated by the profit/loss value calculation means for resource elements belonging to a plurality of resources have a same value, a resource element which when used for assigning the next assignment allows a most favorable assigning of all unassigned assignments which have a lower priority level than the next assignment,

wherein the assigning means assigns the next assignment to the resource element predicted by the prediction means.

44. The resource assigning apparatus of claim 43, wherein the prediction means includes:

first lower order assignment detection means for detecting all unassigned assignments which have a live range which is continuous with the live range of the next assignment and which also have a priority level lower than a priority level of the next assignment.

45. The resource assigning apparatus of claim 44, wherein the prediction means further includes:

second lower order assignment detection means for detecting, when a plurality of resource elements are determined by the first optimal resource element determination means to be most favorable, unassigned assignments which have a live range which interferes with the live range of next assignment and unassigned assignments which have a live range which is continuous with a live range of an assignment which has a live range which interferes with the live range of the next assignment;

second estimation means for estimating what will happen to a total value, which expresses at least one of a number of execution cycles and a code size of all definition instructions in which each detected assignment is defined and use instructions in which each assignment is used, when assigning each unassigned assignment detected by second lower order assignment detection means to each resource element, by calculating estimated values for the total value for pairings of each assignment detected by the second lower order assignment detection means and each resource element;

second live range length calculation means for calculating a continuous length of live range for each assignment detected by the second lower order assignment detection means, the length of live range being between an unassigned assignment whose live range interferes with the live range of the next assignment and an assignment which has a live range which is continuous with the live range of the unassigned assignment whose live range interferes with the live range of the next assignment;

second weighting means for weighting the estimated value calculated by the second estimation means for pairings of each unassigned assignment detected by the second lower order assignment detection means and each resource element using the length of live range calculated for each assignment by the second live range length calculation means and the priority value of each assignment;

second totalling means for totalling the estimated values of each assignment weighted by the second weighting means for each resource element; and

second optimal resource element determination means for determining that a resource element, which when used for assigning the next assignment allows a most favorable assigning of all unassigned assignments which have a lower priority level than the next assignment, is a resource element which has a highest total value totalled by the second totalling means.

46. The resource assigning apparatus of claim 45, wherein the first and second weighting means perform weighting using an extent of live range length of "1" when the live range lengths between assignments calculated by a respective one of the first live range length calculation means and the second live range length calculation means is "0", and the first and second weighting means calculate a reciprocal of a live range length and perform weighting using the calculated reciprocal as an extent of live range length when the lengths of live range between assignments calculated by a respective one of the first live range length calculation means and the second live range length calculation means is not "0".

47. The resource assigning apparatus of claim 46, further including cost storage means for storing a plurality of instruction patterns, each being information which uses an instruction format of machine language instructions and which expresses definition instructions and use instructions of an assignment in a program, and for storing a cost showing at least one of a number of execution cycles and a code size of definition instructions and use instructions of an assignment in the program when resource elements of each resource are used as each operand in a machine language instruction, corresponded to each instruction pattern,

wherein the first estimation means includes:

a first instruction pattern output unit for retrieving instruction patterns corresponding to all definition instructions and use instructions for an unassigned assignment detected by the first lower order assignment detection means and outputting the retrieved instruction patterns; and

a first cost totalling unit for retrieving a cost from the cost storage means corresponding to the output instruction patterns, for totalling the retrieved costs for each resource element and setting the totalled costs as estimated values,

wherein the second estimation means includes;

a second instruction pattern output unit for retrieving instruction patterns corresponding to all definition instructions and use instructions for an unassigned assignment detected by the second lower order assignment detection means and outputting the retrieved instruction patterns; and

a second cost totalling unit for retrieving a cost from the cost storage means corresponding to the output instruction patterns, for totalling the retrieved costs for each resource element and setting the totalled costs as estimated values.

48. A resource assigning apparatus to be used by a compiler which compiles a program written in a high-level language into a machine language program, wherein the resource assigning apparatus assigns a plurality of assignments, which are a combination of a variable in the program written in the high-level language and a live range, in order to resource elements of hardware resources such as registers and memory, the resource assigning apparatus comprising:

assignment storage means for storing assignments in the program, each assignment being corresponded to a priority level;

first resource element assigning means for retrieving an assignment with a highest priority level in the assignment storage means and assigning the assignment with the highest priority level to any of the resource elements;

assignment retrieval means for retrieving from the assignment storage means an assignment which has a priority level which comes in order directly after a priority level of an assignment which has just been assigned;

following assignment interfering assignment detection means for detecting any assignments with a live range which interferes with a live range of the assignment retrieved by the assignment retrieval means;

resource element detection means for detecting resource elements which have been assigned assignments detected by the following assignment interfering assignment detection means;

assignment-resource element detection means for detecting all assignments which have been assigned to any resource element which has not been detected by the resource element detection means;

profit continuation assigned assignment determination means for determining every assignment which has a live range which is continuous with a live range of the assignment retrieved by the assignment retrieval means, out of the assigned assignments detected by the assignment-resource element detection means;

first profit/loss value calculation means for calculating a profit/loss value, which is a value showing appropriateness of assigning a next assignment to a resource element to which an assignment has already been assigned, based on an extent of live range length from an assignment determined by the profit continuation assigned assignment determination means to the assignment retrieved by the assignment retrieval means, for each resource element assigned an assignment determined by the profit continuation assigned assignment determination means;

totalling means for totalling the calculated profit/loss values for each resource element determined by the assignment-resource element detection means;

second resource element assigning means for assigning the assignment retrieved by the assignment retrieval means to a resource element with a highest total value totalled by the totalling means; and

control means for repeatedly activating the assignment retrieval means until every assignment has been assigned.

49. The resource assigning apparatus of claim 48, further including:

first non-interfering non-continuous assigned assignment determination means for determining assignments whose live range is not continuous with a live range of an assignment retrieved by the assignment retrieval means nor interferes with the live range of the assignment retrieved by the assignment retrieval means, out of the assigned assignments detected by the assignment-resource element detection means;

profit continuation unassigned assignment determination means for detecting an assignment whose live range is continuous with a live range of the assignment retrieved by the assignment retrieval means and which is an unassigned assignment whose live range interferes with a live range of the assignment determined by the first non-interfering non-continuous assigned assignment determination means;

second profit/loss value calculation means for calculating a profit/loss value of a resource element assigned an assigned assignment detected by the first non-interfering non-continuous assigned assignment determination means, based on an extent of live range length from an unassigned assignment detected by the profit continuation unassigned assignment determination means to the assignment retrieved by the assignment retrieval means; and

first subtraction means for subtracting a profit/loss value calculated by the second profit/loss value calculation means from the profit/loss value for an appropriate resource element totalled by the totalling means,

wherein the second assigning means assigns the assignment retrieved by the assignment retrieval means to a resource element with a highest profit/loss value after a profit/loss calculated by the second profit/loss value has been subtracted by the first subtraction means.

50. The resource assigning apparatus of claim 49, further including:

interfering assignment continuation assigned assignment determination means for determining assignments whose live range is continuous with an assignment retrieved by the following assignment interfering assignment detection means, out of assigned assignments detected by the assignment-resource element detection means;

third profit/loss calculation means for calculating a profit/loss value of a resource element assigned an assigned assignment determined by the interfering assignment continuation assigned assignment determination means, based on an extent of live range length from an assigned assignment detected by the interfering assignment continuation assigned assignment determination means to an assignment detected by the following assignment interfering assignment detection means; and

second subtraction means for subtracting a profit/loss value calculated by the third profit/loss value calculation means from the profit/loss value for an appropriate resource element totalled by the totalling means,

wherein the second assigning means assigns the assignment retrieved by the assignment retrieval means to a resource element with a highest total value after a profit/loss calculated by the third profit/loss value has been subtracted by the second subtraction means.

51. The resource assigning apparatus of claim 50, further including:

second non-interfering non-continuous assigned assignment determination means for determining assignments whose live range is not continuous with a live range of an assignment detected by the following assignment interfering assignment detection means nor interferes with the live range of the assignment detected by the following assignment interfering assignment detection means, out of the assigned assignments detected by the assignment-resource element detection means;

interfering assignment continuation unassigned assignment determination means for determining assignments whose live range is continuous with a live range of an assignment detected by the following assignment interfering assignment detection means and which are unassigned assignments whose live range interferes with a live range of an assigned assignment determined by the second non-interfering non-continuous assigned assignment determination means;

fourth profit/loss calculation means for calculating a profit/loss value of a resource element assigned an assigned assignment determined by the second non-interfering non-continuous assigned assignment determination means, based on an extent of live range length from an assignment determined by the interfering assignment continuation unassigned assignment determination means to an assignment detected by the following assignment interfering assignment detection means; and

first addition means for adding a profit/loss value calculated by the fourth profit/loss value calculation means from the profit/loss value for an appropriate resource element totalled by the totalling means,

wherein the second assigning means assigns the assignment retrieved by the assignment retrieval means to a resource element with a highest total value after a profit/loss calculated by the fourth profit/loss value has been added by the second addition means.