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
deMiniCC2
. - 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.
- S’il existe une expression disponible équivalente
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 branchemaster
). - Utilisez
git format-patch
(ougit 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é !