一句话:提出 3CPS 中间表示及静态分析,判定变量绑定范围(寄存器/栈/堆),以支持高阶函数式语言的高效编译。
严格高阶函数式语言(如 OCaml、Scheme、SML)的传统高效编译通常依赖全程序变换,将程序转换为可由传统优化处理的一阶单态表示,但这会丢失高阶和多态特性。本文探索在优化过程中保留高阶与多态性的编译路径,核心是 3CPS:一种分因式化的 CPS 中间表示,静态标注变量的绑定范围。作者将绑定范围分为寄存器、栈、堆三类,分别对应不同机器资源管理方式,并用小步操作语义形式化绑定结构管理,定义判定变量绑定范围的静态分析。在标准 SML 基准程序上评估,分析取得出乎意料的高产出率,并表现出可扩展的性能。该算法也可迁移到 ANF 等 λ-演算 IR。
To date, the most effective approach to compiling strict, higher-order functional languages (such as OCaml, Scheme, and SML) has been to use whole-program techniques to convert the program to a first-order monomorphic representation that can be optimized using traditional compilation techniques. This approach, popularized by MLton, has limitations, however. We are interested in exploring a different approach to compiling such languages, one that preserves the higher-order and polymorphic character of the program throughout optimization. To enable such an approach, we must have effective analyses that both provide precise information about higher-order programs and that scale to larger units of compilation. This paper describes one such analysis for determining the extent of variable bindings. We classify the extent of variables as either register (only one binding instance can be live at any time), stack (the lifetimes of binding instances obey a LIFO order), or heap (binding lifetimes are arbitrary). These extents naturally connect variables to the machine resources required to represent them. We believe that precise information about binding extents will enable efficient management of environments, which is a key problem in the efficient compilation of higher-order programs. At the core of the paper is the 3CPS intermediate representation, which is a factored CPS-based intermediate representation (IR) that statically marks variables to indicate their binding extent. We formally specify the management of this binding structure by means of a small-step operational semantics and define a static analysis that determines the extents of the variables in a program. We evaluate our analysis using a standard suite of SML benchmark programs. Our implementation gets surprisingly high yield and exhibits scalable performance. While this paper uses a CPS-based IR, the algorithm and results are easily transferable to other λ-calculus IRs, such as ANF.