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-java.tar.gz), vous obtenez un répertoire mini_c/ contenant plusieurs fichiers Java :

Ces classes sont complètes et documentées ici. On prendra le temps de bien comprendre le code fourni.

1. Production de code ERTL

On pourra récupérer ce nouveau Main.java 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

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

=== 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 ERpush_param) ;
2. effectuer l'appel avec l'instruction ERTL ERcall(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 ERalloc_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 ERget_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 ERdelete_frame ;
  4. terminer avec l'instruction ERreturn.

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

class Liveness {

  Map<Label, LiveInfo> info;

  Liveness(ERTLgraph g) { ... }
}

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
}

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.

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

Avec un programme comme

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