Editing Graph coloring (section)

=== Register allocation ===
{{Main|Register allocation}}

A [[compiler]] is a [[computer program]] that translates one [[computer language]] into another. To improve the execution time of the resulting code, one of the techniques of [[compiler optimization]] is [[register allocation]], where the most frequently used values of the compiled program are kept in the fast [[processor register]]s. Ideally, values are assigned to registers so that they can all reside in the registers when they are used.

The textbook approach to this problem is to model it as a graph coloring problem.{{sfnp|Chaitin|1982}} The compiler constructs an  ''interference graph'', where vertices are variables and an edge connects two vertices if they are needed at the same time. If the graph can be colored with ''k'' colors then any set of variables needed at the same time can be stored in at most ''k'' registers.