Inter-procedure global register allocation method

• US 7,069,548 B2
• Filed: 06/28/2002
• Issued: 06/27/2006
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kushlis, Robert J
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/183,663
• Publication Number:
  US 20040003385A1
• Time in Patent Office: 1,460 Days
• Field of Search: 717/156, 717/153, 717/155, 717/152, 717/157, 717/158, 717/144, 717/146, 717/151, 717/161, 717/128, 712/208, 710/305, 707/200
• US Class Current: 717/156
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

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.

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, wherein constructing the interference graph includes sorting the acyclic call graph into a doubly-linked list;

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.

2. The method of claim 1, wherein said coloring the interference graph includes associating each of said plurality of virtual registers with one of said plurality of physical registers.

3. The method of claim 1, wherein said spilling at least one virtual register includes:

removing the virtual register from the interference graph; and

associating the virtual register with a memory location.

4. The method of claim 1, wherein the plurality of variables includes at global variables, local variables, argument variables, return address variables, and return value variables.

5. The method of claim 1, wherein each of the plurality of variables is smaller than a predetermined size.

6. The method of claim 5, wherein the predetermined size is no larger than each of the plurality of physical registers.

7. The method of claim 1, wherein said plurality of functions includes library functions.

8. The method of claim 1, wherein the acyclic call graph includes a full call graph of an entire program.

9. The method of claim 1, wherein the acyclic call graph includes an acyclic branch of a full call graph of an entire program.

10. The method of claim 1, wherein said constructing the interference graph includes:

while traversing the doubly-linked list in reverse order, for each function in the doubly-linked list;

determining a first virtual register set including any of the plurality of virtual registers used by the function, and any of the plurality of virtual registers used by a called function that are not previously assigned, and

determining a second virtual register set including any of the plurality of virtual registers unconditionally assigned on all executions of the function; and

while traversing the doubly-linked list in forward order, for each function in the doubly-linked list;

determining a third virtual register set including any of the plurality of virtual registers that are live immediately following any call to the function,

tracing a liveness for each of the plurality of virtual registers, and

constructing an edge between pairs of virtual registers based on the liveness.

11. The method of claim 10, wherein said edge indicates that the pair of virtual registers can not be associated with the same physical register.

12. 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, wherein constructing the interference graph includes sorting the acyclic call graph into a doubly-linked list;

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.

13. The computer-readable medium of claim 12, wherein:

said coloring the interference graph includes associating each of said plurality of virtual registers with one of said plurality of physical registers; and

said spilling at least one virtual register includes;

removing the virtual register from the interference graph; and

associating the virtual register with a memory location.

14. The computer-readable medium of claim 12, wherein:

the plurality of variables includes global variables, local variables, argument variables, return address variables and return value variables; and

each of the plurality of variables is no larger than each of the plurality of physical registers.

15. The computer-readable medium of claim 12, wherein the acyclic call graph includes at least one acyclic branch of a full call graph of an entire program.

16. The computer-readable medium of claim 12, wherein said constructing the interference graph includes:

while traversing the doubly-linked list in reverse order, for each function in the doubly-linked list;

determining a first virtual register set including any of the plurality of virtual registers used by the function, and any of the plurality of virtual registers used by a called function that are not previously assigned, and

determining a second virtual register set including the virtual registers unconditionally assigned on all executions of the function; and

while traversing the doubly-linked list in forward order, for each function in the doubly-linked list;

determining a third virtual register set including any of the plurality of virtual registers that are live immediately following any call to the function,

tracing a liveness for each of the plurality of virtual registers, and

constructing an edge between pairs of virtual registers based on the liveness, the edge indicating that the pair of virtual registers can not be associated with the same physical register.

17. 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, wherein to construct of the interference graph, the one processor is adapted to sort the acyclic call graph into a doubly-linked list,

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.

18. The system of claim 17, wherein the target system includes a core processor and at least two data processors having a plurality of physical registers.

19. The system of claim 17, wherein the target system and the developer system are a single system.

20. The system of claim 17, wherein:

said color the interference graph includes associating each of said plurality of virtual registers with one of said plurality of physical registers; and

said spill at least one virtual register includes;

removing the virtual register from the interference graph; and

associating the virtual register with a memory location.

21. The system of claim 17, wherein:

the plurality of variables includes global variables, local variables, argument variables, return address variables, and return value variables; and

each of the plurality of variables is no larger than each of the plurality of physical registers.

22. The system of claim 17, wherein the acyclic call graph includes at least one acyclic branch of a full call graph of an entire program.

23. The system of claim 22, wherein said construct the interference graph includes:

traverse the doubly-linked list in reverse order, and for each function in the doubly-linked list;

determine a first virtual register set including any of the plurality of virtual registers used by the function, and any of the plurality of virtual registers used by a called function that are not previously assigned, and

determine a second virtual register set including the virtual registers unconditionally assigned on all executions of the function; and

traverse the doubly-linked list in forward order, and for each function in the doubly-linked list;

determine a third virtual register set including any of the plurality of virtual registers that are live immediately following any call to the function,

trace a liveness for each of the plurality of virtual registers, and

construct an edge between pairs of virtual registers based on the liveness, the edge indicating that the pair of virtual registers can not be associated with the same physical register.