Majeure 2
Langages et Compilation
Cours 7


Durée de vie
Allocation de registres
Allocation mémoire

jean-jacques.levy@inria.fr

16 mars 1998

Les supports de cours sont en

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/
http://http.cs.berkeley.edu/~aiken/cs164temp/
http://www.cs.princeton.edu/~appel/modern/ml/
Livres:

Introduction

Rappel sur les cours précédents

1.
CTigre (mini Pascal avec données dynamiques)
(a)
Lexeur et table des symboles
(b)
Analyseur syntaxique
2.
AST de CTigre
(a)
Résolution des noms
(b)
Allocation des variables
3.
IC
(a)
Séparation des instructions et des expressions
(b)
Élimination des branchements inutiles
4.
IC canonisé et linéarisé
(a)
Gestion de la pile des blocs d'activation
(b)
Protocole d'entrée et de sortie des procédures
(c)
Sélection des instructions

5.
Code 3 adresses (pico-Risc)

Aujourd'hui

1.
Code 3 adresses (pico-Risc)
(a)
Allocation des registres
2.
Code R2000
(a)
Gestion de la mémoire dynamique

Durée de vie des variables

Pour pouvoir utiliser un même registre pour y ranger les valeurs de deux variables différentes, il faut analyser la durée de vie des variables. Exemple: 

1      x := 0
2  l1: y := x+1
3      s := s + y
4      x := 2 * y
5      if x < N then goto l1
6      return s

x vit de la fin de 1 au début de 2, et de la fin de 4 à l'entrée de 2,
y vit de la sortie de 2 à l'entrée dans 4,
s vit pendant tout le programme.

Quel est le sens de la vie d'une variable?

Définition de la durée de vie des variables

Une variable est vivante entre sa définition et son utilisation.

Autrement dit, en considérant le graphe de contrôle d'un programme (dont les n\oe uds sont les instructions), une variable est vivante sur un arc, ssi cet arc est sur le chemin entre un n\oe ud qui la définit et un n\oe ud qui l'utilise.

Les ensembles $\mathop{\mbox{in}}(n)$ et $\mathop{\mbox{out}}(n)$ des variables vivantes à l'entrée et à la sortie d'un n\oe ud n sont définis récursivement par:

$\mathop{\mbox{in}}(n) = \mathop{\mbox{use}}(n) \cup (\mathop{\mbox{out}}(n) - \mathop{\mbox{def}}(n))$
$\mathop{\mbox{out}}(n) = \cup \{\mathop{\mbox{in}}(s) \mid s \in \mathop{\mbox{succ}}(n) \}$

Calcul de la durée de vie des variables

Il s'agit d'une définition arrière (backward analysis). Pour calculer ces ensembles, on itère la définition à partir des ensembles vides jusqu'à trouver un état stationnaire. (On applique un théorème de point fixe de Tarsky; on peut aussi le justifier par la théorie des domaines de Scott et des points fixes; c'est aussi la base de la théorie de l'interprétation abstraite).

Dans notre exemple, voici les itérations: 

  def use in out  in   out   in    out   in    out   in 
1  x                   x           x,s   s     x,s   s  
2  y  x           x    s,y   x,s   s,y   x,s   s,y   x,s
3  s  s,y         s,y  y     s,y   y     s,y   y,s   s,y
4  x  y           y    x     y     s,x   y,s   x,s   y,s
5     x           x    s,x   s,x   x,s   x,s   x,s   x,s
6     s           s          s           s           s

Graphe d'interférence

C'est un graphe non dirigé dont les noeuds sont les variables et les arcs relient les variables vivantes simultanément. Dans l'exemple précédent, ce graphe est


\begin{figure} \expandafter\ifx\csname graph\endcsname\relax \csname newbox\endc... ...t 0pt}\kern 0.824in }}{\center\mbox{}{\box\graph}\mbox{}\endcenter}\end{figure}

Intuitivement, deux variables qui interfèrent ne peuvent être allouées au même endroit.

Durée de vie des variables et affectations simples 

1    x := 5
2    y := x
3    z := x + 2
4    y := 3

En fait, x et y peuvent être alloués au même endroit. Dans ce cas, on ne met pas d'interférence entre les deux qui contiennent la même valeur. Mais cet arc sera rajouté plus tard, si 

1    x := 5
2    y := x
3    y := 3
4    z := x + 2

Allocation de registres

