Warum wird bei vielen branchenüblichen Compilern die statische Einzelzuweisung der Weitergabe vorgezogen?

Laut der Wikipedia-Seite zu statischer Einzelzuweisung (SSA) wird SSA von großen und bekannten Projekten wie LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey und V8 verwendet, während die Seite zu Projekten im Continuation-Passing-Stil verwendet wird (CPS) ist im Vergleich etwas mangelhaft.

Ich habe die Vorstellung, dass CPS von Compilern und Interpreten bevorzugt wird, die hauptsächlich funktionale Sprachen implementieren. Insbesondere scheinen Haskell und Scheme aufgrund der Einschränkungen bei der Mutation oder der Notwendigkeit einer erstklassigen Unterstützung für die Fortsetzung eine starke Neigung zum CPS-Stil zu haben (ich würde raten) dass Smalltalk dies möglicherweise auch brauchen würde). Die Hauptliteratur, auf die ich gestoßen bin und die CPS verwendet, scheint jene zu sein, die hauptsächlich an Scheme arbeiten oder in gewisser Hinsicht mit Scheme zusammenhängen.

Gibt es einen besonderen Grund, warum SSA in der Industrie eingesetzt wird, abgesehen von dem Moment der Übernahme? SSA und CPS haben eine enge Beziehung. Das bedeutet, dass es einfach wäre, eine andere Aussage zu treffen, aber die Informationsdarstellung wäre für CPS möglicherweise weniger kompakt oder weniger effizient.

Ich stelle mir vor, dass viele Compiler-Implementierer für typische imperative Sprachen mit CPS und CPS-basierten Kompilierungstechniken einfach nicht so vertraut waren. In der Community der funktionalen Programmierung sind sowohl CPS- als auch CPS-basierte Kompilierungen sehr bekannte Techniken - letztere stammen von Guy Steele. Trotzdem verwenden die meisten Compiler selbst in der FP-Community keine CPS-basierten Techniken zum Kompilieren, es sei denn, die Sprache selbst unterstützt Steueroperatoren wie call/cc. Es wird eine Art administrative Normalform (ANF) (manchmal auch als monadische Normalform bezeichnet, die aus Gründen, die noch deutlicher werden, eng miteinander verwandt ist) verwendet, die eine noch engere Beziehung zu SSA aufweist als CPS .

Wenn ich mich richtig erinnere, hat die administrative Normalform ihren Namen von der Tatsache, dass CPS-basierte Kompilierung zu Beta-Redexes im Zwischencode führen kann, die nichts im Quellcode entsprachen. Diese wurden als "administrative Redexes" bezeichnet. Diese konnten zur Kompilierungszeit reduziert werden, aber es gab eine Menge Nachforschungen zur Durchführung einer CPS-Transformation, die Code ohne die administrativen Redexes ausgeben würde. Das Ziel war es dann, eine Ausgabe in normaler Form zu erzeugen, bei der alle "administrativen" Redexes reduziert wurden, und dies war der Ursprung der administrativen Normalform. Es dauerte nicht lange, bis klar wurde, dass es keinen großen Nutzen brachte, dies als (n) Optimierung eines) zweistufigen Prozesses zu betrachten: CPS-Transformation, Reduzierung administrativer Redexes. Im Speziellen, Die administrative Normalform ähnelt eher der monadischen Form, wie sie vor allem in Haskell (von Hand) praktiziert wird. Die CPS-Transformation kann als Konvertierung in den monadischen Stil verstanden werden, bei der Sie zufällig die CPS-Monade verwenden (es gibt also mehrere Möglichkeiten, entsprechend den verschiedenen Bewertungsreihenfolgen in den monadischen Stil zu konvertieren). Im Allgemeinen könnten Sie jedoch eine ganz andere Monade verwenden, sodass die Konvertierung in eine monadische und damit administrative Normalform nicht wirklich mit CPS im Zusammenhang steht.

