Michael Schimmel
8f7947bde1
This commit introduces a new AST analysis pass that identifies function purity and recursion. This information is then used by the optimizer and specializer to make more informed decisions, particularly regarding inlining. The `Analyzer` struct and its associated `Analysis` struct are responsible for traversing the AST and collecting this data. Key changes include: - A new `analyzer` module is added to `ast::compiler`. - `Analyzer::analyze` performs a two-pass traversal to collect global-to-lambda mappings and then analyze purity and recursion. - The `Optimizer` and `Specializer` are updated to accept and utilize the `Analysis` data. - Recursion checks in `Optimizer` and `Specializer` are replaced with checks against the pre-computed `Analysis.is_recursive` set. - The `Environment` now stores and passes the `Analysis` results to the compiler stages.
49 lines
3.3 KiB
Markdown
49 lines
3.3 KiB
Markdown
# Analyse der AST-Optimierungen und Spezialisierung
|
|
|
|
*Datum: 23.05.2024*
|
|
*Tool: `src/bin/ast.rs` mit `--dump`*
|
|
|
|
## 1. Motivation
|
|
Diese Analyse untersucht die Effektivität der Rust-Portierung des Optimizers. Ziel war es, die theoretischen Konzepte aus den Design-Dokumenten (wie "Closure Cracking" und "Beta-Reduction") empirisch am lebenden Objekt zu verifizieren.
|
|
|
|
## 2. Kern-Erkenntnisse
|
|
|
|
### A. Aggressives Constant Folding (The "Zero-Cost" Promise)
|
|
Der Optimizer ist extrem aggressiv bei der Vorkalkulation von Werten. Ein komplexer Ausdruck wie:
|
|
```lisp
|
|
(do
|
|
(def MYPI 3.14)
|
|
(def radius 10)
|
|
(* MYPI (* radius radius)))
|
|
```
|
|
wird im optimierten AST zu einer einzigen Konstante reduziert: `Constant: 314`.
|
|
**Erstaunlich:** Nicht nur die Arithmetik wird gefaltet, sondern auch die `def`-Bindungen werden komplett eliminiert (Dead Code Elimination), da sie nach dem Inlining nicht mehr benötigt werden.
|
|
|
|
### B. Beta-Reduction & Lambda-Inlining
|
|
Aufrufe von Lambda-Literalen werden bereits zur Compile-Zeit "geknackt" (Cracking).
|
|
* **Beispiel:** `((fn [x] (+ x 1)) 10)` -> `Constant: 11`.
|
|
* **Verschachtelung:** Selbst bei verschachtelten Lambdas wie `((fn [x] (fn [] x)) 10)` erkennt der Optimizer die Konstante und reduziert den äußeren Aufruf auf ein Lambda, das lediglich `Constant: 10` zurückgibt.
|
|
|
|
### C. Die Rolle der Spezialisierung (Monomorphisierung)
|
|
Eine der wichtigsten architektonischen Erkenntnisse war das Verhalten des `Specializer`. Selbst wenn das Tool mit `--no-opt` aufgerufen wird, tauchen im Dump oft spezialisierte Closures auf.
|
|
* **Grund:** Die Spezialisierung ist in `Environment::link` fest verdrahtet, da sie für die Korrektheit (z. B. Overload-Resolution von Operatoren wie `+`) notwendig ist.
|
|
* **Effekt:** Ein globaler Aufruf von `f` mit einem `Int` wird zu einem Aufruf einer spezialisierten Version von `f`, die bereits auf `Int` optimiert wurde. Der "echte" Optimizer baut darauf auf und führt dann das Inlining durch.
|
|
|
|
## 3. Überraschungen & Kuriositäten
|
|
|
|
### Der Rekursions-Schutz
|
|
Beim Testen einer rekursiven Funktion `(def f (fn [x] (f x)))` zeigte der Dump ein interessantes Muster:
|
|
* Der Optimizer führt genau eine Ebene des Inlinings durch, bevor der `inlining_stack` greift.
|
|
* Im Dump resultiert dies in einem "Callee", der selbst ein Lambda ist, welches wiederum die globale Funktion aufruft.
|
|
* Dabei tauchten spezialisierte Typen wie `Vector(Any, 1)` oder `Matrix(Any, [1, 1])` auf. Dies sind interne Artefakte der Monomorphisierung, die zeigen, wie das System versucht, Argumentlisten in einheitliche Tupel-Strukturen zu zwingen (Unification).
|
|
|
|
### String-Folding
|
|
Der Optimizer beherrscht das Zusammenfügen von Strings via `+` bereits zur Compile-Zeit.
|
|
* `(+ "Hello, " "Rust!")` wird im AST direkt zu `"Hello, Rust!"`.
|
|
* Dies ist besonders wertvoll für Makros, die Code-Teile oder Bezeichner generieren.
|
|
|
|
## 4. Fazit für die Entwicklung
|
|
Die Pipeline (Expand -> Bind -> Specialize -> Optimize -> TCO) ist robust. Die Entscheidung, die Spezialisierung vor den Optimizer zu schalten, erweist sich als goldrichtig, da der Optimizer so auf einem bereits typsicheren und "aufgecrackten" Baum operieren kann.
|
|
|
|
Das Tool `ast.exe --dump` bleibt das wichtigste Instrument, um sicherzustellen, dass neue Sprachfeatures nicht den "Fast Path" des Compilers verlassen.
|