Compilerkonstruktion

Heute nutzt man Frameworks wie LLVM (Low Level Virtual Machine). Clang, Rust, Swift, Kotlin... alle basieren auf LLVM. Du schreibst das Frontend (Parsing deiner Sprache). Dann gibst du es an LLVM (Intermediate Representation). LLVM macht die heavy Optimierung und Codegenerierung für alle CPUs der Welt.

1. Phasen

1. Lexer (Scanner): Zerhackt Text in Wörter (Tokens). if, (, x, ).
2. Parser: Baut den Baum (AST - Abstract Syntax Tree). if (x) { ... }.
3. Semantic Analysis: Prüft Sinn. "x ist ein String, du kannst ihn nicht addieren." (Type Checking).
4. Optimization: Loop Unrolling, Constant Folding, Dead Code Elimination. (Hier passiert die Magie).
5. Code Gen: Register Allocation (schwerstes NP-Problem), Instruktionsauswahl.

2. Bootstrapping

Wie kompiliert man den ersten C-Compiler? Wenn er in C geschrieben ist... wer kompiliert ihn dann? Man schreibt den allerersten Compiler in Assembler (oder einer anderen Sprache). Dann kompiliert der erste C-Compiler den zweiten (besseren) C-Compiler. "Sich am eigenen Schopf aus dem Sumpf ziehen."

1. SSA Form (Static Single Assignment)

Moderne Compiler (wie GCC oder LLVM) arbeiten intern fast ausschließlich in SSA-Form. Jede Variable wird exakt einmal zugewiesen. Aus x = x + 1 wird x2 = x1 + 1. Warum dieser Aufwand? Es macht Optimierungen trivial.

• Dead Code Elimination: Wenn x2 nirgendwo benutzt wird, kann man die ganze Zeile löschen.
• Constant Propagation: Wenn der Compiler sieht, dass x1 immer 5 ist, kann er x2 = 6 direkt zur Kompilierzeit berechnen. Ohne SSA-Form wären moderne hocheffiziente Programme (Videospiele, Video-Encoder) ca. 30-50% langsamer.

2. Data Flow Analysis & Liveness

Wie weiß der Compiler, ob er eine Variable in ein CPU-Register oder in den (langsamen) RAM stecken soll? Durch Liveness Analysis. Der Compiler wandert den Kontrollfluss-Graphen (CFG) rückwärts ab und prüft für jeden Punkt: "Wird dieser Wert in der Zukunft noch gebraucht?". Werte, die sich "überlappen" (beide gleichzeitig leben), dürfen nicht im selben Register liegen. Dieses Problem wird als Graph-Coloring (Graphenfärbung) modelliert. Da echte Graphenfärbung NP-vollständig ist, nutzen Compiler clevere Heuristiken (Linear Scan), um in Millisekunden eine "gut genug" Entscheidung zu treffen.

3. Das "Ken Thompson Hack" Problem

Eine gruselige Erkenntnis aus dem Compilerbau: Der Trusting Trust Angriff. Wenn ein Hacker den C-Compiler so manipuliert, dass er beim Kompilieren von Login-Programmen (wie sudo) ein Backdoor einbaut – und gleichzeitig den Code des Compilers selbst so manipuliert, dass er das Backdoor beim Sich-selbst-kompilieren weiterträgt – dann ist das Backdoor im Binärcode "unsichtbar". Man sieht es im Sourcecode des Compilers nicht, aber jedes Programm, das damit gebaut wird, ist infiziert. Es gibt kaum eine Verteidigung dagegen, außer Compiler mit verschiedenen anderen Compilern querzuprüfen (Diverse Double-Compiling).