Quelles sont quelques astuces pour optimiser le code d'assemblage généré par un compilateur?

Question

Je suis actuellement en train d'écrire un compiler et j'ai l'impression d'avoir eu quelques problèmes pour l'obtenir en code de sortie qui s'exécute dans un délai décent.

Un bref aperçu du compilateur:

7Basic est un compilateur qui vise à compiler le code 7Basic directement en code machine pour l'architecture cible/plate-forme. Actuellement, 7Basic génère un assemblage x86 avec un fichier source.

Le problème est que le code assembleur généré par le compilateur est lent et inefficace.

Par exemple, le code this (qui se compile jusqu'au code d'assembly this) est 80,47 fois plus long à exécuter que the equivalent C code.

Une partie du problème est que le compilateur génère le code comme le suivant:

push eax 
push 5000000 
pop ebx 
pop eax 

Au lieu de plus logique:

mov ebx,5000000 

... qui accomplit la même chose.

Ma question est: quelles sont les techniques pour éviter ce genre de problème? L'analyseur utilise essentiellement récursion pour analyser les expressions, de sorte que le code généré reflète cela.

Answer 1

Une technique est appelée peephole optimisation. Cela nécessite une approche itérative pour nettoyer le code d'assemblage. Essentiellement, vous parcourez le code de l'assemblage, en regardant seulement deux ou trois instructions à la fois, et voyez si vous pouvez les réduire en quelque chose de plus simple. Par exemple,

push eax  ; 1 
push 5000000 ; 2 
pop ebx   ; 3 
pop eax   ; 4 

La première étape se pencherait sur les lignes 2 et 3, et le remplacer par:

push eax  ; 1 
mov ebx,5000000 ; 2a 
pop eax   ; 4 

Deuxièmement, vous pourriez envisager 1 et 4, et si eax est pas touché dans la instruction moyenne, les supprimer à la fois, en laissant ce que vous voulez:

mov ebx,5000000 ; 2a 

Answer 2

vous pouvez envisager de générer du code C plutôt que de l'assemblage puis laisser un compilateur C (gcc) gérer le code g l'énonciation pour vous. Il ne sert à rien d'essayer de réinventer la roue.

Answer 3

Il existe un certain nombre de raisons pour lesquelles un générateur de code particulier peut émettre la séquence d'instructions que vous avez listée. Le plus probable est que le générateur de code que vous utilisez n'essaye pas vraiment d'émettre du code optimal. Ce modèle de code émis me suggère que votre générateur de code ne sait pas que le x86 a des instructions "mov immédiates" qui incorporent directement la valeur constante dans le flux d'instructions. L'encodage x86 pour les opcodes avec des valeurs immédiates peut être un peu compliqué (longueur variable R/M octets) mais cela est déjà requis si vous voulez utiliser de nombreuses instructions x86.

Ce code émis suggère également que le générateur de code ne sait pas que EAX n'est pas modifié par les instructions EBX. C'est comme si le codegen était piloté par un modèle plutôt que par une logique discrète.

Ce type de code se produit lorsque la représentation intermédiaire interne des opérations du compilateur n'est pas suffisamment détaillée pour représenter toutes les facettes de l'architecture cible. Cela est particulièrement vrai si l'architecture du générateur de code a été conçue à l'origine pour un jeu d'instructions RISC mais a été modifiée pour émettre des instructions x86. L'architecture RISC a tendance à avoir des instructions reg/reg très peu nombreuses et très simples, tandis que le jeu d'instructions x86 a évolué organiquement au fil des décennies pour inclure une grande variété d'opcodes qui fonctionnent directement sur la mémoire, et tout un tas d'autres choses. Si la représentation intermédiaire du compilateur (graphe d'expression) est câblée pour RISC, il sera difficile de faire grimper la grande variété et les subtilités de x86.

Answer 4

Je suis en train de suivre un cours de compilateur pour le moment. J'ai fait de grands progrès dans la production de code efficace, mais vous devriez regarder dans le livre du dragon. C'est un rite de passage. Vous devriez jeter un coup d'œil au code du livre de Jeremy Bennett, Introduction aux techniques de compilation: Un premier cours utilisant ANSI C, LEX et YACC. Le livre lui-même est très difficile à trouver, mais vous pouvez télécharger le code source pour le compilateur libre de

http://www.jeremybennett.com/publications/download.html

Le fichier générateur de code (cg.c) a des fonctions pour générer du code assez optimisé. La langue cible n'est pas i386, mais vous devriez envisager de regarder comment il décrit les registres et garder trace de l'endroit où les entrées de la table de symboles sont stockées. Son ensemble de sortie pourrait être encore optimisé, mais il fournit une excellente base pour produire du code qui pourrait rivaliser avec la sortie de gcc -S à certains égards.

Une optimisation générale consisterait à soustraire le pointeur de la pile à l'espace de réserve pour toutes les variables locales et temporaires lors de l'entrée d'une fonction. Ensuite, il suffit de référencer les décalages au lieu de constamment pousser/éclater. Par exemple, si votre code intermédiaire est une liste de quadruples, vous devez simplement passer par l'itérateur pour chaque fonction et garder une trace du décalage maximal. Ensuite, affichez la ligne pour soustraire la quantité d'espace sur la pile. Cela supprime le besoin d'activer et de désactiver tant de variables. Pour supprimer le besoin de les déplacer, vous pouvez simplement déplacer leur valeur de leur décalage sur la pile dans un registre. Cela améliorera considérablement les performances.

Answer 5

Les optimisations de judas aideront, mais un problème évident est que votre compilateur n'effectue pas l'allocation de registre!

http://en.wikipedia.org/wiki/Register_allocation

Si vous souhaitez obtenir des niveaux sérieux de performance, vous faites devoir examiner cette question. Cela peut se faire en un seul passage si vous le faites avidement "à la volée".