Option Traduction de Programmes
TD mardi 20 avril
Optimisation
- 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.''
- Expliquer pourquoi il est impossible de donner un algorithme
pour trouver toutes les variables d'induction selon cette
définition.
- 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.
- Quelle serait une définition plus raisonnable?
- Donner un algorithme efficace pour trouver un sous-ensemble
utile le plus large possible des variables d'induction (selon
votre définition).
- 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.
-
- 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).
- 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.