Global Register Allocation

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 (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf).

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 6 of 6 algorithms


Linear Scan, Poletto & Sarkar	1999	$O(n)$	$O(r)$
Kong and Wilken Algorithm	1998	$O(n^3)$	Probably dependent on the choice of ILP solver
Optimal Register Allocation (ORA), Goodwin & Wilken Algorithm	1996	$O(n^3)$	Depends on the choice of 0-1 ILP solver
Demand-Driven Register Allocation	1996	$O(n^2)$	$O(n^2)$
Chow's Algorithm	1984	$O(n^2)$	$O(n^2)$
Chaitin's Algorithm	1981	$O(n^2)$	$O(n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms