Make Lambda optimization decisions stable across normalization timing

[cristianoc]

Objective

Make Lambda optimization decisions stable when equivalent normalization moves between production and later passes. Such movement must preserve semantics, and it should not accidentally degrade generated JavaScript because a downstream cost model or analysis saw a different intermediate shape.

This is an incremental hardening effort, not a proposal to replace the backend or put Lambda into a heavyweight normal form.

Current state

• Merge the Lam IR into Lambda #8608 removed the duplicate Lam representation and its conversion layer. The backend now operates on one private Lambda.t.
• Lambda has seven constructors that normalize as they build. Code outside lambda.ml cannot bypass them, but code inside the owning module still can.
• Lambda.apply now routes the primitive terms produced by eta reduction through the folding constructors.
• offset_ref is gone: it was removed along with the %incr, %decr and %refget builtins it served, so there is nothing left to route.
• mk_builtin routes its primitive case through Lambda.prim. Its Eliminated Ignore case still builds Lsequence directly, so it does not get the folding seq performs.
• Match guards are kept as structured action data until their fallthrough is known. Normalization can no longer erase the only record that a case was guarded.
• tests/tests/src/switch_action_count_test.res pins both sides of the remaining normalization-timing problem: merging actions earlier can improve one integer switch and degrade another.

Critical path

1. Stabilize integer-switch planning for normalized actions

The integer switcher chooses between jump tables and interval tests using the set of distinct actions it receives. Normalization can merge actions before the switcher plans, changing that count and therefore changing the plan.

This is not uniformly beneficial or harmful:

• In improves_when_merged, folding 10 + 10 to 20 reveals one contiguous action for cases 1–3 and allows four branches to collapse to one range test.

• In regresses_when_merged, the same kind of merging drops the action count below the current jump-table threshold and turns a compact table into a longer comparison chain.

• Decide the cost model against the representation the switcher should consume: either normalize actions before planning and recalibrate the model, or make the decision insensitive to equivalent action merging.

• Make improves_when_merged select the compact range plan.

• Keep regresses_when_merged as a jump table.

• Verify that no unrelated generated-JavaScript snapshots change.

2. Finish making normalization a single point

Once switch planning is stable against normalized actions:

• Route Lambda.apply through the folding constructors.
• Remove offset_ref rather than route it; its builtins are gone.
• Route mk_builtin's primitive case through Lambda.prim.
• Route mk_builtin's Eliminated Ignore case through Lambda.seq, which drops a discarded block allocation or null conversion that the raw Lsequence keeps.
• Audit remaining direct construction inside lambda.ml. Every raw node built there is now either a constructor's own fallthrough or the Ignore case above.
• Run the full compiler, analysis, and generated-output suites after each step.

mk_builtin must remain after the switch-planning work in this sequence. Routing it through Lambda.prim folds actions earlier and exposes the cost-model sensitivity described above.

Independent workstreams

Make the pass sequence and diagnostics truthful

compiler/core/lam_compile_main.ml currently performs three deep_flatten rounds, three simplify_alias rounds, three simplify_exits rounds, and three collect_info refreshes. The sequence is hand-unrolled and its diagnostic labels do not all describe the pass whose output they dump.

• Rename the -debug-ir labels to match the actual pass sequence.
• Remove the inactive scc dump label with its commented-out pass, or restore the pass and label together.
• Stop labelling the output of guard_raises as simplify_lets.
• Document the current sequence as a table, including which statistics snapshot each pass consumes.
• Update compiler/core/README.md: it still links to deleted lam_convert.ml and says six constructors normalize, while lambda.mli defines seven.

Define statistics freshness and ownership

One mutable Lam_stats.t.ident_tbl is refreshed between passes and also mutated during rewriting, including by beta reduction. Shape-sensitive decisions consume it without an explicit validity interval.

• Catalogue each reader and writer of ident_tbl and state the term version for which each entry is valid.
• Decide whether each analysis round should produce a fresh immutable snapshot or whether controlled mid-pass refinement is required.
• Add a focused regression that demonstrates the stale-information behavior before changing ownership.
• Remove accumulation of entries that no longer describe identifiers in the current term.

Choose one binding-placement policy

Lam_pass_deep_flatten hoists bindings into enclosing groups, while Lam_pass_lets_dce can substitute only bindings that remain local. The current rhs_is_beta_residue guard prevents one known regression by keeping beta-reduction residue local.

• Decide where final binding placement belongs relative to substitution and DCE.
• Express that policy in the pass schedule rather than through producer-specific shape recognition.
• Remove the beta-residue exception once the general policy preserves the intended a_recursive_type.mjs output.

Grow effect-order oracle coverage

• Add an observable test for inlined-call argument order in Fix argument evaluation order under function inlining #8572.
• Add focused tests for effect ordering across eta reduction, partial application, match-action sharing, and binding movement.

Audit remaining cross-layer conventions

The consumer that recognized *opt_<label>* identifier names disappeared with lam_convert; the generated name is now only a producer-side artifact. The #default and #optional_arg_default attributes remain cross-layer conventions.

• Document the remaining producers and consumers of these attributes.
• Replace an attribute with structural data only where it still carries information across a boundary and can be lost or forged.

Investigation: pipeline idempotence

Running the entire optimization pipeline twice may be a useful diagnostic, but “the second run is the identity” is not yet a well-defined CI invariant.

Before promoting it to CI, define:

• structural versus physical equality;

• treatment of fresh identifiers;

• whether statistics are rebuilt or reused;

• the exact pass interval being repeated;

• whether the required invariant is Lambda equality or generated-JavaScript equality.

• Build the experiment and classify the differences before deciding whether an idempotence assertion belongs in CI.

Resolved findings

• Fix argument evaluation order under function inlining #8572 fixed beta reduction stacking non-substitutable argument bindings in reverse parameter order.
• Merge the Lam IR into Lambda #8608 made match guards structural instead of encoding “patch this fallthrough later” as Lstaticraise (0, []) inside a foldable conditional.
• Merge the Lam IR into Lambda #8608 removed the duplicate Lam IR, conversion layer, obsolete alpha/apply-arity passes, and the optional-identifier name consumer.
• Lambda.apply now uses the folding constructors for terms created by eta reduction.

Operational design rules

1. A foldable Lambda shape must not be the only record of a semantic decision that a later phase must recover. Carry such information structurally until it is consumed.
2. Shape recognition used as a conservative optimization may remain semantically sound, but output stability additionally requires that it consume a canonical representation or explicit metadata.
3. A constructor may replace a node with an equivalent one, but code motion between branches belongs in a scheduled pass.
4. Every optimization change needs both an observable semantic oracle where ordering matters and generated-output fixtures around relevant cost-model boundaries.

Background

• N-ary functions: make arity structural across the compiler #8557 / Eliminate Pjs_fn_make, Pjs_fn_make_unit, and unsafe_adjust_to_arity #8570 exposed round- and binding-shape sensitivity while removing the old function wrappers.
• Fix argument evaluation order under function inlining #8572 fixed the argument-evaluation-order miscompilation uncovered during that review.
• Merge the Lam IR into Lambda #8608 unified Lambda and Lam, removed conversion, and made the remaining normalization boundary explicit.
• flexible_array_test.res and a_recursive_type.mjs contain the historical examples that motivated the pass-timing and binding-placement work.