Warum hat LLVM eine assemblierungsähnliche IR und keine baumähnliche IR? Oder: Warum zielen Projekte auf LLVM IR anstatt auf Clangs AST?

14

Warum ist die LLVM-Intermediate-Representation (LLVM-IR) nicht wie ein Baum, sondern wie eine Assembly?

Warum zielen Sprachimplementierungen alternativ eher auf LLVM-IR als auf Clangs AST?

Ich versuche nicht, zwei verschiedene Fragen gleichzeitig zu stellen, wenn es so scheint. Mir scheint, dass sowohl Client- als auch Bibliotheksprogrammierer zu dem Konsens gekommen sind, dass die LLVM-API nicht mehr und nicht weniger ein gutes Softwaredesign ist und meine Frage lautet "Warum?".

Der Grund, den ich frage, ist, dass LLVM anscheinend mehr Funktionen für Frontends bereitstellen könnte, wenn es sich um ein AST-ähnliches IR handelt, da dann die AST-basierten Tools von Clang für jedes Frontend verwendet werden könnten. Alternativ könnten Sprachen, die auf LLVM-IR abzielen, mehr Funktionalität erhalten, wenn sie auf Clangs AST abzielen.

Clang hat Klassen und Funktionen zum Erstellen und Arbeiten mit ASTs und es ist die einzige Frontend-Projekt, das eng mit dem LLVM-Projekt verknüpft ist. Warum ist die AST-Funktionalität von Clang also außerhalb von LLVM?

Ich weiß, dass Rust (rustc), D (ldc) und Haskell (GHC) LLVM als Backend verwenden können, aber sie verwenden nicht den Clang AST (soweit ich weiß, dass ich es könnte) falsch liegen). Ich kenne nicht alle internen Details dieser Compiler, aber zumindest scheinen Rust und D so zu sein, als könnten sie zu Clangs AST kompiliert werden. Vielleicht könnte Haskell das auch, aber da bin ich mir viel weniger sicher.

Liegt dies an historischen Gründen (LLVM war ursprünglich eine "virtuelle Maschine auf niedriger Ebene" und klirrte später)? Liegt das daran, dass andere Frontends so viel Kontrolle wie möglich darüber haben möchten, was sie an LLVM weitergeben? Gibt es fundamentale Gründe, warum Clangs AST für "nicht C-ähnliche" Sprachen ungeeignet ist?

Ich beabsichtige nicht, dass diese Frage eine Übung zum Gedankenlesen ist. Ich möchte nur, dass es für diejenigen von uns hilfreich ist, die neugierig sind, aber das Compiler-Design noch nicht fließend beherrschen. Da die LLVM- und Clang-Projekte öffentlich entwickelt werden, hoffe ich, dass jemand, der mit der Entwicklung dieser Projekte vertraut ist, antworten kann oder dass die Antwort für einige Compiler-Nerds so offensichtlich ist, dass sie sich sicher genug fühlen, zu antworten.


Um einige offensichtliche, aber unbefriedigende Antworten vorwegzunehmen:

Ja, mit einem Montageartigen gibt IR mehr Kontrolle wer die IR - Handwerk (vielleicht X lang hat ein besseres Code - Basis und AST - Format als Klappern) , aber wenn das die einzige Antwort ist, dann wird die Frage „warum LLVM nur eine montage- hat wie IR anstelle einer baumähnlichen IR auf hoher Ebene und einer assemblierungsähnlichen IR auf niedriger Ebene? "

Ja, es ist nicht so schwer, eine Programmiersprache in einen AST zu zerlegen (zumindest im Vergleich zu den anderen Schritten des Kompilierens). Warum jedoch separate ASTs verwenden? Wenn Sie denselben AST verwenden, können Sie Tools verwenden, die auf ASTs ausgeführt werden (auch auf einfachen Dingen wie AST-Druckern).

Ja, ich stark darüber einig , dass mehr modular ist eine gute Sache ist, aber wenn das der einzige Grund ist, warum dann tut andere Sprache Implementierungen neigt LLVM IR statt AST von Klirren zielen?

Diese Vorannahmen können fehlerhaft sein oder Details übersehen. Geben Sie diese Antworten, wenn Sie weitere Details haben oder meine Annahmen falsch sind.


Für alle, die eine eindeutig beantwortbare Frage beantworten möchten: Welche Vor- und Nachteile hat eine assemblierungsähnliche IR gegenüber einer baumähnlichen IR?

