\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 11}
\end{center}
\hrule


\ex
\item Construire le graphe de flot de contr\^ole ${\cal G}$ pour 
le code suivant.
\begin{verbatim}
    while d > 0 do
            a := b + c;
            d := d - b;
            e := a + f;
            if e # 0 then 
               f := a - d;
               b := d + f
            else 
               e := a - c
            fi;
            b := a + c
     od;
\end{verbatim}
\item Calculer l'ensemble des variables actives pour chaque bloc, 
sachant qu'aucune variable n'est utilisée après ce code.
\item Quelles sont les variables que vous avez envie de ranger dans 
des registres?
\exe


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% O P T I M I S A T I O N   D E S   B O U C L E S 
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ex
{\bf Optimisation des boucles}\\
Considérons le programme de multiplication de matrices suivant ({\tt N} est une constante, 
les matrices {\tt a}, {\tt b} et {\tt c} sont allouées statiquement:
\begin{verbatim}
 pour i := 1 a N faire
    pour j := 1 a N faire
       pour k := 1 a N faire
          c[i,j] := a[i,k]*b[k,j]
\end{verbatim}

\begin{enumerate} 
\item
  \label{simple}
  Produire le code à
  trois adresses pour ce programme.
\item
  Construire un graphe de flot de contrôle à partir des instructions à
  trois adresses.
\item
  Éliminer les sous-expressions communes de chaque bloc de base.
\item
  Trouver les boucles dans le graphe de flot de contrôle.
\item
  Déplacer les invariants des boucles à l'extérieur de celles-ci.
\item \label{opt}
  Déterminer les variables d'induction de chaque boucle et les
  éliminer quand c'est possible.
\item
  Produire du code machine cible à partir du résultat des questions
  \ref{simple} et \ref{opt} et comparer les codes obtenus.
\end{enumerate}
\exe

\end{document}