GVN-PRE stands for "Global Value Numbering and Partial Redundancy Elimination". It is a new partial redundancy elimination algorithm proposed by Thomas VanDrunen in his PhD. dissertation, and in his paper appearing at CC'04.

GVN-PRE is a value based Partial Redundancy Elimination algorithm that elegantly exploits the properties of SSA form to extend dominator based global value numbering to eliminate partially redundant *values*: The algorithm does not look for partially redundant expressions, but instead for partially redundant values. Classic PRE and SSAPRE can only find *lexically* equivalent partially redundant expressions. GVN-PRE uses value numbering to recognize *semantically* equivalent expressions, unifying two of the most powerful redundancy elimination algorithms.

The algorithm as described in the thesis is very powerful, yet relatively easy to understand. The algorithm does not require any special kind of SSA form (unlike SSAPRE which requires building the unintuitive ESSA form) and builds on classic concepts like availability, anticipatability and value numbering. Actually implementing GVN-PRE requires careful design of the data structures used to represent the various sets of values.

The GCC GVN-PRE implementation, which is quite fast, replaces the old Kennedy and Chow style SSAPRE implementation. The source code can be found in [gccsource:tree-ssa-pre.c].

None: GVN-PRE (last edited 2008-01-10 19:39:02 by localhost)