Live-Range Unsplitting for Faster Optimal Coalescing (extended version)

National audienceRegister allocation is often a two-phase approach: spilling of registers tomemory, followed by coalescing of registers. Extreme live-range splitting (\ielive-range splitting after each statement) enables optimal solutions based onILP, for both spilling and coalescing. However, while the solutions are easily found for spilling, for coalescing they are more elusive. This difficulty stemsfrom the huge size of interference graphs resulting from live-range splitting.This report focuses on optimal coalescing in the context of extreme live-rangesplitting. We present some theoretical properties that give rise to analgorithm for reducing interference graphs, while preserving optimality. Thisreduction consists mainly in finding and removing useless splitting points. Itis followed by a graph decomposition based on clique separators. The last optimizationconsists in two preprocessing rules. Any coalescing technique can be appliedafter these optimizations.Our optimizations have been tested on a standard benchmark, the optimal coalescingchallenge. For this benchmark, the cutting-plane algorithm for optimalcoalescing (the only optimal algorithm for coalescing) runs 300 times fasterwhen combined with our optimizations. Moreover, we provide all the solutions of theoptimal coalescing challenge, including the 3 instances that were previously unsolved