OPTIMISATION
à lucarne (``Peephole'')

Petites optimisations plus ou moins locales qui seraient évidentes à un être humain; améliorations à l'intérieur d'un bloc de base ou analyse triviale du flot de contrôle.
peut être effectuée au niveau du code intermédiaire ou du code objet.

Exemples

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..

LES BOUCLES

Deuxième source très importante d'améliorations:

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)

Les invariants

Ceci veut dire ici les variables et expressions dont la valeur ne change pas à cause des affectations dans la boucle

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.

L'UTILISATION DE REGISTRES

En général, à la fin d'un bloc de base on doit stocker les valeurs dans les registres si (i) les valeurs sont les valeurs de variables, (ii) ces variables ne contiennent pas leurs propres valeurs et (iii) il existe la possibilité d'utiliser cette valeur de la variable sans passer par un bloc de base qui lui en affecte une autre.

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.

VARIABLES D'INDUCTION (DES BOUCLES)

Souvent des variables sont incrémentées par une constante à chaque itération d'une boucle. s'il y a plusieurs de ces variables la valeur de chacune est donnée par une fonction (linéaire) de la valeur d'une autre.

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)

BOUCLES COMPRISES DE PLUSIEURS BLOCS DE BASE

Une suite de blocs qui a plusieurs sorties possibles ne change pas grand-chose.

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

OPTIMISATION GLOBALE

Des optimisations qui dépendent des interactions entre plusieurs blocs de base

Une optimisation est possible si quelque chose est arrivée avant l'entrée de ce bloc ou va arriver après la fin

Nécessite une analyse des chemins possibles dans le graphe

[Supposition pas forcément vraie mais sans danger que chaque chemin dans le graphe correspond à une suite d'exécutions de blocs]

Cette analyse serait triviale si les programmes n'avaient pas de boucles ...

LES OPTIMISATIONS

LES ENSEMBLES A CALCULER

UTILISER CES ENSEMBLES

LES EQUATIONS

UN EXEMPLE: LES VARIABLES VIVANTES

Di: l'ensemble de variables vivantes au début de bloc numéro i
Fi: idem à la fin
Ui: les variables utilisées en bloc i (avant d'être définies)
Ci: les variables changées en bloc i (avant d'être utilisées)


Fi = Èj successeur de i Dj


Di = Fi ÈUi - Ci

Nous voulons la solution minimale

RESOUDRE LES EQUATIONS

LES COMPLICATIONS

On doit prendre un point de vue conservateur: ne faire que les optimisations qui ne pourraient pas changer l'effet d'un programme (tant que cet effet est défini?!)




File translated from TEX by TTH, version 3.05.
On 19 Apr 2005, 11:32.