OPTIMIZATION FOR REGISTER ALLOCATION USING GRAPH-COLORING ALGORITHM

Abstract

One of the most interested problems of the compiler optimization is register allocation and assignment. The problem is addressed is how to minimize traffic between the CPU registers which are usually fast to access. The graph coloring algorithm usually results in very effective allocations with a low cost in compilation speed. It views the fact that two objects must be registers at the same time as excluding them from being in the same register. It represents the objects by nodes in a graph and the exclusions (called interferences) by arcs between the corresponding nodes. The nodes may represent real registers also, and the arcs may represent exclusions such as that the base address in a memory access may not be register. Given the graph corresponding to an entire procedure, this method then attempts to color the nodes, with the number of colors equal to the number of available real registers, so that every node is assigned a color that is distinct from those of all the nodes adjacent to it.