Option Traduction de Programmes

TD mercredi 4 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.”

(a) Expliquer pourquoi il est impossible de donner un algorithme pour trouver toutes les variables d’induction selon cette définition.

(b) 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.

(c) Quelle serait une définition plus raisonnable?

(d) Donner un algorithme efficace pour trouver un sous-ensemble utile le plus large possible des variables d’induction (selon votre définition).

2. (a) 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).

(b) 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.