A system for local context spilling for graph colouring register allocators

Abstract From the Canadian patent

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 colouring techniques, attempting to assign colours (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 …