Etude des problèmes de spilling et coalescing liés à l'allocation de registres en tant que deux phases distinctes

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).The goal of register allocation is to assign the variables of a program to the registers or to spill them to memory whenever there are no register left. Minimizing the spilling is a difficult problem, tightly bounded with the colorability of the program. The SSA form simplifies the coloring by splitting variables : we discovered that it makes the interference graph chordal. Our first goal was to better understand from where the complexity of register allocation does come, and why SSA seems to simplify the problem, by revisiting to the original proof of Chaitin (1981). The difficulty comes from the presence of (critical) edges and the possibility to perform permutations of colors or not. We studied the spill problem under SSA and several versions of the coalescing problem. We used it to design new heuristics to better solve the coalescing problem, so that an aggressive splitting can be used beforehand. This led us to promote a better register allocation scheme : First, spilling to reduce the register pressure to the number of registers, possibly by splitting a lot; Then color the variables and perform coalescing to remove most of the added copies. This scheme is expected to perform well in an aggressive compiler. However, the high number of splits and the increased compilation time required to perform the coalescing is prohibitive for just-in-time (JIT) compilation. So, we devised a heuristic, called "permutation motion," that is intended to be used with SSA-based splitting in place of our more aggressive coalescing in a JIT context.LYON-ENS Sciences (693872304) / SudocSudocFranceF