Value numbering

Value numbering is a technique of determining when two computations in a program are equivalent and eliminating one of them with a semantics-preserving optimization.

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 [math]\displaystyle{ \left\{ {w} \mapsto 1, {x} \mapsto 1, {y} \mapsto 2, {z} \mapsto 2 \right\} }[/math] 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.

In IRs and source languages where rebinding (assigning to the same variable more than once) is possible, SSA form is required to perform GVN so that false [math]\displaystyle{ \left\{ \text{variable name} \mapsto \text{value number} \right\} }[/math] mappings are not created.

Local value numbering

Local value numbering (LVN) is a compiler optimization that aims to find multiple instances of equivalent expressions (i.e. expressions which yield the same result) and replace them with the first occurrence. LVN is a local optimization, meaning that unlike global value numbering, it operates on a single basic block at a time.

Local value numbering works by assigning a unique number to each operation and remembering these associations. Subsequent instructions are then looked up and, in case an identical instruction has already been registered, replaced with the previous instruction's result. For example:

a ← 4         a is tagged as #1
b ← 5         b is tagged as #2
c ← a + b     c (#1 + #2) is tagged as #3
d ← 5         d is tagged as #2, the same as b
e ← a + d     e, being '#1 + #2' is tagged as #3

By assigning numbers to instructions, comparing for duplicates is turned into simple integer comparisons. In this particular example, c and e are assigned the same number (#3), thus signalling to the compiler that any references to e may simply be replaced with ones to c.

Difficulties and extensions

Issues when not using SSA

A naive implementation might attempt to perform the optimization by directly using the variable names instead of numbers. However, this approach does not work when the values of variables can change. Consider the pseudocode:

a ← 1         a is tagged as #1
b ← 2         b is tagged as #2
c ← a + b     c is tagged as #3
b ← 3
d ← a + b     d is incorrectly tagged as #3

In this scenario, d is incorrectly assigned the number 3 because the arguments match those of c. This is incorrect, however, because b has changed value from 2 to 3, making the actual results differ. Using the SSA representation resolves this disparity.

Using mathematical identities

A simple implementation might also be unable to catch all equivalent expressions, even when they only differ by the order of their operands. In the following example, a and b could be assigned the same number:

a ← 1 + 2
b ← 2 + 1

This issue can easily be resolved either by assigning the same number to both cases (i.e. a + b and b + a are both recorded with the same number) or by sorting the operands before checking for equivalents.

Local value numbering optimizers may also be aware of mathematical identities. Assuming a is an integer, all of the following expressions can be assigned the same value:

b ← a + 0
c ← a * 1
d ← min(a, MAX_INT)
e ← max(a, a)
f ← a & 0xFF..FF       (assuming '&' denotes bitwise AND)

See also

• Partial redundancy elimination
• Optimizing compiler
• Common subexpression elimination

Further reading

• "A unified approach to global program optimization". Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73. Popl '73. 1973. pp. 194–206. doi:10.1145/512927.512945. ISBN 9781450373494. http://portal.acm.org/citation.cfm?id=512945&coll=portal&dl=ACM. Retrieved 2006-11-20.  [1]
• 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)
• Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. 1997. ISBN 978-1-55860-320-2. https://archive.org/details/advancedcompiler00much. 
• "Value Numbering". Software-Practice and Experience 27 (6): 701–724. 1997.