Pour compléter un peu : traditionnellement le front-end s'occupe de l'analyse lexicale (« l'orthographe »), de l'analyse syntaxique (« la grammaire ») et de l'analyse sémantique (analyse des types, etc.).
Il y a très peu d'optimisations faites dans les 2 premières phases, qui se bornent à vérifier que le programme est bien formé. Ceci étant dit, faire une séparation claire de l'analyse lexicale et syntaxique est bien niveau « génie logiciel » mais peut avoir un mauvais impact sur les performances du compilateur lui-même. Du coup certains compilateurs entrelacent les deux phases pour accélérer l'analyse du programme (Clang fait ça si je me souviens bien; je ne sais pas/plus pour GCC).
Le front-end produit un arbre de syntaxe abstraite (AST), qui, lui, peu être « décoré » pendant la phase d'analyse sémantique. Cette dernière est la seule des trois phases du front-end (à ma connaissance) qui apporte non seulement un aspect feedback pour le programmeur via des erreurs de compilations (« tu ne peux pas affecter un entier à une chaîne de caractères : pas les mêmes types »), mais aussi qui peut potentiellement effectuer certaines optimisations grâce à une connaissance poussée du système de types, ou bien à la reconnaissance de motifs dans l'AST (par exemple, le compilateur d'Intel reconnaît les formes simples d'opérations d'algèbre linéaire, et va remplacer une boucle naïve par un appel à la fonction qui va bien dans la bibliothèque mathématique qui vient avec le compilateur).
Puis vient le middle-end : dans cette partie, on part d'un AST, et on construit une représentation intermédiaire (« IR » : GIMPLE pour GCC, et un code à trois adresse pour LLVM1, qui est essentiellement une forme de langage d'assemblage « générique »/abstrait). C'est ici que la plupart des transformations optimisantes de haut niveau sont effectuées (déroulage, fusion, fission de boucle; suppression de code mort; propagation de constantes; etc.). À la sortie du middle-end, on se retrouve avec une représentation intermédiaire substantiellement modifiée.
Enfin, vient le back-end, qui se charge de générer du code. À ce niveau, on doit savoir quel processeur on vise. Traditionnellement il y a trois phases : sélection d'instructions, ordonnancement d'instructions, et allocation des registres. La première se charge d'associer des morceaux de la représentation intermédiaire à une instruction particulière. Par exemple, si dans mon IR j'ai quelque chose du genre :
mul$r2,$r2,$r3add$r1,$r1,$r2
... Alors, en fonction du jeu d'instruction de la machine cible, je vais peut-être simplement copier-coller ces deux lignes, ou bien, si l'architecture a une instruction « fused multiply-add », je vais la sélectionner et générer le code suivant :
fma$r1,$r2,$r3
... Ce qui me fait économiser une instruction et sans doute un ou deux cycles processeur.
Une fois que j'ai sélectionné les instructions à exécuter, il faut que je décide dans quel ordre je vais les déclencher. L'idée étant qu'on veut recouvrir les latences mémoire par des calculs, tout en préservant les dépendances de données. À ce niveau, on considère qu'on a un nombre infini de registres à notre disposition.
Enfin, on passe à l'allocation de registres. Dans cette phase, on associe un ordonnancement donné, qui utilise un nombre infini de registres au jeu de registres réel de la machine. Ça implique d'ajouter du code pour sauvegarder/restorer les valeurs contenues dans les registres lorsqu'il n'y a plus de place (on fait « déborder les valeurs des registre en mémoire— aka « register spill »).
En règle générale, il y a un aller-retour entre phase d'ordonnancement et phase d'allocation de registres, puisque du code est rajouté et peu du coup influer sur l'ordonnancement initial.
Il y a tout plein d'optimisations qui peuvent être effectuées au niveau du back-end et qui sont spécifiques à l'architecture, comme par exemple l'optimisation du « voyeur » / « trou de serrure » (« peephole optimisation »).
si je suis trop imprécis, voire incorrect, n'hésitez pas à me corriger ! ↩
[^] # Re: Dommage alors
Posté par lasher . En réponse au journal LLVM se fait de vieux os ? La recherche pour rester jeune.. Évalué à 10.
Pour compléter un peu : traditionnellement le front-end s'occupe de l'analyse lexicale (« l'orthographe »), de l'analyse syntaxique (« la grammaire ») et de l'analyse sémantique (analyse des types, etc.).
Il y a très peu d'optimisations faites dans les 2 premières phases, qui se bornent à vérifier que le programme est bien formé. Ceci étant dit, faire une séparation claire de l'analyse lexicale et syntaxique est bien niveau « génie logiciel » mais peut avoir un mauvais impact sur les performances du compilateur lui-même. Du coup certains compilateurs entrelacent les deux phases pour accélérer l'analyse du programme (Clang fait ça si je me souviens bien; je ne sais pas/plus pour GCC).
Le front-end produit un arbre de syntaxe abstraite (AST), qui, lui, peu être « décoré » pendant la phase d'analyse sémantique. Cette dernière est la seule des trois phases du front-end (à ma connaissance) qui apporte non seulement un aspect feedback pour le programmeur via des erreurs de compilations (« tu ne peux pas affecter un entier à une chaîne de caractères : pas les mêmes types »), mais aussi qui peut potentiellement effectuer certaines optimisations grâce à une connaissance poussée du système de types, ou bien à la reconnaissance de motifs dans l'AST (par exemple, le compilateur d'Intel reconnaît les formes simples d'opérations d'algèbre linéaire, et va remplacer une boucle naïve par un appel à la fonction qui va bien dans la bibliothèque mathématique qui vient avec le compilateur).
Puis vient le middle-end : dans cette partie, on part d'un AST, et on construit une représentation intermédiaire (« IR » : GIMPLE pour GCC, et un code à trois adresse pour LLVM1 , qui est essentiellement une forme de langage d'assemblage « générique »/abstrait). C'est ici que la plupart des transformations optimisantes de haut niveau sont effectuées (déroulage, fusion, fission de boucle; suppression de code mort; propagation de constantes; etc.). À la sortie du middle-end, on se retrouve avec une représentation intermédiaire substantiellement modifiée.
Enfin, vient le back-end, qui se charge de générer du code. À ce niveau, on doit savoir quel processeur on vise. Traditionnellement il y a trois phases : sélection d'instructions, ordonnancement d'instructions, et allocation des registres. La première se charge d'associer des morceaux de la représentation intermédiaire à une instruction particulière. Par exemple, si dans mon IR j'ai quelque chose du genre :
... Alors, en fonction du jeu d'instruction de la machine cible, je vais peut-être simplement copier-coller ces deux lignes, ou bien, si l'architecture a une instruction « fused multiply-add », je vais la sélectionner et générer le code suivant :
... Ce qui me fait économiser une instruction et sans doute un ou deux cycles processeur.
Une fois que j'ai sélectionné les instructions à exécuter, il faut que je décide dans quel ordre je vais les déclencher. L'idée étant qu'on veut recouvrir les latences mémoire par des calculs, tout en préservant les dépendances de données. À ce niveau, on considère qu'on a un nombre infini de registres à notre disposition.
Enfin, on passe à l'allocation de registres. Dans cette phase, on associe un ordonnancement donné, qui utilise un nombre infini de registres au jeu de registres réel de la machine. Ça implique d'ajouter du code pour sauvegarder/restorer les valeurs contenues dans les registres lorsqu'il n'y a plus de place (on fait « déborder les valeurs des registre en mémoire— aka « register spill »).
En règle générale, il y a un aller-retour entre phase d'ordonnancement et phase d'allocation de registres, puisque du code est rajouté et peu du coup influer sur l'ordonnancement initial.
Il y a tout plein d'optimisations qui peuvent être effectuées au niveau du back-end et qui sont spécifiques à l'architecture, comme par exemple l'optimisation du « voyeur » / « trou de serrure » (« peephole optimisation »).
si je suis trop imprécis, voire incorrect, n'hésitez pas à me corriger ! ↩