System for local context spilling for graph coloring register allocators
US6090156A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | May 15, 1998 |
| Grant date | Jul 18, 2000 |
| Priority date | — |
| Expiry date | May 15, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F8/441
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A register allocator for allocating machine registers during compilation of a computer program. The register allocator performs the steps of building an interference graph, reducing the graph using graph coloring techniques, attempting to assign colors (i.e. allocate machine registers to symbolic registers), and generating spill code. The spill code is generated by a local context spiller which processes a basic block on an instruction by instruction basis. The local context spiller attempts to allocate a machine register which is free in the basic block. If the basic block does not have any free machine registers, the local context spiller looks ahead to select a machine register for spilling. The register allocator improves the performance of a compiler by limiting the rebuilding of the interference graph and the number of the graph reduction operations.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.