On a supposé un nombre infini de registres dans le code 3 adresses, mais dans la réalité, on n'a que k registres (k=16, k=32, etc). Comment donc allouer les variables dans cet ensemble fini de ressources? En 1980, Chaitin fait une percée en réduisant cette question à un problème de coloriage de graphes.

En effet, il s'agit de colorier avec k couleurs les noeuds du graphe d'interférence avec la seule règle: ne pas mettre la même couleur à deux noeuds reliés par un arc.

Exemple 1 - cf le livre d'Appel






















.

Exemple 2 - cf le livre d'Appel






















.

Heuristique simple pour le coloriage

On choisit un noeud n qui n'a pas plus que k-1 voisins. On l'empile en l'enlevant du graphe. On colorie le graphe restant. Puis on donne à n une couleur différente de celle de ses k-1 voisins, ce qui est possible puisqu'on dispose de k couleurs.

Cette procédure est récursive. On peut remarquer qu'un noeud avec plus k voisins peut se retrouver plus tard avec moins que k-1 voisins. Mais il se peut qu'on arrive à une situation où il n'y a plus que des noeuds avec plus de k voisins.

On empile un tel noeud marqué spill (débordement) en l'enlevant du graphe, et on continue pour explorer tous les possibles spill. Il se peut qu'au retour on sache colorier ce noeud si deux voisins ont même couleur.

Heuristique simple pour le coloriage - bis

Si on n'arrive pas à colorier les noeuds spill, on les alloue dans la pile, en changeant le programme pour mettre les instructions d'accès à la pile.

Et on relance la procédure de coloriage. En principe, ca converge alors.

Elimination des affectations inutiles

Deux variables x et y qui n'interfèrent pas mais qui sont reliées par x:= y peuvent être allouées au même endroit. Pour éliminer cette instruction inutile, on peut confondre les 2 noeuds dans le graphe d'interférence, mais alors il y a plus de contraintes à ce noeud, ce qui n'est pas grave si l'ensemble de ses voisins n'a lui-même pas plus que k voisins de degrés plus grands que k.

On peut mélanger cette stratégie au coloriage en traitant d'abord les noeuds non reliés par un move élémentaire. Puis en essayant de confondre les autres.

Noeuds précolorés et procédures

Certaines variables sont pré-colorées: fp, sp, rv. Attention qu'il n'y en ait pas trop, sinon on risque de ne pas savoir colorier le graphe.

Certaines variables doivent rester vivantes pendant un appel de fonctions. D'habitude, on les sauve dans la pile à l'entrée de la procédure et on les restitue à la sortie. Ce qui peut être obtenu automatiquement par l'allocateur de registres en déclarant que la procédure redéfinit toutes les variables à sauver de l'appelant.

Allocation des registres dans les expressions

Si on n'a que des expressions (et leur AST en arbre), une technique simple d'allocation est due à Ershov.

Pour évaluer $e \otimes e'$, si on évalue e avec n registres et e' avec n' registres, on évalue e+e' en $\max(m, 1+n)$ ou $\max(1+m,n)$ registres selon qu'on calcule e ou e' d'abord.

On a donc intérêt à évaluer d'abord l'expression qui demande le plus de registres.

Allocation des données dynamiques

Les variables déclarées par des $\mathop{\mathtt{let}}$ ou arguments de fonctions ont une durée de vie qui n'excède pas celle du bloc où elles sont définies. On peut donc les allouer dans la pile.

D'autres peuvent être crées dynamiquement à tout moment (enregistrements et tableaux en CTigre, new en Pascal ou Java, malloc en C), et on peut continuer à les référencer en dehors du bloc où elles sont apparues. On les alloue donc dans le tas ( heap).

A quel moment peut-on les détruire?

Glaneur de cellules - garbage collector

On peut laisser la déallocation des données dynamiques à la charge du programmeur (dispose en Pascal ou free en C).

Mieux et plus moderne: le système d'exécution du langage le fait automatiquement (Lisp, ML, Mesa, Modula-3, Java).

Il y a un garbage collector ou glaneur de cellule, GC pour simplifier, qui fait la déallocation implicite.

Tous les langages modernes ont un GC.

Mark and Sweep

Le GC est souvent appelé quand il n'y a plus de place dans le tas. Il existe alors un ensemble de racines dans le programme en cours d'exécution, ie toutes les variables de la pile qui sont des références vers le tas.

