Register Allocation, Graph Coloring Algorithm

Register Allocation is one of the most important problems in compiler optimization. It is also one of the most studied problems in compiler theory, and a vast number of different algorithms exist to solve it. Register Allocation can happen over a basic block (local register allocation), over a whole function/procedure (global register allocation), or across function boundaries traversed via call-graph (inter-procedural register allocation). The objective of this technical paper is to give an overview of the Graph Coloring approach, and how it can be applied to perform Local Register Allocation.