Register allocation and code spilling using interference...

Details Register allocation and code spilling using interference... Register allocation and code spilling using interference...

2007-07-03

2007-07-03

Kendall, Chuck (Department: 2192)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S131000, C717S132000, C717S133000, C717S154000, C717S155000, C717S157000, C717S158000

Reexamination Certificate

active

10640549

ABSTRACT:
An improved method is provided for performing register allocation in a compiler. This method determines the allocation of a plurality R of registers of a processor for use during the execution of a software program. The register allocation process is treated as a graph-coloring problem, such that an interference graph is constructed for the software program, the graph is simplified, and an R-coloring the interference graph to the extent possible is attempted. Then, spill code is inserted in the software program each for each uncolored node of the graph, a new interference graph is constructed, and the process is repeated. During the simplification process, nodes with degree greater than or equal to R are removed from the graph in an order dictated by a spill cost metric. During the coloring process, these same nodes are reinserted in the graph in an order dictated by reapplying the spill cost metric.

REFERENCES:
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5774730 (1998-06-01), Aizikowitz et al.
patent: 6016466 (2000-01-01), Guinther et al.
patent: 6090156 (2000-07-01), MacLeod

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3757657