\input{format1.tex}
  \input{intro1.tex}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}


\begin{document}

\noindent \Large {\bf Université d'Orléans} \hfill {\bf Maîtrise d'Informatique}

\normalsize

\begin{center}
{\it Feuille de Travaux Dirigés 9}
\end{center}
\hrule

\vspace{0.5cm}

\noindent {\bf La machine cible\,:}\,machine \`a registres, adressable par 
octets avec 
des mots de 4 octets et $n$ registres g\'en\'eraux $R_0,~R_1,\ldots,~R_{n-1}$.
Elle poss\`ede des instructions \`a 2 adresses de la forme\,:
\[op \hspace*{.2in} source,~destination\]
dans laquelle $op$ est un code op\'eration, et $source$ et $destination$ sont 
des champs de donn\'ees. Ex\,:\\
\begin{itemize}
\item MOV (charger $source$ dans $destination$)
\item ADD (ajouter $source$ \`a $destination$)
\item SUB (soustraire $source$ \`a $destination$)
\end{itemize}

\noindent {\bf Les modes d'adressage\,:}\,(contenu($a$) d\'enote le contenu du 
registre ou de l'emplacement m\'emoire repr\'esent\'e par $a$).\\
\begin{tabular}{llll}\\
Mode & Format & Adresse & Co\^ut additionnel \\
absolu & M & M & 1\\
registre & R & R & 0 \\
index\'e & c(R) & c+contenu(R) & 1 \\
registre indirect & *R & contenu(R) & 0 \\
indirect index\'e & *c(R) & contenu(c + contenu(R)) & 1
\end{tabular}

\vspace*{2 mm}
\noindent {\bf Le co\^ut des instructions\,:}\,c'est la somme des co\^uts des 
modes d'adressage(r\'ef\'erenc\'es par des co\^uts additionnels dans les 
tableaux) augment\'ee de 1. Ce co\^ut correspond \`a la longueur (en mots) de 
l'instruction. Les modes d'adressage impliquant les registres ont un co\^ut 
\'egal \`a 0, tandis que les co\^uts aff\'erant \`a un emplacement en m\'emoire 
ou \`a un litt\'eral ont un co\^ut de 1, parce que de tels op\'erandes doivent 
\^etre sp\'ecifi\'es dans un mot additionnel \`a l'instruction.


\ex
Traduire l'expression arithm\'etique $a * -(b + c)$ en\,:
\begin{itemize}
\item un arbre abstrait\,;
\item du code \`a 3 adresses.
\item du code à 2 adresses.
\end{itemize}
\exe

\ex
Traduire l'expression $-(a + b) * (c + d) + (a + b + c)$ en\,:
\begin{itemize}
%\item quadruplets\,;
\item DAG.
\item code \`a 2 adresses\,;
\end{itemize}
\exe

\ex
Traduire les instructions ex\'ecutables du programme C suivant\,:
\begin{verbatim}
main()
{
   int i;
   int a[10];
   i = 0;
   while (i < 10)
   {
       a[i] = 0;
       i = i + 1;
   }
}
\end{verbatim}
en\,:
\begin{itemize}
\item un arbre abstrait\,;
\item du code \`a 2 adresses.
\end{itemize}
\exe

\ex
Traduire l'instruction d'affectation\,:
\[A[i, j] := B[i,j] + C[A[k,l]] + D[i+j] \]
en code \`a 2 adresses pour les d\'eclarations suivantes\,:\\
var $A,~B\, :\, array[0..10, 1..5]$ of integer;\\
\hspace*{.1in} $C,~D\,:\,array[1..15]$ of integer;
\exe

\ex
En C, l'instruction {\em for} a la forme suivante\,:
\[for~(e_1\,;\,e_2\,;\,e_3)~ins\]
Elle a la m\^eme signification que\,:
\begin{verbatim}
e1;
while (e2) {
    ins;
    e3;
}
\end{verbatim}
Construire une d\'efinition dirig\'ee par la syntaxe pour traduire les 
instructions \'ecrites \`a la mani\`ere de C en code \`a 3 adresses. On suppose 
qu'une instruction \`a 3 adresses peut \^etre \'etiquet\'ee symboliquement et 
que la fonction {\em NouvEtiq} retourne une nouvelle \'etiquette symbolique 
\`a chaque fois qu'elle est appel\'ee.\\
\exe

\ex
Proposer un algorithme qui d\'etermine
le nombre de registres n\'ecessaires \`a la production de code \`a partir 
d'un arbre abstrait.

\smallskip
D\'eterminer le nombre de registres n\'ecessaires pour les instructions\,:
\begin{itemize}
\item $x = a + b * c$
\item $x = a / (b + c) - d * (e + f)$
\end{itemize}
\exe


\end{document}