知识卡片

专业/工作 · 1270.e

图着色分配

理解等级:未标注

寄存器分配可转化为图着色:同时活跃的变量互相冲突,不能使用同一寄存器;颜色就是寄存器。图着色只给近似解,颜色不够时变量仍要落回内存。这个模型把资源竞争从指令细节抽成图问题。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《自己动手构造编译系统:编译、汇编与链接》第4章《编译优化》(源文件:_epub-src/OEBPS/text00072.html) - 结论依据:原文用活跃变量构造冲突图,并说明图着色节点颜色对应寄存器,图着色问题是 NP 问题,只能采用近似方案。 - 原始内容:如果将颜色看作寄存器,由于冲突图的节点表示代码中的变量,因此对冲突图的图着色实际是完成了变量的寄存器分配。由于图着色问题是NP问题……存在多项式时间的近似最佳图着色方案。