Previous Next |

Kempe [1879] invented the simplification algorithm that colors graphs by removing vertices of degree < *K*. Chaitin [1982] formulated register allocation as a graph-coloring problem - using Kempe's algorithm to color the graph - and performed copy propagation by (nonconservatively) coalescing nonin- terfering move-related nodes before coloring the graph. Briggs et al. [1994] improved the algorithm with the idea of optimistic spilling, and also avoided introducing spills by using the conservative coalescing heuristic before coloring the graph. George and Appel [1996] found that there are more opportunities for coalescing if conservative coalescing is done during simplification instead of beforehand, and developed the work-list algorithm presented in this chapter.

Ershov [1958] developed the algorithm for optimal register allocation on expression trees; Sethi and Ullman [1970] generalized this algorithm and showed how it should handle spills.

JaVa |
Previous Next |