Dans la méthode Mark and Sweep, on marque tous les noeuds accessibles à partir de la racine par une exploration en profondeur d'abord. Puis on scanne tout le tas, en rangeant les noeuds non marqués dans une liste des cellules libres, free-list.

Pour marquer, on peut utiliser un vecteur de bits. Pour l'exploration, si on n'a pas de place pour mettre dans la pile, on retourne les pointeurs pendant l'exploration.

Stop and copy

Mark and Sweep ne compactifie pas la mémoire utilisée. Avec Stop and Copy, on coupe la mémoire en 2 parties. Et on alloue dans une des deux moitiés. Quand cette moitié from-space est pleine, en partant des racines, on recopie les cellules utilisées dans l'autre moitié to-space. Pour faire la copie, on laisse un renvoi dans from-space à chaque cellule recopiée vers to-space.

Il y a bien d'autres méthodes: incrémentales, concurrentes, etc. Depuis 5-10 ans, on ajoute des générations aux GC traitées différemment, car souvent il n'y a que 2 types de données dynamiques: les très éphémères et les permanentes.

CAML a deux générations et le GC majeur est en Mark en Sweep.

Ce qu'on n'a pas traité

Types (statiques, dynamiques)
Modules
Données persistantes
Les 50 méthodes d'optimisation:
propagation des constantes
constant folding
peephole optimisation
dépliage des boucles
ordonnancement des instructions
analyse de localité et caches
élimination du code inaccessible,
parallélisme, etc

Comment simplifier le projet

Ne pas faire de définitions de fonctions imbriquées (comme en C). Plus besoin du lien statique des blocs, 2 espaces de variables: globales et locales.

Générer directement le code 3 adresses sans passer par IC. Alors on n'optimise pas les branchements et on crée des étiquettes au fur et à mesure qu'on compile le code. Le choix des instructions n'est pas non plus optimisés.

Allouer les registres de manière triviale, ie dans l'ordre de leur apparition, en mettant en pile dès qu'il y a débordement ( spill).

C'est ce qu'y est fait dans le livre SPMlt;<le Langage CamlSPMgt;>, Weis-Leroy 93.

Comment améliorer le projet

Tracer les erreurs de syntaxe, en gardant le numéro de caractère dans les lexèmes, pour pouvoir localiser les messages d'erreur du compilateur.

Mettre un GC.

Faire les objets (cf cours 8)

Faire l'allocation de registres qui supprime les affectations inutiles.

Générer de l'assembleur MIPS et l'exécuter soit sur un IRIS, decstation (non alpha station), où sur le simulateur Spim.

Conclusions sur langages et compilation

Un langage s'impose parce qu'il comble un vide. (Aiken)

Un mauvais langage peut s'imposer. Fortran a été le langage de l'analyse numérique, remplacé par C++. Java est celui de la programmation du Web. Les deux derniers ont été crées pour faire autre chose.

Beaucoup de confusion dans la terminologie des langages de programmation. Objets veut souvent dire modulaire ou abstraction, mais il existe aussi d'autres mécanismes pour y arriver: modules, fonctions.

Les méthodes d'analyse statique peuvent aussi servir à la certification du logiciel, au delà de l'optimisation. De manière générale, peu a encore été fait comme aides à la mise au point, souvent arrétée par des problèmes d'efficacité.

Encore un bel avenir pour les langages spécialisés: réactif, agents, circuits.

2 exemples de DEA: DEA Algorithmique

1. Algorithmique et combinatoire des mots, [J. Berstel]
2. Géométrie computationnelle, [J.-D. Boissonnat]
3. Introduction au calcul parallèle et distribué, [M. Morvan]
4. Algorithmes probabilistes, [J.-M. Steyaert]
*. Pratique du calcul formel.
Filières, responsables et cours

1. Analyse d'algorithmes [J.-M. Steyaert]:
2. Automates et mots [J.-E. Pin]:
3. Calcul formel [D. Lazard]:
4. Combinatoire [R. Cori]:
5. Complexité, codage et cryptographie [J. Stern]:
6. Géométrie, images et robotique [O. Faugeras]:
7. Parallélisme et concurrence [A. Petit]:
*. Conception de circuits, [P. Bertin, J. Vuillemin].

http://www.polytechnique.fr/Ens/prog/3cycle/DEAP/algo.html
Autre exemple 1997-98: DEA Sémantique, Preuves et Programmation

