[BR09] Live-Range Unsplitting for Faster Optimal Coalescing

Conférence Internationale avec comité de lecture : LCTES'09 ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, January 2009, pp.70-79, Series ACM,

Auteurs: S. Blazy , B. Robillard

motcle:

Résumé: Register allocation is often a two-phase approach: spilling of registers to memory, followed by coalescing of registers. Extreme live-range splitting (i.e. live-range splitting after each statement) enables optimal solutions based on ILP, for both spilling and coalescing. However, while the solutions are easily found for spilling, for coalescing they are more elusive. This difficulty stems from the huge size of interference graphs resulting from live-range splitting. This paper focuses on optimal coalescing in the context of extreme live-range splitting. It presents some theoretical properties that give rise to an algorithm for reducing interference graphs, while preserving the optimality of coalescing. This reduction consists mainly in finding and removing useless splitting points. It is followed by a graph decomposition based on clique separators. Any coalescing technique can be applied after this decomposition. Our strategy for reducing and decomposing interference graphs has been tested on a standard benchmark, the optimal coalescing challenge. For this benchmark, the cutting-plane algorithm for optimal coalescing (the only optimal algorithm for coalescing) runs 300 times faster when combined with our strategy. Moreover, we provide all the optimal solutions of the optimal coalescing challenge, including the three instances that were previously unsolved.

BibTeX

@inproceedings {
	BR09,
	title	=	"{Live-Range Unsplitting for Faster Optimal Coalescing}",
	author	=	" S. Blazy and B. Robillard ",
	booktitle	=	"{LCTES'09 ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems}",
	year	=	2009,
	month	=	"January",
	series	=	"ACM",
	pages	=	"70-79",
}