lacc
1.0.0
Dies ist ein Spielzeugprojekt von mir mit dem Ziel, einen Compiler für C zu machen, der in C geschrieben wurde und sich selbst kompilieren kann.
Klon und bauen aus der Quelle, und die Binärdatei wird in bin/lacc platziert.
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
Die Standardkonfiguration umfasst eine grundlegende Untersuchung der Umgebung, um festzustellen, für welche Maschine und LIBC wir zusammenstellen. Zu den anerkannten Plattformen gehören derzeit Linux mit Glibc oder Musl und OpenBSD.
Bestimmte Standardbibliotheksüberschriften wie stddef.h und stdarg.h enthalten Definitionen, die von Natur aus Compilerspezifisch sind und speziell für LACC unter LIB/bereitgestellt werden. Wenn Sie bin/lacc direkt verwenden möchten, ohne die Header zu installieren, können Sie den Speicherort überschreiben, indem Sie --libdir , so auf diesen Ordner hinweisen.
Das install Target kopiert die Binär- und Header an den üblichen Standorten oder wie mit --prefix oder --bindir konfiguriert. Es gibt auch eine Option zum Festlegen DESTDIR . Execute make uninstall , um alle Dateien zu entfernen, die kopiert wurden.
Siehe ./configure --help , um Optionen zum Anpassen von Build- und Installationsparametern anzupassen.
Die Befehlszeilenschnittstelle wird GCC und anderen Compilern ähnlich gehalten, wobei hauptsächlich eine Teilmenge der gleichen Flaggen und Optionen verwendet wird.
-E Output preprocessed.
-S Output GNU style textual x86_64 assembly.
-c Output x86_64 ELF object file.
-dot Output intermediate representation in dot format.
-o Specify output file name. If not speficied, default to input file
name with suffix changed to '.s', '.o' or '.dot' when compiling
with -S, -c or -dot, respectively. Otherwise use stdout.
-std= Specify C standard, valid options are c89, c99, and c11.
-I Add directory to search for included files.
-w Disable warnings.
-g Generate debug information (DWARF).
-O{0..3} Set optimization level.
-D X[=] Define macro, optionally with a value. For example -DNDEBUG, or
-D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v Print verbose diagnostic information. This will dump a lot of
internal state during compilation, and can be useful for debugging.
--help Print help text.
Argumente, die keine Option übereinstimmen, werden als Eingabedateien angenommen. Wenn kein Kompilierungsmodus angegeben ist, fungiert LACC als Wrapper für den System Linker /bin/ld . Einige gemeinsame Linker -Flaggen werden unterstützt.
-Wl, Specify linker options, separated by commas.
-L Add linker include directory.
-l Add linker library.
-shared Passed to linker as is.
-rdynamic Pass -export-dynamic to linker.
Als Beispielaufruf finden Sie hier das Kompilieren von Tests/C89/Fact.c zum Objektcode und verwenden Sie dann den System -Linker, um die endgültige ausführbare Datei zu erstellen.
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
Das Programm ist Teil der Testsuite und berechnet 5! Verwenden der Rekursion und mit der Antwort. Laufen ./fact , gefolgt von echo $? sollte 120 drucken.
Der Compiler ist in C89 geschrieben und zählt insgesamt etwa 19K -Codezeilen. Es gibt keine externen Abhängigkeiten außer der C -Standard -Libary und einigen Systemaufrufen, die zum Aufrufen des Linkers erforderlich sind.
Die Implementierung ist in vier Hauptteile organisiert. Präprozessor, Parser, Optimierer und Backend, jeweils in ihrem eigenen Verzeichnis unter SRC/. Im Allgemeinen hängt jedes Modul (eine .c -Datei, die normalerweise mit einer .h -Datei gepaart ist, die die öffentliche Schnittstelle definiert) hauptsächlich von Header in ihrem eigenen Unterbaum ab. Erklärungen, die auf globaler Ebene geteilt werden, befinden sich in einschließlich/LACC/. Hier finden Sie die Kerndatenstrukturen und Schnittstellen zwischen Vorverarbeitung, Analyse und Codegenerierung.
Die Vorverarbeitung umfasst Lesedateien, Tokenisierung, Makroerweiterung und Richtlinienhandhabung. Die Schnittstelle zum Präprozessor ist peek(0) , peekn(1) , consume(1) , try_consume(1) und next(0) , die einen Strom vorverarbeiteter struct token -Objekte betrachtet. Diese sind in einschließlich/lacc/token.h definiert.
Die Eingangsverarbeitung erfolgt vollständig träge, was vom Parser angetrieben wird, der diese Funktionen aufruft, um mehr Eingaben zu konsumieren. Ein Puffer von vorverarbeiteten Token wird für Lookahead aufbewahrt und die Nachfrage ausgefüllt, wenn sie nach vorne spähten.
Der Code wird als Kontrollflussgraphen grundlegender Blöcke modelliert, wobei jeweils eine Sequenz von Dreiadress-Code-Anweisungen enthält. Jede externe Variable oder Funktionsdefinition wird durch ein struct definition dargestellt, wodurch ein einzelnes struct symbol und ein CFG definiert werden, das den Code hält. Die Datenstrukturen, die die Zwischendarstellung unterstützen, finden Sie in einschließlich/lacc/ir.h.
Die Visualisierung der Zwischendarstellung ist ein separates Ausgangsziel. Wenn die Option -dot angegeben ist, wird eine dot -formatierte Textdatei als Ausgabe erstellt.
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
Im Folgenden finden Sie ein Beispiel aus einer Funktion in SRC/Backend/Compile.c, die eine Scheibe des gesamten Graphen zeigt. Die vollständige Ausgabe kann als PostScript -Datei generiert werden, indem die angegebenen Befehle ausgeführt werden.
Jeder grundlegende Block in der Grafik hat eine Liste von Aussagen, am häufigsten IR_ASSIGN , der einer Variablen ( struct var ) einen Ausdruck ( struct expression ) zuweist. Ausdrücke enthalten auch variable Operanden, die Speicherorte, Adressen und Derereferenzierter auf hohem Niveau codieren können.
DIRECT Operanden beziehen sich auf den Speicher bei *(&symbol + offset) , wobei das Symbol an einem bestimmten Ort im Speicher eine Variable oder temporär ist (z. B. Stapel).ADDRESS repräsentieren genau die Adresse eines DIRECT Operanden, nämlich (&symbol + offset) .DEREF -Operanden beziehen sich auf den Speicher, auf das ein Symbol (das aus Zeigertyp sein muss). Der Ausdruck ist *(symbol + offset) , wodurch zwei Lastvorgänge zur Zuordnung der Montage erforderlich sind. Nur DEREF und DIRECT Variablen können ein Ziel für die Zuordnung oder einen L-Wert sein.IMMEDIATE Operanden halten eine konstante Zahl oder eine String. Die Bewertung der sofortigen Operanden wird automatisch konstant gefaltet.Der Parser ist von Hand codiert rekursiv, wobei die Hauptteile in src/parser/deklaration.c, src/parser/initializer.c, src/parser/expression.c und src/parser/modschrift aufteilt werden. Der aktuelle Funktionssteuerungsdarsteller und der aktuelle aktive Basisblock in diesem Diagramm werden als Argumente für jede Produktion übergeben. Der Diagramm wird allmählich konstruiert, da dem aktuellen Block neue Anweisungen mit drei Dreiadressen-Code hinzugefügt werden.
Das folgende Beispiel zeigt die Parsing -Regel für bitweise oder Ausdrücke, die dem aktuellen Block eine neue IR_OP_OR -Operation hinzufügt. Die Logik in eval_expr stellt sicher, dass die value und block->expr gültig sind und im Falle eines Fehlers enden.
static struct block *inclusive_or_expression(
struct definition *def,
struct block *block)
{
struct var value;
block = exclusive_or_expression(def, block);
while (try_consume('|')) {
value = eval(def, block, block->expr);
block = exclusive_or_expression(def, block);
block->expr = eval_or(def, block, value, eval(def, block, block->expr));
}
return block;
}
Das neueste Evaluierungsergebnis wird immer in block->expr gespeichert. Die Verzweigung erfolgt durch Instanziieren neuer Basisblöcke und Wartung von Zeigern. Jeder grundlegende Block hat einen echten und falschen Zweigzeiger auf andere Blöcke, so werden Zweige und Gotos modelliert. Beachten Sie, dass zu keinem Zeitpunkt eine Syntaxbaumstruktur gebaut wird. Es existiert nur implizit in der Rekursion.
Die Hauptmotivation für den Aufbau eines Kontrollflussdiagramms besteht darin, die Datenflussanalyse und -optimierung durchzuführen. Die aktuellen Funktionen hier sind immer noch begrenzt, können jedoch problemlos mit zusätzlichen und fortschrittlicheren Analyse- und Optimierungspannen erweitert werden.
Die Lebendigkeitsanalyse wird verwendet, um bei jeder Aussage herauszufinden, welche Symbole später gelesen werden können. Der DataFlow-Algorithmus wird unter Verwendung von Bitmasken zur Darstellung von Symbolen implementiert und nummeriert sie 1-63. Infolgedessen funktioniert die Optimierung nur bei Funktionen mit weniger als 64 Variablen. Der Algorithmus muss auch sehr konservativ sein, da (noch) keine Zeiger -Alias -Analyse gibt.
Mit den Informationen zur Lebendigkeit kann ein Transformationspass, der die Dead Store -Eliminierung durchläuft, IR_ASSIGN -Knoten entfernen, die nachweislich nichts bewirken und die Größe des generierten Codes verringern.
Es gibt drei Backend -Ziele: Text -Assembly -Code von Text, Elf -Objektdateien und Punkt für die Zwischendarstellung. Jedes vom Parser ergebende struct definition wird an das Modul SRC/Backend/Compile.c übergeben. Hier führen wir eine Zuordnung von der Intermediate Control Flow Graph Repräsentation bis zu einem niedrigeren IR durch, wodurch der Code auf etwas reduziert wird, das direkt x86_64 Anweisungen darstellt. Die Definition hierfür findet sich in SRC/Backend/x86_64/coding.h.
Abhängig von den Funktionszeigern, die beim Programmstart eingerichtet sind, werden die Anweisungen entweder an das Elf -Backend oder an die Textanordnung gesendet. Der Code zur Ausgabe von Textbaugruppen ist daher sehr einfach, mehr oder weniger nur eine Zuordnung zwischen den IR -Anweisungen auf niedriger Ebene und ihrem GNU -Syntax -Montagecode. Siehe SRC/Backend/X86_64/Assemble.c.
DOT -Ausgang ist eine separate Pipeline, für die kein niedriger Niveau IR erforderlich ist, um zu erzeugen. Das Kompilierungsmodul leitet den CFG einfach an SRC/Backend/Graphviz/dot.c weiter.
Die Prüfung erfolgt durch Vergleich der Laufzeitausgabe von Programmen, die mit LACC und dem System Compiler (CC) zusammengestellt wurden. Eine Sammlung kleiner eigenständiger Programme, die zur Validierung verwendet werden, finden Sie im Test/ Verzeichnis. Tests werden mit Check.sh ausgeführt, wodurch die Vorverarbeitungs-, Montage- und ELF -Ausgänge validiert werden.
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
Ein vollständiger Test des Compilers wird durchgeführt, indem alle Testfälle in einer selbst gehosteten Version von LACC durchgeführt werden.
make -C test
Dadurch werden zunächst die bereits erstellte bin/lacc zur Herstellung von bin/bootstrap/lacc verwendet, das wiederum zum Erstellen von bin/selfhost/lacc verwendet wird. Zwischen den Bootstrap- und Selfhost -Stufen werden die Zwischenobjektdateien für die Gleichheit verglichen. Wenn alles richtig funktioniert, sollten diese Stufen identische Binärdateien erzeugen. Der Compiler ist "gut", wenn alle Tests die Binärdatei für die Selbsthost bestehen. Dies sollte bei jedem Commit immer grün sein.
Es ist schwierig, eine gute Testsuite zu finden, die alle möglichen Fälle abdeckt. Um Fehler auszurotten, können wir CSmith verwenden, um zufällige Programme zu generieren, die zur Validierung geeignet sind.
./csmith.sh
Das CSmith.SH -Skript führt CSmith aus, um eine unendliche Folge von zufälligen Programmen zu erzeugen, bis etwas den Testkabelbaum fehlschlägt. In der Regel werden Tausende von Tests ohne Versagen durchgeführt.
Die von CSmith generierten Programme enthalten eine Reihe globaler Variablen und Funktionen, die auf diese Mutationen erstellen. Am Ende wird eine Prüfsumme des vollständigen Zustands aller Variablen ausgegeben. Diese Prüfsumme kann dann mit verschiedenen Compilern verglichen werden, um Disktionen oder Fehler zu finden. Siehe Doc/Random.c für ein von CSmith generierter Beispielprogramm, das ebenfalls korrekt von LACC zusammengestellt wird.
Wenn ein Fehler gefunden wird, können wir einen Credits verwenden, um einen minimalen Repro -Repro -Bereich zu erstellen. Dies wird dann als neuer Testfall in der normalen Testsuite enden.
Es wurden einige Anstrengungen unternommen, um den Compiler selbst schnell zu machen (obwohl der generierte Code immer noch sehr unaufhaltsam ist). Wir dienen sowohl als Leistungsbenchmark- als auch als Korrektheitstest und verwenden die SQLite -Datenbank -Engine. Der Quellcode wird als einzelne ~ 7 MB (7184634 -Bytes) große C -Datei verteilt, die mehr als 200 K -Zeilen (einschließlich Kommentare und Whitespace) überspannt, was perfekt für Spannungstests des Compilers geeignet ist.
Die folgenden Experimente wurden auf einem Laptop mit einer I5-7300U-CPU durchgeführt, in der Version 3.20.1 von SQLite3 zusammengestellt wurde. Die Messungen erfolgen aus dem Kompilieren zu Objektcode (-C).
Es dauert weniger als 200 ms, um die Datei mit LACC zu kompilieren, aber anstelle der Zeit sehen wir uns eine genauere Abtastung von CPU -Zyklen und -anweisungen an. Die Hardware-Performance-Zählerdaten werden mit perf stat und Speicherzuweisungen mit valgrind --trace-children=yes gesammelt. In Valgrind zählen wir nur Beiträge des Compiler selbst ( cc1 Executable), während wir GCC ausführen.
Die Zahlen für LACC stammen aus einem optimierten Build, der durch make CC='clang -O3 -DNDEBUG' bin/lacc erzeugt wird. Jeder Compiler wird mit Argumenten -c sqlite/sqlite3.c -o foo.o aufgerufen.
| Compiler | Zyklen | Anweisungen | Zuweisungen | Bytes zugewiesen | Ergebnisgröße |
|---|---|---|---|---|---|
| Lacc | 412.334.334 | 619.466,003 | 49.020 | 24.244,107 | 1,590.482 |
| TCC (0.9.27) | 245.142.166 | 397.514.762 | 2.909 | 23.020.917 | 1.409.716 |
| GCC (9.3.0) | 9,958,514,599 | 14.524.274.665 | 1.546.790 | 1.111.331.606 | 1.098.408 |
| Klang (10.0.0) | 4,351.456,211 | 5.466.808.426 | 1.434.072 | 476.529.342 | 1,116,992 |
Es muss noch Arbeit erledigt werden, um TCC näher zu kommen, was wahrscheinlich einer der schnellsten C -Compiler ist. Trotzdem sind wir in angemessener Entfernung von der TCC -Leistung und einer Größenordnung besser als GCC und Clang.
Aus der obigen Tabelle können wir sehen, dass die Größe der von LACC generierten SQLite -Objektdatei größer ist als die von anderen Compilern generierten, was darauf hindeutet, dass wir weniger optimale Code ausgeben.
Um die relative Qualität des von LACC und GCC generierten Codequalität zu vergleichen, können wir uns mit der Anzahl der dynamischen Anweisungen befassen, die von der von GCC erstellten Binäranlehnung ausgesetzt werden. Wir führen den gleichen Test wie oben aus und kompilieren SQLite zu Objektcode. Ziele für den Test sind der von GCC erzeugte Standard -Compiler Build ( bin/lacc ) und der von LACC erzeugte Self -Binary ( bin/selfhost/lacc ). Beide Ziele werden ohne aktivierende Optimierungen und ohne NDEBUG produziert.
| Compiler | Zyklen | Anweisungen |
|---|---|---|
| Lacc | 946.315.653 | 1.481.608.726 |
| LACC (Selfhost) | 1.417.112.690 | 2.046.996.115 |
Der selbstgeschädigte Binär ist langsamer, SQLite zu kompilieren als der von GCC erstellte Compiler, der zeigt, dass LACC tatsächlich einen eher ineffizienten Code erzeugt. Die Verbesserung des Backends mit einer besseren Auswahl der Anweisungen hat eine Priorität, daher sollten diese Zahlen hoffentlich in Zukunft näher kommen.
Dies sind einige nützliche Ressourcen für den Aufbau eines C -Compilers, der auf X86_64 abzielt.
