Intermediate Representation
***************************

A compiler includes a lot of code which is independent from the source language, and the target language. Par conséquent, la factorisation est recherchée.  Mais si on supporte s langages sources et c langages cibles, on doit implémenter s \times c traductions ???

Bien entendu on va chercher à produire un langage intermédiaire, un représentation intermédiaire, ce qui permet de se limiter à s + c. Remarquer que la syntaxe abstraite est déjà une façon d'asbtraire du langqge de départ.  Certains languages peuvent probablement être exprimés dans la même syntaxe abstraite, mais s'il existe autant de langages aujourd'hui c'est aussi et surtout parce qu'ils sont profondément différents, et par conséquent leur syntaxe abstraite sont aussi très différentes.

Pourquoi ne pas se définir une syntaxe abstraite universelle vers laquelle traduire tous les langages ?

D'abord parce que cette syntaxe abstraite n'a pas de raison d'exister, et si elle existait, on aurait les défauts suivants :

syntaxe abstraite riche
     donc en aval, on  aurait beaucoup de cas à traiter ;

traduction difficile
     la traduction, au sortir du parseur, vers la syntaxe abstraite  sera certainement plus délicate que pour une synatxe abstraite spécialisée.

Par conséquent, en général, c'est un peu plus loin qu'on canonisera la représentation de langages différents : juste avant l'assembleur.

La représentation intermédiaire, sous une forme linéaire, est un bon candidat de byte-code.

Tiger Intermediate Representation
=================================

La représentation intermédiaire sera la dernière représentation entre la partie haute, proche du langage source, et la partie basse, proche du langage cible.  On a donc tout intérêt à se rapprocher de notre langage cible.  Comme ici on parle de compilation vers l'assembleur, on va prendre des instructions réellement élémentaires.  Ceci dit, on va chercher à rester assez générique : il s'agit de n'avoir qu'une représentation intermédiaire quelque soit les assembleurs qui suivent.

De toutes façons, on veut aussi qu'il ne soit pas exagérément difficile de passer de l'arbre abstrait vers la représentation intermédiaire.

Voici une proposition de RI.

Expressions
-----------

const(I)

name(N)
     pour les noms comme les label

temp(T)

binop(op, E_1, E_2)
     pour les expressions arithmétiques, mais pas pour les booléennes qui seront traitées spécialement.

mem(E)

call(fun, args)

eseq(s, E)
     pour l'implémentation de la virgule comme en C.

Instructions
------------

move(temp(T), E)

move(mem(E_1), E_2)

exp(E)
     évaluer, jete

jump(E)
     Le paramètre E est évalué E donne la destination (adresse, ou label).

cjump(OP, E_1, E_2, IF_TRUE, IF_FALSE)
     E_1 OP E_2 s'évalue en booléen.  La raison c'est qu'on veut pouvoir avoir les opérations booléennes paresseuses.

seq(s_1, s_2)
     pour l'implémentation de la virgule comme en C.

label(N)

Note that this IR is weak: there is nothing to translate switch statements and many others.  To represent switch, just extend jump(E) into jump(E, labs) where LABS holds the list of the possible destination of the jump.  This is required for liveness analysis.

Au total on a trois types : les expressions, les instructions, et les conditionnelles.

IR Samples
----------

R-value
.......

Lecture d'une variable dans le frame d'une routine :

     mem(binop(plus, const(k), temp(fp)))

qu'on peut se permettre d'abréger par

     mem(+(const(k), temp(fp)))

Ca peut devenir plus pénible pour accéder à une variable en descendant les static links.

     mem(const(k) + const(l_(n-1)) + ... + const(l_1) + temp(fp))

where L_I are the static links.

Pour un tableau, la descente de l'indice nécessite du code dynamique d'accès à la variable de l'indice, puis conversion en adresse de la cellule du tableau.  Bien entendu un bon compilateur est supposé prendre garde que l'on accède à un indice valide (Bound Checking).  Il est certain que tous les langages ne le permettent pas, en particulier le C ne rend pas la tâche aisée.  Par contre en Ada, pas de problème.

Pour une structure, il faut ajouter l'offset.

L-values
........

L'affectation d'un tableau à un autre peut avoir plusieurs sens selon la sémantique des langages.  Qu'en est-il du Pascal et du C ?

C'est la même chose pour les structures.  Qu'en est-il du Pascal et du C ?

