Algorithme de Sethi-Ullman

En informatique , l' algorithme de Sethi-Ullman est un algorithme nommé d'après Ravi Sethi et Jeffrey D. Ullman , ses inventeurs, pour traduire des arbres syntaxiques abstraits en code machine qui utilise le moins de registres possible.

Lors de la génération de code pour des expressions arithmétiques, le compilateur doit décider quelle est la meilleure façon de traduire l'expression en termes de nombre d'instructions utilisées ainsi que de nombre de registres nécessaires pour évaluer un certain sous-arbre. En particulier dans le cas où les registres libres sont rares, l'ordre d'évaluation peut être important pour la longueur du code généré, car des ordres différents peuvent conduire à un nombre plus ou moins grand de valeurs intermédiaires déversées dans la mémoire puis restaurées. L'algorithme de Sethi-Ullman (également connu sous le nom de numérotation de Sethi-Ullman ) produit du code qui nécessite le moins d'instructions possible ainsi que le moins de références de stockage (en supposant qu'au maximum la commutativité et l'associativité s'appliquent aux opérateurs utilisés, mais que les lois distributives ne sont pas valables). L'algorithme réussit également si ni la commutativité ni l'associativité ne sont valables pour les expressions utilisées, et que par conséquent les transformations arithmétiques ne peuvent pas être appliquées. L'algorithme ne tire pas non plus parti des sous-expressions courantes ou ne s'applique pas directement aux expressions représentées sous forme de graphes acycliques orientés généraux plutôt que d'arbres.

L' algorithme simple de Sethi-Ullman fonctionne comme suit (pour une architecture de chargement/stockage ) :

1. Parcourez l' arbre de syntaxe abstraite en pré- ou post-ordre
   1. Pour chaque nœud feuille, s'il s'agit d'un enfant gauche non constant, attribuez un 1 (c'est-à-dire qu'un registre est nécessaire pour contenir la variable/le champ/etc.), sinon attribuez un 0 (il s'agit d'un enfant droit non constant ou d'un nœud feuille constant (RHS d'une opération - littéraux, valeurs)).
   2. Pour chaque nœud non-feuille, si les sous-arbres gauche et droit nécessitent respectivement un nombre différent de registres l et r , attribuez alors max( l , r ), sinon attribuez r + 1.
2. Pour émettre du code, si les sous-arbres ont besoin d'un nombre différent de registres, évaluez d'abord le sous-arbre ayant besoin du plus de registres (puisque le registre nécessaire pour sauvegarder le résultat d'un sous-arbre peut faire déborder l'autre ), sinon l'ordre n'est pas pertinent.

Pour une expression arithmétique , l' arbre syntaxique abstrait ressemble à ceci :

 = / \ un * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ bcfg 

Pour continuer avec l'algorithme, il suffit d'examiner l'expression arithmétique , c'est-à-dire qu'il suffit de regarder le sous-arbre de droite de l'affectation '=' :

 * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ bcfg 

Nous commençons maintenant à parcourir l'arbre (en préordre pour l'instant), en attribuant le nombre de registres nécessaires pour évaluer chaque sous-arbre (notez que la dernière somme de l'expression est une constante) :

 * 2 / \ / \ + 2 + 1 / \ / \ / \ d 1 3 0 + 1 * 1 / \ / \ b 1 c 0 f 1 g 0

À partir de cet arbre, on peut voir que nous avons besoin de 2 registres pour calculer le sous-arbre gauche de '*', mais seulement d'un registre pour calculer le sous-arbre droit. Les nœuds 'c' et 'g' n'ont pas besoin de registres pour les raisons suivantes : Si T est une feuille d'arbre, alors le nombre de registres pour évaluer T est soit 1 soit 0 selon que T est un sous-arbre gauche ou droit (puisqu'une opération telle que l'addition de R1, A peut gérer directement le composant droit A sans le stocker dans un registre). Par conséquent, nous commencerons par émettre du code pour le sous-arbre gauche en premier, car nous pourrions nous retrouver dans une situation où il ne nous reste que 2 registres pour calculer l'expression entière. Si nous calculions maintenant le sous-arbre droit en premier (qui ne nécessite qu'un seul registre), nous aurions alors besoin d'un registre pour contenir le résultat du sous-arbre droit tout en calculant le sous-arbre gauche (qui nécessiterait toujours 2 registres), nécessitant donc 3 registres simultanément. Le calcul du sous-arbre de gauche nécessite d'abord 2 registres, mais le résultat peut être stocké dans 1, et comme le sous-arbre de droite n'a besoin que d'un seul registre pour être calculé, l'évaluation de l'expression peut se faire avec seulement 2 registres restants.

Dans une version avancée de l’ algorithme de Sethi-Ullman , les expressions arithmétiques sont d’abord transformées, exploitant les propriétés algébriques des opérateurs utilisés.