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 :
Reports
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102282
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:00:15 AM
Last modification on : Friday, April 19, 2019 - 1:38:15 AM

File

RR2006-15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102282, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

16

Files downloads

28