一句话：提出结合可达性类型与效应系统的类型化图IR，为含副作用与高阶函数的语言提供精确依赖与廉价激进优化。
图中间表示广泛用于编译器优化，但此前只在纯函数语言中支持过程间优化，或在命令式语言中支持过程内优化。对于同时具有副作用与高阶函数的语言，别名与间接控制转移使依赖信息难以保持足够精细，从而阻碍激进的全局优化。本文提出一种新型类型化图IR，将可达性类型与表达力强的效应系统结合，以可负担的代价计算精确且细粒度的效应依赖，同时支持局部推理与分离编译。该图IR通过词法结构表示结构化控制流与嵌套，使针对非纯高阶程序的代码移动等优化既激进又廉价。作者基于带可达性类型-效应系统的λ演算形式化了该图IR，并给出多种优化的规约。在Scala LMS编译框架中，通过张量循环融合、CUDA核融合、LLVM IR符号执行与SQL查询编译等案例评估，最高获得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 21 x .
@article{paperbot1870,
title = {Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect Dependencies},
author = {Oliver Bračevac and Guannan Wei and Songlin Jia and Supun Abeysinghe and Yuxuan Jiang and Yuyan Bao and Tiark Rompf},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622813}
}