Page "Register allocation" Paragraph 3

Through liveness analysis, compilers can determine which sets of variables are live at the same time, as well as variables which are involved in instructions.

Using this information, the compiler can construct a graph such that every vertex represents a unique variable in the program.

Interference edges connect pairs of vertices which are live at the same time, and preference edges connect pairs of vertices which are involved in move instructions.

Register allocation can then be reduced to the problem of K-coloring the resulting graph, where K is the number of registers available on the target architecture.

No two vertices sharing an interference edge may be assigned the same color, and vertices sharing a preference edge should be assigned the same color if possible.

Some of the vertices may be precolored to begin with, representing variables which must be kept in certain registers due to calling conventions or communication between modules.

As graph coloring in general is NP-complete, so is register allocation.

However, good algorithms exist which balance performance with quality of compiled code.