LDT $1, $5, 0
LDT $2, $5, 0
STT, $1, $5, 1
LDT, $1, $5, 1
ADD $2, $1, 0
ADD $1, $1, 1
ADD $1, $1, 5
MULU $1, $2, 32
SLU $1, $2, 5
ADD $1, $2, $2
JMP L
L: ...
JMP M
...
M: JMP B..
Définition d'une boucle à partir du graphe des blocs de base: un sous-graphe fortement connexe avec une seule entrée (et une façon de rentrer).
Quels sont les boucles imbriquées??
(évident dans le programme initial; ne l'est plus)
Mais noter les instructions du type PBZ $X, RA de MMIX
L'entrée est un bloc de base qui en ``domine'' tous les autres.
Important parce qu'il y a souvent des optimisations intéressantes et l'effet dynamique peut être très important (parce qu'il y aura plusieurs itérations).
Des instructions du programme de départ qui sont
textuellement
dans une boucle ne sont forcément pas dans la boucle selon
cette définition
(si elles sont exécutées après la décision
de sortir)
Optimisation: calculer les valeurs une seule fois (dans un nouveau bloc le ``pré-en-tête'' de la boucle). Peut-être affecter ces valeurs à leur destination finale. Si possible laisser ces valeurs dans des registres pendant toute l'exécution de la boucle.
Plus précisément une expression est une invariant si chaque évaluation donnera le même résultat: elle peut dépendre d'autres variables si elles sont des invariants (et ont déjà reçu leur valeur): algorithme assez simple pour les trouver.
A la fin d'une itération d'une boucle on peut très souvent supprimer ces opérations, c'est-à-dire on peut les déplacer à l'extérieur.
optimisations:
réduire leur nombre: si i est j+5;
peut-être
supprimer i et remplacer A[i] par A'[j]
(A' un pointer à A[5])
remplacer des multiplications par des additions: peut-être
j:=2*i est remplacé par j:=j+2 après
initialisation
de j
(cas très commun où une variable d'induction est
utilisée pour
indiçage
dans un tableau).
exemple d'utilisation d'information sur les invariants
i=exp; while(i>j) équivaut à i=exp-j;
while(i>0)
si j est une invariant (et i n'est pas
utilisée ailleurs)
S'il y a plusieurs retours à la tête ou généralement plusieurs ordres possibles d'exécuter les blocs, il devient plus compliqué de décider:
On aborde la question de l'analyse des flots (des données).