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).
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 invariante si chaque évaluation donnera le même résultat: elle peut dépendre d'autres variables si elles sont des invariantes (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])
simplifier les expressions (et les tests):
pas un exemple de variables d'induction!
i=exp; while(i>j) équivaut à i=exp-j; while(i>0)
si j est une invariante
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).
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).