Organizing the IR Passes

A plan for running datafun's IR passes in one order, per function, memoized, and for the compile time they cost. Written October 2026, after inline and the cleanup after it (ir::simplify) made the passes a quarter of lowering.

Contents

• Where compile time goes
• The passes as they are
• The order
• Per function, in the module's query
• Later: per-function queries
• Later: lowering on demand
• Phases

Where compile time goes

A script requiring every sys/std module and calling nothing, release build, timed inside the pipeline:

Lowering is twice what analysis costs, and nearly all of it is for functions that never run. Inlining alone is a quarter of it: a pass over every module of the graph, not memoized, that clones each function calling something inline and mints a new handle for its module, which salsa then compares whole.

The passes as they are

The two pipelines do not agree on the order. A script const-inlines, then specializes, then inlines; a module specializes, inlines, then const-inlines. The difference is observable: specialization finds a const argument's value only where a Const instruction defines it, so in a module a function's own const cannot be a const argument, while in a script it can.

The order

One order for both, each step per function:

1. Const inlining: declared consts replaced by their values, branches on them folded, dead blocks and dead code removed.
2. Specialization: each call with const arguments pointed at the copy for those values. Graph-wide, since it makes functions, and gated as now.
3. Inlining, with simplify as its last step: each call to an inline function replaced by the callee's body as steps 1 and 2 left it.
4. Dead code, for what inlining left unread.
5. Const promotion, last, since specialization reads const arguments out of the Const instructions it replaces.

Steps 1 and 3 to 5 touch one function at a time and read nothing but that function and, for step 3, the bodies of inline functions. That is what lets them run where the function's module is assembled.

Per function, in the module's query

For modules, step 1 moves to just after const evaluation (5b), a memoized query per module (const_inlined_module), and steps 3 to 5 move into phase 5d's lower_module, which is already a query per module and already runs in parallel. The graph-wide phase 5c' goes. lower_module is given the handles of the modules that define an inline function (InlineModules, interned, so an unchanged set is the same key), and resolves an inline callee there. One Inliner serves every function of a module, so a callee is expanded once per module rather than once per call.

Scripts run the same steps through the same function (optimize::finish), over the module registry's finished functions for a module callee.

A cycle of inline functions is refused by typecheck (F085), from the calls it resolved, so that no step here can fail: lowering a function, inlining included, reports nothing that analysis did not. That matters for lowering on demand, below, where a failure would surface at the first call. A cycle cannot cross modules, since modules do not require each other in a cycle, so the check is per module.

Later: per-function queries

The module is the finest key the pipeline has: phase 5a lowers a module's functions together, and its result is one handle. A query per function would need a handle per function out of 5a, so that editing one function's body changes one key. With that, steps 3 to 5 become optimized_function, a query per function reading its callees' expanded bodies through queries of their own, and an edit re-optimizes the function and what inlined it.

Later: lowering on demand

The interpreter and the JIT could ask for a function's IR the first time it is called, rather than finding every function of the import closure lowered. For a script requiring every module, that would save 5a's lowering and most of 5d, around a quarter of the run; analysis (parse, typecheck, ownership) is another 9ms and stays eager, so that is the cap.

Consts are the open question. A module's consts are evaluated when the module compiles, and a failure is an error then, whether or not anything reads the const. Lowered on demand, a const's evaluation and its failure would move to its first use, and CTFE's own lowering with them. Whether that is acceptable, and what a module author would see, is not settled. Specialized copies also need an identity that does not depend on which others exist, which today they get from being numbered in a pass over the graph.

Functions that name no const are not part of that question. Keeping consts, and the functions naming them, eager would leave 952 of sys/std's 970 functions to lower on demand; the other 18 name index's and offset's module consts. Nothing is in the way of those 952 semantically:

• Lowering one cannot fail. The only LowerError lowering constructs is BindingNotAvailable, a module const not yet evaluated. Analysis errors are reported before lowering, and a cycle of inline functions is refused by typecheck (F085), so inlining cannot fail either.
• None reaches specialization. A const argument has to be the name of a const binding, so every call site that is specialized names a const, and is eager.
• A call to one is already addressable unlowered: function ids come from the AST (compute_func_id_map), not from lowering.
• The interpreter already turns IR into bytecode on a body's first call, and the JIT compiles on hotness.

What is in the way is plumbing. In rough order of size:

1. The engines are handed a finished ModuleFunctionRegistry, a map built in a memo. Lowering on a miss means a registry that can call back into the compiler, so a salsa handle held while the program runs.
2. That handle pins a revision, and setting an input cancels queries running on other handles: an edit in the REPL or a reactive session would surface as a cancellation in the middle of a run. A one-shot datalove script has no edits. For the others, whether an edit waits for the run, stops it, or leaves it on its revision is a design question of its own.
3. Lowering is per module. This is the per-function query above, which on demand needs anyway.
4. Consts call functions. The first stratum of 5a lowers every function that names no const so that CTFE has them; on demand, CTFE's registry would ask for them through the same query, and the strata go.
5. The AOT and C backends compile what they are given, and would walk what is reachable from the entry instead.
6. Engine fixtures dump every function's IR, and the incremental_lowering and module_memo tests assert what is lowered, so an eager mode stays, for them and for AOT.

Phases

1. The order, per function (done): const inlining moved before specialization for modules, as phase 5b'; steps 3 to 5 in lower_module and in the script pipeline through one function; phase 5c' removed. Specialization now removes the code that built the const arguments of the calls it rewrites, which module const inlining used to do after it. Against the table above, 5b' is 0.23ms and 5d 4.4ms, where 5c' and 5d were 5.65ms together; the whole run went from 35.0ms to 33.6ms. With DATALOVE_PARALLEL set, 5d is 1.5ms, and the run went from 29.3ms to 26.3ms, since inlining now runs in the parallel phase.
2. Per-function handles out of 5a, and optimized_function.
3. Lowering on demand, for functions naming no const once the question of a salsa handle across edits is settled, and for the rest once the const question is.