HCL Technologies
Register Allocation, Graph Coloring Algorithm
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.