A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases
Florent Bouchez · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
Le but de l'allocation de registres est d'assigner les variables d'un programme aux registres ou de les spiller en mémoire s'il n'y a plus de registre disponible. Minimiser le spilling est un problème est difficile étroitement lié à la colorabilité du programme. La forme SSA facilite le coloriage en coupant les variables : nous avons découvert que le graphe d'interférence devient alors cordal. Nous avons d'abord cherché à comprendre d'où venait la complexité de l'allocation de registres, et pourquoi la forme SSA semblait simplifier le problème, en revisitant la preuve de NP-complétude de Chaitin (1981). La difficulté vient de la présence d'arcs critiques et de la possibilité d'effectuer des permutations de couleurs ou non. Nous avons alors étudié le problème du spill sous SSA et différentes versions du problème de coalescing. Nous nous en sommes servis de ces résultats pour élaborer de nouvelles heuristiques plus efficaces pour le problème du coalescing et par conséquent un meilleur schéma pour l'allocation de registres. Notre coalescing amélioré permet de séparer proprement l'allocation de registres en deux phases indépendantes : premièrement, spiller pour réduire la pression registre ; deuxièmement, colorier les variables et appliquer le coalescing pour supprimer le plus de copies possible. Notre algorithme étant coûteux, nous avons donc créé une heuristique appelée déplacement de permutation , adapté à la compilation just-in-time (JIT).