一句话：提出以自由变量为基础、用 φ 函数和函数参数直接表达数据依赖的 SSA 新基础，摆脱支配关系并支持高阶程序。
支配关系是 SSA 编译器的核心概念，支撑众多分析与变换，并要求每个使用被其定义支配。但论文指出该依赖存在精度与适用性问题：控制流过近似数据流，使基于支配的分析不精确；支配仅对一阶控制流图良定义，而高阶程序无显式 CFG，该定义失去意义。作者因此提出以自由变量为基础，让 φ 函数与函数参数直接表达数据依赖，从而重建传统分析、提高精度并自然支持高阶程序。论文还给出在可变 IR 中高效维护自由变量集的技术，并引入 nesting tree——按变量依赖而非控制流构造的支配树松弛对应物。基准显示算法与数据结构随程序规模对数线性扩展。
Dominance is a fundamental concept in compilers based on static single assignment (SSA) form. It underpins a wide range of analyses and transformations and defines a core property of SSA: every use must be dominated by its definition. We argue that this reliance on dominance has become increasingly problematic—both in terms of precision and applicability to modern higher-order languages. First, control flow overapproximates data flow, which makes dominance-based analyses inherently imprecise. Second, dominance is well-defined only for first-order control-flow graphs (CFGs). More critically, higher-order programs violate the assumptions underlying SSA and classic CFGs: without an explicit CFG, the very notion that all uses of a variable must be dominated by its definition loses meaning. We propose an alternative foundation based on free variables. In this view, 𝜙-functions and function parameters directly express data dependencies, enabling analyses traditionally built on dominance while improving precision and naturally extending to higher-order programs. We further present an efficient technique for maintaining free-variable sets in a mutable intermediate representation (IR). For analyses requiring additional structure, we introduce the nesting tree—a relaxed analogue of the dominator tree constructed from variable dependencies rather than control flow. Our benchmarks demonstrate that the algorithms and data structures presented in this paper scale log-linearly with program size in practice.
@article{paperbot3776,
title = {SSA without Dominance for Higher-Order Programs},
author = {Roland Leißa and Johannes Max Griebler},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808286}
}