Optimisation du judas

L'optimisation par judas est une technique d'optimisation effectuée sur un petit ensemble d' instructions générées par le compilateur , appelé judas ou fenêtre, qui consiste à remplacer les instructions par un ensemble logiquement équivalent qui a de meilleures performances.

Par exemple:

• Au lieu de pousser un registre sur la pile, puis de réinsérer immédiatement la valeur dans le registre, supprimez les deux instructions
• Au lieu de multiplier x par 2, faitesx + x
• Au lieu de multiplier un registre à virgule flottante par 8, ajoutez 3 à l'exposant du registre à virgule flottante

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

Les remplacements d’optimisation du judas incluent, sans s’y limiter :

• Séquences nulles – Supprimer les opérations inutiles
• Combiner des opérations – Remplacer plusieurs opérations par une seule équivalente
• Lois algébriques – Utilisez les lois algébriques pour simplifier ou réorganiser les instructions
• Instructions pour cas spéciaux – Utilisez des instructions conçues pour des cas d'opérandes spéciaux
• Opérations en mode d'adresse – Utilisez les modes d'adresse pour simplifier le code

Les compilateurs modernes implémentent souvent des optimisations de type peephole avec un algorithme de correspondance de motifs .

Le bytecode Java suivant :

à charger 1 à charger 1 beaucoup 

peut être remplacé par ce qui suit qui s'exécute plus rapidement :

à charger 1 dup beaucoup 

Comme pour la plupart des optimisations de type peephole, cela est basé sur l'efficacité relative des différentes instructions. Dans ce cas, dup(qui duplique et pousse le haut de la pile ) est connu/supposé être plus efficace que (qui charge une variableaload locale et la pousse sur la pile).

Le code source suivant :

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

est simplement compilé comme suit :

MOV b , R0 ; Copier b dans le registre ADD c , R0 ; Ajouter c au registre, le registre est maintenant b+c MOV R0 , a ; Copier le registre dans a MOV a , R0 ; Copier a dans le registre ADD e , R0 ; Ajouter e au registre, le registre est maintenant a+e [(b+c)+e] MOV R0 , d ; Copier le registre dans d

mais peut être optimisé pour :

MOV b , R0 ; Copier b dans le registre ADD c , R0 ; Ajouter c au registre, qui est maintenant b+c (a) MOV R0 , a ; Copier le registre dans a ADD e , R0 ; Ajouter e au registre, qui est maintenant b+c+e [(a)+e] MOV R0 , d ; Copier le registre dans d

Si le compilateur enregistre les registres sur la pile avant d'appeler une sous-routine et les restaure lors du retour, les appels consécutifs aux sous-routines 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 APPEL _ADRESSE POP HL POP DE POP BC POP AF

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

PUSH AF PUSH BC PUSH DE PUSH HL APPEL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL APPEL _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ù elle est redondante, une optimisation du 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 la sous-routine _ADDR2 ne dépende pas des valeurs de registre précédentes, la suppression de tout le code redondant dans l'exemple ci-dessus laisserait finalement le code suivant :

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