The Design and Implementation of a SSA-based Register Allocator
The Design and Implementation of a SSA-based Register Allocator
复制标题
基于SSA的寄存器分配器的设计与实现
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Fernando Magno Quintão Pereira
中科院分区：
文献类型：
--
作者：
Fernando Magno Quintão Pereira
最先进的寄存器分配器是编译器中最复杂的部分之一，部分原因是寄存器分配通常是NP完全的。令人惊讶的是，Bouchez，Brisk等人，Hack在2005年独立发现，如果程序是单静态分配（SSA）形式，那么核心寄存器分配问题可以在多项式时间内解决。这个结果支持我们所说的基于SSA的寄存器分配。在这份报告中，我们提出了第一个设计和实现的基于SSA的寄存器分配器，集成到LLVM。与现有技术相比，我们的寄存器分配器要简单得多，并生成同等质量的代码。我们展示了新的静态分析，我们使用的philifting，溢出，并合并，我们解释说，这些分析的选择影响我们如何必须做SSA解构。
A state-of-the-art register allocator is among the most complicated parts of a compiler, partly because register allocation is NPcomplete in general. Surprisingly, Bouchez, Brisk et al., and Hack independently discovered in 2005 that if a program is in single static assignment (SSA) form, then a core register allocation problem can be solved in polynomial time. This result enables what we call SSA-based register allocation. In this report we present the first design and implementation of an SSA-based register allocator, integrated into LLVM. Compared to state of the art, our register allocator is much simpler and generates code of equivalent quality. We show the new static analyses we use for philifting, spilling, and coalescing, and we explain that the choice of those analyses influence how we must do SSA deconstruction.