Local Value Numbering

Local value numbering is a way to perform compiler optimization locally in a control block. There is a global counterpart of local value numbering called global value numbering.

Motivation

Let’s consider some challenges in local optimization. What do these different forms have in common?

Value Numbering

Value numbering stores pairs of value and canonical variable name into a table. When building up values, we can refers to previous values by number in expression.

Example

numbervalue(expression)Canonical Variable Name
1x
2(+, #1, #1)a
3(*, #2, #1)d
4(+, #3, #2)c

We also need to interpret the basic block. Though unlike an actual interpreter, instead of calculating the actual values, we calculate values as the numbers shown above. (since we don’t know the actual inputs)

Extending LVN

While the basic version is already useful for common subexpression elimination, value numbering is a framework that we can extend with fancier optimizations.

Copy Propagation

For example, the basic implementation of LVN can’t optimize out our copy propagation example. To make this example work, our LVN algorithm need to understand the semantics of the instructions. In this case, we can say that whenever we encounter the id instruction, we assign the value to the underlying value.

Commutativity

Another example is that we can also exploit commutativity of integer arithmetic. This optimization enhance common subexpression elimination.

We can achieve that by canonicalizing values in instruction.

Constant Propagation

Constant propagation is just like copy propagation but we replace id with a const instruction.

Constant Folding

It is possible to achieve constant folding with LVN by combining all the above extensions

Pseudocode for Basic LVN

Note: We need to define equality comparison for the structure that represent a value

table = {} # mapping from value tuples to canonical variables,
  # with each row numbered
var2num = {} # mapping from variable names to their current
  # value numbers (i.e., rows in table)
 
for instr in block:
    value = (instr.op, var2num[instr.args[0]], ...)
 
    if value in table:
        # The value has been computed before; reuse it.
        num, var = table[value]
        replace instr with copy of var # a.k.a. dest = id var
 
    else:
        # A newly computed value.
        num = fresh value number
 
        # TODO: Can SSA make this redundent?
        # To handle mutation in cases like this
        # x = a + b
        # ...
        # x = c
        # ...
        # y = x
        # where we can rename the old variable to a different name
        # x' = a + b
        # ...
        # x = c
        # ...
        # y = x'
        if instr will be overwritten later:
             dest = fresh variable name
             instr.dest = dest
        else:
             dest = instr.dest
 
        # Add new entry to the table
        table[value] = num, dest
 
        # Use (canonical) variables in the table rather than old args
        for a in instr.args:
            replace a with table[var2num[a]].var
 
    # Always need to update the value of destination variable
    # The value is represented by number in the table
    var2num[instr.dest] = num

See Also