Skip to Main content Skip to Navigation

On the complexity of register coalescing

Abstract : Due to the increasing latencies of memory accesses and recent developmentson the SSA form, it has become important to revisit the spilling (load/storeinsertion) and register coalescing (removal of move instructions) problems inorder to develop more aggressive register allocation strategies. This report isdevoted to the complexity of register coalescing. We distinguish several optimizationsthat occur in most coalescing heuristics: a) aggressive coalescingremoves as many moves as possible, regardless of the colorability of the resultinginterference graph; b) conservative coalescing removes as many movesas possible while keeping the colorability of the graph; c) incremental conservativecoalescing removes one particular move while keeping the colorabilityof the graph; d) optimistic coalescing coalesces all moves (when possible),aggressively, and gives up about as few moves as possible (de-coalescing) sothat the graph becomes colorable. We (almost) completely classify the NPcompletenessof these problems, discussing also on the structure of the interferencegraph (arbitrary, chordal, or k-colorable in a greedy fashion). We believethat such a study is a necessary step for designing new coalescing strategies.
Document type :
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:00:15 AM
Last modification on : Wednesday, November 20, 2019 - 2:52:30 AM


Files produced by the author(s)


  • HAL Id : hal-02102282, version 1



Florent Bouchez, Alain Darte, Fabrice Rastello. On the complexity of register coalescing. [Research Report] LIP RR-2006-15, Laboratoire de l'informatique du parallélisme. 2006, 2+19p. ⟨hal-02102282⟩



Record views


Files downloads