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
