System for local context spilling for graph coloring register allocators

• US 6,090,156 A
• Filed: 05/15/1998
• Issued: 07/18/2000
• Est. Priority Date: 05/22/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: MacLeod, Andrew Wilfred
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Nguyen-Ba, Hoang-Vu Antony
• Application Number:
  US09/079,556
• Time in Patent Office: 795 Days
• Field of Search: 395/707, 395/709, 345/440
• US Class Current: 717/157
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A register allocator for allocating machine registers during compilation of a computer program. The register allocator performs the steps of building an interference graph, reducing the graph using graph coloring techniques, attempting to assign colors (i.e. allocate machine registers to symbolic registers), and generating spill code. The spill code is generated by a local context spiller which processes a basic block on an instruction by instruction basis. The local context spiller attempts to allocate a machine register which is free in the basic block. If the basic block does not have any free machine registers, the local context spiller looks ahead to select a machine register for spilling. The register allocator improves the performance of a compiler by limiting the rebuilding of the interference graph and the number of the graph reduction operations.

Claims

1. A register allocation procedure for a compiler for converting a high level source code program into a machine executable program, the compiler includes an optimizer for translating the high level source code into an intermediate language wherein storage requirements for the program are specified as a plurality of symbolic registers, said register allocation procedure comprising the steps of:

(a) generating an interference graph for said program;

(b) reducing said interference graph via application of graph reduction techniques and selecting symbolic registers for spilling;

(c) allocating machine registers to said program via graph colouring techniques without spilling; and

(d) after a single iteration of steps (a) through (c), applying local context spilling to allocate machine registers to said symbolic registers selected for spilling that were not allocated using said graph colouring techniques, wherein said local context spilling comprises determining one or more free machine registers in a section of said intermediate language program, and allocating said free machine registers to the symbolic registers in said program, and when it is determined that the section does not have a free machine register, selecting a machine register for spilling and generating spill code for instructing said program to spill said selected machine register.

2. The register allocation method as claimed in claim 1, wherein said local context spilling step includes a look-ahead operation for determining which machine register is to be selected for spilling in the section of the program.

3. A compiler for converting a high level source code program into a machine executable program, said compiler comprising:

a parser for translating said source code into an intermediate language program wherein storage requirements for said program are specified as a plurality of symbolic registers;

an optimizer for optimizing operation of said intermediate language program;

a register allocator for rewriting symbolic registers to machine registers in the intermediate language program;

a code generator for generating the machine executable program from said rewritten intermediate language program;

said register allocator having means for generating an interference graph for said intermediate language program, graph reduction means for reducing the number of symbolic registers in said interference graph and means for selecting symbolic registers for spilling, and graph colouring means for allocating machine registers to said symbolic registers without spilling; and

said register allocator further including a local context spiller for allocating a machine register to a symbolic register selected for spilling and not allocated by said graph colouring means after a single execution of generating means, reducing means and colouring means, said local context spiller comprising means for determining availability of a free machine register in a section of said program and means for allocating said free machine register to said symbolic register, and said local context spiller further including means for selecting a machine register for spilling when the section of the program does not have any free machine registers.

4. The compiler as claimed in claim 3, wherein said local context spiller includes look-ahead means for looking-ahead and assessing the optimal machine register for spilling.

5. In a compiler for converting a high level source code program into a machine executable program, the compiler including a parser for translating high level source code program into an intermediate language program wherein storage requirements for the program are specified as a number of symbolic registers, the improvement comprising a register allocator for rewriting symbolic registers to machine registers in the intermediate language program, said register allocator comprising:

means for generating an interference graph for said intermediate language program;

graph reduction means for reducing the number of symbolic registers in said interference graph and means for selecting symbolic registers for spilling;

graph colouring means for allocating machine registers to said symbolic registers without spilling; and

a local context spiller for allocating a machine register to a symbolic register selected for spilling and not allocated by said graph colouring means after a single iteration of generating means, reduction means and colouring means;

said local context spiller including means for determining availability of a free machine register in a section of said program and means for allocating said free machine register to said symbolic register, and said local context spiller further including means for selecting a machine register for spilling when the section of the program does not have any free machine registers.

6. A computer program product for use in a computer system to compile a high level source code program and generate a machine executable program, said computer program product comprising:

a recording medium;

means recorded on said medium for instructing said computer system to perform the steps of,

(a) translating said high level source code into an intermediate language program wherein storage requirements for said program are specified as a plurality of symbolic registers;

(b) optimizing operation of said intermediate language program;

(c) rewriting symbolic registers to machine registers in the intermediate language program;

(d) generating the machine executable program from said rewritten intermediate language program;

(e) wherein rewriting said symbolic registers to machine registers comprises the steps of,

generating an interference graph for said program,

reducing said interference graph via application of graph reduction techniques and selecting symbolic resisters for spilling,

allocating machine registers to said program via graph colouring techniques without spilling,

applying local context spilling to allocate said symbolic registers selected for spilling which were not allocated using said graph colouring techniques after a single iteration of generating interference graph, reducing said interference graph and allocating machine registers via graph colouring,

said local context spilling comprising determining one or more free machine registers in a section of said intermediate language program, and allocating said free machine registers to the symbolic registers in said program, and when it is determined that the section does not have a free machine register, selecting a machine register for spilling and generating spill code for instructing said program to spill said selected machine register.