History

Please fill in your query. A complete syntax description you will find on the General Help page.
Optimistic chordal coloring: a coalescing heuristic for SSA form programs. (English)
Des. Autom. Embed. Syst. 13, No. 1-2, 115-137 (2009).
Summary: The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the $k$-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coalescing. Since copies can be folded during SSA construction, instances of the coalescing problem under SSA have fewer affinities than traditional methods. This paper presents Optimistic Chordal Coloring (OCC), a coalescing heuristic for chordal graphs. OCC was evaluated on interference graphs from embedded/multimedia benchmarks: in all cases, OCC found the optimal solution, and ran, on average, $2.30\times$ faster than Iterated Register Coalescing.