GENERATION DU (VRAI) CODE
Blocs de base

Les problèmes

Génération directe de code pour les expressions
à l'intérieur d'un bloc de base
Première méthode basée sur un arbre
Pour décider où trouver un opérand et où calculer un résultat, il faut savoir
pour chaque identificateur, où est sa valeur actuelle (éventuellement registre/ mémoire
pour chaque registre, quel(s) identificateur(s) il stocke.
On suppose les registres ne contiennent pas de valeurs au début du bloc.

ADD $x, $y, $z

Choisir location (vrai registre) L pour le résultat
Choisir location Y qui va contenir y; générer LD** $Y (si nécessaire) pour y mettre y
Même chose avec Z et z
Générer ADD* $L $Y $Z; mettre à jour les informations sur L et x
mettre à jour les informations sur Y, Z, y et z

Choisir une location L
(resp. Y, Z)

Le prétraitement:

calculer pour chaque identificateur s'il est vivant à la fin du bloc (sa valeur peut-elle être utilisée avant affectation?) et pour chaque valeur où est sa dernière utilisation dans le bloc.

Code à générer à la fin du bloc:

Stocker les valeurs des identificateurs vivants qui ne sont pas déjà dans leur adresse mémoire.

Application à de vrais langages
Comment traiter les variables du langage qui sont stockés sur la pile?

Du code intermédiaire on peut savoir que deux accès à une adresse de type $pile, constante peuvent être traités comme deux accès au même pseudo-registre (même constante) ou à deux registres (constantes différentes).

Pour incorporer aussi des variables de niveau différents (statiques ou adressées par l'adresseur), il faut s'en servir des informations qui ne sont pas évidentes du code intermédiaire
(non-interférence entre blocs distincts).

De la même façon, tout accès à un élément d'un tableau ou accès via un pointeur doit être considéré comme un accès aléatoire faute d'utilisation d'information spécifique au langage source.

Une méthode plus raisonnable
Basée sur le dag de dépendances
En général, on peut trouver des sous-expressions communes qui seraient calculées plusieurs fois par le code simple.

On évite ça si on construit le dag (graphe orienté acyclique) de toutes les valeurs calculées ou utilisées dans le bloc avec les dépendances indiquées par les arcs.

En générant le code selon un tri topologique de ce graphe, on ne calcule pas deux fois le résultat du même opérateur sur les mêmes opérands.

CHANGER L'ORDRE D'EXECUTION
Parce que plusieurs tris topologiques sont possibles, plusieurs ordres d'exécution sont possibles.

Il y a une différence dans le nombre de registres utilisés à un moment donné, et donc dans le nombre d'instructions LD** et ST** générées.

Sauf dans le cas où le graphe est un arbre il est trop difficile de calculer l'ordre optimal.

L'ORDRE OPTIMAL D'EXECUTION POUR UN ARBRE

ALLOCATION DE REGISTRES PAR COLORIATION DE GRAPHES
Quand un ordre de calcul est fixé, on peut construire un graphe dont les sommets sont les affectations aux identificateurs et les arêtes sont les incompatibilités (2 affectations sont incompatibles si à un moment de l'exécution leurs valeurs existent et seront utilisées plus tard)

On essaie de décider si ce graphe peut être coloré avec k couleurs où k est le nombre de registres disponibles

Un problème NP-complet si k > 2 !

Mais il existe des heuristiques qui sont utiles

Effacer un sommet de degré inférieur à k

Si impossible, choisir un sommet de degré grand, le supprimer du graphe, résoudre le problème pour le graphe réduit
et ajouter des instructions pour stocker et relire la valeur.




File translated from TEX by TTH, version 3.05.
On 12 Apr 2005, 10:55.