Register allocation via selective spilling
First Claim
1. A method for minimizing register spilling in an optimizing compiler by updating a first set of code instructions to include one or more code instructions for causing specified data to be stored in a first memory location during the execution of the first set of code instructions, the method comprising the steps of:
- a) determining a code region hierarchy based upon the first set of code instructions, wherein the code region hierarchy includes a set of code regions;
b) generating a second set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the second set of code instructions causes the specified data to be moved from a second memory location to the first memory location;
c) generating a third set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the third set of code instructions causes the specified data to be moved from the first memory location to the second memory location; and
d) adding both the second set of code instructions and the third set of code instructions to one or more locations in the first set of code instructions based upon code region boundaries specified by the code region hierarchy,whereby register spilling is reduced.
2 Assignments
0 Petitions
Accused Products
Abstract
An approach for allocating a set of virtual registers to a set of physical registers using selective spilling is described. A set of code and a spill variable are specified. A code region hierarchy containing a set of code regions is determined based upon the set of code. The first level of the code region hierarchy is evaluated and if the spill variable is referenced in more than one code region, code for performing a spill operation on the specified spill variable is added to the set of code based upon a code region which defines the specified spill variable. In addition, code for performing a reload operation on the specified spill variable is added to the set of code based upon code regions that use the specified spill variable. If the spill variable is only referenced in a single code region in the first level of the code region hierarchy, then code regions that are both in a second level of the code region hierarchy and which correspond to the code region in the first level which references the spill variable are analyzed and code added in a similar manner.
31 Citations
15 Claims
-
1. A method for minimizing register spilling in an optimizing compiler by updating a first set of code instructions to include one or more code instructions for causing specified data to be stored in a first memory location during the execution of the first set of code instructions, the method comprising the steps of:
-
a) determining a code region hierarchy based upon the first set of code instructions, wherein the code region hierarchy includes a set of code regions; b) generating a second set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the second set of code instructions causes the specified data to be moved from a second memory location to the first memory location; c) generating a third set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the third set of code instructions causes the specified data to be moved from the first memory location to the second memory location; and d) adding both the second set of code instructions and the third set of code instructions to one or more locations in the first set of code instructions based upon code region boundaries specified by the code region hierarchy, whereby register spilling is reduced. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer system for minimizing register spilling in an optimizing compiler, the computer system comprising:
-
a) a memory; b) one or more processors coupled to the memory, wherein the one or more processors are configured to update the first set of code instructions to include one or more code instructions for causing specified data to be stored in a first memory location during the execution of the first set of code instructions based upon code region boundaries associated with a set of code regions specified by a code region hierarchy determined from the first set of instructions, and to determine whether the specified data is referenced in one or more code regions specified by a first level of the code region hierarchy, if the specified data is referenced in one or more code regions specified by the first level of the code region hierarchy then to generate a set of reload code instructions for causing the specified data to be moved from a second memory location to the first memory location, and if the specified data is referenced in only one code region specified by the top level of the code region hierarchy then to examine one or more other levels of the code region hierarchy which correspond to the code region specified by the top level of the code region hierarchy that references the specified data.
-
-
8. A computer program embodied in a computer-readable medium for minimizing register spilling in an optimizing compiler by updating a first set of code instructions to include one or more code instructions for causing specified data to be stored in a first memory location during the execution of the first set of code instructions, the computer program comprising:
-
a) a first code segment for determining a code region hierarchy based upon the first set of code instructions, wherein the code region hierarchy includes a set of code regions; b) a second code segment for generating a second set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the second set of code instructions causes the specified data to be moved from a second memory location to the first memory location; c) a third code segment for generating a third set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the third set of code instructions causes the specified data to be moved from the first memory location to the second memory location; and d) a fourth code segment for adding both the second set of code instructions and the third set of code instructions to locations in the first set of code instructions based upon code region boundaries specified by the code region hierarchy, whereby register spilling is reduced. - View Dependent Claims (9, 10, 11)
-
-
12. A computer data signal embodied in a carrier wave and representing a computer program for minimizing register spilling in an optimizing compiler by updating a first set of code instructions to include one or more code instructions for causing specified data to be stored in a first memory location during the execution of the first set of code instructions, the computer program comprising:
-
a) a first code segment for determining a code region hierarchy based upon the first set of code instructions, wherein the code region hierarchy includes a set of code regions; b) a second code segment for generating a second set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the second set of code instructions causes the specified data to be moved from a second memory location to the first memory location; c) a third code segment for generating a third set of code instructions based upon both the code region hierarchy and the specified data, wherein the execution of the third set of code instructions causes the specified data to be moved from the first memory location to the second memory location; and d) a fourth code segment for adding both the second set of code instructions and the third set of code instructions to the first set of code instructions based upon the code region hierarchy, whereby register spilling is reduced. - View Dependent Claims (13, 14, 15)
-
Specification