L'implémentation aura peut-être besoin de faire appel à une recopie de blocs de mémoire : mem devrait avoir un autre paramètre pour spécifier la taille.

Literals
........

Pour les chaînes de caractères (et autres bitmap), on se donnera une fonction (du compilateur) qui est chargée de l'émission de la bitmap dans l'assembleur.  Elle nous donne une adresse, qui servira de valeur à la chaîne manifeste.  On ne peut pas le gérer explicitement ici, puisque cela dépend de l'assembleur.

Un bon langage de programmation cachera la plus des efforts d'implémentation (allocation de la mémoire etc.) au programmeur.  Ceci implique que le compilateur devra mettre du code supplémentaire pour certaines opérations.

Dans certains langages la création de structure littérales implique que le compilateur doit faire des allocations mémoire.  Dans des conditions pareilles, il faut que le compilateur vide aussi la mémoire quand elle n'est plus nécessaire : il faut du garbage collecting.

Control Structures
..................

Dans un langage à saveur fonctionelle, comment représenter

     if e_1 then e_2 else e_3

Une boucle WHILE

     test:
       if not (condition)
         goto done
       body
       goto test
     done:

Traduction de

     for i := min to max
       do body

Proposition 1

     let i := min
         limit := max
     in while i<= limit
       do
          (body; i++)
     end

Proposition 2

     let i := min
         limit := max
     in
       if (i > limit)
         goto end
     loop:
         body
         if (i >= limit)
           goto end
         i++
         goto loop
     end:

Les appels de fonctions doivent passer les liens statiques.

Function Definition
-------------------

