INF7641 - Devoir 3

Devoir à remettre le mardi 1er avril (c’est pas une blague) avant 9h par courriel à privat.jean@uqam.ca.

Le travail est individuel.

Il y a quatre exercices, mais vous n’êtes tenu d’en faire que trois. Je considérerai les trois meilleures notes.

1. BOO! (ça fait peur)

Le retour des opérateurs logiques booléens traditionnels &&, || et !.

  • Notez que l’implémentation dans les analyses sémantiques, MiniC et MiniCC sont déjà en place (correction du devoir 2). Ainsi que des programmes de tests.
  • On peut s’en sortir avec une soixantaine de lignes (dans plusieurs fichiers).
  • Regardez les fichiers *.dot générés pour vous aider si besoin.

Tâche 1.1

Implémentez l’opérateur unaire ! dans MiniCC2.

  • La pseudo-instuction seqz RISC-V peut servir à implémenter !.
  • Vous devez créer une nouvelle catégorie d’instruction, appelez-là Instr.Not.
  • Et mettez à jour divers fichiers pour intégrer cette nouvelle instruction.

Tâche 1.2

Implémentez les deux opérateurs binaires && et || dans MiniCC2.

  • Comme en C, assurez-vous que ces opérateurs soient paresseux.
  • Vous ne devez pas créer de nouvelles instructions dans le code intermédiaire. Contentez-vous de celle que vous avez.

2. AE-CSE (on dirait le nom d’une association étudiante)

Tâche 2.1

Implémentez l’analyse classique AvailableExpressions comme sous-classe de Dataflow. Squelette très minimal déjà fourni.

  • IR.isArith() peut vous aider.
  • Indice : faites circuler des IR dans l’analyse de flux.
  • On peut s’en sortir en une trentaine de lignes.
  • N’oubliez-pas de l’ajouter à getPasses de MiniCC2.
  • Regardez les fichiers *AvailableExpressions*.dot (automatiquement) générés pour vous aider.

Tâche 2.2

Implémentez l’optimisation classique CommonSubexpressionElimination comme sous classe de Pass et qui prend un AvailableExpressions en paramètre.

Stratégie :

  • Avoir le résultat d’une analyse available expression
  • Pour chaque expression e arithmétique x = y @ z du programme (où @ est un opérateur +, -, * ou <)
    • S’il existe une expression disponible équivalente t = y @ z
    • Alors remplacer e par x = t
    • Note : on peut se contenter d’une équivalence simplement syntaxique : mêmes instructions et mêmes opérandes dans le même ordre.

Squelette très minimal déjà fourni. L’option -O1 active cette passe.

  • IR.replaceWith peut vous aider.
  • Indice : n’importe quelle expression équivalente disponible est utilisable. Toutes celles présentent se valent, ce sera la job de passes ultérieures d’optimiser mieux.
  • On peut s’en sortir en une quarantaine de lignes.

Tâche 2.3

  • Identifiez les programmes d’exemple dans lesquels cette optimisation a un effet.
  • Discutez de son efficacité.

3. Kemping

Tâche 3.1

Implémentez un allocateur RegisterAllocationKempe qui utilise l’heuristique de Kempe et s’utilise à la place de RegisterAllocationLinearScan.

Squelette très minimal déjà fourni. L’option -kempe du compilateur utilise cet allocateur plutôt que le linearscan par défaut.

  • N’utilisez pas de bibliothèques tierces, codez l’heuristique vous-même.
  • On peut s’en sortir en mois d’une centaine de lignes.
  • LiveVariables.dumpInterference peut produire un joli graphe coloré une fois la coloration calculée.

Tâche 3.2

Comparez et discutez l’efficacité des deux allocateurs en comparant les résultats sur les programmes d’exemples.

4. Déversement

Implémenter un mécanisme de spilling qui associe des registre IR non pas a des registres matériels mais à des emplacement dans la pile.

  • On s’en sort en moins d’une centaine de lignes ajoutés ou modifiés.

Note

En RISC il y a beaucoup de registres, c’est difficile d’atteindre la limite pour de petites fonctions. mandelbrot.c étant l’exception :).

Il y a donc une option -ramax=n qui fixe à n le nombre de registres machines alloués aux registres IR. Si n vaut zéro, cela veut dire que tous les registres IR sont en mémoire dans la pile.

Utilisez cette option pour testez le fonctionnement de votre mécanisme de spilling.

  • Pour simplifier, on considère que n est autant le nombre de registres sauvés max, que le nombre de registre non sauvé max.
  • Les registres nécessaires à la manipulations de la pile ne compte pas pour ramax.

Tâche 4.1

Étendez RegisterAllocationLinearScan pour spiller certains registres en mémoire.

  • Aide: en plus des registres sauvés et non sauvés, vous pouvez considérer une 3e catégorie de registres IR, ceux spillés.
  • Réutilisez les emplacements dans la pile pour plus de performance.
  • Attention, en RISC-V, il faut prévoir nécessairement 2 registres temporaires libres pour pouvoir manipuler la pile et stocker des valeurs intermédiaires.

Tâche 4.2

Modifiez AsmEmitter pour mettre en œuvre le spilling afin de récupérer les arguments et/ou stoker les résultats des instructions machine de ou depuis la pile lorsque des registres IR spilés sont utilisés.

  • Alternativement, vous pouvez laisser AsmEmitter relativement tranquille et ajouter des instructions IR de chargement et de sauvegarde dans la pile, c’est plus propre, mais je ne conseille pas forcément cette approche dans le cadre de l’exercice.

Tâche 4.3 (bonus)

Si vous faite aussi Kempe (exercice 3), appliquez-y aussi le spilling à RegisterAllocationKempe.

  • L’AsmEmitter devrait fonctionner sans changement supplémentaire.
  • Quelques lignes font l’affaire.

Remise:

  • Pour les tâches avec discussion, mettez votre texte dans un ficher markdown dans le sous-répertoire minic/doc, ou en commentaire de commit.
  • Envoyez une série de 3 patchs (4 si vous êtes gourmand), un par exercice. S’il y a des jolis commentaires de commits qui expliquent des trucs, c’est mieux.
  • Les patchs doivent être applicables sur le tag devoir3 du dépôt de code du cours (ou sur tout commit public ultérieur de la branche master).
  • Utilisez git format-patch (ou git send-email) pour formater vos patches. Note: git diff n’est pas suffisant car la base n’est pas clairement indiquée.
  • Important : si vous forkez le dépôt sur gitlab, passez le en privé !