search

tannal / ohmywork

0 stars 0 forks source link

Register allocation via hierarchical graph coloring #46

Open tannal opened 7 months ago

tannal commented 7 months ago

https://dl.acm.org/doi/pdf/10.1145/113445.113462

llvm/bolt/include/bolt/Passes/ReorderAlgorithm.h

tannal commented 3 months ago

构建冲突图: 根据程序的变量使用情况构建冲突图,其中节点表示变量,边表示变量之间的冲突(同时活跃)。 层次化分解: 将冲突图分解成多个层次,每个层次包含一组相互独立的子图。 自底向上着色: 从最底层开始,对每个子图进行独立着色。对于无法着色的节点,将其移至上一层。 合并与简化: 在着色过程中,尝试合并相容的节点,并移除低度数节点以简化图结构。 spillage处理: 对于最终无法着色的节点,执行spillage操作,将变量存储到内存中。

tannal commented 3 months ago

层次化方法可以有效处理大规模和复杂的程序,提高算法的可扩展性。 结合多种优化技术(如合并、简化、启发式选择)可以提升寄存器分配的质量。 自底向上的处理方式有助于在局部范围内做出更好的决策,同时考虑全局影响。 寄存器分配问题本质上是NP完全的,因此启发式算法在实践中非常重要。 良好的spillage策略对于平衡性能和代码大小至关重要。 该算法为后续的寄存器分配研究奠定了基础,启发了许多改进和变体。