Option Traduction de Programmes
TD mardi 20 avril
Optimisation

  1. La section § 10.7 du dragon définit: ``Une variable x est une variable d'induction d'une boucle L si, chaque fois que la variable x change de valeur elle est incrémentée ou décrémentée par une constante.''

    1. Expliquer pourquoi il est impossible de donner un algorithme pour trouver toutes les variables d'induction selon cette définition.
    2. Expliquer pourquoi les valeurs de deux variables d'induction selon cette définition ne sont pas forcément reliées par une fonction linéaire.
    3. Quelle serait une définition plus raisonnable?
    4. Donner un algorithme efficace pour trouver un sous-ensemble utile le plus large possible des variables d'induction (selon votre définition).
    5. Si deux variables sont des variables d'induction selon la définition du dragon, et elles sont dans le même bloc de base, elles sont forcément reliées par une fonction linéaire et les optimisations associées aux variables d'induction sont peut-être toujours valables entre elles mais pas entre elles et d'autres variables. Donner une méthode de chercher plusieurs ``familles'' de variables telles que ces optimisations sont valables entre toutes les variables d'une même famille.

    1. Expliquer pourquoi
      while (E)
      {
      x=0;
      Inst;
      }

      et
      x=0;
      while (E)
      {
      Inst;
      }

      ne sont pas forcément équivalents (même quand Inst ne contient pas d'autres affectations à x).
    2. Montrer qu'on peut quand même générer du code raisonnable qui évite de répéter l'affectation x=0; si l'expression E est simple.



File translated from TEX by TTH, version 3.05.
On 20 Apr 2004, 13:38.