On the Complexity of Register Coalescing
| Autor: | Fabrice Rastello, Alain Darte, Florent Bouchez |
|---|---|
| Přispěvatelé: | Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'informatique du parallélisme, Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Rok vydání: | 2007 |
| Předmět: |
Computational complexity theory
Computer science Graphe triangulé 02 engineering and technology Parallel computing graphe (glouton)-k colorable Chordal graph Register allocation 0202 electrical engineering electronic engineering information engineering Allocation de registres Quantitative Biology::Populations and Evolution SSA form [INFO]Computer Science [cs] Graph coloring (greedy)-k-colorable graph Greedy algorithm Static single assignment form Forme SSA 020207 software engineering NP-completeness NP-complétude Graph (abstract data type) 020201 artificial intelligence & image processing Register coalescing Hardware_CONTROLSTRUCTURESANDMICROPROGRAMMING Heuristics |
| Zdroj: | CGO [Research Report] LIP RR-2006-15, Laboratoire de l'informatique du parallélisme. 2006, 2+19p |
| DOI: | 10.1109/cgo.2007.26 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|