纯数据流场景下局部寄存器分配最优算法及相关论文问询

• 针对无Phi节点、无CFG边的纯数据流局部分配场景，以下是几个更贴合需求的算法和研究方向：
  • Chaitin-Briggs算法的局部变种：Chaitin-Briggs原本用于全局寄存器分配，但在无控制流的纯数据流图（DFG）中，可简化冲突图构建与着色逻辑——无需处理跨基本块的活跃范围。该算法通过构建指令间的寄存器冲突图，采用图着色实现最优分配，当冲突图为完美图时，能保证最小寄存器使用量。核心参考论文：Register Allocation via Coloring（Chaitin et al., 1981）。
  • 优化版线性扫描算法（适配DFG）：标准线性扫描针对线性指令序列，针对纯数据流DAG结构，可基于拓扑序扫描，结合活跃范围的嵌套特性调整分配策略，避免不必要的寄存器溢出。相关改进可参考Linear Scan Register Allocation for the Java HotSpot Client Compiler（Poletto & Sarkar, 1999）中针对DAG的适配部分。
  • 树状DFG的最优着色算法：若你的数据流图是树状结构，可采用Optimal Register Allocation for Expression Trees（Baker, 1977）中的方法，该算法针对表达式树能给出线性时间复杂度的最优寄存器使用方案，比Sethi-Ullman算法更适配无控制流的纯树状数据流场景。
  • MCFN算法的场景化优化：你当前使用的MCFN方案，可优化节点遍历逻辑——替换Strahler编号+子节点数的平局打破规则，改为动态优先处理能最大程度减少当前活跃寄存器数量的节点，进一步提升分配效率。核心基础论文：Register Allocation as a Minimum Cost Flow Problem（Goodwin & Wilken, 1996），后续有专门针对无控制流DFG的简化扩展研究。

内容的提问来源于stack exchange，提问作者Noah