Spec M13 (backlog) — sizing a program's memory at compile time

Owner's idea: mc figures out how much memory the compiled program needs and fixes the runtime allocation at compile time (today a program declares u8 heap[N] by hand; the compiler itself uses 32 MiB and touches 14.5 MiB).

What's statically decidable and what isn't:

• Static: globals, strings, arrays, frames (already known by gen). A --mem-report is cheap and already useful.

• Dynamic (rt_alloc/xalloc in a loop): undecidable in the general case. Three viable paths, from cheapest to most ambitious:

  1. Profiling: --profile-heap instruments the runtime's xalloc to record the peak (hp), and the compiler writes the value (with a configurable margin) as HEAP_SIZE on a rebuild — exactly the measurement we did by hand for mc itself.
  2. Annotation: #heap N or per-call limits (rt_alloc(n) with a constant n and a call count outside of loops) — Tier 2's pass() can sum this over the AST.
  3. Bound analysis: for programs with loops bounded by constants (the compiler is one of them: MAX*), a pass estimates sum(n_i * k_i); otherwise it falls back to path 1.
• The mechanics of "fixing it at compile time" already exist: the arena is a symbol in __bss with zsize; the backend just needs to write the computed size (the .o/--exe don't grow on disk).

Prerequisites: M12 (the example's lib/rt.mc runtime is the guinea pig). No deadline.

Edit this page