知识卡片
图着色分配
寄存器分配可转化为图着色:同时活跃的变量互相冲突,不能使用同一寄存器;颜色就是寄存器。图着色只给近似解,颜色不够时变量仍要落回内存。这个模型把资源竞争从指令细节抽成图问题。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《自己动手构造编译系统:编译、汇编与链接》第4章《编译优化》(源文件:_epub-src/OEBPS/text00072.html)
- 结论依据:原文用活跃变量构造冲突图,并说明图着色节点颜色对应寄存器,图着色问题是 NP 问题,只能采用近似方案。
- 原始内容:如果将颜色看作寄存器,由于冲突图的节点表示代码中的变量,因此对冲突图的图着色实际是完成了变量的寄存器分配。由于图着色问题是NP问题……存在多项式时间的近似最佳图着色方案。