1. Les termes en logique du premier ordre, [J.P. Jouannaud]
2. Lambda calcul, [T. Hardin]
3. Preuves constructives, [G. Dowek]
4. Sémantique dénotationnelle, [R. Di Cosmo]
5. Typage et programmation, [M. Mauny - D. Rémy - X. Leroy]


Filières, responsables et cours

1. Langages, [G. Cousineau]
Langages distribués, [C. Queinnec];
Sous-typage et langages à objets, [G. Castagna - F. Rouaix - D. Rémy]
Compilation des langages fonctionnels et impératifs, [X. Leroy]
Programmation logique avec contraintes et systèmes concurrents, [F. Fages - L.Fribourg]

2. Modèles Sémantiques, [P.-L. Curien]
Types, catégories et domaines, [P.-L. Curien-G. Longo]
Logique linéaire, [R. Di Cosmo]
Concurrence et Communication, [G. Gonthier - J.-J. Lévy]
Modèles algébriques des processus et méthodes de vérification, [ Ph. Schnoebelen]

3. Preuves et spécifications, [J.-P. Jouannaud]
Calcul des constructions inductives, [C. Paulin - B. Werner]
La méthode B, [V. Donzeau-Gouge, M. Simonot]
Preuve par des techniques d'automates, [H. Comon]
Réécriture et preuves, [J.-P. Jouannaud - C. Marche - M. Rusinowitch]

4. Sémantique et Interprétation abstraite, [R. Cousot]
Fondements de l'interprétation abstraite, [P. Cousot]
Interprétation abstraite: applications, [A. Deutsch - P. Granger - R. Cridlig]
Langages objets, contraintes et typage, [F. Bourdoncle - B. Monsuez]
Parallélisme : sémantique et preuve, [R. Cousot - E. Goubault - I. Mackie]

http://www.ens.fr/ dicosmo/DEA/SPP/
Laboratoires de recherche

CNET Issy, Lannion Labri Bordeaux
CNRS Imag Grenoble
INRIA, 5 Unités de recherche Marseille Lumigny
ENS Paris 6
ENS Cachan Paris 7, (Logique)
ENS Lyon Marne la Vallée
ENPC ORSAY
ENSMP Saint Denis
ENST Léonard de Vinci
LIX CNAM
Thomson LCR Lucent, AT&T Bell labs
Alcatel Marcoussis Bellcore
GENSET Digital SRC, WRL
ILOG IBM Almaden, Yorktown
O2 Technology Microsoft Research Redmond, Cambridge
Chorus Systèmes Xerox PARC
Xerox Grenoble HPlabs
Web Consortium SUN

