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-java.tar.gz

Une fois cette archive décompressée (par exemple avec tar zxvf ertl-java.tar.gz), vous obtenez un répertoire mini_c/ contenant plusieurs fichiers Java :

ERTL.java Langage ERTL (Explicit Register Transfer Language)
ERTLinterp.java Interprète de code ERTL (pour tester)

Ces classes sont complètes et documentées ici. 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 ERTLfile. Ajouter au compilateur une option --interp-rtl pour exécuter ce code avec la classe ERTLinterp fournie. Pour débugger, on pourra aussi afficher le résultat avec la méthode print de la classe ERTLfile.

On pourra récupérer ce nouveau Main.java 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 Rconst, Rload, Rstore, Rmunop, Rmbinop, Rmubranch, Rmbbranch et Rgoto. Il s'agit d'une traduction mot à mot. On pourra utiliser le visiteur RTLVisitor fourni avec le code du TD 6.

La seule exception est le cas d'une instruction Rmbinop(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 Rcall pour l'instant.

Traduire ensuite une fonction RTL vers une fonction ERTL, en se contentant pour l'instant de traduire chaque instruction. Comme pour la traduction vers RTL, on pourra stocker le graphe de flot de contrôle en cours de construction dans une variable globale. Ajouter dans ce graphe une instruction ERreturn 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 Rcall (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 ERpush_param) ;
  2. effectuer l'appel avec l'instruction ERTL ERcall(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 classe
class Liveness {

  Map<Label, LiveInfo> info;

  Liveness(ERTLgraph g) { ... }
}
qui prend en argument un graphe de flot de contrôle ERTL et construit un dictionnaire qui associe à chaque étiquette une information du type suivant :
class LiveInfo {
           ERTL instr;
        Label[] succ;   // successeurs
     Set<Label> pred;   // prédécesseurs
  Set<Register> defs;   // définitions
  Set<Register> uses;   // utilisations
  Set<Register> ins;    // variables vivantes en entrée
  Set<Register> outs;   // variables vivantes en sortie
}
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.
    Des méthodes fournies dans la classe ERTL 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 du code suivant :
  private void print(Set<Label> visited, Label l) {
    if (visited.contains(l)) return;
    visited.add(l);
    LiveInfo li = this.info.get(l);
    System.out.println("  " + String.format("%3s", l) + ": " + li);
    for (Label s: li.succ) print(visited, s);
  }

  void print(Label entry) {
    print(new HashSet<Label>(), entry);
  }
et d'une méthode toString appropriée dans la classe LiveInfo.

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