La consommation en registres en présence de parallélisme d'instructions

It has become a truism that memory accesses play the major role of degrading program performances. Optimizing compilers must avoid requesting data from memory, if possible, by using the available registers of underlying hardware in the best ways.This thesis reconsiders the register pressure concept so that it gets higher priority than instruction scheduling, but with full respect to intrinsic fine grain parallelism. We propose to handle register pressure early in code optimization process, before instruction scheduling. Two main strategies are developed. In the first strategy, we handle data dependence graphs (DDG) so that we guarantee register constraints without increasing critical execution paths if possible. We introduce and study the concept of register saturation, which is the exact upper-bound of register need for all valid schedules independently of resource constraints. Its aim is to add some serial arcs to the original DDG such that the worst register need does not exceed the number of available registers. On the other hand, register sufficiency is the exact minimal register requirement. Its aim is to detect unavoidable spilling when it exceeds the number of available registers. After this first analysis pass, any instruction scheduler is free from register constraints and the final allocator would not require avoidable spilling. Our second strategy consists in directly applying an early register allocation while optimizing the performance loss. It is built directly into the input DDG, hence register constraints are fixed before instruction scheduling.This thesis addresses direct acyclic graphs, acyclic control flow graphs and innermost loops intended for software pipelining. Experimental results show that our heuristics are nearly optimal. This thesis proves that we can and must handle register constraints early in code optimization process while keeping freedom for a further instruction scheduler.Aujourd'hui, le fait que la mémoire constitue un goulot d'étranglement pour les performances des programmes est un truisme. Les compilateurs doivent donc optimiser les programmes afin d'éviter de recourir à la mémoire, et ceci en utilisant au mieux les registres disponibles dans le processeur à parallélisme d'instructions (ILP).Cette thèse réexamine le concept de la pression des registres en lui donnant une plus forte priorité par rapport à l'ordonnancement d'instructions, sans ôter à ce dernier ses possibilités d'extraction de parallélisme. Nous proposons de traiter le problème des registres avant la phase d'ordonnancement. Deux grandes stratégies sont étudiées en détail. La première consiste à analyser et manipuler un graphe de dépendance de données (GDD) pour garantir les contraintes de registres sans allonger son chemin critique (si possible). Nous introduisons la notion de saturation en registres qui est la borne exacte maximale du besoin en registres de tout ordonnancement valide, indépendamment des contraintes architecturales. Son but est d'ajouter des arcs au GDD pour que la saturation soit en dessous du nombre de registres disponibles. Réciproquement, la suffisance est le nombre minimal de registres dont il faut disposer pour produire au moins un ordonnancement valide pour le GDD. Si cette suffisance est au dessus du nombre effectif de registres, alors les accès à la mémoire sont inévitables.Notre deuxième stratégie construit une allocation de registres directement dans le GDD en optimisant la perte du parallélisme intrinsèque.Cette thèse considère des blocs de base, des graphes acycliques de flots de contrôles et des boucles internes destinées au pipeline logiciel. Nos expériences montrent que nos heuristiques sont presque optimales. L'étude prouve que nous pouvons et devons traiter les contraintes de registres avant la phase d'ordonnancement tout en garantissant une liberté pour l'extraction et l'exploitation de l'ILP