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 SoA layouts, no-IR-rewalk choices, lazy DFG. Concrete structural choices only — feeds s17 benchmark design and BIR layout confirmation.

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: enumerated structural choices (storage layouts, pass counts, lowering shape) with measured-claim citations; feeds s17 methodology.
  • Decision records appended to the plan decisions set: one per subsystem verdict, each citing dossier evidence.