一句话：提出精确刻画结构化程序控制流图的文法分解，使 Chaitin 寄存器分配的参数化算法渐进加速并可扩展到 20 个寄存器。
结构化程序的控制流图（CFG）具有稀疏性，此前常用 treewidth、pathwidth 等图参数形式化，并据此设计参数化算法加速编译器优化、模型检测与程序分析。本文指出这些参数无法精确刻画 CFG 的稀疏性：所有结构化 CFG 的 treewidth 至多为 7，但 treewidth ≤ 7 的图未必能作为程序的 CFG 实现，因此既有参数化算法实际求解的是更一般的图问题。作者基于一种文法提出新的图分解概念，其生成的语言恰好对应可作为 CFG 实现的图，并证明该分解同样支持 treewidth/pathwidth 方法中常用的动态规划。作为应用，作者为 Chaitin 经典寄存器分配的两个变体（不允许活跃区间分裂）给出渐近更快的算法：固定寄存器数下的最小代价分配由 O(|G|·||^16·r) 降至 O(|G|·||^5·r)，无溢出分配的判定问题由 O(|G|·r^16·r) 降至 O(|G|·r^5·r+5)。实验表明该方法可处理多至 20 个寄存器的真实实例，而此前工作仅能扩展到 8，因而在 x86 等 16 寄存器架构上首次给出可扩展的精确算法。
It is well-known that control-flow graphs (CFGs) of structured programs are sparse. This sparsity has been previously formalized in terms of graph parameters such as treewidth and pathwidth and used to design faster parameterized algorithms for numerous compiler optimization, model checking and program analysis tasks. In this work, we observe that the known graph sparsity parameters fail to exactly capture the kind of sparsity exhibited by CFGs. For example, while all structured CFGs have a treewidth of at most 7, not every graph with a treewidth of 7 or less is realizable as a CFG. As a result, current parameterized algorithms are solving the underlying graph problems over a more general family of graphs than the CFGs. To address this problem, we design a new but natural concept of graph decomposition based on a grammar that precisely captures the set of graphs that can be realized as CFGs of programs. We show that our notion of decomposition enables the same type of dynamic programming algorithms that are often used in treewidth/pathwidth-based methods. As two concrete applications, using our grammatical decomposition of CFGs, we provide asymptotically more efficient algorithms for two variants of the classical problem of register allocation as defined by Chaitin, i.e. assigning program variables to a limited number of registers such that variables with intersecting lifetimes are not assigned to the same register. Note that Chaitin's formulation of register allocation does not allow live-range splitting. Our algorithms are asymptotically faster not only in comparison with the non-parameterized solutions for these problems, but also compared to the state-of-the-art treewidth/pathwidth-based approaches in the literature. For minimum-cost register allocation over a fixed number of registers, we provide an algorithm with a runtime of O(|G| ⋅ || 5 ⋅ r) where |G| is the size of the program, is the set of program variables and r is the number of registers. In contrast, the previous treewidth-based algorithm had a runtime of O(|G| ⋅ || 16 ⋅ r). For the decision problem of spill-free register allocation, our algorithm's runtime is O(|G| ⋅ r5 ⋅ r + 5) whereas the previous works had a runtime of O(|G| ⋅ r16 ⋅ r). Finally, we provide extensive experimental results on spill-free register allocation, showcasing the scalability of our approach in comparison to previous state-of-the-art methods. Most notably, our approach can handle real-world instances with up to 20 registers, whereas previous works could only scale to 8. This is a significant improvement since most ubiquitous architectures, such as the x86 family, have 16 registers. For such architectures, our approach is the first-ever exact algorithm that scales up to solve the real-world instances of spill-free register allocation.
@inproceedings{CaiGHL25,
title = {Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs},
author = {Xuran Cai and Amir Kafshdar Goharshady and S. Hitarth and Chun Kit Lam},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3669940.3707286}
}