Patent
1995-08-31
1998-06-02
Voeltz, Emanuel Todd
G06F 945
Patent
active
057615144
ABSTRACT:
A method and apparatus for truncating runaway lifetimes of program variables calculates liveness for each variable based on upwardly exposed uses. Reaching definitions are then calculated for at least the program variables that have runaway lifetimes. The liveness information is compared to the reaching definition information to determine whether a variable that is live upon entry to a basic block has a definition that reaches the end of each predecessor block, or has a use within the basic block. If the reaching definition for a variable reaches the beginning of the block and if there is a predecessor block for which there is no reaching definition, the variable has a runaway lifetime. The variable also has a runaway lifetime if there is a use of the variable in a block without a reaching definition for the variable at the beginning of the block. The runaway lifetime is truncated by inserting an instruction such as a pseudo-definition of the variable into the instruction stream at an appropriate place. Once runaway lifetimes are truncated using this method, subsequent stages of the compiler may calculate liveness by performing a single dataflow analysis which calculates lifetimes based on upwardly exposed uses.
REFERENCES:
patent: 4571678 (1986-02-01), Chaitin et al.
patent: 4782444 (1988-11-01), Munshi et al.
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5261062 (1993-11-01), Sato
patent: 5339428 (1994-08-01), Burmeister et al.
patent: 5355494 (1994-10-01), Sistare et al.
patent: 5367684 (1994-11-01), Smith
patent: 5418958 (1995-05-01), Goebel
patent: 5530866 (1996-06-01), Koblenz et al.
patent: 5555417 (1996-09-01), Odnert et al.
Peter E. Bergner, Peter J. Dahl, and Matthew T. O'Keefe, Spill Code Minimization Techniques for Graph Coloring Register Allocators, Unversity of Minnesota Manuscript, Department of Electrical Engineering, 1995.
Preston Briggs, Register Allocation via Graph Coloring, PhD Thesis, Rice University, 1992.
Preston Briggs, Keith D. Cooper, 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 K. Chandra, John Cocke, Martin E. Hopkins and Peter W. Markstein, Register Allocation via Graph Coloring, Computer Languages, 6:47-57, 1981.
Aizikowitz Nava Arela
Bar-Haim Roy
Prosser Edward Curtis
Roediger Robert Ralph
Schmidt William Jon
Corcoran, III Peter J.
International Business Machines - Corporation
Martin Derek P.
Todd Voeltz Emanuel
LandOfFree
Register allocation method and apparatus for truncating runaway 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 method and apparatus for truncating runaway , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Register allocation method and apparatus for truncating runaway will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1472820