Doit comprendre plusieurs choses, d'abord le prologue

  - Annonce de début de fonctions (pour les asm)

  - étiquette

  - réglage du frame

  - sauvegarde des arguments qui échappent (eg, ceux dont on veut l'adresse),

  - sauvegarde des registres dont on est responsable.

ensuite le corps de la fonction, enfin, l'épilogue

  - mettre la valeur de retour là où il le faut

  - restaurer les registres qu'on a protégés

  - désallouer la frame

  - le return (ou un jump)

  - annonce de la fin de fonction  à l'intention de l'assembleur.

Translation to IR
-----------------

Sometimes an expression (in the sense of the IR) can be used in another expression, in which case its actual value is needed, and sometimes, it is simply used as an instruction, and its value is thrown away (think of a function call for instance, used only for its side effects and not for its return value).

At other times, this same expression might be used in a condition.

It appears that an expression can be used for three distinct purposes. If we want to produce nice IR, we should take this into account.  To this end we will introduce wrappers around them : a wrapper for things which are intrinsically expression, a wrapper for instructions, and a wrapper for conditionals (i.e., cjump.

Translation Samples
...................

The program

     if 1 < 2 then ()

can be translated as

     SXP
         ESEQ
         SEQ
             CJUMP NE
                 CONST 1
                 CONST 0
                 NAME l9
                 NAME l10
             LABEL l9
             MOVE
                 TEMP t0
                 CONST 2
             JUMP
                 NAME l11
             LABEL l10
             MOVE
                 TEMP t0
                 CONST 0
             JUMP
                 NAME l11
             LABEL l11
         SEQ END.
             TEMP t0

or, if you work some more

     SEQ
         CJUMP NE
             CONST 1
             CONST 0
             NAME l9
             NAME l10
         LABEL l9
         SXP
             CONST 2
         JUMP
             NAME l11
         LABEL l10
         SXP
             CONST 0
         JUMP
             NAME l11
         LABEL l11
     SEQ END.

Normalization
=============

La transformation depuis un langage de haut vers un langage de plus bas niveau est déjà bien avancée.  Pourtant il reste encore trop de concepts de trop haut niveau dans notre RI, on va donc transformer les RI vers quelque chose de plus proche de l'assembleur : on va normaliser les représentations.

En fait, la différence essentielle est que l'on doit passer d'une représentation en arbre vers une représentation linéaire.  Pour ce faire, on va s'attaquer aux instructions suivantes :

ESEQ and SEQ
     il est pratique que les expressions puissent être évaluées dans n'importe quel ordre, mais ESEQ nous en empêche.  On fera remonter les ESEQ et SEQ tout en haut, au point de pouvoir même nous débarasser des ESEQ.

CALL
     pose le même problème, et celui de la concurrence sur les registres quand on a des appels de fonctions imbriqués (en clair, on ne veut pas de CALL avec des CALL en paramètres).  On exigera des CALL d'être soit fils de MOVE, soit de EXP.

CJUMP
     doesn't exist in assembly languages: either you jump to an address, or fall to the next instruction.

Normalization of ESEQ
---------------------

Essayer sur les cas suivants

     ESEQ(s_1, ESEQ(s_2, e))
     BINOP(op, ESEQ(s, e_1), e_2)
     MEM(ESEQ(s, e_1))
     BINOP(op, e_1 ESEQ(s, e_2))
     CJUMP(op, e_1 ESEQ(s, e_2), l_1, l_2)

Remember that some permutations cannot be made because the order might be important: it doesn't commute.  OTOH, it dramatically improves the code if you can recognize some cases which can be simplified.

The end result must be a list of statements, and then a list of expressions.

Normalization of CALL
---------------------

Un des problèmes des CALL est le conflit entre les appels sur les registres (en particulier l'occupation des registres servant au passage de paramètres, et celui pour le retour de valeur).

Comment normaliser

     CALL(foo, foos) + CALL(bar, bars)

L'idée la plus simple c'est de réécrire

     CALL(f, args)

en

     ESEQ(MOVE(TEMP(t), CALL(f, args)), TEMP(t)

puis laisser la remontée des ESEQ se faire.  Ca chifonne un peu l'esprit : on est en train de générer beaucoup trop de MOVE, mais on compte sur l'allocation des registres pour améliorer la situation, par la suite.

Normalization of CJUMP
----------------------

Ce sont les CJUMP qui donnent à notre RI cette forme d'arbre pas très minces : on va essayer d'amincir les arbres.  Dans le cas des CJUMP(\cdots, l_f), on va essayer de mettre le lavel l_f juste derrière.

On sent bien le type d'entitées qu'on va manipuler : des blocs.

Un bloc commence par un LABEL, termine par un JUMP ou CJUMP, et n'a aucun des trois dedans.

Une fois les blocs définis, on peut les mettre dans n'importe quel ordre dans la mémoire, puisqu'ils ont tous des étiquettes et des sauts !  On va en particulier pouvoir choisir l'ordre qui nous arrange.  Comme on s'intéresse à la vitesse, on cherche à éviter les instructions inutiles, c'est-à-dire qu'on va essayer de limiter au maximum les sauts, c'est-à-dire qu'on va essayer au maximum de mettre derrière les sauts les étiquettes qui leur correspondent.  Alors le saut sera inutile.

About CJUMP, since in assembly the `else' part means to fall through, when possible we will move the `else' branch right afterwards. Sometimes it will be advantageous to negate the test, and sometimes another jump might be needed.

Quant aux sauts conditionnels, on essaie de mettre la branche d'échec juse derrière eux.

The consecutive execution of several blocks is called a trace. Note that a bloc is defined statically, and a trace, dynamically.

Finalization
------------

Il reste à garantir la linéarité du résultat.

  - si un saut conditionnel est suivi de son étiquette succès, inverser le test,

  - si suivi ni de succès, ni d'échec, introduire une nouvelle étiquette, et la brancher là où il faut.

A good choice of traces can improve the performances of the compiled code.  For instance, here are there different coverings of the following basic blocks:

     LABEL(prologue)
     /* Some prologue. */
     JUMP(test)

     LABEL(test)
     CJUMP(i <= N, body, done)

     LABEL(body)
     /* Work. */
     JUMP(test)

     LABEL(done)

     LABEL(prologue)
     /* Prologue */
     JUMP(NAME(test))
     LABEL(test)
     CJUMP(>, i, N, done, body)
     LABEL(body)
     /* Body */
     JUMP(NAME(test))
     LABEL(done)

     LABEL(prologue)
     /* Prologue */
     JUMP(NAME(test))
     LABEL(test)
     CJUMP(<=, i, N, body, done)
     LABEL(done)
     /* Epilogue */
     LABEL(body)
     /* Body */
     JUMP(NAME(test))
     LABEL(done)

     LABEL(prologue)
     /* Prologue */
     JUMP(NAME(test))
     LABEL(body)
     /* Body */
     JUMP(NAME(test))
     LABEL(test)
     CJUMP(>, i, N, done, body)
     LABEL(done)