Global Register Allocation (Register Allocation)

From Algorithm Wiki
Jump to navigation Jump to search


Register allocation is the process of mapping the unlimited number of symbolic registers assumed in the intermediate language into the limited real machine registers.

Global register allocation deals with the allocation of registers in code containing branches (

Related Problems

Related: Local Register Allocation


$n$: number of live ranges (the number of candidates to reside in registers)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Chaitin's Algorithm 1981 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time
Chow's Algorithm 1984 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time
Linear Scan, Poletto & Sarkar 1999 $O(n)$ $O(r)$ Exact Deterministic Time
Cooper and Dasgupta algorithm 1983 $O(n^{2})$ Exact Deterministic
Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm 1996 $O(n^{3})$ Depends on the choice of {0}-{1} ILP solver Exact Deterministic Time
Kong and Wilken Algorithm 1998 $O(n^{3})$ ? Probably also dependent on the ILP solver Exact Deterministic Time
Demand-Driven Register Allocation 1996 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time

Time Complexity Graph

Register Allocation - Global Register Allocation - Time.png