Le projet de compilation

Le projet de compilation

L'approfondissement d'un des aspects de la chaîne de compilation devrait vous amener à mieux maîtriser l'ensemble de la chaîne et à permettre d'apporter votre solution personnelle à un problème concret de compilation.

Chaque projet devrait vous obliger à faire des modifications légères dans l'ensemble de la chaîne et à reprendre de façon détaillée l'un des maillons, voir d'en ajouter un nouveau. Vous pourrez vous appuyez indifféremment sur votre propre implémentation menée au cours des travaux dirigés ou bien sur l'assemblage des corrigés.

Quelques conseils pour la présentation de votre projet

Le projet est l'approfondissement d'un exercice, et doit être mené jusqu'au bout. Il est absolument essentiel que votre projet tourne!

Vous devez maîtriser l'ensemble de la chaîne de compilation, et être prêt à le démontrer, y compris sur les aspects qui ne sont pas directement liés à votre projet.

Le projet est le support de votre présentation orale. L'oral durera entre 40 et 45 minutes. Vous aurez 25 à 30 minutes pour décrire votre projet de façon magistrale, c'est-à-dire quasiment sans interruption. La démonstration indispensable doit être incluse à votre guise dans la présentation magistrale. Le reste de votre oral sera plus interactif et guidé par des questions.

La présentation de votre projet est aussi un exercice oral. Ne la négligez pas. On peut faire un mauvais oral avec un bon projet, ou inversement. Alors, bon projet et bon oral!

De nombreux projets!

La difficulté des projets est variable: à vous de choisir un exercice à votre niveau et qui vous plaît.

  1. Implémenter (un mini) lex.

  2. Implémenter (un mini) yacc .

  3. Transformer les fonctions locales en fonctions globales au niveau du langage source en passant des arguments supplémentaires.

  4. Ajouter des enregistrements, des chaînes de caractères (enregistrements et chaînes allouées dans le tas), des caractères.

  5. Allouer les tableaux et les enregistrements en pile.

  6. Compiler les fonctions locales en chaînant les environnements dans la pile

  7. Ajouter une construction switch dans le langage et la compilée de façon efficace en une combinaison de sauts et branchements indexés.

  8. Optimisations au niveau du code source (mise en ligne, évaluation partielle)

  9. Générer du code pour un mini-ML (fonctions locales, retournés, compilées en des fermetures).

  10. Remplacer une solution approchée proposée dans le cours pour un des maillons par une solution plus efficace (produisant un meilleur résultat).

  11. Optimisations globales. Par exemple, on pourra calculer exactement l'ensemble des registres lus et écrit par les fonctions et procédures et améliorer l'appel de fonction (en particulier l'appel à de petites fonctions).

  12. Gestion mémoire.

  13. Compilation vers une autre architecture RISC ou vers un processeur x86.
Vous pouvez aussi nous proposer un sujet qui vous tente.


Gestion mémoire

Comme la plupart des langages modernes, pseudo pascal alloue systématiquement ses structures dans la tas. Cela décharge l'utilisateur de la gestion mémoire.
  1. À la demande du programme, il faut allouer dynamiquement des petits blocs de mémoire en puisant dans un bloc de plus grande taille représentant la mémoire libre. Avant chaque allocation, il faut s'assurer que la mémoire libre est assez grande pour allouer un petit bloc. Si ce n'est pas le cas, il faut...

  2. Glaner les cellules qui ne sont plus utilisées. Dans la plupart des cas, cela fournit suffisamment de mémoire libre pour continuer. Sinon...

  3. Demander au système d'étendre la mémoire du programme.
La phase la plus délicate est l'écriture du GC (Glaneur de Cellule). Il existe plusieurs techniques. Nous en décrivons deux orthogonale.

Stop and Copy

Le principe est d'avoir deux zones mémoires, et de recopier les données actives de l'une dans l'autre à chaque GC. Il faut d'abord trouver toutes les racines: registres et emplacements en pile qui pointent dans le tas, puis parcourir les récursivement ces structures et le recopier en préservant le partage.

Cela impose de pouvoir distinguer les pointeurs dans le tas des entiers. Comme les adresses, se terminent toujours par 00, il faut représenter les entiers sur les 30 bits de poids fort et écrire une marque 01 par exemple sur les deux bits de poids faible. Cette distinction n'est nécessaire que lorsque les entiers sont sauvés sur la pile ou en mémoire. Dans les registres, les entiers peuvent être non-boxés.

Il y a donc deux projets en un et il est conseillé de le faire en binôme.

Comptage des références

La technique ici est de maintenir à jour pour chaque structure allouée le nombre de pointeurs sur celle-ci. Pour cela on réserve un compteur dans l'entête de chque bloc alloué. À chaque affectation de cette structure dans un structure parente, le compteur est incrémenté. Inversement, chaque fois qu'un pointeur est retiré d'une structure parente, le compteur est décrémenté.

Lorsque le compteur passe à zéro, la struture est libérée: on la met alors dans une liste de structures libres pour être réutilisé plus tard de façon prioritaire. Lorsqu'une structure est libérée, il faut aussi récursivement décrémenter le nombre de références contenues dans chacune de ses cases.

Il faut également compter les pointeurs partant des variables globales et locales du programme (source). Pour cela, il faut initialiser les variables locales qui peuvent contenir des structures à l'entrée des fonctions avec un pointeur nul et décrémenter le pointeur courrant à la sortie des fonctions.

Le gc par comptage de référence est plus simple que le gc par copie, notemment parce qu'il ne nécessite pas de codé les entiers, mais mais il est aussi beaucoup moins performant. De plus il ne récupère pas les cycles.