Global Register Allocation (Register Allocation)
Jump to navigation
Jump to search
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