一种高效的完全值编号算法

值编号是一种重要的静态分析技术，广泛应用于优化编译器和程序验证工具。实际应用中的各种值编号算法在检测等值关系上都存在各种局限性。功能更加强大的能够检测全部 Herbrand 等值关系的完全值编号算法工作效率都十分低下而无法实用。我们发现采用静态单赋值形式能够大幅提高完全值编号算法的性能。本文基于 Herbrand 等值关系给出了静态单赋值形式的程序中值编号的一般定义，建立了值编号和 Herbrand 等值关系的对应关系。基于该定义，判断两个表达式之间的 Herbrand 等值关系等价于判断该两个表达式的值编号是否相同。之后给出了用于计算这种值编号的新的完全值编号算法。我们在 GCC 中实现了该算法并利用别名信息使其能够检测访存语句间的等值关系。基于新算法的部分冗余优化比 GCC 中原有算法消除了更多的动态冗余计算。

An Efficient Complete Global Value Numbering Algorithm

Global value numbering(GVN) is an important static analysis technique both for optimizing compilers and for program verification tools.Practically used GVN algorithms all have some restrictions on detecting equivalences.The traditional more powerful complete GVN algorithms that can discover all Herbrand equivalences are all inefficient and cannot be used in practice.We find that the static single assignment(SSA) form can be adopted to improve the efficiency greately.In this paper,we define a kind of value n...