System for local context spilling for graph coloring register al

Details System for local context spilling for graph coloring register al System for local context spilling for graph coloring register al

1998-05-15

2000-07-18

Hafiz, Tariq R.

Data processing: software development, installation, and managem

Software program development tool

Translation of code

717 7, G06F 9445, G06F 945

Patent

active

06090156&

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.

REFERENCES:
patent: 4571678 (1986-02-01), Chaitin
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 4782444 (1988-11-01), Munshi et al.
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5784066 (1998-07-01), Aizikowitz et al.
Eichenberger-Davidson, Register Allocation for Predicated Code, Proceedings of the 28th Annual International Symposium on Microarchitecture, IEEE, Nov. 1995.
Foster III-Grossman, An Empirical Investigation of the Haifa Register allocation Technique in the GNU C Compiler, Southeastcon '92, Proceedings, IEEE, Apr. 1992.
Bernstein et al., Spill Code Minimization Techniques for Optimizing Compilers, ACM, Jan. 1989.
Callahan-Koblenz, Register Allocation via Hierarchical Graph Coloring, ACM SIGPLAN 91, Jun. 1991.
Chen-Alewine-Fuchs-Hwu, Incremental Compiler Transformations For Multiple Instruction Retry, Software-Practice and Experience, V.24(12), 1179-1198, Dec. 1994.
Callahan-Koblenz, Register Allocation via Hierarchical Graph Coloring, Proceedings of the ACM SIGPLAN'91 Conference on Programming language Design and Implementation, Jun. 1991.
Norris-Pollock, An Experimental Study of Several Cooperative Register Allocation and Instruction Scheduling Strategies, Proceedings of MICRO-28, IEEE, Jan. 1995.

Affiliated with

Also associated with

Rating

System for local context spilling for graph coloring register al does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for local context spilling for graph coloring register al, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for local context spilling for graph coloring register al will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2032098