INF564 - TD 7 - Production de code ERTL, analyse de durée de vie

Le but de ce TD est de réaliser la production de code intermédiaire ERTL pour le langage mini-C, puis l'analyse de durée de vie sur le code obtenu.

Code fourni

Archive à télécharger : ertl-ocaml.tar.gz

Une fois cette archive décompressée (par exemple avec tar zxvf ertl-ocaml.tar.gz), vous obtenez un répertoire mini-c/ contenant un module OCaml :

Ertltree Explicit Register Transfer Language (ERTL)
Ertlinterp Interprète de code ERTL (pour tester)

Ces modules sont complets. Cliquer sur le nom du module pour accéder à sa documentation. On prendra le temps de bien comprendre le code fourni.

1. Production de code ERTL

Ajouter au compilateur mini-C une fonction traduisant le code RTL en code ERTL, c'est-à-dire en une valeur du type Ertltree.file. Ajouter au compilateur une option --interp-ertl pour exécuter ce code avec la fonction Ertlinterp.program fournie. On affichera le résultat avec la fonction Ertltree.print_file fournie.

On pourra récupérer ce nouveau minic.ml qui ajoute ces fonctionnalités au compilateur.

On suggère très fortement de procéder construction par construction, en testant systématiquement à chaque fois.

1.1. Instructions inchangées

Commencer par les instructions qui sont inchangées entre RTL et ERTL, c'est-à-dire Econst, Eload, Estore, Emunop, Embinop, Emubranch, Embbranch et Egoto. Il s'agit d'une traduction mot à mot, qu'on pourra écrire comme une fonction de la forme
let instr = function
  | Rtltree.Econst (r, n, l) ->
      Econst (r, n, l)
  | ...
La seule exception est le cas d'une instruction Embinop (Mdiv, r1, r2, l) pour laquelle il faut placer r2 dans %rax avant de faire la division, puis récupérer le résultat dans %rax pour le mettre dans r2. Ne pas traiter le cas de l'instruction Ecall pour l'instant.

Traduire ensuite une fonction RTL vers une fonction ERTL, en se contentant pour l'instant de traduire chaque instruction avec la fonction ci-dessus. Comme pour la traduction vers RTL, on pourra stocker le graphe de flot de contrôle en cours de construction dans une référence globale. Ajouter dans ce graphe une instruction Ereturn au niveau de l'étiquette de sortie de la fonction.

Tester avec le programme :

int main() {
  return 42;
}
On doit obtenir quelque chose comme :
=== ERTL =================================================
main(0)
  entry : L2
  locals:
  L2: mov $42 #1  --> L1
  L1: return
Tester avec d'autres programmes plus complexes (mais sans appel de fonction pour l'instant).

1.2. Appel de fonction

Traduire l'instruction RTL Ecall (r, f, rl, l). Pour cela, il faut
  1. passer les arguments (liste rl) dans les registres donnés par la liste Register.parameters (avec Mmov) et sur la pile s'il y en a trop (avec Epush_param) ;
  2. effectuer l'appel avec l'instruction ERTL Ecall(f, n, ...)n est le nombre d'arguments passés dans des registres ;
  3. copier Register.result dans r ;
  4. dépiler les arguments mis sur la pile, le cas échéant, avec une manipulation arithmétique de %rsp.

Tester avec des programmes comme

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}
Au niveau de l'appel fact(42), par exemple, on doit obtenir quelque chose comme
  L3: mov $42 #2  --> L2
  L2: goto L16
  L16: mov #2 %rdi  --> L15
  L15: call fact(1)  --> L14
  L14: mov %rax #1  --> L1
(un seul argument, passé dans %rdi).

1.3. Traduction d'une fonction

Ajouter enfin de nouvelles instructions à l'entrée et à la sortie de chaque fonction pour

