Memory Allocation for Constant-Bounded Programs
2026-08-14 • Programming Languages
Programming Languages
AI summaryⓘ
The authors study how to efficiently manage memory for programs that have fixed, known limits on how long they run. They propose a new way to allocate stack memory by treating the program’s control flow like a tree and using a method that reduces wasted space, sometimes rearranging memory (defragmentation). Their approach guarantees nearly optimal memory use and works especially well when swapping memory areas in place is allowed. They tested this method in two real-world cases and found it significantly reduces stack size, often by more than 90%, while rarely needing defragmentation.
memory allocationconstant-bounded programsstack usagecontrol flowtree-scan allocationmemory defragmentationeBPFMLIRheap allocationstack spilling
Authors
Vinícius Silva, Kael Soares, Márcio Costa e Fernando Magno Quintão Pereira
Abstract
This work studies memory allocation for constant-bounded programs, whose execution length is syntactically limited for all inputs. Examples of such programs include verified kernel extensions, cryptographic routines, and fixed-shape machine-learning models. We show that constant boundedness enables a tight, polynomial-time approximation of optimal stack usage by viewing control flow as a tree and applying a tree-scan allocation strategy augmented with memory defragmentation. Our approach guarantees memory usage bounded by the maximum live memory plus, at most, the size of the largest buffer, and is optimal when in-place swapping is permitted. We deploy the proposed allocator in two scenarios. First, in an Elixir-to-eBPF compiler, as a spiller that optimizes stack space. Second, as a static heap allocator for bounded MLIR programs using the Structured Control-Flow dialect. Results demonstrate stack reductions exceeding 90% on real eBPF workloads and show that, even under aggressive code expansion, defragmentation is rarely required and memory usage remains a small fraction of that required by naive allocation strategies.