Compiler and register allocation method

• US 7,174,546 B2
• Filed: 09/12/2001
• Issued: 02/06/2007
• Est. Priority Date: 09/12/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Koseki, Akira
• Primary Examiner(s): Chaki; Kakali
• Assistant Examiner(s): Kang; Insun
• Application Number:
  US09/950,904
• Publication Number:
  US 20020095668A1
• Time in Patent Office: 1,973 Days
• Field of Search: 717/155, 717/156, 717/153, 717/141
• US Class Current: 717/157
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A computer, computer compiler and method for reducing the number of interferences between variables during graph coloring while maintaining the possibility that the instructions will be executed in parallel. 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 directed acyclic graph 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 instructions; and a graph coloring unit 13 for allocating registers for the instruction based on the interference graph that is constructed.

Claims

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

a directed acyclic graph 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, 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; and

a graph identifier for allocating registers for said instruction using 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 computer-readable medium embodying a computer-executable 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.

3. The computer-readable medium embodying a computer-executable 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.

4. The computer-readable medium embodying a computer-executable 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.

5. The computer-readable medium embodying a computer-executable 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.

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

a directed acyclic graph 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, 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; and

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

7. The computer according to claim 6, 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.

8. 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 directed acyclic graph DAG for each of said instructions based on said program;

employing as a reference the longest non-parallel instruction queue in said DAG, and constructing an interference graph that 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, wherein said constructing 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; and

allocating registers for said instructions using said obtained interference graph.

9. The register allocation method according to claim 8, wherein said step of constructing and analyzing comprises 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.

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

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 interference between variables used for said instructions, based on said obtained execution start time for said instructions.

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

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.

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

13. A program transmission apparatus comprising:

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

a process for constructing and analyzing a directed acyclic graph DAG for each of 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 that 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, wherein said interference graph constructing 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, and

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

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