Tester avec des programmes comme

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}
Pour la fonction fact, par exemple, on doit obtenir quelque chose comme
fact(1)
  entry : L31
  locals: #11, #12
  L31: alloc_frame  --> L30
  L30: mov %rbx #11  --> L29
  L29: mov %r12 #12  --> L28
  L28: mov %rdi #3  --> L13
  ...
  L4: goto L36
  L36: mov #4 %rax  --> L35
  L35: mov #11 %rbx  --> L34
  L34: mov #12 %r12  --> L33
  L33: delete_frame  --> L32
  L32: return
Les pseudo-registres #11 et #12 sont ici utilisés pour sauvegarder les registres callee-saved (limités ici à %rbx et %r12 pour simplifier).

1.4. Tests

Des tests sont fournis dans tests-v1.tar.gz, qui remplacent les tests précédents (deux fichiers de plus et une légère modification dans mandelbrot.c).

On teste comme pour le code RTL :

> ./run -i  "mon/chemin/vers/mini-c --interp-ertl"
Test de mon/chemin/vers/mini-c --interp-ertl

Interprétation
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
...
Compilation:
Compilation : 62/62 : 100%
Comportement du code : 62/62 : 100%

2. Analyse de durée de vie

On va maintenant réaliser l'analyse de durée de vie sur le code ERTL obtenu. L'objectif est de construire une fonction
val liveness: Ertltree.cfg -> live_info Label.map
qui prend en argument un graphe de flot de contrôle ERTL et renvoie un dictionnaire qui associe à chaque étiquette une information du type suivant :
type live_info = {
         instr: Ertltree.instr;
          succ: Label.t list;    (* successeurs *)
  mutable pred: Label.set;       (* prédécesseurs *)
          defs: Register.set;    (* définitions *)
          uses: Register.set;    (* utilisations *)
  mutable  ins: Register.set;    (* variables vivantes en entrée *)
  mutable outs: Register.set;    (* variables vivantes en sortie *)
}
On suggère d'utiliser localement une table de hachage associant à chaque étiquette une information de type live_info. On pourra procéder ainsi :
  1. Remplir la table à partir du graphe de flot de contrôle, avec pour l'instant des ensembles vides pour les champs pred, ins et outs.
    Les fonctions Ertltree.succ et Ertltree.def_use fournies permettent de remplir les champs succ, defs et uses.

  2. Parcourir la table pour remplir les champs pred (les prédécesseurs), à partir de l'information contenue dans les champs succ (les successeurs).

  3. Écrire enfin l'algorithme de Kildall pour calculer les champs ins et outs.
Pour tester, on pourra afficher le résultat obtenu en se servant de la fonction Ertltree.visit fournie et d'une fonction comme
let print_set = Register.print_set

let print_live_info fmt li =
  fprintf fmt "d={%a}@ u={%a}@ i={%a}@ o={%a}"
    print_set li.defs print_set li.uses print_set li.ins print_set li.outs
Avec un programme comme
int main() {
  return 42;
}
on doit obtenir quelque chose comme
  L5: alloc_frame  --> L4 d={} u={} i={%r12, %rbx} o={%r12, %rbx}
  L4: mov %rbx #2  --> L3 d={#2} u={%rbx} i={%r12, %rbx} o={#2, %r12}
  L3: mov %r12 #3  --> L2 d={#3} u={%r12} i={#2, %r12} o={#2, #3}
  L2: mov $42 #1  --> L1 d={#1} u={} i={#2, #3} o={#1, #2, #3}
  L1: goto L10 d={} u={} i={#1, #2, #3} o={#1, #2, #3}
 L10: mov #1 %rax  --> L9 d={%rax} u={#1} i={#1, #2, #3} o={#2, #3, %rax}
  L9: mov #2 %rbx  --> L8 d={%rbx} u={#2} i={#2, #3, %rax} o={#3, %rax, %rbx}
  L8: mov #3 %r12  --> L7 d={%r12} u={#3} i={#3, %rax, %rbx} o={%r12, %rax, %rbx}
  L7: delete_frame  --> L6 d={} u={} i={%r12, %rax, %rbx} o={%r12, %rax, %rbx}
  L6: return d={} u={%r12, %rax, %rbx} i={%r12, %rax, %rbx} o={}
Tester ensuite avec des programmes plus complexes.
retour à la page du cours