Notes de la séance 9 de TransProg M2
====================================

Calcul de hauteur maximale de pile

Lorsqu’on compile Kontix vers Javix, on va pouvoir déterminer
la hauteur maximale de pile et l’indiquer au début du fichier Javix.
Pour cela, on peut procéder directement en parcourant la suite des
instructions Javix. Une simple itération de la liste de ces instructions
suffit, même si ce n’est pas forcément l’ordre dans lequel les
instructions seront exécutées. Et pour chaque instruction,
les informations nécessaires sont dans
JavixAST.StackUse.

Cas séquentiel

Prenons par exemple:

Push ...
Box
AStore ...

Si la pile est vide avant ces instructions:

;==> pile vide
Push  // max utilisé par Push : 1 + pile avant (0)
;==> pile de taille 1 (car le "delta" de Push est +1)
Box // max utilisé par Box : 3 + pile avant (1)
;==> pile de taille 1 (car le "delta" de Box est 0)
AStore // max utilisé par AStore : 0 + pile avant 1
;==> pile vide (car le "delta" de AStore est -1)

Données à maintenir lors du calcul:

A chaque instruction, pile_max := max(pile_max avant, maxuse(instr)+taille avant).

Au final pour notre exemple le max des max est 4.

Code structuré

Que faire des Goto et des labels ?

Au moment d’un label de fonction (ou de continuation), la pile est
vide. Pas forcément besoin de s’en assurer, normalement le code qui
précède amènera bien à cette valeur. Pour les autres labels possibles,
à savoir les elseXYZ et endXYZ des If, voir plus bas.

Au moment d’un Goto(f) avec f le nom d’une fonction : là encore
la pile sera vide à ce moment-là, on peut s’en assurer si on est
prudent, ou ne pas le faire si on est optimiste. Cette propriété vient
du fait qu’on finira là une TailExpr de Kontix.

Au moment d’un Goto dispatch, la pile contient exactement le code
de label où on veut aller. Ce Goto dispatch provient soit d’un Ret
soit d’un Call indirect. La zone après ce Goto dispatch est issu
de la compilation d’un autre TailExpr, on la visite donc avec au
départ une hauteur de pile de 0.

Règle pratique : A la ligne suivant un Goto dispatch, passer la
taille de pile courante à 0 (ce qui revient à la faire évoluer de -1).

Ceci suffit à gérer le cas d’un If_icmp ou If dans un TailExpr.

Par exemple:

...
...
If...  elseNNN:
...
Goto dispatch // pour un Ret, par exemple
elseNNN:  // ici pile vide de nouveau
...
Goto f  // pile vide

Conditionnelle venant d’un BIf de BasicExpr

Quant on compile des BasicExpr, leurs imbrications peuvent faire
monter la hauteur de pile actuelle.

...
...
If_icmp ou If  elseNNN:
 ;; si la pile est de hauteur h ici...
...
...  ;; mise en place d'un resultat en haut de pile
 ;; ici hauteur h+1
Goto endXYZ
elseNNN:
 ;; hauteur doit être de nouveau h
...
... ;; mise en place d'un resultat en haut de pile
 ;; ici hauteur h+1
endXYZ:

Règle pratique : à la ligne suivant un Goto endXYZ on enlève 1 à la
hauteur actuelle pour calculer correctement le max des hauteurs dans
la branche else.

Optimisations possibles lors de la compilation

Voir Optims.md