Inter-procedure global register allocation method
First Claim
Patent Images
1. A method for optimizing processor register allocation, comprising:
- identifying a plurality of variables from an acyclic call graph having a plurality of functions;
creating a plurality of virtual registers by assigning each of the plurality of variables to at least one virtual register;
constructing an interference graph based on the plurality of virtual registers;
coloring the interference graph with a plurality of physical registers; and
if the interference graph is not colorable, spilling at least one virtual register from the interference graph.
1 Assignment
0 Petitions
Accused Products
Abstract
Embodiments of the present invention provide a method and system for optimizing processor register allocation. Variables from an acyclic call graph having a plurality of functions may be identified and a plurality of virtual registers may be created by assigning each of the identified variables to at least one virtual register. An interference graph may be constructed based on the plurality of virtual registers and may be colored with a plurality of physical registers. If the interference graph is not colorable, then at least one virtual register may be spilled from the interference graph.
-
Citations
24 Claims
-
1. A method for optimizing processor register allocation, comprising:
-
identifying a plurality of variables from an acyclic call graph having a plurality of functions;
creating a plurality of virtual registers by assigning each of the plurality of variables to at least one virtual register;
constructing an interference graph based on the plurality of virtual registers;
coloring the interference graph with a plurality of physical registers; and
if the interference graph is not colorable, spilling at least one virtual register from the interference graph. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer-readable medium storing instructions adapted to be executed by a processor, the instructions comprising:
-
identifying a plurality of variables from an acyclic call graph having a plurality of functions;
creating a plurality of virtual registers by assigning each of the plurality of variables to at least one virtual register;
constructing an interference graph based on the plurality of virtual registers;
coloring the interference graph with a plurality of physical registers; and
if the interference graph is not colorable, spilling at least one virtual register from the interference graph. - View Dependent Claims (14, 15, 16, 17)
-
-
18. A system for optimizing processor register allocation, comprising:
-
a target system including a memory and at least one processor having a plurality physical registers; and
a developer system, coupled to the target system, including;
a memory, and at least one processor adapted to;
identify a plurality of variables from an acyclic call graph having a plurality of functions, create a plurality of virtual registers by assigning each of the plurality of variables to at least one virtual register;
construct an interference graph based on the plurality of virtual registers, color the interference graph with at least one of the plurality of physical registers, and if the interference graph is not colorable, spill at least one virtual register from the interference graph. - View Dependent Claims (19, 20, 21, 22, 23, 24)
-
Specification