Resource assigning apparatus which assigns the variable in a program to resources5790862
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
What is claimed is:
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.
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a resource assigning apparatus which assigns the variables in a program to resources such as registers and memory, to be used by a compiler which compiles a program written in a high-level language into a machine language program.
2. Description of the Related Art
In recent years there have been great improvements in information processing devices with embedded microprocessors which are flexible enough to manage the needs of a variety of users. The software side of the development of such information processing devices has sought the greatest possible reductions in hardware cost (measured in terms of memory size) and the greatest possible improvements in processing speed. This has involved the complete removal of redundant transfer instructions and the maximum possible utilization of microprocessor functions such as addressing mode when developing programs in assembly language. However, since the syntax rules for the assembly language are the instruction system of the processor itself, this leads to very low efficiency in program development and to problems regarding the portability of source files. As a result, attention has been increasingly focussed on the use of high-level programming languages for the development of software for embedded microprocessors in order to increase the efficiency of program development.
By using high-level programming languages, the programmer can express such processes as the storage, operation and transfer of numerical values as operations (steps) which use variables as their operands. Since variables can be freely defined by the programmer, and are used only according to necessity, the programmer is free to write the program according to his/her desires and needs. When these programs (known as source programs) are compiled, they are converted into machine language programs which can be readily understood by the CPU in the computer. Operations in such machine language programs are expressed as machine language instructions which use registers and memory as operands, so that during compiling it becomes necessary to assign the variables in the source program to the registers and memory. This assigning process is known as the resource assigning process. By optimally executing this resource assigning process, the code size of the machine language program produced can be reduced to a minimum, with the execution time of the generated program also being optimized.
The following is a definition of the terms to be used in describing conventional resource allocation devices.
Definition/Reference/Use of a Variable
The setting of a value of a variable is called a "definition" and a use of a set value of a variable is called a "reference". Here, a definition or a reference of a variable in the program is also referred to as a "use" of the variable.
Intermediate Instruction
An intermediate language is a set of code which enables smooth processing when a compiler converts the code of a source program. One step in the intermediate language code is referred to as one intermediate instruction. Intermediate language instructions can be of three- or four-variable format, for example, and provide the basis for the generation of final object code. Here also, the set of intermediate instructions generated by converting a source program is called the intermediate program.
Live Range
The live range, in its widest sense, refers to the range for which the stored value of a variable is valid, while in its narrowest sense, it refers to the range of the program from the step in which a value is substituted into a variable to the step in which this substituted value is used. Here, the live range is expressed as the set of intermediate instructions within the aforementioned range. The intermediate instruction which defines the value of a variable is the start point of the live range, while the final intermediate instruction out of the intermediate instructions which refer to this set value is the end point of the live range. Here, in determining from the sets of intermediate instructions whether live ranges interfere with one another, the coincidence of the end point of one live range with the start point of another is set as not constituting interference between two live ranges.
FIG. 1 shows one example of an intermediate instruction program and the corresponding live ranges (this program is generated by converting the source program shown in FIG. 3A). The live ranges are shown by vertical lines s1, s2, and s3 in FIG. 1. The start point and the end point are expressed in the drawing by the points p1, p2, p3, p4 etc., In FIG. 1, there are two start points for each of the variables c and d, but this is because variables c, d are defined in terms of the two processes p2 and p2 in the decision statement "if (b>=10) {process p1} else {process p2}".
Assignment
The assignment for a resource can be simply the taking of a variable but, since assigning can be performed using different resource elements for each respective live range when there are several live ranges for one variable, this specification takes an assignment as comprising a combination of one variable and one live range. As can be seen with the variable b in FIG. 1A, when one variable has a number of live ranges, these live ranges are expressed as separate assignments b1, b2 etc. so as to distinguish between them.
Here, the "definition", "reference" and "use" of a variable in an assignment are respectively referred to as the "definition", "reference" and "use" of the assignment which includes that variable. In the same way, the intermediate instructions which define an assignment or refer to an assignment are respectively referred to as "definition intermediate instructions" and "reference intermediate instructions", with both kinds being referred to in general as use intermediate instructions.
Assigning Priority Level
This is the parameter for deciding the order in which assignments are assigned to resources.
There are several methods for evaluating this assigning priority level. An example of an assigning priority level calculation based on the activity ratio of the assignment is given below as {numerical equation 1}.
{numerical equation 1}
assigning priority level=activity ratio=(number of intermediate instructions using an assignment)/length of live range
When an intermediate instruction using this assignment is inside a loop process, the loop-nesting depth level may also be used in this calculation of assigning priority level, as shown in the example below.
assigning priority level=activity ratio=total loop-nesting depth level of loops including use intermediate instructions/length of live range.
Resource Element
This refers to the smallest unit among the elements in computer hardware to which an assignment can be assigned. Buffers for temporarily storing a value, individual registers, memory elements of a single address in the memory are all examples of this. The number 0 register, the number 1 register, the memory at address 100 and the memory at address 101 are all separate resource elements.
Resource
This refers to a group of resource elements which perform the same function.
As one example, resources can consist of memory and registers. Registers can be subdivided in terms of function into address registers AR!, data registers DR!, global registers and local registers. Additionally, memory can be subdivided in terms of fulfilling the functions of high-speed memory and low-speed memory. If it is possible to subdivide the resource elements in this way into groups which perform the same function, then each of these subdivisions becomes a separate resource.
Interference Graph
The interference graph is a graph to show pictorially the interference between the live ranges of two or more assignments.
The interference graph has the assignments as its vertices, and shows the assignments (vertices) where the live ranges interfere as joined together by edges (lines).
Degree of Vertex
The number of edges joining one vertex in the interference graph.
FIG. 2 shows the construction of a compiler. This compiler is comprised of a syntax analysis apparatus 11, an optimizing apparatus 12, a resource assigning apparatus 63, and a code generation apparatus 14. The following is an explanation of the different components of this compiler with reference to FIG. 1, to the construction in FIG. 2, and to FIGS. 3A, 3B and 3C.
The syntax analysis apparatus 11 executes the lexical analysis, the syntax analysis and the semantic analysis for the source program stored as a file in the storage apparatus (not shown in the figure), and converts the source program into an intermediate program. As one example, it converts the source program in FIG. 3A into the intermediate program shown in FIG. 1.
The optimizing apparatus 12 executes the optimizing of the intermediate program with the object of minimizing the program size and the process execution time of the finally-generated the machine language program. Since the details of this optimizing process are not the gist of this invention, they have been omitted, so that only the aspects which are especially related to resource assigning will be explained. The optimizing operation includes a basic block conversion operation, control flow analysis, and data flow analysis. Basic block conversion refers to the dividing of the program to be processed into basic blocks.
This is a simplified explanation of this division process. First of all, the optimizing apparatus 12 refers to the first intermediate instruction, instructions which are the destinations of an unconditional or a conditional jump, and instructions which are directly before or after an unconditional or a conditional jump and regards these instructions as the leaders. Then the optimizing apparatus 12 extracts all of the program steps from one leader to the next leader or to the end of the program. The set of instructions obtained by this extraction process is known as a basic block, and becomes the processing unit of the following processes.
The control flow analysis analyses the control flow between all of the basic blocks.
The data flow analysis analyses where values are substituted into each variable and where each variable is used within each separate block. By referring to the results of these analyses, the live ranges of the variables are obtained.
The resource assigning apparatus 63 is an algorithm for assigning resources which assigns the assignments in the intermediate program to the registers and memory using a graph coloring method by means of graph degeneration. The graph coloring method by means of graph degeneration is an algorithm which executes the color classification of every vertex in the interference graph using approximately the least necessary number of colors, according to the principle where, in color classifying, vertices which are joined by an edge are painted using a different color. The assignments in the program shown in FIG. 3A are assigned to the resource elements by the resource assigning process shown in FIG. 3B. In these drawings, the assignment a shown in FIG. 3A is shown as being assigned to resource element R0, while assignment b2 is shown as being assigned to resource element R2.
The code generation apparatus 14 executes the machine language instruction conversion for every intermediate instruction in the intermediate program, converting this intermediate program into a machine language program (shown in FIG. 3C) that can be understood by the target machine. The machine code program which is the result of this conversion by the code generation apparatus 14 is called the object program. The machine language instructions in this object program and the corresponding intermediate instructions in the program of FIG. 1 are shown by the symbols (1), (2), (3), (4) etc. in FIG. 3C. In the above machine language instruction conversion, the resource assigning results shown in FIG. 3B are used as the machine language instruction operands. Also the transfer instructions in the drawing t11, t12, t13, t14, t15 etc. are generated by the code generation apparatus 14 so that the processing of every step in the intermediate program shown in FIG. 1 can be achieved by machine language instructions. Here, depending on the results of the resource assigning, it can be the case that several of these transfer instructions will no longer be necessary. As one example, it can be seen that in FIG. 3C, since in (7) assignments b2 and c are both assigned to the same register, the generation of a transfer instruction is no longer necessary.
The following is an explanation of the resource assigning apparatus 63. The details of the resource assigning process using the graph coloring method mentioned above are described by the following documents.
1! A. V. Aho, R. Sethi, J. D. Ullman; "Compilers Principles, Techniques and Tools" Addison-Wesley, 1986
2! Chaitin.; "Register allocation and spilling via graph coloring", U.S. Pat. No. 4,571,678, Feb. 18, 1986.
3! Frederick Chow, John Hennessy; "Register Allocation by Priority-based Coloring", Computer Systems Laboratory, Stanford University.
4! David Bernstein, . . . Ron Y. Pinter; "Spill code minimization techniques of optimizing compilers", SIGPLAN 1989, IBM Israel Science and Technology Technion City Haifa, Israel.
5! Masataka Sasa; "Programming Gengo Shorikei",Register Assignment p420-p423, Iwanami Books.
6! Mori et al.: "A Systematic Register Assigning Method for a Composite Bank Construction and its General Implementation" Johoshori Gakkai (Information Processing Society) Vol.30, No.6, Jun. 1989.
The construction of the aforementioned resource assigning apparatus 63 is shown in FIG. 4. As shown in FIG. 4, the resource assigning apparatus 63 is comprised of an assignment generation unit 71 for generating the assignments in accordance with the process results of the optimizing apparatus 12, an assignment storage unit 72 for storing the assignments generated by the assignment generation unit 71, a priority level calculator 73 for calculating the priority level of every assignment stored in the assignment storage unit 72 by means of the equation given above as {numerical equation 1} as well as storing the results, a live range information storage unit 74 for storing information about the live ranges, as shown in FIG. 1, for every assignment and the information as to how these live ranges interfere, an expansion unit 75 for expanding all of the assignments stored in the storage unit 72 in the interference graph, a buffer 76 for expansion by the expansion unit 75, a stack 77 for piling up all the assignments once they have been expanded by the expansion unit 75, a control unit 80 for executing the resource assigning by means of the graph coloring method according to graph degeneration, and a storage unit 78 for storing the assigning result in the form shown in FIG. 3B.
FIGS. 5A, 5B, and 6A through 6I are drawings for illustrating the graph coloring method according to graph degeneration. The following is an explanation of the operational process of the resource assigning apparatus 63 with reference to these drawings. Here, the number of registers for which assigning is possible is given as 3, with the assignments which cannot be assigned to these registers being assigned to the memory.
The aforementioned expansion unit 75 expresses the assignments shown in FIG. 1 and the interference between the live ranges of these assignments in an interference graph, as shown in FIG. 5A. In this kind of interference graph, the extent to which a live range of an assignment interferes with the live ranges of other assignments is shown as the number of edges which emerge from a vertex. Also, as shown in FIG. 5B, when the start point and end point of live ranges coincide in the same step (assignments b2 and c in FIG. 1), then the control unit 80 combines the corresponding vertices, as shown in FIG. 5B, in order to regard them as one assignment and hence simplify the interference graph (see FIG. 5B, b2c). After accomplishing the simplification, then the modulation of the vertices is executed. The degree of vertex is referred to as being low for vertices with under 3 registers and as being high for vertices with a same number as the number of registers or more. This modulation of degree is used as the formation condition in graph degeneration. The graph degeneration, as indicated by the arrows y11, y12 in FIG. 6A, is carried out so that the vertices of low degree are removed in order of priority value as calculated in (numerical equation 1), from lowest to highest priority level, with the assignment of the removed vertices being piled up in the stack area in last in, first out order. The result of the removal of e2 and d and the transformation of the interference graphs shown in FIGS. 5A and 5B is shown in FIG. 6B.
Since all the vertices in FIG. 6B are of high degree, the above formation condition is not satisfied. As a result, the assignment having the lowest priority level out of these vertices, b1, is assigned to the memory and is removed as shown by the arrow y13 in the drawings. By removing b1, the interference graph is transformed as shown in FIG. 6C, so that, once again, the above formation condition is satisfied. Graph degeneration is again repeated for the state shown in FIG. 6C, and all of the assignments are piled up in the stack, as shown in FIG. 6D. After this piling up process has been completed, the resource assigning process is executed. First, as shown in FIG. 6E, assignment a is retrieved from the top of the stack and is assigned to register R0. Next, as shown in FIGS. 6F and 6G, assignments e1 and b2c are taken from the top of the stack and are assigned to registers R1 and R2 as shown in FIGS. 6E and 6F. The following assignments e2 and d interfere with the live range of b2c, but, since they do not interfere with the live ranges of assignments a and e1, then e2 is assigned to the lowest number register R0 for which assignment is possible, as shown in FIG. 6H, while assignment d is assigned to register R1, as shown in FIG. 6I. By means of this kind of assignment process, assignments whose live ranges interfere with each other can be assigned to different registers.
The above assignments a, b2, c, d, e1, e2, and b1 are all assigned to resource elements by the resource assigning process, but, for high-level languages such as C language, there are registers for which the combination with assignments is already decided. These registers are used to improve the efficiency of function call operations, and are known as argument registers, return value registers and broken registers.
Argument registers are registers for transferring arguments when there is a function call. Assignments used as arguments in the intermediate program are assigned to these argument registers.
Return value registers are registers for returning the return value of the function call. Assignments used for returning the return value in the intermediate program are allocated to these return value registers.
Broken registers are registers for assigning the assignments for which it is not necessary to store and restore the stored values at the start and end of the function call. The object of these broken registers is to reduce the overheads of a function call. When such a function call is executed, there is the possibility that the content of every register will be changed according to the process within the called function, so that before or after the function call, it will be necessary to store and restore the content of the registers. These storing and restoring functions for every register increase the overheads of the function call. However, by setting beforehand the broken registers for which storing and restoring are unnecessary and assigning the assignments which do not include function calls in their live ranges to the broken registers, the number of storing and restoring operations can be minimized.
However, for resource assigning apparatuses constructed according to the prior art, there has been the problem that resource allocation can increase execution time and the memory size of the object program. This will be explained with reference to FIG. 7. In this drawing, the vertical lines show the live ranges of the assignments, with the lines shown as thick white lines showing the assignments which are yet to be assigned, and the thick shaded lines showing the assignments which have been assigned. Here, parts of the vertical lines representing assignments x0, x1, and x5 run parallel with the vertical lines representing assignments z0, z1 and z2, showing that the live ranges of these assignments interfere with one another.
In the example shown in FIG. 7, assignments whose live ranges follow on one after the other can be combined (assignments x0, x1, x2, x3, x4, x5) so as to form one vertex as described above, this being the assignment y. This combined assignment y has a live range which interferes with the live range of the assignment z0 which has already been assigned to the resource element R0, with the live range of the assignment z1 which has already been assigned to the resource element R1, and with the live range of the assignment z2 which has already been assigned to the resource element R2. If its live range interferes with those of assignments which have already been assigned in this way, then it is not possible to assign assignment y to any resource element which has been assigned one of these assignments (in other words, to any of resource elements R0, R1 and R2). This results in the assignment y which consists of the assignments x0, x1, x2, x3, x4, x5 being assigned to the memory, so that intermediate instructions which use any of these assignments as operands are converted into machine language instructions which take memory addresses as operands. Machine language instructions which take the memory as operands are usually of low operational speed and take up a large amount of memory space, increasing the execution time and memory size of the object program.
Additionally, when the resources are split up into 3 or more functions, then there is the problem in that resource assigning cannot be achieved in accordance with the functions of the resources, which has a detrimental effect on the execution speed and memory size of the object program.
The Mori et al. treatise mentioned above teaches the assigning of resources after first referring to the cost of accessing each of the different kinds of register when there are a number of registers of different classes such as address registers and data registers. In this treatise, the basic conception, "In C language, all assignments storing pointer-type variables are assigned to the address registers" is given. However, such address-type assignments can also include assignments which are used several times in addition and subtraction and which to a small extent include indirect reference of the memory. Such assigning will lead to the uniform assigning of assignments to the address register, even for a target machine which includes a data register which can execute such addition and subtraction at high speed, thereby creating a large number of transfer instructions from the address register to the data register in the object program, resulting in an increase in the memory size and execution time of the object program.
For the above reasons, it can be seen that assigning in accordance with only the necessary cost of assigning registers sorted merely in terms of class can result in the generation of a large number of transfer instructions.
There has also been the problem of not be able to execute resource assigning using the stored values of the argument registers, the return value registers and the broken registers as they are. These registers are originally set so that function calls can be executed efficiently.
The graph coloring method is an approximate algorithm for executing the most suitable color classification of the vertices in the interference graph. Since the argument registers, the return value registers and the broken registers are resource elements to which assignments are assigned before the execution of the algorithm, then these registers are regarded as colored vertices in the interference graph. In order to realize resource assigning which can use the stored values of the argument registers, return value registers and the broken registers as they are, then it becomes necessary to build the colored vertices into the interference graph and to execute a coloring process using that color for other vertices if it is valid, although this leads to deviation of the limits of the graph coloring method. For the above reason, it is normally necessary to prepare separately the argument registers, the return value registers and the broken registers as assignable registers so that they may be used. Therefore, to use the stored values of the argument registers, the return value registers and the broken registers, a transfer instruction for the register used for assigning becomes necessary. Once this kind of transfer instruction becomes necessary, the necessary memory size and the execution time of the object program have to be increased by the amount used by this instruction.
The effect of the aforementioned problems can be regarded as being of an insignificant level when there is an abundant supply of registers. However, when there are only a limited number of registers, such as with many embedded microprocessors, or when there are a small number of registers of several different kinds which fulfill different functions, then the effect of these problems becomes significant.
The first object of the present invention is to provide a resource assigning apparatus which is able to assign assignments to resource elements in order of priority ranking and, by limiting as much as possible the generation of transfer instructions, can restrict as far as possible the memory size and execution time needed by an object program.
The second object of the present invention is to provide a resource assigning apparatus which can achieve a "smart" assigning wherein assignments whose loop-nesting depth level is deep can be prioritized and assigned to registers, with remaining assignments with progressively shallower loop-nesting depth levels being distributed among these registers.
The third object of the present invention is to provide a resource assigning apparatus which can achieve a "smart" assigning wherein assignments whose frequency of use is high can be prioritized and assigned to registers, with remaining assignments with progressively lower frequencies of use being distributed among these registers.
The fourth object of the present invention is to provide a resource assigning apparatus which can execute resource assigning with a detailed understanding for assignments of the distance from, the running into of live ranges with, and interference with assigned assignments.
The fifth object of the present invention is to provide a resource assigning apparatus which can execute assigning of assignments making fullest use of the separate functions of the resources included in a microprocessor.
The sixth object of the present invention is to provide a resource assigning apparatus which can achieve a "smart" assigning wherein assigning of assignments which are predetermined by an operator can be performed to resources such as argument registers, return value registers and broken registers.
SUMMARY OF THE INVENTION
The first and fourth objects of the present invention are achieved by 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:a profit/loss value calculation unit 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; an assigning unit 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 a control unit for repeatedly activating the profit/loss value calculation unit and the assigning unit until every assignment has been assigned.
By means of this construction, assignments in groups of assignments which have positional relationships such that their live ranges are continuous have their profit/loss values increased in accordance with the extent of the live range length, with any assignments in such a group having a live range which interferes with a live range of an already assigned assignment being assigned to a different resource element as the assigned assignment with which there is interference, so that resource assigning is performed with consideration to the positional relationship between live ranges and so that assignments whose live ranges are continuous will not be uniformly assigned in all cases. Accordingly, the assigning state of the surrounding assignments influences the next resource assigning to be executed, which results in a greater reduction in the number of transfer instructions.
Also, the resource assigning apparatus may further comprise a positional relationship determination unit for determining the positional relationships between all of the assignments in the program written in the high-level language, wherein the positional relationship determination unit may include: an interfering relation determination unit 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 an assigned-next continuation determination unit 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 unit may include a first increase unit for increasing, when the assigned-next continuation determination unit 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 unit may determine not to assign the next assignment to a resource element which has been assigned an assignment determined by the interfering relation determination unit 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.
Also, the positional relationship determination unit may further include: a first assigned assignment interference detection unit for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment; an unassigned-next continuation determination unit for determining whether the live range of the unassigned assignment detected by the first assigned assignment interference detection unit 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 unit 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 unit to the next assignment.
By means of this construction, by reducing the profit/loss value for a resource element which has been assigned an assignment which, from the viewpoint of the assignment to be assigned, causes a loss, the assigning state of the surrounding assignments is made to influence the next resource assigning to be executed, which results in a greater reduction in the number of transfer instructions.
Also, when a plurality of unassigned assignments are determined by the first assigned assignment interference detection unit, the unassigned-next continuation determination unit may determine whether a live range of any of the plurality of unassigned assignments determined by the first assigned assignment interference detection unit is continuous with the live range of the next assignment.
By means of this construction, the multiple reduction of the profit/loss values of resource elements which have been assigned assignments by the detection of unassigned assignments, leading to relatively low evaluations of such elements, can be avoided.
The second and third objects of the present invention are achieved by a resource assigning apparatus which may further include a priority level storage unit 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 unit and the assigning unit determine which assignment is a next assignment in order of priority levels stored in the priority level storage unit.
By means of this construction, assigning to resource elements is executed in order of the frequency of use or loop-nesting depth level of assignments, so that resource assigning is performed taking into account the positional relationships between live ranges, frequency of use and loop-nesting depth level of assignments, leading to an improvement in the quality of the object program.
Also, the positional relationship determination unit may further include: a next assignment interfering assignment detection unit for detecting, when there is a plurality of resource elements whose profit/loss values calculated by the profit/loss value calculation unit are of a same value, any unassigned assignments whose live range interferes with the live range of the next assignment; and an unassigned-assigned continuation determination unit for determining whether a live range of an assignment detected by the next assignment interfering assignment detection unit is continuous with the live range of an assigned assignment, wherein the profit/loss calculation unit may further include: a priority level detection unit for detecting a priority level of an assignment detected by the next assignment interfering assignment detection unit; 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 unit to the assigned assignment determined by the unassigned-assigned continuation determination unit 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.
By means of this construction, by reducing the profit/loss value for a resource element which has been assigned an assignment which, from the viewpoint of the assignment to be assigned, causes a loss, the assigning state of the surrounding assignments is made to influence the next resource assigning to be executed, which results in a greater reduction in the number of transfer instructions.
Also, the positional relationship determination unit may further include: a second assigned assignment interference detection unit for detecting an unassigned assignment whose live range interferes with a live range of any assigned assignment; and an unassigned-unassigned continuation determination unit for determining whether a live range of an unassigned assignment detected by the next assignment interfering assignment detection unit is continuous with a live range of an unassigned assignment detected by the second assigned assignment interference detection unit, and wherein the profit/loss value calculation unit may further include: 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 unit to the unassigned assignment detected by the second assigned assignment interference detection unit 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.
By means of this construction, by increasing the profit/loss value for a resource element which has been assigned an assignment which, from the viewpoint of the assignment to be assigned, causes a profit, the assigning state of the surrounding assignments is made to influence the next resource assigning to be executed, which results in a greater reduction in the number of transfer instructions.
Also, when a plurality of unassigned assignments are determined by the second assigned assignment interference detection unit, the unassigned-unassigned continuation determination unit may determine 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.
By means of this construction, the multiple reduction of the profit/loss values of resource elements which have been assigned assignments by the detection of unassigned assignments, leading to relatively low evaluations of such elements, can be avoided.
Also, the resource assigning apparatus may further include 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 may increase a profit/loss value of each resource element stored in the profit/loss value storage unit and the first and second reduction units may reduce a profit/loss value of each resource element stored in the profit/loss value storage unit.
By means of this construction, the profit/loss values of each resource element stored by the profit/loss value storage unit are increased by the first and second increase units and reduced by the first and second reduction units. As a result, the profits and losses caused for each resource element can be objectively evaluated even when a resource element has been assigned assignments which cause a profit for an assignment to be assigned and assignments which cause a loss for an assignment to be assigned, so that more precise resource assigning can be achieved. Here, since the profit/loss value storage unit stores each resource element corresponded with an initial value of the total profit/loss value for each resource element, if some resource elements have been assigned assignments which cause a loss, the profit/loss value of resource elements which have not been assigned an assignment will be given a higher estimation. In this way, assigning to a resource element which has not been assigned an assignment can be achieved.
The fifth object of the present invention is achieved by a resource assigning apparatus which may further include: an estimation unit 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 a resource element singular/plural determination unit 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 unit determines that only one resource element has a lowest estimated value, the assigning unit may assign the next assignment to the resource element determined to have the lowest estimated value, while when the resource element singular/plural determination unit determines that a plurality of resource elements have a lowest estimated value, the assigning unit may assign 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.
By means of this construction, switching is performed between using the estimated value and the profit/loss value, so that when the estimated value is used, code size and execution time can be reflected by assignments so that detailed cost information for the instructions of the microprocessor can be effectively put to use, meaning that a favorable selection of a resource element for assigning an assignment can be made out of resources which are split up between three or more functions. By using the present compiler to develop programs for embedded microprocessors which are equipped with a plurality of resources which have different functions, an object program which puts the different functions available in the microprocessor to good use can be achieved.
Also, the estimation unit may include: 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.
By means of this construction, then in converting the definition instructions and use instructions of an assignment into machine language instructions, a precise judgement of which resource's resource element is most suitable for assigning can be made, so that an object program which puts the different functions available in the microprocessor to good use can be achieved.
Also, the resource assigning apparatus may further include a prediction unit for predicting, when a profit/loss value calculated by the profit/loss value calculation unit 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 unit may assign the next assignment to the resource element predicted by the prediction unit.
By means of this construction, when the calculated profit/loss values of assigned resource elements belonging to a number of different resources have a same value, since the assigning unit assigns the assignment to be assigned to a resource element judged to be suitable for all of the assignments of lower priority levels, a more precise selection of resource element can be made when the merits of resource elements cannot be evaluated by profit/loss values alone. As a result, the assignments of lower priority levels can be assigned so as to reduce the code size/execution time of the definition instructions and use instructions included therein. Furthermore, by assigning to such a resource element, this resource element can be succeeded when assigning a next assignment, so that it becomes more likely that all of the assignments whose live ranges are continuous with one another can be assigned to a same resource element.
Also, the prediction unit may include: a first lower order assignment detection unit 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; a first estimation unit 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 unit 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 unit and each resource element; a first live range length calculation unit for calculating a continuous length of live range for each assignment detected by the first lower order assignment detection unit, the length of live range being between the next assignment and each assignment detected by the first lower order assignment detection unit; a first weighting unit for weighting the estimated value calculated by the first estimation unit for pairings of each detected assignment and each resource element using the calculated length of live range; a first totalling unit for totalling estimated values weighted by the first weighting unit for each resource element; and a first optimal resource element determination unit 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 unit, wherein a resource element determined as a determination result of the first optimal resource element determination unit is set as a prediction result of the prediction unit.
By means of this construction, evaluation is performed based on the distance of the unassigned assignment from the assignment to be assigned and on the size of the estimated value of the code size and the execution time of definition instructions and reference instructions of assignments of lower priority which are assigned after the assignment to be assigned and whose live ranges are continuous with each other, so that the execution time and/or code size of definition instructions and reference instructions of assignments which assignments close to the assignment to be assigned are given a higher estimation and the execution time and/or code size of definition instructions and reference instructions of assignments which assignments far to the assignment to be assigned are given a lower estimation. As a result, there is an increase in the probability that assignments whose live ranges are continuous can be assigned to the same resource element. This leads to an estimation of resource elements which enables a reduction in code size and execution time for lower order assignments.
Also, the prediction unit may further include: a second lower order assignment detection unit for detecting, when a plurality of resource elements are determined by the first optimal resource element determination unit 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; a second estimation unit 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 unit 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 unit and each resource element; a second live range length calculation unit for calculating a continuous length of live range for each assignment detected by the second lower order assignment detection unit, 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; a second weighting unit for weighting the estimated value calculated by the second estimation unit for pairings of each unassigned assignment detected by the second lower order assignment detection unit and each resource element using the length of live range calculated for each assignment by the second live range length calculation unit and the priority value of each assignment; a second totalling unit for totalling the estimated values of each assignment weighted by the second weighting unit for each resource element; and a second optimal resource element determination unit 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 unit.
Also, the first and second weighting units may 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 unit and the second live range length calculation unit is "0", and the first and second weighting units may 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 unit and the second live range length calculation unit is not "0".
By means of the above construction, since evaluation is performed based on a comparison of the estimated costs of the execution time and/or code size of definition instructions and use instructions of assignments which have a lower priority level than the assignment to be assigned and whose live ranges interfere as well as on a distance from the unassigned assignment to the assignment to be assigned, a reliable evaluation of the resource elements can be performed so as to reduce the execution time and/or the code size of the lower order assignments.
Also, the resource assigning apparatus may further include a cost storage unit 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 unit may include: 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 unit and outputting the retrieved instruction patterns; and a first cost totalling unit for retrieving a cost from the cost storage unit 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 unit may include: 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 unit and outputting the retrieved instruction patterns; and a second cost totalling unit for retrieving a cost from the cost storage unit corresponding to the output instruction patterns, for totalling the retrieved costs for each resource element and setting the totalled costs as estimated values.
Also, an instruction pattern may include 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 a cost of instruction patterns where a storage location coincides with either operand may be lower than a cost of instruction patterns where a storage location does not coincide with either operand.
Also, an instruction pattern may include 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 may be lower than a cost of instruction patterns where the corresponding use instruction is not the end point.
By means of the above construction, when converting the definition instructions and use instructions of an assignment into machine language instructions, a precise judgement of which resource's resource element is most suitable for assigning can be made, so that a reliable evaluation of the resource elements can be performed so as to reduce the execution time and/or the code size of the lower order assignments.
The sixth object of the present invention can be achieved by a resource assigning apparatus which may further include: a reserved assignment detection unit for detecting assignments which are to be assigned to a predetermined resource element from the program; and a reserved resource element storage unit for storing resource elements to which the assignments detected by the reserved assignment detection unit should be assigned; wherein the assigning unit may assign the assignments detected by the reserved assignment detection unit 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.
Here, other assignments can be assigned to the argument registers, the return value registers and the broken registers, so that resource assigning can be performed so as to allow the stored values of the argument registers, the return value registers and the broken registers to be used as they are. This enables greater reductions in the number of transfer instructions.
Also, the resource assigning apparatus may further include a live range continuation relation group storage unit 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 unit may include: 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 unit may include: a totalling unit for totalling a live range length of the assignments determined by the assigned-next continuation determination unit: 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.
By means of this construction, a reciprocal of the sum of the live range length totalled by the totalling unit and the live range length of the assignment to be assigned is calculated and since this reciprocal is set by the reciprocal calculation unit as the extent of live range, resource assigning can be performed so as to reflect the total live range length, enabling greater reductions in the number of transfer instructions.
Also, a start point and an end point of a live range may be expressed as instruction position information and the resource assigning apparatus may further include: a start/end point storage unit 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; a first grouping unit for referring to the start/end point storage unit, 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; a second grouping unit for referring to the start/end point storage unit, 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 a writing unit for writing into the live range continuation relation group storage unit 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 unit and the second grouping unit.
By means of this construction, assignments in the program and live range continuation groups grouped by the first and second grouping units are corresponded together by the writing unit in the live range continuation group storage unit, so that judgements of whether there is or is not succession of live ranges can be more efficiently made.
The objects can also be achieved by 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: an assignment storage unit for storing assignments in the program, each assignment being corresponded to a priority level; a first resource element assigning unit for retrieving an assignment with a highest priority level in the assignment storage unit and assigning the assignment with the highest priority level to any of the resource elements; an assignment retrieval unit for retrieving from the assignment storage unit an assignment which has a priority level which comes in order directly after a priority level of an assignment which has just been assigned; a following assignment interfering assignment detection unit for detecting any assignments with a live range which interferes with a live range of the assignment retrieved by the assignment retrieval unit; a resource element detection unit for detecting resource elements which have been assigned assignments detected by the following assignment interfering assignment detection unit; an assignment-resource element detection unit for detecting all assignments which have been assigned to any resource element which has not been detected by the resource element detection unit; a profit continuation assigned assignment determination unit for determining every assignment which has a live range which is continuous with a live range of the assignment retrieved by the assignment retrieval unit, out of the assigned assignments detected by the assignment-resource element detection unit; a first profit/loss value calculation unit 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 unit to the assignment retrieved by the assignment retrieval unit, for each resource element assigned an assignment determined by the profit continuation assigned assignment determination unit; a totalling unit for totalling the calculated profit/loss values for each resource element determined by the assignment-resource element detection unit; a second resource assigning unit for assigning the assignment retrieved by the assignment retrieval unit to a resource element with a highest total value totalled by the totalling unit; and a control unit for repeatedly activating the assignment retrieval unit until every assignment has been assigned.
By means of this construction, the assignment to be assigned is assigned to the already assigned resource element which has a highest profit value, so that in the process assigning assignments to resource elements, a precise judgement of the state of resource elements for a particular assignment can be made. This results in a decrease in the number of transfer instructions between the memory and registers and between different registers, so that improvements in the program size and execution time of the object machine language program can be made. When performing resource assigning for a target machine equipped with only a limited number of registers, the improvements in program size and execution time of the object machine language program are especially remarkable.
Also, the resource assigning apparatus may further include: a first non-interfering non-continuous assigned assignment determination unit for determining assignments whose live range is not continuous with a live range of an assignment retrieved by the assignment retrieval unit nor interferes with the live range of the assignment retrieved by the assignment retrieval unit, out of the assigned assignments detected by the assignment-resource element detection unit; a profit continuation unassigned assignment determination unit for detecting an assignment whose live range is continuous with a live range of the assignment retrieved by the assignment retrieval unit 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 unit; a second profit/loss value calculation unit for calculating a profit/loss value of a resource element assi |
