Génération de code (compilateur)

En informatique , la génération de code fait partie de la chaîne de processus d'un compilateur , dans laquelle une représentation intermédiaire du code source est convertie en un format (par exemple, un code machine ) qui peut être facilement exécuté par le système cible.

Les compilateurs sophistiqués effectuent généralement plusieurs passes sur différentes formes intermédiaires. Ce processus en plusieurs étapes est utilisé parce que de nombreux algorithmes d' optimisation de code sont plus faciles à appliquer un par un, ou parce que l'entrée d'une optimisation repose sur le traitement terminé effectué par une autre optimisation. Cette organisation facilite également la création d'un seul compilateur qui peut cibler plusieurs architectures, car seule la dernière des étapes de génération de code (le backend ) doit passer d'une cible à l'autre. (Pour plus d'informations sur la conception du compilateur, voir Compilateur .)

L'entrée du générateur de code consiste généralement en un arbre d'analyse ou un arbre de syntaxe abstraite . L'arbre est converti en une séquence linéaire d'instructions, généralement dans un langage intermédiaire tel qu'un code à trois adresses . Les étapes ultérieures de compilation peuvent ou non être appelées « génération de code », selon qu'elles impliquent ou non un changement significatif dans la représentation du programme. (Par exemple, une passe d'optimisation de judas ne serait probablement pas appelée « génération de code », bien qu'un générateur de code puisse incorporer une passe d'optimisation de judas.)

En plus de la conversion de base d'une représentation intermédiaire en une séquence linéaire d'instructions machine, un générateur de code typique essaie d'optimiser le code généré d'une manière ou d'une autre.

Les tâches qui font généralement partie de la phase de « génération de code » d'un compilateur sophistiqué incluent :

• Sélection des instructions : quelles instructions utiliser.
• Ordonnancement des instructions : dans quel ordre placer ces instructions. L'ordonnancement est une optimisation de la vitesse qui peut avoir un effet critique sur les machines pipelines .
• Allocation de registres : l'allocation de variables aux registres du processeur
• Déboguer la génération de données si nécessaire afin que le code puisse être débogué .

La sélection d'instructions est généralement effectuée en effectuant une traversée post-ordre récursive sur l'arbre de syntaxe abstraite, en faisant correspondre des configurations d'arbre particulières à des modèles ; par exemple, l'arbre peut être transformé en une séquence linéaire d'instructions en générant de manière récursive les séquences pour et , puis en émettant l'instruction . W := ADD(X,MUL(Y,Z))t1 := Xt2 := MUL(Y,Z)ADD W, t1, t2

Dans un compilateur qui utilise un langage intermédiaire, il peut y avoir deux étapes de sélection d'instructions : une pour convertir l'arbre d'analyse en code intermédiaire, et une deuxième phase beaucoup plus tard pour convertir le code intermédiaire en instructions à partir du jeu d'instructions de la machine cible. Cette deuxième phase ne nécessite pas de parcours d'arbre ; elle peut être effectuée de manière linéaire et implique généralement un simple remplacement des opérations du langage intermédiaire par leurs opcodes correspondants . Cependant, si le compilateur est en fait un traducteur de langage (par exemple, un qui convertit Java en C++ ), la deuxième phase de génération de code peut impliquer la construction d'un arbre à partir du code intermédiaire linéaire.

Lorsque la génération de code se produit au moment de l'exécution , comme dans la compilation juste-à-temps (JIT), il est important que l'ensemble du processus soit efficace en termes d'espace et de temps. Par exemple, lorsque des expressions régulières sont interprétées et utilisées pour générer du code au moment de l'exécution, une machine à états finis non déterministe est souvent générée au lieu d'une machine déterministe, car la première peut généralement être créée plus rapidement et occupe moins d'espace mémoire que la seconde. Bien qu'elle génère généralement du code moins efficace, la génération de code JIT peut tirer parti des informations de profilage qui ne sont disponibles qu'au moment de l'exécution.

La tâche fondamentale qui consiste à prendre des données d'entrée dans une langue et à produire des données de sortie dans une langue non trivialement différente peut être comprise en termes d' opérations de transformation fondamentales de la théorie formelle des langages . Par conséquent, certaines techniques initialement développées pour être utilisées dans les compilateurs sont désormais également utilisées d'autres manières. Par exemple, YACC (Yet Another Compiler-Compiler ) prend des données d'entrée au format Backus-Naur et les convertit en un analyseur en C. Bien qu'il ait été créé à l'origine pour la génération automatique d'un analyseur pour un compilateur, yacc est également souvent utilisé pour automatiser l'écriture de code qui doit être modifié à chaque fois que les spécifications sont modifiées.

De nombreux environnements de développement intégrés (IDE) prennent en charge une certaine forme de génération automatique de code source , utilisant souvent des algorithmes communs avec les générateurs de code du compilateur, bien que généralement moins compliqués. (Voir également : Transformation de programme , Transformation de données .)

En général, un analyseur syntaxique et sémantique tente de récupérer la structure du programme à partir du code source, tandis qu'un générateur de code utilise ces informations structurelles (par exemple, les types de données ) pour produire du code. En d'autres termes, le premier ajoute des informations tandis que le second en perd une partie. Une conséquence de cette perte d'informations est que la réflexion devient difficile, voire impossible. Pour contrer ce problème, les générateurs de code intègrent souvent des informations syntaxiques et sémantiques en plus du code nécessaire à l'exécution.