Register allocation method and apparatus for gernerating spill code as a function of register pressure compared to dual thresholds
First Claim
Patent Images
1. A computer apparatus comprising:
- (A) a processor having a plurality of registers, the processor executing a first instruction stream and in response to the first instruction stream, the processor operates on information stored in the plurality of registers;
(B) a compiler for generating the first instruction stream from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including;
a spill code generator, the spill code generator including;
a register pressure indicator, the register pressure indicator indicating the register pressure at a plurality of regions within the second instruction stream;
a load instruction inserter;
a store instruction inserter;
the load instruction inserter inserting at least one memory load instruction into the second instruction stream and the store instruction inserter inserting at least one memory store instruction into the second instruction stream at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure exceeds a first predetermined threshold level;
the load instruction inserter and the store instruction inserter avoiding the insertion of memory load instructions and memory store instructions at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than the first predetermined threshold level;
wherein the load instruction inserter and the store instruction inserter avoid the insertion of memory load instructions and memory store instructions at locations that reduce register pressure only in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than a second predetermined threshold level.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for minimizing spill code in regions of low register pressure determines the register pressure at various locations in the computer program. When a live range is selected for spilling, spill code is generated to relieve the register pressure in regions of high register pressure, while spill code is avoided in regions of low register pressure. In this manner a minimum amount of spill code is generated, enhancing both the compile time and the run time of the resultant instruction stream.
-
Citations
7 Claims
-
1. A computer apparatus comprising:
-
(A) a processor having a plurality of registers, the processor executing a first instruction stream and in response to the first instruction stream, the processor operates on information stored in the plurality of registers; (B) a compiler for generating the first instruction stream from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including; a spill code generator, the spill code generator including; a register pressure indicator, the register pressure indicator indicating the register pressure at a plurality of regions within the second instruction stream; a load instruction inserter; a store instruction inserter; the load instruction inserter inserting at least one memory load instruction into the second instruction stream and the store instruction inserter inserting at least one memory store instruction into the second instruction stream at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure exceeds a first predetermined threshold level; the load instruction inserter and the store instruction inserter avoiding the insertion of memory load instructions and memory store instructions at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than the first predetermined threshold level;
wherein the load instruction inserter and the store instruction inserter avoid the insertion of memory load instructions and memory store instructions at locations that reduce register pressure only in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than a second predetermined threshold level. - View Dependent Claims (2, 3)
-
-
4. A computer apparatus for generating a first instruction stream from a second instruction stream, the first instruction stream being executable on a processor having a plurality of registers, the second instruction stream having a plurality of variables, the computer apparatus comprising:
-
a spill code generator, the spill code generator including; a register pressure indicator, the register pressure indicator indicating the register pressure at a plurality of regions within the second instruction stream; a load instruction inserter; a store instruction inserter; the load instruction inserter inserting at least one memory load instruction into the second instruction stream and the store instruction inserter inserting at least one memory store instruction into the second instruction stream at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure exceeds a first predetermined threshold level; the load instruction inserter and the store instruction inserter avoiding the insertion of memory load instructions and memory store instructions at locations that reduce register pressure in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than the first predetermined threshold level; wherein the load instruction inserter and the store instruction inserter avoid the insertion of any memory load instructions and memory store instructions at locations that reduce register pressure only in at least one of the plurality of regions where the register pressure indicator indicates that the register pressure is less than a second predetermined threshold level. - View Dependent Claims (5, 6)
-
-
7. A method for generating spill code in an optimizing compiler, the compiler generating a first instruction stream from a second instruction stream, the method comprising the steps of:
-
computing register pressure at a plurality of regions within the second instruction stream; inserting at least one memory load instruction in the second instruction stream; inserting at least one memory store instruction in the second instruction stream; the locations of the inserted memory load instructions and memory store instructions are selected to reduce register pressure in at least one of a plurality of regions where the register pressure exceeds a first predetermined threshold level and to not reduce register pressure in at least one of the plurality of regions where the register pressure is less than the first predetermined threshold level, wherein the locations of the inserted memory load instructions and memory store instructions are selected to avoid reducing register pressure only in at least one of the plurality of regions where the register pressure is less than a second predetermined threshold level.
-
Specification