Register allocation by decomposing, re-connecting and coloring h

Details Register allocation by decomposing, re-connecting and coloring h Register allocation by decomposing, re-connecting and coloring h

1992-07-15

1995-05-23

Kriess, Kevin A.

Boots, shoes, and leggings

364DIG1, 364247, 3642474, 364260, 3642602, 364280, 3642804, 3642805, G06F 1500, G06F 944

Patent

active

054189586

ABSTRACT:
During code generation, a routine is first decomposed into regions. Then, starting from the highest plateau, i.e. the inner most control flow level, the interference graph of each region in a plateau is colored individually. Neighboring regions of the plateau are then combined by connecting the colored nodes of the interference graphs that are live at region boundaries. If connecting the interference graphs render the connected interference graph uncolorable, colored nodes that are live at region boundaries are connected by introducing register to register move or spilling the node. When all neighboring regions of a plateau are combined, the plateau collapses into a region of the lower level plateau. The process is repeated until all plateaus are collapsed and the regions of the base plateau are colored and combined together. Registers are then allocated to the colored nodes.

REFERENCES:
patent: 4435753 (1984-03-01), Rizzi
patent: 4571678 (1986-02-01), Chaitin
patent: 4782444 (1988-11-01), Munshi et al.
patent: 5261062 (1993-11-01), Sato
patent: 5339428 (1994-08-01), Burmeister et al.
ACM Transactions on Programming Languages and Systems; vol. 11, No. 1, Jan. 1989, New York, U.S., pp. 1-32, XP319429; Peter A. Steenkiste et al.: `A Simple Interprocedural Register Allocation Algorithm and Its Effectiveness for LISP`, *abstract* *p. 11, line 26-line 42* *p. 12, line 26-line 40*.
Proceedings of the 1992 International Conference on Computer Languages; 20 Apr. 1992, Oakland, Calif., U.S., pp. 262-271, XP325885; Angelika Zobel: `Program Structure as Basis for Parallelising Global Register Allocation`, *abstract* *p. 262, right col., line 12-p. 263, left col., line 12*.
David Callahan and Brian Koblenz, Register Allocation Via Hierarchical Graph Coloring, Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Toronto, Ontario, Canada, Jun. 26-28, 1991.
Fred Chow and John L. Hennessey, The Priority-Based Coloring Approach to Register Allocation, ACM Transactions on Programming Languages and Systems, vol. 12, No. 4, Oct. 1990, pp. 501-536.
Preston Briggs, Register Allocation Via Graph Coloring, Rice COMP TR92-183, Department of Computer Science, Rice University, P.O. Box 1892, Houston, Tex. 77251-1892.
Callahan, et al., "Register Allocation Via Hierarchical Graph Coloring", 1991.
Steenkiste, "Lisp On A Reduced-Instruction-Set Processor: Characterization and Optimization"; Ph.D. Thesis, Stamford University; 1989; Chapter 5.
Callahan, et al., "Register Allocation Via Tiling"; Tera Computer Co.; 1990.

Affiliated with

Also associated with

Rating

Register allocation by decomposing, re-connecting and coloring h does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Register allocation by decomposing, re-connecting and coloring h, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Register allocation by decomposing, re-connecting and coloring h will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2147908