Global value numbering

From Wikipedia, the free encyclopedia

Global value numbering (GVN) is a compiler optimization based on the SSA intermediate representation. It sometimes helps eliminate redundant code that common subexpression evaluation (CSE) does not. At the same time, however, CSE may eliminate code that GVN does not, so both are often found in modern compilers. Global value numbering is distinct from local value numbering in that the value-number mappings hold across basic block boundaries as well, and different algorithms are used to compute the mappings.

Global value numbering works by assigning a value number to variables and expressions. To those variables and expressions which are provably equivalent, the same value number is assigned. For instance, in the following code:

w := 3
x := 3
y := x + 4
z := w + 4

a good GVN routine would assign the same value number to w and x, and the same value number to y and z. For instance, the map [{w} \mapsto 1, {x} \mapsto 1, {y} \mapsto 2, {z} \mapsto 2] would constitute an optimal value-number mapping for this block. Using this information, the previous code fragment may be safely transformed into:

w := 3
x := w
y := w + 4
z := y

Depending on the code following this fragment, copy propagation may be able to remove the assignments to x and to z

The reason that GVN is sometimes more powerful than CSE comes from the fact that CSE matches lexically identical expressions whereas the GVN tries to determine an underlying equivalence. For instance, in the code:

a := c × d
e := c
f := e × d

CSE would not eliminate the recomputation assigned to f, but even a poor GVN algorithm should discover and eliminate this redundancy.

SSA form is required to perform GVN so that false variable name-value name mappings are not created.

[edit] References

  • Alpern, Bowen, Wegman, Mark N., and Zadeck, F. Kenneth. "Detecting Equality of Variables in Programs."

Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages (POPL), ACM Press, San Diego, CA, USA, January 1988, pages 1-11.

  • L. Taylor Simpson, "Value-Driven Redundancy Elimination." Technical Report 96-308, Computer Science

Department, Rice University, 1996. (Author's Ph.D. thesis)

  • Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.