0%

s01 — Research Ratchet: Cranelift Deep Study

Goal

A grounded dossier set on the four Cranelift subsystems Ori’s design borrows shape from — ISLE, regalloc2, the aegraph mid-end, and the compile-speed architecture — each closing with an explicit adopt/adapt/reject verdict recorded as a decision.

Implementation Sketch

Read actual source under ~/projects/reference_repos/lang_repos/wasmtime/cranelift/ (graph-first via intel queries, then manual reads). One dossier file per subsystem in this plan’s content/:

  • ISLE (cranelift/isle/): rule language, term rewriting, how rules compile to matching automata, the verification work (Crocus/veri-isle), what per-rule soundness means. Verdict feeds the s03 ArchConfig design and the s03-recorded future rule-DSL ratchet.
  • regalloc2 (regalloc2 crate, vendored or fetched): SSA-with-block-params input contract (matches BIR), bundles/ranges model, the symbolic checker (checker.rs) design — this is the model for s11’s checker. Capture the allocator/checker INTERFACE, not the code.
  • aegraphs (cranelift/codegen/src/egraph*): acyclic e-graph design, elaboration, rule application strategy, what it buys vs classic pass pipelines. Verdict feeds s19 mid-end framework choice (e-graph vs rule-pipeline).
  • Compile-speed architecture: single-pass lowering, MachInst/DFG storage, no-IR-rewalk choices, function compilation isolation, immutable-vs-worker-local context boundaries, parallel scheduling, cacheable artifacts, and known serialization points. Separate measured claims from architectural inference and identify which choices bound algorithmic work rather than merely improving constants. This feeds s03’s compilation-unit contract, s17’s benchmark design, and s17B’s cache/parallel implementation.

Constraints

  • Clean-room per s00 doc: dossiers capture algorithms/interfaces/invariants in Ori vocabulary; no code transcription.
  • Every dossier claim cites file paths read; UNVERIFIED claims are flagged, never silently asserted.

Work Items

  • ISLE dossier: rule language semantics, automata compilation, verification prior art; adopt/adapt/reject verdict + decision record for the future rule-DSL ratchet.
  • regalloc2 dossier: algorithm structure, block-param handling, spill heuristics, symbolic checker interface; verdict feeding s11 design.
  • aegraph dossier: acyclic e-graph mechanics, elaboration, cost model; verdict feeding the s19 mid-end framework decision.
  • Compile-speed architecture dossier: storage layouts, pass counts, lowering shape, per-function isolation, cacheability, parallel scheduling, shared-state boundaries, and serialization points with measured-claim citations; feeds s03, s17, and s17B.
  • Decision records appended to the plan decisions set: one per subsystem verdict, each citing dossier evidence.