Method and apparatus for using partner information to color node

Details Method and apparatus for using partner information to color node Method and apparatus for using partner information to color node

1995-11-22

1998-07-21

Nguyen, Phu K.

Computer graphics processing and selective visual display system

Computer graphics processing

Graph generating

G06F 1500

Patent

active

057840660

ABSTRACT:
A method and apparatus for coloring an interference graph eliminates register copy instructions in an instruction stream by taking into consideration the colors of a node's direct or transitive partners when choosing a color for a node. By assigning a color to a node that is also the color of a direct or transitive partner, register copy instructions between the two partners may be eliminated. If more than one of the partners at any given level are colored, one of the colors may be selected over the others using an appropriate heuristic, such as a scheme that weights the colors appropriately.

REFERENCES:
patent: 4571678 (1986-02-01), Chaitlin et al.
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5341466 (1994-08-01), Perlin et al.
Peter E. Bergner, Peter J. Dahl, and Matthew T. O'Keefe, Spill Code Minimization Techniques for Graph Coloring Register Allocators, University of Minnesota Manuscript, Department of Electrical Engineering, 1995.
Preston Briggs, Register Allocation via Graph Coloring, PhD Thesis, Rice University, 1992.
Preston Briggs, Keith D. Copper, and Linda Torczon, Coloring Register Pairs, ACM Letters on Programming Languages and Systems, ACM Press, vol. 1, No. 1, Mar. 1992, pp. 3-13.
David Callahan & Brian Koblenz, "Register Allocation via Hierarchical Graph Coloring", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices, vol. 26, No. 6, pp. 192-203 (Jun. 1991).
Fred C. Chow & John L. Hennessy, "The Priority-Based Coloring Approach to Register Allocation", ACM Transaction on Programming Languages and Systems, vol. 12, No. 4, pp. 501-536 (Oct. 1990).
David Bernstein, Dina Goldin, Martin Golumbic, Hugo Krawczyk, Yishay Mansour, Itai Nahshon and Ron Pinter, Spill Code Minimization Techniques for Optimizing Compilers, ACM SIGPLAN, Conference on Programming Languages Design and Implementation, 1989.
Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon, Coloring Heuristics for Register Allocation, ACM SIGPLAN Conference on Programming Languages Design and Implementation, 1989.
Fred C. Chow & John L. Hennessy, "Register Allocation by Priority-Based Coloring", Proceedings of the ACM Symposium on Compiler Construction, pp. 222-232 (Jun. 1984).
Auslander & Hopkins, An Overview of the PL.8 Compiler, ACM SIGPLAN Notices, vol. 17, No. 6, Jun. 1982.
Gregory J. Chaitin, "Register Allocation & Spilling via Graph Coloring", Proceedings of the ACM Symposium on Compiler Construction, pp. 98-105 (Jun. 1982).
Gregory J. Chaitin, Marc A. Auslander, Ashok E. Chandra, John Cocke, Martin E. Hopkins and Peter W. Markstein, Register Allocation via Coloring, Computer Languages, 6:47-57, 1981.

Affiliated with

Also associated with

Rating

Method and apparatus for using partner information to color node does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for using partner information to color node, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using partner information to color node will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1650806