Optimisation du judas - Peephole optimization

L'optimisation du judas est une technique d'optimisation réalisée sur un petit ensemble d'instructions générées par le compilateur; le petit ensemble est connu comme le judas ou la fenêtre.

L'optimisation du judas consiste à changer le petit ensemble d'instructions en un ensemble équivalent offrant de meilleures performances.

Par exemple:

  • au lieu de pousser le registre A sur la pile, puis de replacer immédiatement la valeur dans le registre A, une optimisation du judas supprimerait les deux instructions;
  • au lieu d'ajouter A à A, une optimisation du judas pourrait effectuer un décalage arithmétique vers la gauche;
  • au lieu de multiplier un registre à virgule flottante par 8, une optimisation de judas pourrait mettre à l'échelle l'exposant du registre à virgule flottante par 3; et
  • au lieu de multiplier un index par 4, d'ajouter le résultat à une adresse de base pour obtenir une valeur de pointeur, puis de déréférencer le pointeur, une optimisation de judas peut utiliser un mode d'adressage matériel qui produit le même résultat avec une instruction.

Le terme optimisation du judas a été introduit par William Marshall McKeeman en 1965.

Règles de remplacement

Techniques courantes appliquées à l'optimisation des judas:

  • Null séquences - Supprimez les opérations inutiles.
  • Combiner les opérations - Remplacez plusieurs opérations par un équivalent.
  • Lois algébriques - Utilisez des lois algébriques pour simplifier ou réorganiser les instructions.
  • Instructions pour cas spéciaux - Utilisez des instructions conçues pour les cas d'opérandes spéciaux.
  • Opérations en mode adresse - Utilisez les modes d'adresse pour simplifier le code.

Il peut y avoir d'autres types d'optimisations de judas.

Exemples

Remplacement des instructions lentes par des instructions plus rapides

Le bytecode Java suivant 

...
aload 1
aload 1
mul
...

peut être remplacé par 

...
aload 1
dup
mul
...

Ce type d'optimisation, comme la plupart des optimisations de judas, fait certaines hypothèses sur l'efficacité des instructions. Par exemple, dans ce cas, on suppose que l' dup opération (qui duplique et pousse le haut de la pile ) est plus efficace que l' aload X opération (qui charge une variable locale identifiée comme X et la pousse sur la pile).

Suppression du code redondant

Un autre exemple consiste à éliminer les magasins de charge redondants. 

 a = b + c;
 d = a + e;

est directement implémenté comme 

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add  c to the register, the register is now b+c
MOV R0, a  ; Copy the register to a
MOV a, R0  ; Copy a to the register
ADD e, R0  ; Add  e to the register, the register is now a+e [(b+c)+e]
MOV R0, d  ; Copy the register to d

mais peut être optimisé pour 

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add c to the register, which is now b+c (a)
MOV R0, a  ; Copy the register to a
ADD e, R0  ; Add e to the register, which is now b+c+e [(a)+e]
MOV R0, d  ; Copy the register to d

Suppression des instructions de pile redondante

Si le compilateur enregistre les registres sur la pile avant d'appeler un sous-programme et les restaure lors du retour, les appels consécutifs aux sous-programmes peuvent avoir des instructions de pile redondantes.

Supposons que le compilateur génère les instructions Z80 suivantes pour chaque appel de procédure: 

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR
 POP HL
 POP DE
 POP BC
 POP AF

S'il y avait deux appels de sous-programmes consécutifs, ils ressembleraient à ceci: 

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 POP HL
 POP DE
 POP BC
 POP AF
 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

La séquence POP regs suivie de PUSH pour les mêmes registres est généralement redondante. Dans les cas où il est redondant, une optimisation judas supprimerait ces instructions. Dans l'exemple, cela entraînerait l'apparition d'une autre paire POP / PUSH redondante dans le judas, et celles-ci seraient supprimées à leur tour. En supposant que le sous-programme _ADDR2 ne dépend pas des valeurs de registre précédentes, la suppression de tout le code redondant dans l'exemple ci-dessus finirait par laisser le code suivant: 

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

Mise en œuvre

Les compilateurs modernes implémentent souvent des optimisations de judas avec un algorithme de correspondance de modèles .

Voir également

Les références

Liens externes

La définition du dictionnaire de l' optimisation du judas chez Wiktionary