Decoupled (SSA-based) Register Allocators: From Theory to Practice, Coping with Just-In-Time Compilation and Embedded Processors Constraints

Quentin Colombet 1, *
* Auteur correspondant
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Ma thèse porte sur l'allocation de registres. Durant cette étape, le compilateur doit assigner les variables du code source, en nombre arbitrairement grand, aux registres physiques du processeur, en nombre limité k. Des travaux récents, notamment ceux des thèses de F. Bouchez et S. Hack, ont montré qu'il était possible de séparer de manière complètement découplée cette étape en deux phases : le vidage (spill) - stockage de variables en mémoire pour libérer des registres - suivi de l'assignation aux registres proprement dite. Ces travaux démontraient la faisabilité de ce découpage en s'appuyant sur un cadre théorique et certaines hypothèses simplificatrices. En particulier, il est suffisant de s'assurer qu'après le spill, le nombre de variables simultanément en vie est inférieur à k. Ma thèse fait suite à ces travaux en montrant comment appliquer ce type d'approche dans un cadre réaliste, en prenant en compte les contraintes liées à l'encodage des instructions, à l'ABI (application binary interface), aux bancs de registres avec aliasing. Différentes approches sont proposées qui per- mettent soit de s'affranchir des problèmes précités, soit de les prendre en compte directement dans le modèle théorique. Les hypothèses des modèles et les solutions proposées sont évaluées et validées par une étude expérimentale poussée dans le compilateur de STMicroelectronics. Enfin, l'ensemble de ces travaux a été réalisé avec, en ligne de mire, les contraintes de la compilation moderne, la compilation JIT (just-in-time), où rapidité et consommation mémoire du compilateur sont des facteurs déterminants. Nous nous sommes efforcés d'offrir des solutions satisfaisant ces critères ou améliorant les résultats attendus tant qu'un certain budget n'a pas été dépassé, exploitant en particulier la forme SSA (static single assignment) pour définir des algorithmes de type tree scan qui généralisent les approches de type linear scan, proposées pour le JIT.
Type de document :
Rapport
[University works] 2012, pp.224
Liste complète des métadonnées

https://hal.inria.fr/hal-00761572
Contributeur : Alain Darte <>
Soumis le : mercredi 5 décembre 2012 - 16:51:50
Dernière modification le : samedi 21 avril 2018 - 01:27:18

Identifiants

  • HAL Id : hal-00761572, version 1

Collections

Citation

Quentin Colombet. Decoupled (SSA-based) Register Allocators: From Theory to Practice, Coping with Just-In-Time Compilation and Embedded Processors Constraints. [University works] 2012, pp.224. 〈hal-00761572〉

Partager

Métriques

Consultations de la notice

135