Pourquoi l'affectation statique-unique est-elle préférée au style de passage de continuation dans de nombreux compilateurs utilisés dans l'industrie?

Selon la page Wikipédia sur l'attribution statique unique (SSA) , SSA est utilisée par de grands projets bien connus tels que LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey et V8 tandis que la page sur les projets utilisant le style de passage continu (CPS) fait un peu défaut en comparaison.

J'ai cette notion que CPS est préféré par les compilateurs et les interprètes qui implémentent principalement des langages fonctionnels - en particulier, Haskell et Scheme semblent avoir de fortes inclinations vers le style CPS en raison des restrictions sur la mutation ou du besoin d'un support de continuation de première classe (je suppose que Smalltalk en aurait peut-être également besoin). La principale littérature que j'ai rencontrée qui utilise CPS semble être celle qui travaille principalement sur Scheme ou qui est liée à Scheme à certains égards.

Y a-t-il une raison particulière pour laquelle le SSA est utilisé dans l'industrie en dehors de la dynamique d'adoption? SSA et CPS ont une relation étroite; cela signifie qu'il serait facile d'énoncer soit en termes d'un autre, mais peut-être que la représentation de l'information serait moins compacte ou moins efficace pour CPS.

J'imagine que de nombreux implémenteurs de compilateur pour les langages impératifs typiques n'étaient tout simplement pas familiers avec CPS et les techniques de compilation basées sur CPS. Dans la communauté de programmation fonctionnelle, CPS et la compilation basée sur CPS sont des techniques très connues - cette dernière issue du travail de Guy Steele. Néanmoins, même dans la communauté FP, la plupart des compilateurs n'utilisent pas de techniques basées sur CPS pour la compilation, sauf si le langage lui-même prend en charge les opérateurs de contrôle comme call/cc. Quelque chose de plus semblable à la forme normale administrative (ANF) (parfois aussi appelée forme normale monadique qui est intimement liée pour des raisons qui deviendront claires) est utilisée, ce qui a une relation encore plus étroite avec la SSA que la CPS .

Si je me souviens bien, la forme administrative normale tire son nom du fait que la compilation basée sur CPS peut conduire à des bêta-redexes dans le code intermédiaire qui ne correspondent à rien dans le code source. Celles-ci étaient appelées "redex administratives". Ceux-ci pourraient être réduits au moment de la compilation, mais il y avait une bonne quantité de recherches sur la réalisation d'une transformation CPS qui produirait du code sans les redex administratives en premier lieu. L'objectif était alors de produire une production sous une forme normale où tous les redex "administratifs" étaient réduits, et c'était l'origine de la forme administrative normale. Il n'a pas fallu longtemps pour réaliser qu'il n'y avait pas beaucoup d'avantages à considérer cela comme un (n optimisation d'un) processus en deux étapes: transformation CPS, réduction des redex administratifs. En particulier, la forme normale administrative ressemble plutôt à un style monadique tel qu'il est pratiqué (à la main) notamment à Haskell. La transformation CPS peut être comprise comme une conversion au style monadique où il se trouve que vous utilisez la monade CPS (il y a donc vraiment plusieurs façons de "convertir" au style monadique correspondant à différents ordres d'évaluation). En général, cependant, vous pourriez utiliser une monade assez différente, et donc la conversion au style monadique et donc à la forme normale administrative n'est pas vraiment liée à CPS en particulier.

Néanmoins, le CPS par rapport à l'ANF présentait certains avantages. En particulier, il y avait certaines optimisations que vous pouviez faire dans CPS avec seulement des optimisations standard, telles que la réduction bêta, qui nécessitaient (apparemment) des règles ad hoc pour ANF. Du point de vue monadique, ces règles correspondent aux conversions de navettage. Le résultat est maintenant qu'il existe une théorie qui peut expliquer quelles règles devraient être ajoutées et pourquoi. Un article récent donne une description (nouvelle et) assez claire de cela (d'un point de vue logique) et sa section de travail connexe sert de survol bref mais décent et de références dans la littérature sur les sujets que je mentionne.

Le problème avec CPS est lié à l'un de ses principaux avantages. La transformation CPS vous permet d'implémenter des opérateurs de contrôle comme call/cc, mais cela signifie que chaque appel de fonction non local dans le code intermédiaire CPS doit être traité comme ayant potentiellement des effets de contrôle. Si votre langage comprend des opérateurs de contrôle, alors c'est exactement comme cela devrait être (même si la plupart des fonctions ne font probablement pas de manigances de contrôle). Si votre langage n'inclut pas d' opérateurs de contrôle, il existe des invariants globaux sur l'utilisation des continuations qui ne sont pas évidents localement. Cela signifie qu'il existe des optimisations qui ne sont pas judicieuses à effectuer sur le code CPS général qui seraient judicieuses à effectuer sur cette utilisation particulièrement bien comportée de CPS. Une façon dont cela se manifeste estl'évolution de la précision des données et des analyses de flux de contrôle . (La transformation CPS aide à certains égards, fait mal à d'autres, bien que les moyens qu'elle aide soient principalement dus à la duplication plutôt qu'à l'aspect CPS lui-même.) ¹ Vous pouvez, bien sûr, ajouter des règles et ajuster les analyses pour compenser cela (c'est-à-dire exploiter les invariants mondiaux), mais vous avez ensuite partiellement vaincu l'un des principaux avantages de la compilation basée sur CPS, à savoir que de nombreuses optimisations ad hoc (apparemment) deviennent des cas spéciaux d'optimisation à usage général (en particulier la réduction bêta ).

En fin de compte, à moins que votre langue n'ait des opérateurs de contrôle, il n'y a généralement pas beaucoup de raisons d'utiliser un schéma de compilation basé sur CPS. Une fois que vous avez compensé les problèmes que j'ai mentionnés ci-dessus, vous avez généralement éliminé les avantages de la compilation basée sur CPS et produit quelque chose d'équivalent à ne pas utiliser CPS. À ce stade, CPS ne fait que créer un code intermédiaire alambiqué pour pas beaucoup d'avantages. Un argument pour une compilation basée sur CPS à partir de 2007 résout certains de ces problèmes et présente d'autres avantages en utilisant une forme différente de conversion CPS. Les choses que le papier soulève sont couvertes en partie par le document (2017) que j'ai mentionné précédemment.

¹ L'équivalence entre SSA et CPS ne rend-elle pas cela plus ou moins impossible? Non. L'une des premières choses que le document introduisant cette équivalence indique est que l'équivalence ne fonctionne pas pour le code CPS arbitraire , mais qu'elle fonctionne pour la sortie d'une transformation CPS (qu'ils définissent) pour une langue sans opérateurs de contrôle.

Je ne suis pas un expert en compilateur, alors prenez ce que je dis avec un grain de sel, j'espère qu'un véritable expert en compilateur se fera entendre. On m'a dit que:

• Le code CPSed a tendance à beaucoup sauter non localement, ce qui ruine la localité du cache, d'où les performances.
• CPS nécessite une collecte des ordures plus coûteuse que la compilation conventionnelle qui peut généralement stocker beaucoup de choses sur la pile (ce qui est plus rapide à allouer et à désallouer).

Les deux conspirent à rendre le code compilé par CPS-transform relativement lent.