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

Code fourni

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 :

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

On pourra récupérer ce nouveau minic.ml qui ajoute au compilateur une option --interp-ertl pour exécuter le code ERTL et qui affiche le code ERTL quand on passe l'option --debug.

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

1.1. Instructions inchangées

let instr = function
  | Rtltree.Econst (r, n, l) ->
      Econst (r, n, l)
  | ...

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;
}

=== ERTL =================================================
main(0)
  entry : L2
  locals:
  L2: mov $42 #1  --> L1
  L1: return

1.2. Appel de fonction

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, ...) où 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);
}

  L3: mov $42 #2  --> L2
  L2: goto L16
  L16: mov #2 %rdi  --> L15
  L15: call fact(1)  --> L14
  L14: mov %rax #1  --> L1

1.3. Traduction d'une fonction

• en entrée :
  1. allouer le tableau d'activation (instruction Ealloc_frame) ;
  2. sauvegarder les registres callee-saved (liste Register.callee_saved) dans des pseudo-registres frais ;
  3. récupérer les arguments dans les registres de la liste Register.parameters (avec Mmov) et sur la pile s'il y en a trop (avec Eget_param).
• en sortie :
  1. copier le résultat de la fonction dans Register.rax ;
  2. restaurer les registres callee-saved ;
  3. désallouer le tableau d'activation avec l'instruction Edelete_frame ;
  4. terminer avec l'instruction Ereturn.

Tester avec des programmes comme

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}

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

1.4. Tests

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

val liveness: Ertltree.cfg -> live_info Label.map

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 *)
}

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.

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

int main() {
  return 42;
}

  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={}