% Document Type: LaTeX
% Master File: Cours10.tex
\documentclass[12pt]{article}
\usepackage{caml}
\usepackage{a4}
\usepackage{url}
\usepackage{alltt}
\usepackage{shadow}
\usepackage{protect_modes}
\usepackage{custompagenum}
\usepackage{graphicx}
\usepackage{color}
\usepackage{portland}
\usepackage{times}
%\usepackage{slide}
%\usepackage{inrules}
%
% Hack pour latex2html
%
\hoffset -.5in
\renewcommand{\shabox}[1]{#1}
\newcommand{\texslidetitle}[1]{\section*{ #1}}
\newenvironment{texslide}[1]{\texslidetitle{#1}}{}
\newenvironment{plaintexslide}{}{\hrule}
\newcommand{\centershabox}[1]{\begin{center}\shabox{#1}\end{center}}
\newcommand{\vcentershabox}[1]{\centershabox{#1}}
\renewcommand{\LARGE}{}
\renewcommand{\Large}{}
\renewcommand{\large}{}

\usepackage{xypic}
\newenvironment{derivd}{\begin{array}{l}}{\end{array}}
\newenvironment{pile}{\begin{array}{@{(}l@{\qquad,\qquad}r@{)}}}{\end{array}}
\newenvironment{pilecomm}{\begin{array}{@{(}l@{\qquad,\qquad}r@{)\qquad}l}}{\end{array}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{D\'efinition}
\newtheorem{notation}[theorem]{Notation}
\newcommand{\sderd}{\ensuremath{\Rightarrow_{d}}}
\newcommand{\sdernd}{\ensuremath{\Rightarrow^{\ast}_{d}}}
\newcommand{\derd}[2]{\ensuremath{#1\Rightarrow_{d}#2}}
\newcommand{\dernd}[2]{\ensuremath{#1\Rightarrow^{\ast}_{d}#2}}
\newcommand{\lrzitem}[2]{(\ensuremath{#1\rightarrow #2})}
\newcommand{\slritem}[2]{\ensuremath{#1\rightarrow #2}}
\newcommand{\lroitem}[3]{(\ensuremath{#1\rightarrow #2},\;#3)}
\newcommand{\lrstate}[2]{\framed<5pt>{(#1)\begin{array}{l}#2\end{array}}}
\newcommand{\lalroitem}[3]{\ensuremath{#1\rightarrow #2}}
\newcommand{\goto}[3]{\ensuremath{\mbox{\bf goto}(#1,#2)=#3}\quad}
\newcommand{\env}[1]{\ensuremath{\{#1\}}}
\newcommand{\bind}[2]{\ensuremath{#1\mapsto #2}}
\long\def\ignore#1{\relax}
\long\def\onlyslides{}
\long\def\onlynotes#1{\ignore{#1}}
\begin{document}
%\landscape
%
% Ok, start from section 1, not 0
%
\refstepcounter{section}
%
% Title
%
\begin{plaintexslide}
\mbox{}
\vfill
\centershabox{\huge Repr\'esentation interm\'ediaire}
\vfill
\LARGE
  \begin{itemize}
    \item Repr\'esentation interm\'ediaire
            \begin{itemize}
              \item arbres de commandes et expression: d\'efinition
              \item exemples de traduction
              \item simplification
              \item lin\'earisation
              \item traces et ordonnancement
            \end{itemize}
  \end{itemize}
\vfill
\end{plaintexslide}

\begin{texslide}{Code Interm\'ediaire \`a Arbre}
\large
Nous introduisons maintenant le premier langage interm\'ediaire
vers lequel vous allons \emph{traduire} notre langage source.\\
Il s'agit encore d'une repr\'esentation arborescente, mais dans laquelle
les instructions disponibles sont beaucoup plus proches des instructions
machines; on retrouve en effet:
  \begin{itemize}
    \item des \'etiquettes, et des sauts (conditionnels ou pas) \`a des \'etiquettes
    \item des acc\`es m\'emoire
    \item des d\'eplacements des donn\'ees
    \item des op\'erations de comparaison
    \item des op\'erations arithm\'etiques
    \item l'instruction CALL
  \end{itemize}
\end{texslide}

\begin{texslide}{AST du Code Interm\'ediaire \`a Arbre}
\large
\begin{verbatim}
module type TREE = 
sig 
  type label
  type temp
  type stm = SEQ of stm * stm
           | LABEL of label
           | JUMP of exp * label list
           | CJUMP of relop * exp * exp * label * label
           | MOVE of exp * exp
           | EXP of exp
  and exp = BINOP of binop * exp * exp
          | MEM of exp
          | TEMP of temp
          | ESEQ of stm * exp
          | NAME of label
          | CONST of int
          | CALL of exp * exp list
  and binop = PLUS | MINUS | MUL | DIV | AND | OR 
            | LSHIFT | RSHIFT | ARSHIFT | XOR
  and relop = EQ | NE | LT | GT | LE | GE | ULT | ULE | UGT | UGE
end
\end{verbatim}
\end{texslide}
\begin{texslide}{Commentaire}
Voici une description des constructeurs Exp:
  \begin{description}
    \item[expressions ] (exp)
    \begin{itemize}
      \item CONST(i) l'entier $i$ (on codera true comme 1 et false comme 0)
      \item NAME(n) la constante symbolique $n$ (une \'etiquette assembleur)
      \item TEMP(t) le ``registre machine'' $t$
      \item BINOP(op,e,e) les op\'erations \'el\'ementaires
      \item MEM(e) la case m\'emoire d'adresse $e$ (un MOVE(MEM(e),\_) sera une \'ecriture de 
            la case m\'emoire d'adresse $e$, alors que MOVE(\_,MEM(e)) sera la lecture
            de la case MEM(e))
      \item CALL(f,l) appel de la fonction $f$ (argument \'evalu\'e en
            premier), avec param\`etres $l$ (\'evalu\'es de gauche \`a droite)
      \item ESEQ(s,e), la valeur de l'expression $e$ apr\`es l'ex\'ecution de la
            commande $s$
    \end{itemize}
  \end{description}
\end{texslide}
\begin{texslide}{Commentaire}
Voici une description des constructeurs Stm:
  \begin{description}
    \item[commandes ] (stm)
    \begin{itemize}
      \item MOVE(TEMP(t),e) \'evalue $e$ et mets le r\'esultat dans $t$
      \item MOVE(MEM(e1,k),e2) \'evalue $e1$ pour obtenir une adresse m\'emoire
            $a$. Ensuite \'evalue $e2$ et place le r\'esultat dans les $k$ bytes
            \`a partir de $a$
      \item EXP(e) \'evalue $e$, et oublie le r\'esultat
      \item JUMP(e,ls) \'evalue $e$ et saute au r\'esultat. $e$ peut \^etre
            NAME(n) ou un adresse entier. La liste $ls$ est l'ensemble des
            valeurs possibles de $e$ (optionnel, sert pour une analyse du programme)
      \item CJUMP(o,e1,e2,t,f) \'evalue e1, puis e2, et compare les r\'esultats
            avec l'op\'erateur de comparaison $o$. Si $vrai$, saute \`a $t$,
            sinon \`a $f$
      \item SEQ(s1,s2) $s1$, puis $s2$
      \item LABEL(n) d\'efinit l'\'etiquette $n$ \'egale \`a l'adresse courante
    \end{itemize}
  \end{description}
\end{texslide}
\begin{texslide}{Traduction}
La traduction $T$ vers le code interm\'ediaire est longue, mais sans surprises.
Voyons quelques cas, le reste \'etant laiss\'e \`a completer.\\

Mais nous remarquons maintenant que la traduction sera effectu\'ee en ayant
acc\`es pour toute variable simple aux attributs \emph{level} et \emph{offset},
et pour toute fonction \`a l'attribut \emph{level}, calcul\'es comme expliqu\'e avant.\\

On supposera aussi que chaque variable occupe exactement un mot m\'emoire (de taille $W$ bytes,
selon la machine).\\
Aussi, pour les types complexes, ce mot m\'emoire contiendra \emph{un pointeur} vers la structure
allou\'ee dans le tas et pas dans la pile.\\
Ces conventions nous permettent de nous passer de la distinction habituelle entre valeurs
gauches et valeurs droits, qu'il faut quand m\^eme rappeler bri\`evement ici.
\end{texslide}

\begin{texslide}{L-Values (valeurs gauches) et R-values (valeurs droits)}
On distingue en lit\'erature (et notamment dans les manuels C), entre deux
types de valeurs:
  \begin{description}
    \item[L-values] les valeurs qui peuvent appara\^{\i}tre \`a \emph{gauche} 
         d'une affectation, i.e.\  les valeurs qui d\'esignent des cases m\'emoire
         dans lesquelles on peut \'ecrire. En CTigre, c'est le cas de
    \begin{description}
      \item[variables simples] comme $x$
      \item[champs d'enregistrements] comme $a.nom$
      \item[\'el\'ements d'un tableau] comme $a[3+5]$
    \end{description}
    \item[R-values] les valeurs qui peuvent appara\^{\i}tre \`a \emph{droite}
         d'une affectation, c'est \`a dire les expressions qui ont une valeur
         que l'on peut \'ecrire dans des cases m\'emoire.\\
         En CTigre, c'est le cas de tous les L-values, mais aussi d'expressions
         qui ne sont pas L-values:
           \begin{description}
             \item[expressions arithm\'etiques] comme $1+x-32$
             \item[fonctions qui retournent des types de base] comme $succ(1)$
           \end{description}
  \end{description}
\end{texslide}

\begin{texslide}{L-Values (valeurs gauches) et R-values (valeurs droits) (suite et fin)}
Comme les L-values sont les plus souvent aussi des R-values, il est n\'ecessaire de regarder
le contexte pour savoir s'il faut produire du code qui \emph{lit} une valeur depuis la
case m\'emoire, ou du code qui \emph{\'ecrit} une valeur dans la case m\'emoire.\\

Dans le cas de CTigre, nous pouvons \'eviter cette analyse gr\^ace \`a deux hypoth\`eses simples:
  \begin{itemize}
    \item toutes les variables prennent la m\^eme place (cela se fait un for\c{c}ant variables
          de type tableaux et enregistrement \`a contenir un pointeur vers la m\'emoire plut\^ot
          que le tableau ou enregistrement tout entier)
    \item la construction MEM du langage interm\'ediaire ne pr\'ejuge pas de la lecture ou \'ecriture,
          qui est d\'ecid\'ee par le contexte
  \end{itemize}

Dans ce qui suit, la traduction d'une variable simple ou compos\'ee sera donc toujours la m\^eme sans
se soucier de savoir si ell'est en position droite ou gauche.
\end{texslide}

\begin{texslide}{Traduction: Variables}
Le cas des variables:\\
\newcommand{\fpoffset}{\(\underbrace{\mbox{MEM(... MEM(}}_{\mbox{level(g)-l fois}}\)}
La traduction de l'acc\`es \`a une \verb|SimpleVar| de \emph{level} et \emph{offset} $o$ sera la suivante:
  \begin{itemize}
    \item {\bf dans la fonction $f$ qui la d\'eclare (l=level(f))}:\\
      \begin{verbatim}
       MEM(BINOP(MINUS,TEMP(fp),CONST(o))
      \end{verbatim}
    \item {\bf dans une fonction $g$ englob\'ee par $f$ (l=level(f)$<$level(g))}, on suit le liens statique:\\
\Large
\begin{alltt}
 MEM(BINOP(MINUS,(\fpoffset TEMP(fp))...),CONST(o))))
\end{alltt}
  \end{itemize}
\end{texslide}

\begin{texslide}{Traduction: \'el\'ements d'un vecteur}

La traduction de l'acc\`es \`a un \'el\'ement d'un vecteur, $e[e1]$ sera trait\'e comme suit:
\begin{alltt}
MEM(BINOP(PLUS,MEM(T(e)),BINOP(MULT,T(e1),CONST(W))))
\end{alltt}
o\`u $W$ est la taille d'une case m\'emoire (2 ou 4 bytes d'habitude), et $T(e), T(e1)$
sont les traductions de $e$ et $e1$.
\end{texslide}

\begin{texslide}{Traduction: boucles}
La traduction de \verb| while b do c done| sera
  \begin{verbatim}
   SEQ(LABEL(n),
       SEQ(CJUMP(EQ,T(b),CONST(1),cont,done),
           SEQ(LABEL(cont),
               SEQ(T(c),
                   SEQ(JUMP(test),LABEL(done))))))
  \end{verbatim}
\end{texslide}
\begin{texslide}{Traduction: boucle while}

La traduction de \verb|  while b do c done| est plus  simple de la visualiser de
la fa\c{c}on suivante.


\begin{verbatim}
test:
       CJUMP(EQ,T(b),CONST(1),cont,done)
cont:  T(c)
       JUMP test
done:
\end{verbatim}
\end{texslide}
\begin{texslide}{Traduction: Appel d'une fonction}
La traduction d'un appel de fonction \verb|f(a1,...,an)| est imm\'ediate
      \begin{verbatim}
       CALL(NAME(lf),[sl,T(a1),...,T(an)])
      \end{verbatim}
Mais avec en plus le liens statique $sl$ qui est ajout\'e en param\`etre.\\
On vous rappelle que pour calculer $sl$ il vous faut le \emph{level} de
$f$ (connu, parce que vous l'avez d\'ej\`a calcul\'e) et celui de la fonction $g$ qui appelle $f$
(facile \`a conna\^{\i}tre, parce-que vous \^etes en train de traduire $g$ en ce moment).
\end{texslide}

\begin{texslide}{Traduction: d\'eclaration de variable et fonction}
  \begin{description}
    \item[variable]
La d\'eclaration d'une variable \verb|let a:=e in ...| produira une expression qui initialise
cette variable (dans le bloc d'activation courant \`a \emph{offset} connu) avec T(e).
\begin{verbatim}
	MOVE(T(a),T(e))
\end{verbatim}
    \item[fonction] 
La d\'eclaration d'une fonction produira une \'etiquette $lf$ qui est associ\'ee \`a la s\'equence d'instructions
pour le prologue, suivie de la traduction du corps de la fonction, et de l'\'epilogue.\\
\emph{Important:} la traduction d'une fonction produit un nouveau Tree.stm
  \end{description}
\end{texslide}

\begin{texslide}{Traduction des cha\^{\i}nes de caract\`eres}

Une cha\^{\i}ne  de caract\`eres est normalement  traduite en  langage d'assemblage par
une \'etiquette rep\'erant l'adresse d'une directive sp\'eciale  suivie du texte de la
cha\^{\i}ne, que l'assembleur traduira ensuite en une s\'equence de mots,
termin\'es ou pas par un byte \`a z\'ero, dans une zone m\'emoire sp\'eciale (g\'en\'eralement
appel\'ee section ``data'').\\

Dans le cas de l'\'emulateur SPIM, vous trouvez par exemple des fragments de code comme

\begin{verbatim}
.data
bonjour:  
	.asciiz "Bonjour tout le monde!\n"
\end{verbatim}

Les op\'erations utilisant cette cha\^{\i}ne de caract\`eres feront r\'ef\'erence \`a l'\'etiquette
assembleur {\tt bonjour}.
\end{texslide}

\begin{texslide}{Traduction: utilisation de EXP et ESEQ}
\Large
Dans notre langage interm\'ediaire, une ``expression'' (type {\tt exp}) est un arbre d'instructions
qui retourne une valeur, alors que un ``statement'' (type {\tt stm}) est un arbre d'instructions
ne rendant pas de valeur.\\

Mais il y a des situations, pendant la traduction, qui nous obligent \`a utiliser l'un pour traduire
l'autre et vice-versa.\\

Voyons quelques exemples d'utilisation de EXP et ESEQ:\\

  \begin{description}
    \item[EXP] on utilise cette conversion pour les ``programmes'' constitu\'es d'une expression.\\
               C'est le cas, par exemple, du programme CTigre
\begin{verbatim}
            3+4
\end{verbatim}
	       qui \'evalue l'expression mais ne fait rien de son r\'esultat.
    \item[ESEQ] on utilise cette conversion quand, pour calculer une valeur, on a besoin
                d'effectuer d'abord une s\'erie d'instructions.\\ C'est le cas de
  \begin{itemize}
    \item la traduction des op\'erateurs bool\'eens
    \item l'initialisation de variables de type structur\'e (tableaux, enregistrements)
  \end{itemize}
  \end{description}
\end{texslide}
\begin{texslide}{ESEQ et op\'erateurs bool\'eens}
En langage machine, les op\'erateurs de  comparaison comme $\geq, \leq$, etc. sont
souvent  disponibles \emph{seulement} pour permettre  un   branchement lors d'un  saut,
donc, on ne peut pas traduire:
\begin{verbatim}
	a+b <= 32
\end{verbatim}
par une {\tt exp}ression
\begin{verbatim}
	BINOP(LT, .. , ..)
\end{verbatim}

Ce fait  est bien mis  en \'evidence dans notre  langage interm\'ediaire par le fait
que les  op\'erateurs de  relation  comme LT, GT, EQ,   NE etc.  sont  utilisables
seulement  dans  l'instruction interm\'ediaire $CJUMP(op,e1,e2,t,f)$,  qui saute a
l'\'etiquette $t$ ou $f$ selon que l'op\'eration $op$ sur $e_1$  et $e_2$ a r\'esultat
vrai ou faux.\\
\end{texslide}

\begin{texslide}{ESEQ et op\'erateurs bool\'eens (suite et fin)}
Cela nous conduit \`a une traduction qui n\'ecessite l'utilisation de ESEQ.

Pour traduire
\[
	exp_1\quad op\quad exp_2
\]
avec $op$ op\'erateur de comparaison, nous allons produire d'abord 
la s\'equence d'instructions
\begin{verbatim}
        CJUMP(op,T(exp1),T(exp2),l0,l1)
        LABEL l0
        MOVE(TEMP t, CONST 1)
        JUMP (NAME l2)
        LABEL l1
        MOVE(TEMP t,CONST 0)
        LABEL l2
\end{verbatim}
avec $l1,l2,l3$ des nouvelles \'etiquettes et $t$ un nouveau nom
de ``registre temporaire''. \`A la fin de cette suite d'instructions, nous
retrouvons dans le temporaire $t$ la valeur correspondante \`a la comparaison
(1 pour vrai et 0 pour faux). On peut alors, \`a l'aide de ESEQ, r\'ecup\'erer la
valeur de $t$.\\

Tr\`es pr\'ecis\'ement, la traduction sera

\begin{verbatim}
   ESEQ(
    SEQ(CJUMP(op,T(exp1),T(exp2),L0,L1),
     SEQ(LABEL L0,
      SEQ(MOVE(TEMP t,CONST 1),
       SEQ(JUMP(NAME L2),
        SEQ(LABEL L1,
         SEQ(MOVE(TEMP t,CONST 0),
          LABEL L2)))))),
    TEMP t)),
\end{verbatim}
\end{texslide}

\begin{texslide}{ESEQ et types structur\'es}
\Large
Supposons maintenant d'avoir \`a traduire un fragment comme celui-ci

\begin{verbatim}
      type  arrtype = array of int in
      let   arr1:arrtype := arrtype [10] of 0
\end{verbatim}

Au moment  de la  traduction  de la variable   {\tt arr1}, nous  devons produire
d'abord  une suite  d'instructions qui allouera   dans le  tas  l'espace m\'emoire
n\'ecessaire pour contenir le tableau de 10 entiers,  puis initialiser chaque case
\`a 0 et ensuite retourner comme traduction de la  variable un ``pointeur'' sur le
d\'ebut  de ce tableau, c'est   \`a dire l'adresse de  la  premi\`ere case m\'emoire  du
tableau.\\

\`A nouveau, nous  avons besoin d'utiliser ESEQ, mais  aussi de faire appel  \`a une
fonction externe (de syst\`eme),  qui sait allouer  de la m\'emoire  dans le tas. Le
nom de cette fonction et  la fa\c{c}on dont  on l'appelle d\'ependent \'evidemment de la
machine   pour laquelle on  compile (par  exemple,  sur le  simulateur SPIM vous
disposez d'un appel  syst\`eme  {\tt sbrk} accessible par  l'instruction  sp\'eciale
{\tt syscall}).\\ Par simplicit\'e, ici on utilisera le nom {\tt malloc} et on
supposera que l'on puisse appeler cette fonction comme une fonction CTigre quelconque.\\

\end{texslide}

\begin{texslide}{ESEQ et types structur\'es}
\large
Alors, la traduction de

\begin{verbatim}
      type  arrtype = array of int in
      let   arr1:arrtype := arrtype [10] of 0
\end{verbatim}

sera la suite d'instructions

\begin{verbatim}
 ESEQ(
  SEQ(MOVE(TEMP t, CALL(NAME malloc, CONST 10*W)),
   SEQ(MOVE(MEM(BINOP(PLUS,TEMP t,CONST 0*W), CONST 0)),
       .
       .
       .
       SEQ(MOVE(MEM(BINOP(PLUS,TEMP t,CONST 9*W), CONST 0)))...)) ,
  TEMP t)
\end{verbatim}

{\bf Remarque}: dans ce code, $W$ est la taille du mot en bytes (sur les machines
                modernes, c'est au moins 2, souvent 4 et quelque fois 8 (Alpha)).
                Aussi, les multiplications dans les CONST ici sont faites \`a la
                compilation, en connaissant $W$, ce n'est pas partie de la syntaxe
                du code interm\'ediaire!

De m\^eme pour les enregistrements.
\end{texslide}


\begin{texslide}{Une pause de reflection}
Avant de proc\'eder, r\'efl\'echissons \`a ce que l'on est en train de faire: nous avons
pris un  programme en entr\'ee  (sous forme d'arbre  de  syntaxe abstraite typ\'e et
annot\'e avec les attributs \emph{level} et \emph{offset}), et nous le traduisons
maintenant vers du code interm\'ediaire.\\

Lors de cette traduction, on  est confront\'es \`a  un certain nombre de d\'etails qui
d\'ependent de la machine cible: le num\'ero du registre  qui contient le FP (30 sur
MIPS) ou  le SP, la taille  d'un mot en  m\'emoire  (4 sur  MIPS), les conventions
d'\'emission des cha\^{\i}nes de caract\`eres,  d'appel des  fonctions de librairie  etc.
Il serait bien de garder ces d\'ependances group\'ees dans un module bien identifi\'e.
\end{texslide}

\begin{texslide}{Une pause de reflection (suite)}
De plus, le r\'esultat de cette traduction n'est pas un seul {\tt Tree.stm}, mais plut\^ot
\emph{une liste} de \emph{fragments} de code distincts:
  \begin{itemize}
    \item un fragment pour le corps du programme principal
    \item un fragment pour toute d\'efinition de fonction (ce fragment
          contient le prologue, le corps et l'\'epilogue de la fonction)
    \item un fragment pour toute cha\^{\i}ne de caract\`ere dans le programme
          (celui ci on ne le traduira pas en Code Interm\'ediaire, mais
           on le gardera dans la liste pour la phase d'\'emission d'assembleur)
  \end{itemize}
\end{texslide}

\begin{texslide}{Une pause de reflection (fin)}
Aussi, le code interm\'ediaire que nous produisons n'est pas, tel quel, pr\^et
\`a \^etre converti vers du langage machine.\\

  \begin{itemize}
    \item on souhaite pouvoir produire le code pour \'evaluer
          une expression dans n'importe lequel ordre (notamment pour
          minimiser le nombre de registres n\'ecessaires pour l'\'evaluer).
          Mais certaines configurations d'un arbre de code interm\'ediaire font
          en sorte que l'ordre d'\'evaluation devient \emph{significatif} en
          g\'en\'eral:
    \begin{itemize}
      \item les noeuds ESEQ dans une Tree.exp (ils peuvent produire des effets
            de bord)
      \item des noeuds CALL dans une Tree.exp (idem)
    \end{itemize}
    \item dans les compilateurs modernes, on renvoie souvent le (pointeur sur le) r\'esultat
          dans un m\^eme registre; il est donc mieux de sauvegarder imm\'ediatement le
          r\'esultat d'une CALL dans un autre registre (sauf si ce r\'esultat est ignor\'e,
          pour les proc\'edures, quand CALL est fils de EXP).
    \item les instructions CJUMP du code interm\'ediaire peuvent sauter
          \`a deux adresses diff\'erents, alors que les sauts conditionnels
          en langage machine ont toujours l'instruction suivante comme
          \'etiquette de saut en cas de \'echec.
  \end{itemize}
\end{texslide}

\begin{texslide}{Transformations du Code Interm\'ediaire}

On peut toujours convertir du code interm\'ediaire dans du code interm\'ediaire
qui n'a pas les inconv\'enients cit\'es ci-dessus.\\

{\bf D\'efinition} Un arbre \emph{canonique} est un arbre de code interm\'ediaire
tel que 
  \begin{itemize}
    \item il n'y a pas de noeuds ESEQ
    \item le p\`ere des noeuds CALL est toujours
          soit un EXP soit un MOVE(TEMP t, \_).
  \end{itemize}

On va d\'efinir une premi\`ere transformation, qui transforme tout arbre en arbre
canonique.\\

\end{texslide}

\begin{texslide}{Mise en forme canonique}

Cette transformation est bas\'ee sur une id\'ee tr\`es simple:

  \begin{itemize}
    \item on remplace tout appel de fonction CALL qui n'est pas d\'ej\`a le fils
          d'un EXP ou un MOVE(TEMP t,\_) par la s\'equence \'equivalente
\begin{verbatim}
          ESEQ(MOVE(TEMP t, CALL(f,el)), TEMP t)
\end{verbatim}
    \item on fait remonter tout ESEQ qui se trouve \`a l'int\'erieur d'une expression,
	  jusqu'en haut, o\`u le ESEQ peut se convertir en SEQ; pour cela, on
	  peut \^etre emmen\'es \`a introduire des nouveaux temporaires pour 
          les expressions qui ne commutent pas avec les commandes que
          l'on fait remonter
  \end{itemize}
\end{texslide}

\begin{texslide}{Remont\'ee des ESEQ (I)}
Voyons un exemple: le fragment
%
\begin{verbatim}
BINOP(PLUS,
      ESEQ(s,e1),
      e2)
\end{verbatim}
%
peut \^etre remplac\'e par le fragment \'equivalent
%
\begin{verbatim}
ESEQ(s,
     BINOP(PLUS,
           e1,
           e2)
    )
\end{verbatim}
\end{texslide}

\begin{texslide}{Remont\'ee des ESEQ (II)}
Par contre, le fragment
%
\begin{verbatim}
BINOP(PLUS,
      e1,
      ESEQ(s,e2)
     )
\end{verbatim}
%
peut \^etre remplac\'e par le fragment
%
\begin{verbatim}
ESEQ(s,
     BINOP(PLUS,
           e1,
           e2)
    )
\end{verbatim}
\emph{seulement} si $s$ et $e1$ \emph{commutent} (i.e.\ si le fait d'executer
$s$ puis $e1$ ou $e1$ puis $s$ ne change pas la s\'emantique du programme).\\
Si on ne sait pas prouver la commutation, on doit introduire un nouveau
temporaire $t$ et utiliser le fragment (toujours \'equivalent):
\begin{verbatim}
ESEQ(MOVE(TEMP t, e1),
     ESEQ(s,
          BINOP(PLUS,
                TEMP t,
                e2)
         )
     )
\end{verbatim}
\end{texslide}
\begin{texslide}{Remont\'ee des ESEQ (III)}
\LARGE
Pour toute possible configuration contenant un ESEQ \`a l'int\'erieur, on peut 
donner un fragment de code \'equivalent o\`u l'ESEQ a soit disparu soit \'et\'e
remont\'e vers la racine.\\
Voici quelques autres exemples:\\
  \begin{tabular}{|cc|}
   \hline
   Le fragment & est remplac\'e par\\ \hline
   MEM(ESEQ(s,e) & ESEQ(s,MEM(e))\\
   JUMP(ESEQ(s,e) & ESEQ(s,JUMP(e))\\
   CJUMP(op,ESEQ(s,e1),e2,t,f) & ESEQ(s,CJUMP(s,e1,e2,t,f))\\
   MOVE(TEMP t,ESEQ(s,e)) & ESEQ(s,MOVE(TEMP t,e))\\\hline
  \end{tabular}
\end{texslide}
\begin{texslide}{Remont\'ee des ESEQ (IV)}
\LARGE
Et, si $s$ et $e$ commutent,\\
  \begin{tabular}{|cc|}
   \hline
   Le fragment & est remplac\'e par\\ \hline
   BINOP(op,e1,ESEQ(s,e)) & ESEQ(s,BINOP(op,e1,e))\\
   CJUMP(op,e1,ESEQ(s,e),t,f) & ESEQ(s,CJUMP(s,e1,e,t,f))\\\hline
  \end{tabular}

Et s'ils ne commutent pas, \\
  \begin{tabular}{|cc|}
   \hline
   Le fragment & est remplac\'e par ($t$ nouveau temporaire)\\ \hline
   BINOP(op,e1,ESEQ(s,e)) & ESEQ(MOVE(TEMP t, e1),ESEQ(s,BINOP(PLUS,TEMP t,e)))\\
   CJUMP(op,e1,ESEQ(s,e),t,f) & ESEQ(MOVE(TEMP t, e1),ESEQ(s,CJUMP(s,TEMP t,e,t,f))\\\hline
  \end{tabular}

{\bf Exercice}: compl\'etez l'ensemble de r\`egles.
\end{texslide}

\begin{texslide}{Remont\'ee des ESEQ (V)}
Une fois les ESEQ arriv\'es en t\^ete, on peut les remplacer par des SEQ, sans
probl\`eme:
\begin{verbatim}
EXP(ESEQ(s,e))
\end{verbatim}
devient
\begin{verbatim}
SEQ(s,EXP(e))
\end{verbatim}
et en g\'en\'eral, 
\begin{verbatim}
EXP(ESEQ(s1,ESEQ(s2,...ESEQ(sn,e))...))
\end{verbatim}
devient
\begin{verbatim}
SEQ(s1,SEQ(s2,...,SEQ(sn,EXP(e))...))
\end{verbatim}
Enfin, les SEQ en t\^ete, on peut les repr\'esenter simplement
comme une liste.
\end{texslide}
\begin{texslide}{R\'e\'ecriture}
Un ensemble de r\`egle comme celui que l'on vient de voir donne
lieu, une fois ferm\'e par contexte, \`a ce que l'on appelle un
\emph{syst\`eme de r\'e\'ecriture}, qui est \'etudi\'e en informatique
th\'eorique, o\`u l'on donne des m\'ethode pour montrer que un ensemble
de r\`egle \emph{termine} (i.e.\ le programme qui op\`ere la transformation
finit toujours) et est \emph{confluent} (i.e.\ peu importe l'ordre
d'application des r\`egles, l'arbre canonique est toujours le m\^eme).\\
Vous pourriez en savoir plus, par exemple, en suivant les cours du
DEA Programmation \`a Paris VII.
\end{texslide}
\begin{texslide}{Remont\'ee des ESEQ: alternative}
On peut aussi remarquer que l'application de ces r\`egles 
revient \`a extraire de tout arbre d'expression $e$ les 
instructions $s1,\ldots{},sn$ produisant des effets de bord et
encapsul\'ees dans des ESEQ(si,ej).\\
Cela produira une s\'equence de Tree.stm,
suivie d'une Tree.exp sans effets de bord.\\
Au cours de cette extraction, il se peut que l'on rencontre, comme on l'a
vu, des expressions qui ne commutent pas avec une instruction que l'on veut
remonter, et alors on passe l'expression dans la partie instruction en
introduisant un nouveau temporaire qui remplace l'expression.\\
\end{texslide}
\begin{texslide}{Remont\'ee des ESEQ: code de l'alternative}
En suivant cette deuxi\`eme approche, on obtient le programme (d\^u \`a Appel,
mais mis en Ocaml par mes soins), suivant (j'admets qu'il ne s'agit pas
d'un exemple lumineux de clart\'e):
{\tiny
\begin{verbatim}
module T = Tree
let linearize (stm0: T.stm) : T.stm list =
        (* A partir d'un Tree.stm, produit une liste d'arbres canoniques t.q.
              1.  il n'y a pas de SEQ ou ESEQ
              2.  Le pere d'une CALL est un EXP(..) ou un MOVE(TEMP t,..)  *)
 let (%) a b = (* simplification: on oublie les EXP(e) dans les SEQ *)
               (* cette d\'efinition introduit un op\'erateur *INFIXE*  *)
   match (a,b) with ((T.EXP(T.CONST _)),x) -> x
   | (x, (T.EXP(T.CONST _))) -> x        
   | (x,y) -> T.SEQ(x,y)

 and commute = function (* approximation minimaliste de commute *)
      (T.EXP(T.CONST _), _) -> true
    | (_, T.NAME _) -> true
    | (_, T.CONST _) -> true
    |  _ -> false

 and nop = T.EXP(T.CONST 0) (* stm trivial sans effet *)

 in let rec reorder = function 
      (* transforme une liste d'exp en une liste de
         stm, puis une liste de exp sans effets de bord *)
      ((T.CALL _ as e)::rest) -> (* ici la transformation des CALL *)
        let t = Temp.new_temp()
         in reorder(T.ESEQ(T.MOVE(T.TEMP t, e), T.TEMP t) :: rest)
    | (a::rest) ->
         let (stms,e) = do_exp a
         and (stms',el) = reorder rest
         in if commute(stms',e) then (stms % stms',e::el)
            else let t = Temp.new_temp() (* si \c{c}a ne commute pas ... *)
                 in (stms % T.MOVE(T.TEMP t, e) % stms', T.TEMP t :: el)
    | [] -> (nop,[])

  and reorder_exp (el,build) = let (stms,el') = reorder el
                               in (stms, build el')

  and reorder_stm (el,build) = let (stms,el') = reorder (el)
                               in stms % build(el')

  and do_stm = function (* canonicalize un stm *)
      (T.SEQ(a,b)) -> do_stm a % do_stm b
    | (T.JUMP(e,labs)) -> reorder_stm([e],fun [e] -> T.JUMP(e,labs))
    | (T.CJUMP(p,a,b,t,f)) -> reorder_stm([a;b], fun[a;b]-> T.CJUMP(p,a,b,t,f))
    | (T.MOVE(T.TEMP t,T.CALL(e,el))) -> 
         reorder_stm(e::el,fun (e::el) -> T.MOVE(T.TEMP t,T.CALL(e,el)))
    | (T.MOVE(T.TEMP t,b)) -> reorder_stm([b],fun[b]->T.MOVE(T.TEMP t,b))
    | (T.MOVE(T.MEM e,b)) -> reorder_stm([e;b],fun[e;b]->T.MOVE(T.MEM e,b))
    | (T.MOVE(T.ESEQ(s,e),b)) -> do_stm(T.SEQ(s,T.MOVE(e,b))) (* ici le travail *)
    | (T.EXP(T.CALL(e,el))) -> reorder_stm(e::el,fun (e::el) -> T.EXP(T.CALL(e,el)))
    | (T.EXP e) -> reorder_stm([e],fun[e]->T.EXP e)
    |  s -> reorder_stm([],fun[]->s)

  and do_exp = function (* canonicalize une exp *)
      (T.BINOP(p,a,b)) -> reorder_exp([a;b], fun[a;b]->T.BINOP(p,a,b))
    | (T.MEM(a)) -> reorder_exp([a], fun[a]->T.MEM(a))
    | (T.ESEQ(s,e)) -> (* encore du travail *)
           let stms = do_stm s
           and  (stms',e) = do_exp e
            in (stms%stms',e)
    | (T.CALL(e,el)) -> reorder_exp(e::el, fun (e::el) -> T.CALL(e,el))
    |  e -> reorder_exp([],fun[]->e)

  (* linear elimine les SEQ en haut de l'arbre, en produisant une liste *)
  in 
    let rec linear = function (T.SEQ(a,b),l) -> linear(a,linear(b,l))
                            | (s,l) -> s::l
 in (* le corps de linearize *)
    linear(do_stm stm0, [])
\end{verbatim}
}
\end{texslide}

\begin{texslide}{Blocs de base}
Une fois notre arbre mis en forme canonique, nous nous retrouvons avec une liste
d'instructions et expressions sans effets de bord, et il nous reste \`a traiter la
deuxi\`eme  diff\'erence entre  code  interm\'ediaire et  assembleur: les  \emph{deux}
\'etiquettes de CJUMP.\\

Nous  souhaitons r\'eordonner  la liste  d'instructions pour  essayer de  faire en
sorte que la deuxi\`eme \'etiquette d'un  CJUMP apparaisse juste apr\`es le CJUMP dans
la liste (quand cela ne sera pas possible, on introduira des nouvelles
\'etiquettes).\\
\end{texslide}
\begin{texslide}{Blocs de base}
Pour pouvoir r\'eordonner notre code sans changer la signification du programme,
nous devons d'abord le d\'ecouper en \emph{blocs de base}.

{\bf D\'efinition}: un bloc de base est une s\'equence d'instruction ayant les
propri\'et\'es suivantes:
  \begin{itemize}
    \item la premi\`ere instruction est un LABEL
    \item la derni\`ere instruction est un JUMP ou un CJUMP
    \item il n'y a pas d'autres LABEL, JUMP ou CJUMP dans le bloc
  \end{itemize}
Pour produire une liste de blocs de base \`a partir d'une liste d'instructions,
il suffit de parcourir la liste, et cr\'eer un nouveau bloc d\'es que l'on rencontre
un LABEL, et de le terminer d\'es que l'on rencontre un JUMP ou CJUMP.\\
Si on se trouve avec un bloc sans LABEL initial, on cr\'ee une nouvelle \'etiquette
que l'on met en t\^ete de ce bloc. Si on trouve un bloc qui ne se termine pas
avec un JUMP ou CJUMP, on rajoute un JUMP vers l'\'etiquette du nouveau bloc.
\end{texslide}
\begin{texslide}{Algorithme BasicBlocks}
Voil\`a le code OCaml
{\small%\normalsize
\begin{verbatim}
type block = T.stm list

let basicBlocks stms = 
 let donel = Temp.new_label() in 
 let rec blocks = 
      function
        ((T.LABEL _ as head) :: tail, blist) ->
           let rec next = function 
                (((T.JUMP _) as s)::rest, thisblock)
                  -> endblock(rest, s::thisblock)
             | (((T.CJUMP _)as s )::rest, thisblock)
                  -> endblock(rest, s::thisblock)
             | ((T.LABEL lab :: _) as stms, thisblock) 
                  -> next(T.JUMP(T.NAME lab,[lab]) :: stms, thisblock)
             | (s::rest, thisblock) -> next(rest, s::thisblock)
             | ([], thisblock) 
                  -> next([T.JUMP(T.NAME donel, [donel])], thisblock)
           and endblock(stms, thisblock) = 
               blocks(stms, List.rev thisblock :: blist)
           in next(tail, [head])
       | ([], blist) -> List.rev blist
       | (stms, blist) -> blocks(T.LABEL(Temp.new_label())::stms, blist)
  in (blocks(stms,[]), donel)
\end{verbatim}
}
\end{texslide}
\begin{texslide}{Traces}
\Large
Une fois que nous avons notre liste de blocs de base, on peut les r\'earranger
dans n'importe quel ordre, parce que les sauts et les \'etiquettes garantissent
que le flot du contr\^ole sera toujours le bon.\\
On peut profiter de cette propri\'et\'e pour chercher un ordre de rearrangement
qui r\'esout notre probl\`eme de doubles \'etiquettes.\\

{\bf D\'efinition} Une \emph{trace} est une s\'equence d'instructions (y compris
sauts et saut conditionnels) qui peuvent \^etre ex\'ecut\'es cons\'ecutivement lors 
de l'ex\'ecution du programme.\\

Un programme poss\`ede multiples traces, dont plusieurs s'intersectent,
mais nous cherchons ici \`a construire un ensemble de traces qui couvre
exactement, et sans r\'ep\'etition, tout le programme. Nous cherchons aussi \`a
maximiser le nombre de JUMP ou CJUMP suivi par une des leurs \'etiquettes,
ce qui permettra un peu d'optimisation ensuite.\\
\end{texslide}
\begin{texslide}{Trouver les traces: un algorithme simple}
\Large
Pour trouver cet ensemble de traces, en commen\c{c}ant avec une liste L de blocs
de bases, on peut utiliser ce simple algorithme:
  \begin{alltt}
    tant que L n'est pas vide faire
       initialiser une nouvelle trace vide T
       enlever l'\'el\'ement de t\^ete de L, le mettre dans a
       tant que a n'est pas marque faire
            marquer a
            ajouter a \`a la trace T
            examiner les successeurs de a
            s'il y a un successeur c non marque
            alors a <- c
       fin faire
       clore la trace T
    fin faire
  \end{alltt}
\end{texslide}
\begin{texslide}{\'Etape finale}
\Large
Une fois obtenu l'ensemble de traces, nous pouvons le transformer
\`a nouveau en une liste d'instructions, et ensuite examiner cette
liste pour quelques op\'erations de finalisation:
  \begin{itemize}
    \item tout CJUMP qui est suivi par l'\'etiquette correspondante \`a la branche
          false est d\'ej\`a correcte
    \item pour tout CJUMP qui est suivi par l'\'etiquette correspondante \`a la branche
          true, on \'echange ses \'etiquettes true et false et on remplace le test
          par son compl\'ementaire (EQ par NE, LT par GE etc.)
    \item pour tout CJUMP(op,e1,e2,t,f) qui n'est suivi par aucune des ses deux
          \'etiquettes t et f, on invente une nouvelle \'etiquette f' et on le
          remplace par la s\'equence:
\begin{verbatim}
          CJUMP(op,e1,e2,t,f')
          LABEL f'
          JUMP(NAME f)
\end{verbatim}
    \item tout JUMP suivi imm\'ediatement par son \'etiquette est \'elimin\'e
  \end{itemize}
Une fois cela fait, tout CJUMP est suivi par son \'etiquette false et on n'a
pas de JUMP imm\'ediatement suivis par leur \'etiquette.\\

{\bf Remarque}: un compilateur industriel chercherait \`a trouver un ensemble de
trace qui minimise les sauts dans les sections critiques du code (boucle, etc.).
\end{texslide}
\begin{texslide}{Conclusions}
Nous avons, \`a la fin de ce cours, pu produire une s\'equence d'instructions en
code interm\'ediaire qui n'a pas d'effets de bord dans les expressions et qui
est assez proche de l'assembleur pour pouvoir \^etre convertie ais\'ement dans
une repr\'esentation interm\'ediaire de plus bas niveau (une sorte de assembleur
abstrait), comme nous verrons dans le cours prochain.
\end{texslide}
\end{document}


