Je réagis bien plus tard, mais les vacances étant finies, je peux enfin procrastiner au boulot ! :)
Dans les faits, pour écrire ce morphisme, on le décompose en fonctions distinctes et séparées aux rôles spécifiques, et on l'obtient par composition. Que certains groupes de fonctions se nomment backend et frontend _ (voire _middle-end d'après la réponse de lasher) était le sens de ma question initiale. Cela semble relever du vocabulaire du génie logiciel, soit de l'ingénierie, vocabulaire que je ne connais pas spécialement.
Deux choses :
Si un compilateur est dit « optimisant » alors il y a 99,99% de chances qu'il y ait un middle-end1. Il y a deux raisons à ça, et ton intuition est la bonne, l'une d'elle est liée au génie logiciel (séparation des fonctions, encapsulation, etc.). Cependant, je pense qu'il y a aussi une raison plus théorique, liée à la notion de préservation de la sémantique de programme que tu as bien décrite. Et encore comme tu le décris, c'est lié à la notion de composition. Le middle-end travaille uniquement sur une représentation abstraite du langage. À ce niveau, il s'agit (en exagérant pas mal) de considérer le programme comme un graphe (et d'ailleurs, plusieurs graphes sont construits/modifiés lors de cette phase : graphe de flot de données, graphe de flot de contrôle, etc.). GCC et LLVM utilisent aussi une transformation qui en elle-même n'est pas optimisante, mais qui permet de simplifier la détection de cas d'optimisation : l'affectation unique et statique (static single assignment, SSA). Pour faire simple, tu prends un programme impératif/procédural, qui accepte donc par définition les effets de bord (et l'affectation de valeurs successives à une variable), et tu le transforme en programme qui va indicer les variables à chaque nouvelle affectation. Je te passe les détails2, mais ça permet d'identifier assez vite si du code est mort (càd, qu'on ne peut jamais l'exécuter), si une variable est affectée une seule fois durant toute sa vie (et s'il s'agit d'une affectation par constante, on peut alors la remplacer directement par sa valeur), etc. Dans le cas de (nids de) boucles, il existe tout un tas de techniques pour manipuler l'espace d'itération tant qu'il est linéaire, et qui mène à des transformations franchement peu intuitives lorsqu'on voit le résultat final, mais qui sont complètement logiques dès lors qu'on pige les fondements du modèle polyédrique (et qu'on a des bases relativement solides en algèbre linéaire). Et bien entendu, aucune optimisation n'est correcte si elle accélère l'exécution d'un programme sans en préserver la justesse/exactitude (correctness en anglais).
Concernant le vocabulaire spécifique « génie logiciel » ton intuition est la bonne, et la raison est pragmatique. Tu peux écrire ton propre compilateur assez « simplement » en passant par Flex/Bison (et pendant longtemps le front-end de GCC faisait exactement ça). Si tu ne prends pas le temps de faire les choses bien, alors tu peux « directement » générer du code (C ou assembleur, etc.) depuis le lexer ou le parser (analyseur lexical ou syntaxique). C'est d'ailleurs plus ou moins ce que je fais faire aux étudiants (construction d'un interpréteur de « Cminus », puis génération de code assembleur au lieu d'interprétation du code à l'exécution). Mais ce faisant, à moins d'être vraiment rigoureux, du coup tu te retrouves avec un mélange d'analyse lexicale, syntaxique, et sémantique (Flex/Bison séparent analyse lexicale et syntaxique, et donnent des outils pour le typage, mais ces derniers sont « mélangés » au reste du code) et de génération de code, ce qui rend les choses tout bonnement impossibles à démêler lorsque tu cherches à garantir de façon sûre, portable, et générale qu'une optimisation de code est valide. En séparant en le compilateur en front/middle/back end, pour reprendre ton post, tu passes par la composition de « fonctions », en effet. La première transforme un langage spécifique en représentation générique (langage → AST); la deuxième prend une représentation générique, la transforme en une représentation intermédiaire, puis opère des transformations « isomorphes » sur cette dernière (quelque part, seul le middle-end effectue réellement des transformations de ce genre, car on opère plusieurs passes qui prennent une IR et retournent une IR); la dernière prend une IR et la transforme en code machine/assembleur. On se retrouve donc avec une cible spécifique. Sans cette séparation claire entre front/middle/back end, il y a des risques d'appliquer des transformations « au mauvais moment3 » — en bref, on est obligé d'être plus conservateur dans l'application des transformations.
Mon deuxième point répond en partie à cette phrase :
Après, une représentation intermédiaire, pour moi, c'est juste le domaine d'arrivée (puis de définition) d'une des fonctions qui composent le compilateur.
(c'est moi qui grasse œuf corse)
Justement, ;-) ça va plus loin que ça selon moi. Il y a une séparation nette entre les phases qui ont des effets de bord (front-end, back-end), et celles qui n'en ont pas (le middle-end), à l'exception du changement de représentation. Même dans le back-end on cherche le plus possible à garder des abstractions (sinon les itérations entre ordonnancement d'instruction et allocation de registre seraient infernales à gérer, surtout si on considère certaines optimisations de bas-niveau qui ne peuvent se faire qu'à ce moment).
Bref, ça ne contredit pas ton interprétation (qui est somme toute correcte), mais je voulais renforcer le « pourquoi » on architecture un compilateur ainsi. Au passage, ça permet aussi à LLVM de proposer une interface pour insérer ses propres passes d'optimisation dans le middle-end, et ça explique aussi pourquoi pendant longtemps GCC avait le back-end et le front-end « mélangés » pour des raisons idéologiques (pour éviter que les efforts de la communauté du libre soient fagocités par des éditeurs propriétaires qui brancheraient leur middle/back end proprio en dessous du front-end de GCC).
Donc pas de « voire middle-end », quelque part. À de très très rares exceptions près, tout compilateur « industriel » moderne est architecturé selon ces trois parties distinctes. ↩
Il y en a beaucoup, notamment le fait qu'il faut insérer des pseudo-fonctions phi lorsque plusieurs chemins de contrôle se rejoignent avec des valeurs potentiellement différentes. L'insertion est facile à identifier, c'est la reconversion du graphe SSA en graphe « normal » (interprétable par le back-end) qui peut devenir compliquée. Les auteurs du premier papier démontrant comment mettre un programme sous forme SSA efficace et opérer une « dé-SSA » proposent un mécanisme simple mais potentiellement coûteux en registres/opérations de chargement/déchargement (mais au moins la complexité est correcte). ↩
À noter que par exemple dans le middle end, il n'est pas rare que l'inversion de deux passes d'optimisation résultent en une performance clairement différente (par exemple, le déroulage d'une boucle avant/après sa fission peut avoir une importance lorsque l'IR est ensuite passée au back-end). Il n'est aussi pas rare de devoir opérer exactement la même transformation plusieurs fois d'affilée. ↩
[^] # Re: Dommage alors
Posté par lasher . En réponse au journal LLVM se fait de vieux os ? La recherche pour rester jeune.. Évalué à 7.
Je réagis bien plus tard, mais les vacances étant finies, je peux enfin procrastiner au boulot ! :)
Deux choses :
Mon deuxième point répond en partie à cette phrase :
(c'est moi qui grasse œuf corse)
Justement, ;-) ça va plus loin que ça selon moi. Il y a une séparation nette entre les phases qui ont des effets de bord (front-end, back-end), et celles qui n'en ont pas (le middle-end), à l'exception du changement de représentation. Même dans le back-end on cherche le plus possible à garder des abstractions (sinon les itérations entre ordonnancement d'instruction et allocation de registre seraient infernales à gérer, surtout si on considère certaines optimisations de bas-niveau qui ne peuvent se faire qu'à ce moment).
Bref, ça ne contredit pas ton interprétation (qui est somme toute correcte), mais je voulais renforcer le « pourquoi » on architecture un compilateur ainsi. Au passage, ça permet aussi à LLVM de proposer une interface pour insérer ses propres passes d'optimisation dans le middle-end, et ça explique aussi pourquoi pendant longtemps GCC avait le back-end et le front-end « mélangés » pour des raisons idéologiques (pour éviter que les efforts de la communauté du libre soient fagocités par des éditeurs propriétaires qui brancheraient leur middle/back end proprio en dessous du front-end de GCC).
Donc pas de « voire middle-end », quelque part. À de très très rares exceptions près, tout compilateur « industriel » moderne est architecturé selon ces trois parties distinctes. ↩
Il y en a beaucoup, notamment le fait qu'il faut insérer des pseudo-fonctions phi lorsque plusieurs chemins de contrôle se rejoignent avec des valeurs potentiellement différentes. L'insertion est facile à identifier, c'est la reconversion du graphe SSA en graphe « normal » (interprétable par le back-end) qui peut devenir compliquée. Les auteurs du premier papier démontrant comment mettre un programme sous forme SSA efficace et opérer une « dé-SSA » proposent un mécanisme simple mais potentiellement coûteux en registres/opérations de chargement/déchargement (mais au moins la complexité est correcte). ↩
À noter que par exemple dans le middle end, il n'est pas rare que l'inversion de deux passes d'optimisation résultent en une performance clairement différente (par exemple, le déroulage d'une boucle avant/après sa fission peut avoir une importance lorsque l'IR est ensuite passée au back-end). Il n'est aussi pas rare de devoir opérer exactement la même transformation plusieurs fois d'affilée. ↩