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 number of expressions of programs in SSA form based on Herbrand semantics. With this definition, determining whether two expressions are Herbrand equivalent are equivalent to determining whether their value numbers are same. Then, we give a new complete GVN algorithm that can compute such kind of value numbers. We also implement the new algorithm in GCC and extend it to be able to handle memory operations. Based on the new GVN algorithm, the partial redundancy elimination (PRE) optimization eliminates more redundant computations.EI02416-4213