# `firnc`: der `escape`-Durchgang ist exponentiell in der Blocktiefe **Befund aus RUNDE SCHLEUSE-2/-3 (08.09.2026).** Betrifft `firnc` Stufe 0, ``. **Am Compiler wurde nichts geändert** — dieser Text ist der Befund samt Messreihe und einem konkreten Behebungsvorschlag. --- ## 1. Kurzfassung Beim Übersetzen von tief geschachteltem Firn-Quelltext verdoppelt sich die Laufzeit von `firnc` **mit jeder weiteren Schachtelungsebene**. Die Kosten sind zusätzlich linear in der Zahl der Anweisungen: ``` Kosten ≈ 2^Tiefe · Anweisungen ``` Ab etwa 25 Ebenen ist damit Schluss. Ein maschinell erzeugter Quelltext aus SQLite (WASM → Firn, 1340 Funktionen) ließ sich **überhaupt nicht mehr bauen**: der Lauf brach nach 1,5 Stunden bei 682 MB Speicher immer noch nicht ab. Der Durchgang lässt sich **nicht abschalten** — `--no-pass` kennt ihn nicht, er gehört zur semantischen Analyse, nicht zum Optimierer. --- ## 2. Die Messreihe ### 2.1 Reine Tiefe Minimalprogramm: `n` geschachtelte `while true`, **eine** Anweisung ganz innen, sonst nichts. | Ebenen | `firnc` | |---:|---:| | 22 | 5 s | | 24 | 22 s | | 25 | 41 s | | 26 | 81 s | **Faktor ≈ 2 je Ebene.** Von 24 auf 26 Ebenen — zwei Ebenen mehr — vervierfacht sich die Bauzeit. ### 2.2 Anweisungen bei fester Tiefe Tiefe konstant 20, verschieden viele Anweisungen je Ebene: | Aufbau | `firnc` | |---|---:| | Tiefe 20, 50 Anweisungen je Ebene (1 000 gesamt) | 49 s | | Tiefe 20, 100 Anweisungen je Ebene (2 000 gesamt) | 90 s | **Linear in der Anweisungszahl.** Zusammen mit 2.1 ergibt das das Kostenmodell oben. ### 2.3 Gegenprobe: flach ist billig Dieselbe Menge Code (≈ 9 000 Anweisungen), einmal flach als Zustandsautomat, einmal 22 Ebenen tief geschachtelt: | Form | `firnc` | |---|---:| | flach: `while true { match fall { 300 Arme × 30 Anweisungen } }` | **1 s** | | geschachtelt: 22 Ebenen × 410 Anweisungen | **1 477 s** | **Faktor 1 477 bei gleicher Codemenge.** Nicht die Codemenge ist das Problem, sondern **allein die Tiefe**. ### 2.4 Der Beweis am echten Fall SQLite 3.45.0, aus WASM erzeugter Firn-Quelltext, ~840 000 Zeilen: | Erzeugung | max. Blocktiefe | `firnc` | |---|---:|---:| | geschachtelt (RUNDE SCHLEUSE-2) | 25 | **> 1,5 h, nie fertig** | | ein flacher Verteiler je Funktion (SCHLEUSE-3) | **4** | **79–81 s** | Die Tiefe 4 gilt für **alle 1340** erzeugten Funktionen. Was in der Datei noch tiefer liegt (bis 24), ist ausschließlich handgeschriebene Laufzeit (`w_fd_readdir` und Geschwister), nicht erzeugter Code. Gleiche Semantik, gleiches Programm, gleicher Compiler. Nur die Schachtelung ist weg. --- ## 3. Wo es brennt Rückverfolgung eines hängenden Laufs (`gdb -p … -batch -ex bt`), immer wieder dasselbe Bild: ``` #0 __memcmp_avx2_movbe () #1 ::path () #2 ::stmt () #3 ::stmt () #4 ::stmt () ... ``` Weitere beobachtete Spitzen: `escape::Pass::expr`, `escape::Pass::store_value`, `escape::merge`. Zwei Beobachtungen aus dem laufenden Prozess: * **Der Speicherverbrauch bleibt konstant** (682 MB über eine Stunde). Es wird also nicht immer mehr aufgebaut, sondern immer wieder *dasselbe durchlaufen*. * Die Rekursionstiefe im Rückverfolgungsstapel ist **klein** (unter 40 Rahmen). Die Explosion steckt nicht in der Rekursionstiefe selbst, sondern darin, **wie oft** `stmt` je Anweisung erneut betreten wird. Das ist das typische Muster eines Durchgangs, der pro Blockebene die Zustände seiner Kindebenen erneut auswertet, ohne Ergebnisse zu behalten: jede Ebene verdoppelt die Arbeit der darunterliegenden. Dazu kommt, dass `path` mit **`memcmp`** arbeitet — Zugriffspfade werden offenbar als Zeichenketten verglichen statt über vorab vergebene Kennungen. --- ## 4. Vorschlag zur Behebung Drei Maßnahmen, nach Aufwand geordnet. Die erste allein sollte das Problem erledigen. ### 4.1 Memoisierung je Anweisungsknoten (der eigentliche Fix) Der Durchgang wertet Teilbäume mehrfach aus. Ein Zwischenspeicher `Knoten-Kennung → Ergebnis` macht daraus einen einzigen Durchlauf: ```rust // Skizze struct Pass { memo: HashMap<(StmtId, ZustandsId), EscapeInfo>, // ... } fn stmt(&mut self, s: StmtId, ein: ZustandsId) -> EscapeInfo { if let Some(fertig) = self.memo.get(&(s, ein)) { return fertig.clone(); } let ergebnis = self.stmt_berechnen(s, ein); self.memo.insert((s, ein), ergebnis.clone()); ergebnis } ``` Aus `2^Tiefe` wird damit `Anzahl Knoten × Anzahl verschiedener Eingangszustände` — in der Praxis linear. **Voraussetzung:** der Eingangszustand muss als Wert vergleichbar sein (siehe 4.2). Ist er das nicht, ist die Memoisierung wertlos, weil kein Treffer je passt. ### 4.2 Blockmengen statt Pfad-Zeichenketten `escape::Pass::path` landet in `memcmp`, also werden Zugriffspfade als Text verglichen. Zwei Änderungen: 1. **Pfade internieren.** Jeder Pfad (`a.b.c`, `*p`, `&DATA0[0]`) bekommt beim ersten Auftreten eine `u32`-Kennung. Vergleiche werden zu Ganzzahlvergleichen, `memcmp` verschwindet aus dem Profil. 2. **Zustände als Bitmengen führen.** Der Zustand einer Blockebene ist „welche Pfade entkommen hier" — also eine Menge über den internierten Kennungen. Als Bitmenge (`FixedBitSet`) sind Vereinigung (`merge`) und Vergleich ein paar Maschinenwörter statt einer Schleife über Zeichenketten. Genau das macht `merge` billig genug, damit 4.1 überhaupt trifft. Damit wird der Durchgang zu einer gewöhnlichen Datenflussanalyse über Blockmengen — dieselbe Bauform, die jeder Compiler für Lebendigkeitsanalyse verwendet. ### 4.3 Notbremse für erzeugten Quelltext Unabhängig von 4.1/4.2 sinnvoll, weil billig: * Eine **Warnung ab einer Schachtelungstiefe** von etwa 30 — „diese Funktion ist *n* Ebenen tief, der `escape`-Durchgang wird dadurch sehr teuer". Wer maschinell erzeugten Quelltext baut, sieht sofort, woran es liegt, statt eine Stunde zu warten. * `--zeit-je-durchgang` (oder `--pass-timings`): eine Zeile je Durchgang mit seiner Laufzeit. Der ganze Befund hier hätte damit fünf Minuten statt eines Tages gekostet. --- ## 5. Was das für die Erzeuger bedeutet Bis 4.1/4.2 da sind, gilt für alles, was Firn-Quelltext **erzeugt**: > **Schachteln ist teuer, Zustandsautomaten sind billig.** > Kontrollfluss gehört in eine Fallnummer, nicht in die Blockstruktur. RUNDE SCHLEUSE-3 hat das umgesetzt: statt geschachtelter Blöcke bekommt jede Funktion **einen** flachen Verteiler. ```firn var fall: u64 = 0 while true { match fall { 0 => { … fall = 3 continue } 1 => { … break } _ => { break } } } ``` Tiefe: `while` + `match` + Arm = **3**, unabhängig davon, wie tief das Eingabeprogramm schachtelt. Ergebnis siehe 2.4. Nebenbefund, für Erzeuger wichtig: **`firnc` erlaubt keine zwei Anweisungen in einer Zeile**, auch nicht in geschweiften Klammern. `if x { a = 1 continue }` ist ein Syntaxfehler (`expected ';' or an end of line`). Erzeugter Quelltext muss mehrzeilig sein. --- ## 6. Wie sich der Befund nachstellen lässt ```bash # 26 Ebenen, eine Anweisung innen -> ~80 s python3 - <<'PY' D=26 o=['fn g(p: u64) -> u64 {',' var a: u64 = p'] i=1 for d in range(D): o.append(' '+' '*i+'while true {'); i+=1 o.append(' '+' '*i+'a = a + 1') for d in range(D): i-=1; o.append(' '+' '*(i+1)+'break'); o.append(' '+' '*i+'}') o+=[' return a','}','fn main() -> i32 { return 0 }'] open('/tmp/tief26.fi','w').write('\n'.join(o)) PY time firnc --profile=app -o /tmp/tief26 /tmp/tief26.fi ``` `D` auf 22/24/25/26 setzen ergibt die Reihe aus 2.1.