Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect Dependencies
Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect Dependencies
复制标题
非纯高阶语言的图 IR：通过精确的效果依赖性使积极的优化变得经济实惠
DOI：
10.1145/3622813
复制
发表时间：
2023
影响因子：
--
通讯作者：
Rompf, Tiark
中科院分区：
文献类型：
--
作者：
Bračevac, Oliver;Wei, Guannan;Jia, Songlin;Abeysinghe, Supun;Jiang, Yuxuan;Bao, Yuyan;Rompf, Tiark
基于图的中间表示（IR）被广泛用于强大的编译器优化，无论是在纯函数式语言中的过程间，还是在命令式语言中的过程内。然而，到目前为止，没有合适的图IR存在积极的全局优化的语言与效果和高阶函数：别名和间接控制转移，使其难以保持足够的粒度依赖信息的优化是有效的。为了弥补这一长期存在的差距，我们提出了一种新的类型化图IR，将可达性类型的概念与表达效果系统相结合，以合理的成本计算精确和粒度效果依赖关系，同时支持本地推理和单独编译。我们的高级图IR施加词法结构来表示结构化的控制流和嵌套，使侵略性和廉价的代码运动和其他优化不纯的高阶程序。我们正式的新的图IR的基础上的λ-演算与可达性类型和效果系统沿着与各种优化的规范。我们目前的性能案例研究张量循环融合，CUDA内核融合，LLVM IR的符号执行，SQL查询编译在Scala LMS编译器框架中使用新的图IR。我们观察到显着的加速高达21倍。
Graph-based intermediate representations (IRs) are widely used for powerful compiler optimizations, either interprocedurally in pure functional languages, or intraprocedurally in imperative languages. Yet so far, no suitable graph IR exists for aggressive global optimizations in languages with both effects and higher-order functions: aliasing and indirect control transfers make it difficult to maintain sufficiently granular dependency information for optimizations to be effective. To close this long-standing gap, we propose a novel typed graph IR combining a notion of reachability types with an expressive effect system to compute precise and granular effect dependencies at an affordable cost while supporting local reasoning and separate compilation. Our high-level graph IR imposes lexical structure to represent structured control flow and nesting, enabling aggressive and yet inexpensive code motion and other optimizations for impure higher-order programs. We formalize the new graph IR based on a λ-calculus with a reachability type-and-effect system along with a specification of various optimizations. We present performance case studies for tensor loop fusion, CUDA kernel fusion, symbolic execution of LLVM IR, and SQL query compilation in the Scala LMS compiler framework using the new graph IR. We observe significant speedups of up to 21x.
登录
查看更多内容
延续传递风格的通用说明
DOI：
--
发表时间：
1994
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
J. Hatcliff;O. Danvy
通讯作者：
O. Danvy
多态可达性类型：跟踪高阶通用程序中的新鲜度、别名和分离
DOI：
--
发表时间：
2023
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
Guannan Wei;Oliver Bračevac;Songlin Jia;Yuyan Bao;Tiark Rompf
通讯作者：
Tiark Rompf
代数子类型的简单本质：使子类型变得简单的主类型推理（功能性珍珠）
DOI：
--
发表时间：
2020
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
L. Parreaux
通讯作者：
L. Parreaux
二次时间内的 Lambda 提升
DOI：
--
发表时间：
2002
期刊：
Journal of Functional and Logic Programming
影响因子：
--
作者：
O. Danvy;U. Schultz
通讯作者：
U. Schultz
高阶控制流分析回顾：吸取的教训，放弃的教训
DOI：
--
发表时间：
2004
期刊：
SIGP
影响因子：
--
作者：
O. Shivers
通讯作者：
O. Shivers