Compiler and register allocation method

• US 20020095668A1
• Filed: 09/12/2001
• Published: 07/18/2002
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Koseki, Akira
• Granted Patent: US 7,174,546 B2
• Time in Patent Office: Days
• US Class Current: 717/157
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

The number of interferences between variables during graph coloring is reduced, while maintaining the possibility that the instructions will be executed in parallel, so that an efficient compiler can be provided. A compiler, which converts into a machine language the source code of a program written in a programming language and optimizes the program, includes: a DAG analysis unit 11 for constructing and analyzing a DAG for an instruction in a program to be processed; an interference graph construction unit 12 for employing the analysis results to construct an interference graph representing the probability that an interference will occur between variables used by the instruction; and a graph coloring unit 13 for allocating registers for the instruction based on the interference graph that is constructed, wherein, when the overall time for executing the program is extended unless predetermined multiple instructions are executed in parallel, the interference graph construction unit 12 assumes that an interference has occurred among variables used by the multiple instructions, and constructs the interference graph.

Claims

1. A compiler, which converts into a machine language the source code of a program written in a programming language and optimizes said program, comprising:

a DAG analysis unit for constructing and analyzing a DAG for an instruction in a program to be processed;

an interference graph construction unit for employing the analysis results obtained by said DAG analysis unit to construct an interference graph representing the probability that an interference will occur between variables used by said instruction; and

a graph identifier for allocating registers for said instruction based on said interference graph that is constructed by said interference graph construction unit,

wherein, when the overall time for executing said program is extended unless predetermined multiple instructions are executed in parallel, said interference graph construction unit assumes that an interference has occurred among variables used by said multiple instructions, and constructs said interference graph.

2. The compiler according to claim 1, wherein said interference graph construction unit determines a phase arrangement order for nodes of said DAG, so that said execution interval for said program is minimized, and when the intervals are overlapped where the variables among said instructions in said phase arrangement order are present, said interference between said variables is reflected in said interference graph.

3. The compiler according to claim 1, wherein, when multiple instructions in said program that may be executed in parallel are not executed in parallel, and when the overall execution time for said program is still not affected, said interference graph construction unit assumes that said variables defined by said multiple instructions do not interfere with each other, and said effect is reflected in said interference graph.

4. The compiler according to claim 1, wherein said DAG analysis unit of said compiler searches for instructions that are nodes of said DAG in accordance with the depth priority order, and uses the search results to generate a reverse post order;

and wherein said interference graph construction unit extracts instructions based on said reverse post order obtained by said DAG analysis unit, and determines whether interferences occur between variables used for said extracted instructions and other variables, while the determination results are reflected in said interference graph, so that said graph of said interferences can be constructed, step by step.

5. The compiler according to claim 1, wherein said DAG analysis unit of said compiler calculates, for said instructions that serve as the nodes of said DAG, both the degree of freedom permitted for changing an execution start time and the earliest execution start time;

and wherein, based on said degree of freedom and said earliest execution start times for said instructions obtained by said DAG analysis unit, said interference graph construction unit determines the execution start time for each of said instructions, employs said obtained execution start times for said instructions to determine whether interferences occur between variables used by said instructions, and reflects said determination results in said interference graph to construct said interference graph.

6. The compiler according to claim 1, wherein said graph identification unit allocates the same register to variables defined on the same path in said DAG that is constructed by said DAG analysis unit.

7. A computer that includes a compiler, for compiling source code for an input program, comprising:

a DAG analysis unit, for constructing and analyzing a DAG for an instruction extracted from said program;

an interference graph construction unit, for employing the analysis results obtained by said DAG analysis unit to construct, with the condition that the overall execution time of said program will not be extended, an interference graph that is required to ensure the parallel execution of said program and that represents interferences between variables used by instructions in said program; and

a register allocation unit for allocating registers to said instruction based on said interference graph that is prepared by said interference graph construction unit.

8. The computer according to claim 7, further comprising:

output means, for writing to said interference graph the register allocation results obtained by said register allocation unit, and for outputting said interference graph.

9. A register allocation method, which for the performance of optimization to improve programming efficiency employs graph coloring to allocate registers to instructions in a program, comprising the steps of:

constructing and analyzing a DAG for said instructions based on said program;

employing as a reference the longest non-parallel instruction queue in said DAG, and constructing an interference graph assumes that an interference has occurred among variables used by said multiple instructions, based on the DAG analysis results, when said instruction queue is extended, unless predetermined multiple instructions are executed in parallel; and

allocating registers for said instructions based on said obtained interference graph.

10. The register allocation method according to claim 9, wherein said step of constructing and analyzing said DAG includes the steps of:

searching for instructions, in accordance with a depth priority order, that are nodes of said DAG; and

generating a reverse post order for the search results;

and wherein said step of constructing said interference graph includes the steps of;

extracting an instruction from said DAG in said obtained reverse post order, and determining whether an interference exists between a variable used by said extracted instruction and another variable; and

constructing said interference graph by reflecting, in said interference graph, said determined interference between said variables.

11. The register allocation method according to claim 10, wherein said step of constructing and analyzing said DAG includes the step of:

calculating, for each of said instructions that serve as the nodes of said DAG, the degree of freedom permitted for changing an execution start time, and the earliest execution start time; and

wherein said step of constructing said interference graph includes the step of;

employing said degree of freedom and said earliest execution start time to determine an execution start time for each of said instructions that are extracted from said DAG in said reverse post order; and

determining said interference occur between variables used for said instructions, based on said obtained execution start time for said instructions.

12. The register allocation method according to claim 10, wherein said step of determining said execution start time for each instruction includes the step of:

employing said degree of freedom and said earliest execution start time for said instruction to determine, when said execution start time for said instruction is delayed within a range wherein the overall program execution time is not extended and when the number of interferences between a function used for said instruction and another function is reduced, the execution start time for said instruction, the time whereat the number of interferences is minimized.

13. The register allocation method according to claim 9, wherein at said step of performing register allocation, the same register is allocated to variables defined on the same path in said DAG.

14. A storage medium on which input means of a computer stores a computer-readable program, which permits said computer to perform:

a process for constructing and analyzing a DAG for said instructions based on said program;

a process for employing as a reference the longest non-parallel instruction queue in said DAG, and constructing an interference graph assumes that an interference has occurred among variables used by said multiple instructions, based on the DAG analysis results, when said instruction queue is extended, unless predetermined multiple instructions are executed in parallel; and

a process for allocating registers for said instructions based on said obtained interference graph.

15. A program transmission apparatus comprising:

storage means for storing a program for permitting a computer to perform

a process for constructing and analyzing a DAG for said instructions based on said program,

a process for employing as a reference the longest non-parallel instruction queue in said DAG, and constructing an interference graph assumes that an interference has occurred among variables used by said multiple instructions, based on the DAG analysis results, when said instruction queue is extended, unless predetermined multiple instructions are executed in parallel, and

a process for allocating registers for said instructions based on said obtained interference graph; and

transmission means for reading said program from said storage means and transmitting said program.