Analyzing binding extent in 3CPS
Analyzing binding extent in 3CPS
复制标题
分析 3CPS 中的结合程度
DOI：
10.1145/3547645
复制
发表时间：
2022
影响因子：
--
通讯作者：
Shivers, Olin
中科院分区：
文献类型：
--
作者：
Quiring, Benjamin;Reppy, John;Shivers, Olin
迄今为止，编译严格的高阶函数式语言（如OCaml、Scheme和SML）的最有效方法是使用整个程序技术将程序转换为一阶单态表示，可以使用传统编译技术进行优化。然而，这种由MLton推广的方法有其局限性。我们有兴趣探索一种不同的方法来编译这样的语言，在整个优化过程中保留程序的高阶和多态特性。为了实现这样的方法，我们必须有有效的分析，既能提供关于高阶程序的精确信息，又能扩展到更大的编译单元。本文描述了一个这样的分析，以确定变量绑定的程度。我们将变量的范围分类为寄存器（任何时候只有一个绑定实例可以存活），堆栈（绑定实例的生命周期遵循LIFO顺序）或堆（绑定生命周期是任意的）。这些区段自然地将变量连接到表示它们所需的机器资源。我们相信，精确的信息绑定程度将使环境的有效管理，这是一个关键问题，在高效率的编译高阶programmes.At文件的核心是3CPS中间表示，这是一个因素的CPS为基础的中间表示（IR），静态标记变量，以表明其绑定程度。我们正式指定管理的绑定结构，通过一个小步骤的操作语义和定义一个静态分析，确定程序中的变量的范围。我们使用一套标准的SML基准程序来评估我们的分析。我们的实现获得了惊人的高产量和可扩展的性能。虽然本文使用了基于CPS的IR，但算法和结果可以很容易地转移到其他λ-演算IR，如ANF。
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 theextentof variable bindings. We classify the extent of variables as eitherregister(only one binding instance can be live at any time),stack(the lifetimes of binding instances obey a LIFO order), orheap(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.
登录
查看更多内容
使用“Pseudoknot”（浮动密集型基准）对函数式语言进行基准测试
影响因子：
1.1
作者：
Pieter H. Hartel;Marc Feeley;M. Alt;Lennart Augustsson;Peter Baumann;M. Beemster;Emmanuel Chailloux;Christine H. Flood;Wolfgang Grieskamp;John H. G. van Groningen;Kevin Hammond;Bogumil Hausman;M. Ivory;Richard E. Jones;J. Kamperman;Peter Lee;Xavier Leroy;R. D. Lins;S. Loosemore;Niklas Röjemo;Manuel Serrano;J. Talpin;J. Thackray;Stephen Thomas;Pum Walters;Pierre Weis;Peter Wentworth
通讯作者：
Peter Wentworth
从 ML 到 Ada：通过源翻译实现强类型语言互操作性
影响因子：
1.1
作者：
A. Tolmach;D. Oliva
通讯作者：
D. Oliva
影响因子：
0.6
作者：
Vardoulakis, Dimitrios;Shivers, Olin
通讯作者：
Shivers, Olin
MLton 中的整个程序编译
DOI：
10.1145/1159876.1159877
发表时间：
2006
期刊：
Higher-Order and Symbolic Computation
影响因子：
--
作者：
Stephen Weeks
通讯作者：
Stephen Weeks
优化模式匹配
影响因子：
4.6
作者：
F. L. Fessant;Luc Maranget
通讯作者：
Luc Maranget