Global value numbering
Encyclopedia
Global value numbering is a compiler optimization
based on the 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. 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
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
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
SSA form is required to perform GVN so that false variable name-value name mappings are not created.
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
based on the SSA intermediate representation. It sometimes helps eliminate redundant code that common subexpression elimination
Common subexpression elimination
In computer science, common subexpression elimination is a compiler optimization that searches for instances of identical expressions , and analyses whether it is worthwhile replacing them with a single variable holding the computed value.- Example :In the following code: a = b * c + g; d = b * c...
(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 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
Copy propagation
In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.From the following code:...
may be able to remove the assignments to
x and to zThe 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.