Domaines de recherche (exemple de l'INRIA)

Thèmes

1. Réseaux et systèmes
2. Génie logiciel et calcul symbolique
3. Interaction homme-machine, images, données, connaissances
4. Simulation et optimisation de systèmes complexes

Action de développements

DYADE : conception de systèmes d'information avancés
GÉNIE : science de l'information et ingénierie concourante
MÉDIACULTURE : système multimédia distribué pour la documentation culturelle
PRAXITELE : transport urbain public individuel
PRÉVISIA : interopérabilité des systèmes d'information
SYNCHRONE : environnement de développement de systèmes temps-réel
W3C : les services d'information sur Internet
WEBTOOLS : outils logiciels pour le World Wide Web

http://www.inria.fr/Recherche/activites-fra.html
Thème 1

Parallélisme et architecture :

APACHE - Algorithmique parallèle et partage de charge
API - Architectures parallèles intégrées
CAPS - Compilation, architectures parallèles et systèmes
PAMPA - Environnement de programmation des architectures massivement parall èles
ReMaP - Régularité et parallélisme massif
SLOOP - Simulation, langages orientés objets et parallélisme

Réseaux, systèmes, évaluation de performances :

MÉVAL - Modélisation et évaluation des systèmes informatiques
MISTRAL - Modélisation en informatique et systèmes de télécommuni cation : recherche et applications logicielles
MODEL - Modélisation de systèmes aléatoires
RESEDAS - Outils logiciels pour les télécommunications et les systèmes d istribués
RODEO - Réseaux a` haut débit, réseaux ouverts
SATURNE - Systèmes répartis tolérant les fautes et les intrusions
SIRAC - Systèmes informatiques répartis pour applications coopératives
SOLIDOR - Architectures et systèmes distribués extensibles, tolérance au x fautes, programmation objet
SOR - Systèmes d'objets répartis

Programmation distribuée et temps-réel :

ADP - Algorithmes répartis et protocoles
EPM-PATR - Environnement de programmation pour applications temps réel
MEIJE - Parallélisme, synchronisation et temps réel
PARA - Parallélisme, mobilité
REFLECS - Systèmes informatiques répartis temps réel tolérant les fautes
SPECTRE - Spécification et programmation des systèmes communicants et tem ps réel

Thème 2

Sémantique et programmation :

CALLIGRAMME - Logique linéaire, réseaux de démonstration et grammaires cat égorielles
COQ - Spécifications et preuves de programmes
CRISTAL - Programmation typée, modularité et compilation
CROAP - Conception et réalisation d'outils d'aide a` la programmation
EURECA - Preuve, calcul symbolique et logique
LANDE - Langages déclaratifs
LOCO - Programmation logique avec contraintes
OSCAR - Outils syntaxiques pour la construction et l'analyse de programmes
PROTHEO - Contraintes, déduction automatique et preuves de propriétés de logiciels

Algorithmique et calcul formel :

ALGO - Algorithmes
CODES - Codes et protection de l'information
PRISME - Géométrie, algorithmes et robotique
SAFIR - Systèmes algébriques formels pour l'industrie et la recherche

Thème 3

Bases de données, bases de connaissances, systèmes cognitifs :

ACACIA - Acquisition des connaissances pour l'assistance a` la conception par interaction entre agents
AIRELLE - Représentations et langages
ATOLL - Atelier d'outils logiciels pour le langage naturel
DIALOGUE - Dialogue homme-machine a` forte composante langagière
OPERA - Outils pour les documents électroniques : recherche et applications
ORION - Modélisation des connaissances pour l'automatisation des tâches
PSYCHO-ERGO - Psychologie ergonomique pour l'informatique
REPCO - Représentation des connaissances
RODIN - Systèmes de bases de données
SHERPA - Bases de connaissances a` objets
SHOOD - Méthodes et outils pour l'intégration de systèmes industriels
SYCO - Systèmes de compréhension et bases de connaissances
VERSO - Bases de données

Vision, analyse et synthèse d'images :

AIR - Traitement d'image et données satellites dynamiques
EPIDAURE - Imagerie et robotique médicale
iMAGIS - Modèles, algorithmes, géométrie pour le graphique et l'image de synthèse
ISA - Image, synthèse, analyse
MOVI - Modélisation, localisation, reconnaissance et interprétation en vis ion parordinateur
PASTIS - Analyse de scènes et traitement d'images symboliques
ROBOTVIS - Vision par ordinateur et robotique
SHARP - Programmation automatique et systèmes décisionnels en robotique
SIAMES - Synthèse d'image, animation, modélisation et simulation
SYNTIM - Analyse et synthèse d'images
TEMIS - Traitement, exploitation et modélisation d'images séquentielles

Thème 4

Automatique, robotique, signal :

AS - Automatique et signal
ATGC - Action transversale génome et calcul
BIP - Conception et contrôle de robots marcheurs et applications
COMORE - Contrôle et modélisation de ressources renouvelables
CONGÉ - Contrôle géométrique des systèmes non linéaires
FRACTALES - Approche fractale pour l'analyse et la modélisation de signaux complexes
ICARE - Instrumentation, commande et architecture des robots évolués
MÉTA 2 - Méta automatique et méthodes de l'automatique
MIAOU - Mathématiques et informatique de l'automatique et de
l'optimisation pour l'utilisateur
PROMATH - Programmation mathématique
SAGEP - Simulation, analyse et gestion des systèmes de production
SOSSO - Applications et outils de l'automatique
SYSTOL - Modélisation statistique et applications biomédicales

Modélisation et calcul scientifique :

ALADIN - Algorithmes adaptés au calcul numérique intensif
CAIMAN - Calcul scientifique, modélisation et analyse numérique
ESTIME - Estimation de paramètres
IDOPT - Identification et optimisation de systèmes en physique et en environnement
M3N - Multi-modèles et méthodes numériques
MODULEF - Méthodes et outils pour le calcul scientifique
NUMATH - Analyse mathématique et traitement numérique de modèles non linéaires
OMEGA - Méthodes numériques probabilistes
ONDES - Modélisation, analyse, simulation des équations des ondes
SINUS - Simulation numérique dans les sciences de l'ingénieur
SYSDYS - Systèmes dynamiques stochastiques

Annexes


3/17/1998