Complexité temporelle d'un compilateur

Je suis intéressé par la complexité temporelle d'un compilateur. De toute évidence, cette question est très compliquée car de nombreux compilateurs, options de compilateur et variables doivent être pris en compte. Plus précisément, je m'intéresse à LLVM mais je serais intéressé par toutes les idées que les gens ont ou les endroits où commencer des recherches. Un assez google semble apporter peu à la lumière.

Je suppose que certaines étapes d'optimisation sont exponentielles, mais ont peu d'impact sur le temps réel. Par exemple, les exponentielles basées sur le nombre sont les arguments d'une fonction.

D’emblée, je dirais que la génération de l’arbre AST serait linéaire. La génération IR nécessiterait de parcourir l’arbre tout en cherchant des valeurs dans des tableaux toujours croissants, donc ou . La génération de code et la liaison constitueraient un type d'opération similaire. Par conséquent, ma supposition serait , si nous supprimions les exponentielles des variables qui ne croissent pas de manière réaliste.$O(n^2)$O ( n 2$O(n\log n)$$O(n^2)$

Je pourrais être complètement faux cependant. Quelqu'un a-t-il des idées à ce sujet?

Le meilleur livre pour répondre à votre question serait probablement: Cooper and Torczon, «Engineering a Compiler», 2003. Si vous avez accès à une bibliothèque universitaire, vous devriez pouvoir en emprunter un exemplaire.

Dans un compilateur de production tel que llvm ou gcc, les concepteurs mettent tout en œuvre pour conserver tous les algorithmes au-dessous de où est la taille de l'entrée. Pour certaines des analyses des phases "d'optimisation", cela signifie que vous devez utiliser des méthodes heuristiques plutôt que de produire un code vraiment optimal.$O(n^2)$$n$

