Register allocation using an improved register candidate usage m

Details Register allocation using an improved register candidate usage m Register allocation using an improved register candidate usage m

1992-11-30

1994-11-22

Eng, David Y.

Boots, shoes, and leggings

3642805, G06F 945

Patent

active

053676840

ABSTRACT:
An improved register allocator is provided to the code generator of a compiler. The improved register allocator allocates registers using an improved register candidate usage matrix. The improved register candidate usage matrix comprises row entries, one for each register candidate. Each row entry comprises usage bits indicating at least whether its register candidate is live at the entries, in the bodies, and at the exits of the various basic blocks. The improved register allocator allocates registers by block, deriving interference information from the improved usage matrix. It then merges the register allocation introducing spill code at points where register candidates are split. As a result, a register can be allocated to two register candidates that are live in the same basic block as long as they are not both live at some point in the basic block, and at the same time, a register candidate can be spilled in one basic block and allocated a register in another basic block.

REFERENCES:
patent: 4571678 (1986-02-01), Chaitin
patent: 5249295 (1993-09-01), Briggs
F. C. Chow & J. L. Hennessy, The Priority-Based Coloring Approach to Register Allocation, ACM Transaction on Programming Languages & Systems, vol. 12, No. 4, Oct. 1990, (ACM 0164-0925/1000-0501) pp. 501-536.
D. Callahan & B. Koblenz, Register Allocation via Hierarchical Graph Coloring, ACM SIGPLAN 1991 Conference on Programming Language Design & Implementation (ACM 0-89791-428-7/91/0005-0192), pp. 192-203.
P. Briggs, Register Allocation via Graph Coloring, A. Ph.D. Thesis, Rice University, Houston, Tex., Apr. 1992.

Affiliated with

Also associated with

Rating

Register allocation using an improved register candidate usage m 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 using an improved register candidate usage m, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Register allocation using an improved register candidate usage m will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1998159