Global Register Allocation

Description

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).

Related Problems

Related: Local Register Allocation

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff

References/Citation

http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf