On the complexity of register coalescing

Florent Bouchez (1) , Alain Darte (1) , Fabrice Rastello (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

L’augmentation croissante de la durée des accès à la mémoire et des développementsrécents liés à la forme SSA poussent à revisiter les problèmes de® spilling ¯ (placement des loads et stores) et de ® coalescing ¯ (suppression demoves) pour développer de nouvelles stratégies d’allocation de registres plusagressives. Ce rapport est consacré à la complexité des problèmes de coalescing.Nous distinguons plusieurs optimisations qui apparaissent dans les heuristiquesde coalescing : a) le coalescing agressif supprime autant de moves quepossible, quelle que soit la colorabilité du graphe d’interférences résultant ; b)le coalescing conservatif supprime autant de moves que possible tout en préservantla colorabilité du graphe ; c) le coalescing incrémental supprime un moveparticulier en conservant la colorabilité du graphe ; d) le coalescing optimistesupprime tous les moves (quand c’est possible), de façon agressive, et en réintroduitle plus petit nombre pour que le graphe redevienne colorable. Nousclassifions (presque) complètement ces problèmes en termes de complexité,discutant également de la structure du graphe d’interférence (quelconque, triangulé,k-colorable de façon gloutonne). Nous pensons qu’une telle étude estun pas nécessaire pour concevoir de nouvelles stratégies de coalescing.

Mots clés: (greedy)-k-colorable graph; Chordal graph; NP-completeness; Register allocation; Register coalescing; SSA form

Mots clés: Allocation de registres; Forme SSA; Graphe triangulé; NP-complétude; graphe (glouton)-k colorable

Domaines: Informatique [cs]

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⟩