Local named functions can allocate dead closures after inlining

[tanyongkiam]

Summary

A small nonrecursive local function written with fun can allocate a fresh
closure on every execution even though its only call is eventually inlined. The
semantically equivalent val f = fn ... spelling is inlined earlier and does
not allocate.

In the example below, the late BVL inliner removes the call to bump but leaves
a dead 24-byte closure allocation inside the loop. Over 100 million iterations,
that is 2.4 GB (about 2.24 GiB) of avoidable allocation. The named form was
1.76× slower in paired x64-64 measurements.

Reproducer

Named local function:

fun loop n acc =
  if n = 0 then acc
  else
    let fun bump x = x + 1
    in loop (n - 1) (acc + bump n) end;

fun main () =
  let val n = Option.valOf (Int.fromString (List.hd (CommandLine.arguments ())))
  in print_int (loop n 0); print "\n" end;

main ();

The control changes only the local binding:

-    let fun bump x = x + 1
+    let val bump = fn x => x + 1
     in loop (n - 1) (acc + bump n) end;

From an x64-64 build directory containing cake and basis_ffi.c, save the
variants as /tmp/named.cml and /tmp/anonymous.cml, then run:

./cake < /tmp/named.cml > /tmp/named.S
./cake < /tmp/anonymous.cml > /tmp/anonymous.S
cc -O2 /tmp/named.S basis_ffi.c -lm -o /tmp/named
cc -O2 /tmp/anonymous.S basis_ffi.c -lm -o /tmp/anonymous

env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
  /tmp/named 100000000 > /tmp/named.out
env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
  /tmp/anonymous 100000000 > /tmp/anonymous.out
cmp /tmp/named.out /tmp/anonymous.out

/usr/bin/time -f 'named: %e s' \
  env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
  /tmp/named 100000000 > /dev/null
/usr/bin/time -f 'anonymous: %e s' \
  env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
  /tmp/anonymous 100000000 > /dev/null

Both variants print 5000000150000000.

Measurements

Form	Median	Interquartile range	Relative
local fun bump	0.640 s	0.620–0.670 s	1.76×
local val bump = fn	0.365 s	0.350–0.385 s	1.00×

Generated-code evidence

After clos_known, the named form still contains a Letrec and an annotated
application of bump. The anonymous form has already substituted the body at
the call site.

After bvl_inline, the named loop has this shape:

(let
  (c <- (Cons closure_tag 0 (Label loop_bump_clos)))
  (call loop
    (Add (let (d <- n) (Add 1 d)) acc)
    (Sub 1 n)))

The Add 1 d is the inlined body of bump, while c is never read. The closure
allocation is therefore dead, but it survives through final code generation.
The x64 loop checks for 24 bytes of heap and stores the closure header, code
pointer, and empty environment on every iteration. The anonymous loop has no
corresponding heap check or allocation.

The named executable also retains separate loop_bump worker and closure-wrapper
symbols; the anonymous executable does not retain a bump symbol.

Cause

clos_known treats anonymous Fn and Letrec differently:

• an anonymous Fn can receive a body-carrying Clos approximation
  (clos_knownScript.sml);
• every Letrec, including this single function with no recursive occurrence,
  receives ClosNoInline
  (clos_knownScript.sml).

decide_inline can body-inline only Clos; ClosNoInline merely enables a
direct-call annotation
(clos_knownScript.sml).
Closure conversion consequently materializes the local closure before the BVL
pass gets an opportunity to inline its call; the single-function Letrec
lowering constructs a closure block
(clos_to_bvlScript.sml).
The later inliner substitutes the worker body but does not perform the
higher-level use/escape cleanup needed to remove the already-materialized
closure, wrapper, and worker.

This is a source-spelling performance cliff, not a correctness problem.

Expected behavior

For a small local function that is provably nonrecursive and nonescaping,
equivalent fun f x = e and val f = fn x => e forms should produce equivalent
optimized code. If all uses have been inlined or converted to direct worker
calls, no closure should be allocated.

Possible implementation direction

1. Analyze dependencies within Letrec groups and identify singleton or
   otherwise nonrecursive SCCs.
2. Give small nonrecursive members body-carrying approximations, subject to the
   existing inlining and growth limits, instead of assigning every member
   ClosNoInline.
3. Split recursive groups into dependency SCCs where possible; retain the
   conservative treatment for genuinely recursive members.
4. Add post-inlining closure use/escape cleanup so a closure allocation and its
   wrapper/worker can be removed when no value use remains.

The first two steps should fix this minimal case by allowing the inlining to
happen before closure conversion.

Regression coverage

• Compare equivalent nonrecursive local fun and val ... = fn ... forms.
• Check optimized IR or emitted code to ensure the hot loop contains no closure
  construction or heap-space check.
• Check that an unused wrapper and worker are removed in sealed compilation.
• Cover self recursion and mutually recursive and groups to ensure SCC and
  growth handling remain bounded.
• Include a nonescaping direct-call case too large to inline, which should use a
  worker call without allocating a closure if all uses are known.

Related issues

• #338, “Function inlining in closLang”, introduced the relevant early-inlining capability and is closed. This issue is a concrete remaining gap for nonrecursive Letrec bindings plus post-inline cleanup.
• #267, “Add simple form of higher-order inlining”, concerns specialization of higher-order recursive library functions and is distinct from this first-order local case.

Written by Codex (OpenAI).

[myreen]

I'm hoping clos_known and clos_call will be removed, and instead implemented as part of source_to_flat. In other words, it might not make sense to fix clos_known and clos_call. Effort should instead be put on improving source_to_flat.