Praxeolitische
quelle
1
Ich bin kein LLVM-Experte, aber ich glaube, Sie haben ein kleines Missverständnis. LLVM hat nicht wie IR asm. Tatsächlich ähnelt seine IR eher einer Grafik als einem Baum. Ich gehe davon aus, dass Sie sich mit "asm-like" auf die von Menschen lesbaren IR-Dateien (* .ll-Dateien) beziehen, wenn dies der Einfachheit halber geschieht. Aber warten wir auf einen echten Experten, der umfassendere Antworten geben kann :)
AlexDenisov
1
Ein wichtiger Aspekt könnte die Geschichte sein: LLVM wurde ursprünglich entwickelt, um Compiler-Backends von Compiler-Frontends zu entkoppeln. Die Idee war, dass Compiler-Anbieter bei Sprachoptimierungen und CPU-Anbieter bei Low-Level-Optimierungen gegeneinander antreten würden. Zum Beispiel würden Microsoft und Apple gegeneinander antreten, deren C-Compiler den "besten" Bitcode aus C erzeugt, und Intel und AMD würden gegeneinander antreten, deren LLVM-Backend den "besten" Maschinencode aus Bitcode erzeugt. Anwendungsanbieter würden ihre Anwendungen in Bitcode versenden, und die endgültige Zusammenstellung würde auf dem Benutzer erfolgen ...
Jörg W Mittag
1
… Maschine. LLVM begann zu einer Zeit, in der es überhaupt nicht klar war, dass jeder Intel verwenden würde. Apple war immer noch auf PowerPC, Intel forcierte immer noch Itanium und so weiter. AFAIK, Apple verwendet LLVM in einigen seiner 3D-Frameworks immer noch auf diese Weise, wobei Code als Bitcode geliefert und dann für nVidia oder ATI kompiliert wird, je nachdem, welcher Kartentyp installiert ist.
Jörg W Mittag
1
Vergib mir, aber was ist eine IR?
Adam Copley
1
@AdamCopley Zwischendarstellung
Praxeolitic

Antworten:

13

Hier gibt es eine Reihe von miteinander zusammenhängenden Fragen. Ich werde versuchen, sie so gut wie möglich zu trennen.

Warum bauen andere Sprachen auf LLVM IR auf und klingen nicht AST?

Dies liegt einfach daran, dass clang ein C / C ++ - Frontend ist und der von ihm erzeugte AST eng an C / C ++ gekoppelt ist. Eine andere Sprache könnte es verwenden, aber es würde eine nahezu identische Semantik für eine Teilmenge von C / C ++ benötigen, was sehr einschränkend ist. Wie Sie bereits erwähnt haben, ist das Parsen auf einen AST relativ einfach. Daher ist es unwahrscheinlich, dass eine Einschränkung Ihrer semantischen Auswahl die geringe Ersparnis wert ist.

Wenn Sie jedoch Tools für C / C ++ schreiben, z. B. statische Analysegeräte, ist die Wiederverwendung des AST sehr sinnvoll, da die Arbeit mit dem AST viel einfacher ist als mit dem Rohtext, wenn Sie mit C / C ++ arbeiten .

Warum ist LLVM IR die Form, die es ist?

LLVM IR wurde als geeignete Form zum Schreiben von Compileroptimierungen ausgewählt. Als solches ist es das Hauptmerkmal, dass es in SSA- Form vorliegt. Es ist eine recht niedrige IR-Stufe, so dass es auf eine Vielzahl von Sprachen anwendbar ist, z. B. wird kein Speicher eingegeben, da dies von Sprache zu Sprache sehr unterschiedlich ist.

Nun ist es zufällig so, dass das Schreiben von Compiler-Optimierungen eine ziemlich spezielle Aufgabe ist und häufig orthogonal zum Sprachfeature-Design ist. Eine kompilierte Sprache schnell laufen zu lassen, ist jedoch eine ziemlich allgemeine Voraussetzung. Außerdem ist die Konvertierung von LLVM IR zu ASM ziemlich mechanisch und auch für Sprachdesigner im Allgemeinen nicht interessant.

Das Reduzieren einer Sprache auf LLVM IR bietet einem Sprachdesigner daher viele "kostenlose Dinge", die in der Praxis sehr nützlich sind, sodass er sich auf die Sprache selbst konzentrieren kann.

Wäre eine andere IR nützlich (OK, nicht gefragt, aber impliziert)?

Absolut! ASTs eignen sich für bestimmte Transformationen in der Programmstruktur, sind jedoch sehr schwer zu verwenden, wenn Sie den Programmfluss transformieren möchten. Ein SSA-Formular ist im Allgemeinen besser. LLVM-IR ist jedoch sehr niedrig, sodass ein Großteil der Struktur auf hoher Ebene verloren geht (absichtlich, damit es allgemeiner anwendbar ist). Ein IR zwischen dem AST und dem niedrigen IR-Pegel kann hier von Vorteil sein. Sowohl Rust als auch Swift verfolgen diesen Ansatz und haben ein hohes IR-Niveau zwischen den beiden.

Alex
quelle
Haskell hat eine Reihe von IRs, bevor es zu LLVM kommt.
DylanSp
1
@ DylanSp In der Tat. Es beginnt sich de facto als Best Practice für komplexe Sprachen zu etablieren. Zum Beispiel hat Rust dies anfangs nicht getan und es wurde überarbeitet, um eine hohe IR-Ebene zu integrieren. Ich glaube auch, dass darüber geredet wurde, aber ich bin mir nicht sicher, wohin das führte.
Alex