EPFL/Compilation avancée

Un article de Le wiki de 2 noisettes - noisette.ch.

Sommaire

Théorie

Machine virtuelle

  • stack based vm, threaded vm, jited vm

Threaded code

Memory management

  • static area
  • stack
  • heap

free list, fragementation algorithme d'allocation des blocks : best fit, first fit, buddy system

reachability graph

Grabage collection

Le grabage collector, ou ramasseur de miettes en français, est la routine qui permet la désallocation automatique des objets instanciés sur le tas.

conservatif = on laisse les objets dont on est pas sûr.

Compter les références

! aux cycles

Mark and sweep

Copying gc

  • Cheney'ys algo

Generational gc

Autres types de gc

  • incremental gc
  • concurrent gc

Additional features of a gc

  • finalisers
  • week references

Compilateur

OO languages

  • inheritance

single heritance, multiple heritance

  • subtyping
  • inclusion polymorphism

Methode de dispatche

  • virtual method table (VMT)
  • dispatch matrix
  • compact dispatch tables
  • optimisations
    • inline caching
    • polymorphic inline caching (PIC)

membership test

  • relative numbering
  • Cohen's encoding
  • range compression
  • packed encoding

Closure

  • flat representation
  • hoisting
  • free variables

Tail calls

  • trampolines
  • Baker's technique
  • extended trampolines

Continuations

Elles contiennent toutes les informations nécessaires à l'état d'exécution :

  • les registres, y compris PC
  • la pile

Les continuations sont exposées aux développeurs sous forme de fonctions. En appelant une fonction de continuation (call-with-current-continuation ou plus simplement call/cc en Scheme), on suspend l'exécution du programme et on retourne la continuation.

  • utilisés pour implémenter les exceptions et les retours non-locaux, mais aussi threads, coroutines et autres itérators.

Continuation-passing style (CPS)

* toutes les fonctions prennent une continuation comme argument supplémentaire
* elles invoquent cette continuation avec le résultat plutôt que de retourner le résultats -> appels terminaux.


Data flow analyse

  • 1
  • 2
  • 3

Projet

But du projet : compiler du scheme (simplifié) en bytecode et ensuite l'interpréter par une machine virtuelle.

Une particularité de la VM est de ne pas avoir de pile. La pile est entièrement émulée par une liste chainée sur le tas, action gérée elle-même bien évidemment par le compilateur : à chaque appelle de fonction, on alloue la place nécessaire sur la pile, puis on sauvegarde l'adresse de l'espace alloué par la fonction précédente pour la restaurer à la fin de la fonction. Chaque bloques du tas aura donc la forme suivante (dessiné de manière descendante, par analogie à la pile) :

+------+ 0
| FP   | 
+------+ 4
| LK   | 
+------+ 8
| R1   | 
+------+ 12
| ...  | 

Notre mémoire de tas contiendra donc plein de bloques de mémoire de fonction reliés entre eux par des pointeurs sur le bloque précédent

Assembleur

L'assembleur à disposition est très simple, et contient les fonctions suivantes :

LOAD a b c                  : R[a] = *(int*)(R[b] + c)
STOR a b c                  : *((int*)(R[b] + c)) = R[a]
ALOC a b                    : alloue b bytes et place le pointeur vers le bloc dans R[a]
LINT a b                    : charge l'entier b dans R[a]
CMOV a b c                  : R[a] := R[b] si c == 0, 
{ADD,MUL,SUB,DIV,MOD} a b c : R[a] = R[b] op R[c]
{ISQE,ISLT,ISLE} a b c      : R[a] = 0 si R[b] op R[c] est vrai, 1 autrement, op = {=, <, <=}, 
PINT,PCHR a                 : Print the int/char located in R[a]
RINT,RCHR a                 : Read a int/char and put it in R[a]

Compilateur

  • Scanner
  • Parser
  • Analyser
  • Generator

Closure conversion

  • hoisting

Tail call elimination

VM

Registres

Les 32 registres de 32 bits à disposition sont utilisés selon la convention suivante :

R0  : valeur 0 constante
R1  : valeur de retour de la fonction
R2  : arguements, valeurs...
...
R28 : LK (link), adresse du code à laquelle revenir après un appel de fonction.
R29 : FP (frame pointer), pointeur de l'emplacement de la pile
R30 : GP (global pointer), pointeur vers le variable globales
R31 : PC (program counter)

Appels de fonction

  • Avant la fonction
LINT  R2  0x8050490  :  load l'adresse de la fonction
LINT  R1  116        :  charge les arguments
LINT  R28 ret        :  charge l'adresse de retour après la fonction (~= PC + 8)
CMOV  R31 R2  R0     :  jump à l'adresse de la fonction
  • Dans la fonction
LINT  R1  16         : spécifie la taille de la stack frame
ALOC  R1  R1         : alloc la stack frame
STOR  R29 R1  0      : backup le FP de l'appelant
CMOV  R29 R1  0      : set current FP
STOR  R28 R1  4      : backup LK
STOR  R2  R1  8      : store the params on the stack
...                  : execute le code de la fonction
  • Après le fonction
LOAD  R28 R29 4       :  restore LK
LOAD  R29 R29 0       :  restore FP
CMOV  R31 R28 R0      :  jump back to LK

Projets avancés

JIT

Copying precise grabage collector