Global value numbering

Global value numbering (GVN) is a compiler optimization based on the static single assignment form (SSA) intermediate representation. It sometimes helps eliminate redundant code that common subexpression elimination (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. The same value number is assigned to those variables and expressions which are provably equivalent. 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

Without copy propagation, 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.

References

G.A. Kildall, "A Unified Approach to Global Program Optimization." Proceedings of the First ACM Symposium on Principles of Programming Languages,194-206, 1973.
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.
P. Briggs, K.D. Cooper, L.T. Simpson,"Value Numbering." Software-Practice and Experience, 27:6, pages :701-724, 1997.

Compiler optimizations

Basic block	Peephole optimization

Loop optimization	Induction variable Strength reduction Loop fusion Loop inversion Loop interchange Loop-invariant code motion Loop nest optimization Loop unrolling Loop splitting Loop unswitching Software pipelining Automatic parallelization

Data-flow analysis	Common subexpression elimination Constant folding Induction variable recognition and elimination Dead store elimination Use-define chain Live variable analysis Available expression

SSA-based	Global value numbering Sparse conditional constant propagation

Code generation	Register allocation Instruction selection Instruction scheduling Rematerialization

Functional	Tail call elimination Deforestation

Global	Interprocedural optimization

Other	Bounds-checking elimination Dead code elimination Inline expansion Jump threading

Static analysis	Alias analysis Pointer analysis Shape analysis Escape analysis Array access analysis Dependence analysis Control flow analysis Data flow analysis

This article is issued from Wikipedia - version of the 7/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.