Le lexer est une machine à états finis, donc la taille de l'entrée (en caractères) et produit un flux de jetons transmis à l'analyseur.O ( n $O(n)$$O(n)$

Pour de nombreux compilateurs et pour de nombreuses langues, l'analyseur est LALR (1) et traite donc le flux de jetons en temps en nombre de jetons d'entrée. Lors de l'analyse, vous devez généralement garder trace d'une table de symboles, mais, pour de nombreuses langues, elle peut être gérée avec une pile de tables de hachage ("dictionnaires"). Chaque accès au dictionnaire est , mais vous pouvez parfois avoir à marcher dans la pile pour rechercher un symbole. La profondeur de la pile est où est la profondeur d'imbrication des étendues. (Ainsi, dans les langages C-like, combien de couches d'accolades vous êtes à l'intérieur.)O ( 1 ) O ( s ) $O(n)$$O(1)$$O(s)$$s$

Ensuite, l'arbre d'analyse est généralement "aplati" dans un graphe de flux de contrôle. Les nœuds du graphe de flux de contrôle peuvent être des instructions à 3 adresses (similaires à un langage d'assemblage RISC), et la taille du graphe de flux de contrôle sera généralement linéaire par rapport à la taille de l'arbre d'analyse.

Ensuite, une série d'étapes d'élimination de la redondance est généralement appliquée (élimination de sous-expression commune, mouvement de code invariant de boucle, propagation constante, ...). (Ceci est souvent appelé "optimisation" bien qu'il y ait rarement quelque chose d'optimal dans le résultat, le but réel est d'améliorer le code autant que possible dans les contraintes de temps et d'espace que nous avons imposées au compilateur.) Chaque étape d'élimination de la redondance exigent généralement des preuves de certains faits concernant le graphe de flux de contrôle. Ces épreuves sont généralement effectuées à l'aide d' une analyse de flux de données . La plupart des analyses de flux de données sont conçues de manière à converger en passes sur le graphe de flux où est (en gros) la profondeur d'imbrication de la boucle et un passage sur le graphe de flux prend du tempsd O ( n ) $O(d)$$d$$O(n)$où est le nombre d'instructions à 3 adresses.$n$

Pour des optimisations plus sophistiquées, vous pouvez effectuer des analyses plus sophistiquées. À ce stade, vous commencez à faire des compromis. Vous voulez que vos algorithmes d'analyse prennent beaucoup moins que$O(n^2)$temps dans la taille du graphe de flux du programme entier, mais cela signifie que vous devez vous passer des informations (et des transformations améliorant les programmes) qui pourraient être coûteuses à prouver. L'analyse d'alias est un exemple classique. Dans le cas d'une paire d'écritures en mémoire, vous souhaitez prouver que les deux écritures ne peuvent jamais cibler le même emplacement de mémoire. (Vous voudrez peut-être effectuer une analyse d'alias pour voir si vous pouvez déplacer une instruction au-dessus de l'autre.) Mais pour obtenir des informations précises sur les alias, vous devrez peut-être analyser tous les chemins de contrôle possibles dans le programme, ce qui est exponentiel en nombre de branches. dans le programme (et donc exponentielle dans le nombre de nœuds dans le graphe de flux de contrôle.)

Ensuite, vous entrez dans l'allocation de registre. L'attribution de registre peut être formulée comme un problème de coloration de graphique, et il est connu que la coloration d'un graphique avec un nombre minimal de couleurs est NP-Hard. La plupart des compilateurs utilisent donc une sorte d’heuristique gloutonne combinée à des renversements de registres dans le but de réduire au mieux le nombre de renversements de registres dans des délais raisonnables.

Enfin, vous entrez dans la génération de code. La génération de code consiste généralement en un bloc de base maximal à un moment où un bloc de base est un ensemble de noeuds de graphe de flux de commande connectés de manière linéaire avec une seule entrée et une seule sortie. Cela peut être reformulé en un problème de couverture de graphe où le graphe que vous essayez de couvrir est le graphe de dépendance du jeu d'instructions à 3 adresses du bloc de base et que vous essayez de couvrir avec un jeu de graphes représentant la machine disponible. instructions. Ce problème est exponentiel dans la taille du bloc de base le plus grand (qui peut, en principe, être du même ordre que la taille de l'ensemble du programme). Il s'agit donc encore d'une fois d'une heuristique où seulement un petit sous-ensemble des couvertures possibles est examiné.

En fait, certains langages (comme C ++, Lisp et D) sont complets à la compilation, donc leur compilation est indécidable en général. Pour C ++, cela est dû à l'instanciation de modèles récursive. Pour Lisp et D, vous pouvez exécuter presque tous les codes au moment de la compilation, vous pouvez donc lancer le compilateur dans une boucle infinie si vous le souhaitez.

D'après mon expérience actuelle avec le compilateur C #, je peux dire que pour certains programmes, la taille du binaire de sortie augmente de façon exponentielle par rapport à la taille de la source d'entrée (ceci est en fait requis par la spécification C # et ne peut pas être réduit), donc la complexité temporelle doit aussi être au moins exponentiel.

La tâche générale de résolution de la surcharge en C # est connue pour être NP-difficile (et la complexité de la mise en œuvre réelle est au moins exponentielle).

Un traitement des commentaires de la documentation XML dans les sources C # nécessite également l'évaluation d'expressions XPath 1.0 arbitraires au moment de la compilation, qui est également exponentielle, AFAIK.

Mesurez-le avec des bases de code réalistes, telles qu'un ensemble de projets open source. Si vous tracez les résultats sous la forme (codeSize, finishTime), vous pouvez alors tracer ces graphiques. Si vos données f (x) = y sont O (n), le traçage g = f (x) / x devrait vous donner une ligne droite une fois que les données commencent à devenir volumineuses.

Tracer f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x), etc. Le graphique plongera soit à zéro, augmenter sans limite, ou aplatir. Cette idée est pratique dans des situations telles que la mesure du temps d'insertion à partir d'une base de données vide (par exemple: rechercher une «fuite de performance» sur une longue période).