1 - Un problème de robots

Un robot se déplace verticalement, vers le bas dans une grille rectangulaire. Cette grille peut contenir des paires de portails téléporteurs reliés entre eux qui modifient le déplacement du robot : lorsqu’il rentre dans une case contenant un portail, il est envoyé sur la case contenant un portail “jumeau” avant de continuer son déplacement vers le bas.

1.1 - Grilles statiques

1.1.1 - Questions préliminaires

1.1.2 - Implémentation

Tests

1.2 - Grilles dynamiques

2 - Problème Algorithmes pour la compilation

La plupart des programmes sont écrits dans des langages de programmation de haut niveau, tels que Python. Cependant, les machines qui exécutent ces programmes ne sont souvent capables d'exécuter que des instructions élémentaires très simples. Pour pouvoir exécuter ces programmes écrits dans des langages de haut niveau, il est nécessaire d'avoir une transformation du langage source, de haut niveau, vers le langage cible, proche de la machine. Un compilateur est un programme qui effectue cette transformation.

La compilation d'un programme dépend très fortement des contraintes du langage cible :

- il existe des contraintes matérielles, notamment sur les emplacements en mémoire disponibles pour manipuler des variables, que l'on étudie en partie 2.1. Cette partie utilise notamment une première approche pour résoudre un problème de coloriage ;

- la transformation du programme source en programme cible n'est en général pas directe, mais elle passe par plusieurs étapes intermédiaires où le programme change légèrement de forme. Ceci sert notamment à réaliser certaines optimisations. En partie 2.2 on étudie une représentation intermédiaire fréquemment utilisée.

Ce problème comporte deux parties. Chaque partie peut être abordée de manière totalement indépendante de l'autre partie. Il est possible de traiter chaque partie séparément.

2.1 - Allocation de registres dans les compilateurs

2.1.1 - Allocation par durée de vie

2.1.2 - Gérer le nombre insuffisant de registres

2.1.3 - Une heuristique de coloriage

2.1.4 - Vers un coloriage optimal

2.2 - Représentation intermédiaire en forme SSA

2.2.1 - Mise en forme SSA de blocs simples

2.2.2 - Gestion des branchements

2.2.3 - Gestion des boucles

2.2.4 - Amélioration des branchements