Trotzdem hatte CPS gegenüber ANF einige Vorteile. Insbesondere gab es bestimmte Optimierungen, die Sie in CPS nur mit Standardoptimierungen wie der Beta-Reduzierung durchführen konnten, die (scheinbar) Ad-hoc-Regeln für ANF erforderten. Aus monadischer Sicht entsprechen diese Regeln Pendelumwandlungen. Das Fazit ist nun, dass es eine Theorie gibt, die erklären kann, welche Regeln hinzugefügt werden sollten und warum. Ein kürzlich veröffentlichter Aufsatz bietet eine (neue und) ziemlich klare Beschreibung (aus einer logischen Perspektive), und der zugehörige Arbeitsabschnitt dient als kurze, aber vernünftige Übersicht über und Verweise in die Literatur zu den von mir genannten Themen.

Das Problem mit CPS hängt mit einem seiner Hauptvorteile zusammen. Mit der CPS-Transformation können Sie Steueroperatoren wie die folgenden implementieren. call/ccDies bedeutet jedoch, dass jeder nicht lokale Funktionsaufruf im CPS-Zwischencode als potenziell steuernd behandelt werden muss. Wenn Ihre Sprache Steueroperatoren enthält, ist dies genau so, wie es sein sollte (obwohl selbst dann die meisten Funktionen wahrscheinlich keine Steuerfunktionen ausführen). Wenn Ihre Sprache keine Steueroperatoren enthält, gibt es globale Invarianten für die Verwendung von Fortsetzungen, die lokal nicht erkennbar sind. Dies bedeutet, dass es Optimierungen gibt, die für den allgemeinen CPS-Code nicht geeignet sind, die für diese besonders gutmütige Verwendung von CPS geeignet wären. Eine Möglichkeit, dies zu manifestieren, ist indie Änderung der Genauigkeit von Daten- und Kontrollflussanalysen . (CPS-Transformation hilft in gewisser Weise, schadet in anderer Hinsicht, obwohl die Art und Weise, wie sie hilft, hauptsächlich auf Duplizierung und nicht auf den CPS-Aspekt selbst zurückzuführen ist.) ¹ Sie können natürlich Regeln hinzufügen und Analysen anpassen, um dies zu kompensieren (dh um sie auszunutzen) die globalen Invarianten), aber dann haben Sie einen der Hauptvorteile der CPS-basierten Kompilierung teilweise besiegt: Viele (scheinbar) zweckgebundene Ad-hoc-Optimierungen werden zu Spezialfällen der allgemeinen Optimierung (insbesondere der Beta-Reduzierung) ).

Letztendlich gibt es, sofern Ihre Sprache keine Steueroperatoren hat, normalerweise nicht viele Gründe, ein CPS-basiertes Kompilierungsschema zu verwenden. Sobald Sie die oben genannten Probleme behoben haben, haben Sie in der Regel die Vorteile der CPS-basierten Kompilierung beseitigt und etwas produziert, das der Nichtverwendung von CPS entspricht. Zu diesem Zeitpunkt macht CPS nur einen verworrenen Zwischencode, der nicht viel Nutzen bringt. Ein Argument für eine CPS-basierte Kompilierung aus dem Jahr 2007 behandelt einige dieser Probleme und zeigt einige andere Vorteile auf, wenn eine andere Form der CPS-Konvertierung verwendet wird. Die Dinge, die von Papier angesprochen werden, werden teilweise von dem (2017) -Papier abgedeckt, das ich zuvor erwähnt habe.

¹ Macht die Äquivalenz zwischen SSA und CPS dies nicht mehr oder weniger unmöglich? Nein. Eines der ersten Dinge, die in der Veröffentlichung zur Einführung dieser Äquivalenz erwähnt werden , ist, dass die Äquivalenz nicht für beliebigen CPS-Code funktioniert, sondern für die Ausgabe einer CPS-Transformation (die sie definieren) für eine Sprache ohne Steueroperatoren.

Ich bin kein Compiler-Experte, also nimm, was ich mit einem Körnchen Salz sage, ich hoffe, dass sich ein echter Compiler-Experte einmischt. Mir wurde gesagt, dass:

• CPSed-Code neigt dazu, nicht lokal zu springen, was die Cache-Lokalität und damit die Leistung beeinträchtigt.
• CPS erfordert eine teurere Speicherbereinigung als die herkömmliche Kompilierung, bei der in der Regel viel Material auf dem Stapel gespeichert werden kann (was die Zuordnung und Freigabe von Speicherbereinigungen beschleunigt).

Beide verschwören sich, um durch CPS-Transformation kompilierten Code vergleichsweise langsam zu machen.