Cours pdf production de code Assembleur, tutoriel & guide de travaux pratiques en pdf.

Motifs et temporaires

On appellera motif (tile en anglais signifie plutôt carreau) un fragment d’arbre de code intermédiaire qui est aussi un arbre, ayant une racine et des feuilles.
En général, une instruction assembleur corresponde à un motif, et un arbre de code intermédiaire doit pouvoir être recouvert entièrement par des motifsdisjoints, qui cor-respondent à des instruction assembleur. Il n’est pas nécessaire de prévoir des tem-poraires pour les noeud internes d’un motif (dans le cas de lw $5, 10($fp), il ne nous intéresse pas de savoir par quel moyen la machine assembleur fait la somme entre FP et 10 et lit la mémoire). Par contre, on doit allouer des temporaires pour les noeuds racine (le résultat de l’instruction) et les feuilles (les paramètres de l’instruction).
Voir exemple fait au tableau pour x:=a[10].

Algorithmes!

Quelle séquence d’instruction assembleur doit-on utiliser pour recouvrir un arbre de code intermédiaire?
Un critère raisonnable est la minimisation du coût de la séquence d’instructions assembleur produite (où le coût est souvent le temps d’exécution).
Vis à vis d’une notion de coût fixée, on peut obtenir des séquence assembleur:
optimale si on ne peut remplacer aucune instruction assembleur par une suite d’autres instructions (ayant le même effet) de coût inférieur
optimum s’il n’existe pas d’autre séquence d’instruction assembleur (ayant le même effet) de coût inférieur

Algorithme: MaximalMunch

Il est facile d’obtenir une séquence optimale:
Algorithme MaximalMunch(arbre)
Parmi tous les motifs qui peuvent recouvrir arbre en partant de la racine, choisir le plus gros.
Émettre l’instruction correspondante
Se rappeler récursivement sur les sous-arbres correspondants aux feuilles du motif choisi
Attention: cet algorithme émets les instructions dans l’ordre inverse!

Un mot sur le filtrage de motifs

Le filtrage primitif de Ocaml est très bien adapté à la sélection de motifs opérée par MaximalMunch.
Il faut mettre les motifs les plus gros d’abord, et le compilateur Ocaml produira un arbre de décision qui permet d’opérer le filtrage en temps linéaire (on ne reviendra pas sur une comparaison déjà effectuée).