Local Register Allocation (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.

Local register allocation deals with the allocation of registers in straight-line code segments (http://www.cs.ucr.edu/~gupta/research/Publications/Comp/p370-gupta.pdf).

Related Problems

Related: Global 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
Cooper and Dasgupta algorithm	1983	$O(n^{2})$		Exact	Deterministic

References/Citation

http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf