10.2 Value Numbering Scheme

One particular scheme we present here is called value numbering scheme, which helps in redundant expression elimination and constant folding. As an additional bonus it provides information necessary for global optimization.

Consider a C source code:

a = 4;
k = i * j + 5;
l = 5 * a * k;
m = i;
b = m * j + i * a;

This may give the following 4-tuple sequence:

1:  LD 4 T1 −−
2:  = T1 a −−
3:  MUL i j T2
4:  ADD T2 5 T3
5:  = T3 k −−
6:  MUL 5 a T4
7:  MUL k T4 T5
8:  = T5 1 −−
9:  LD i T6 −−
10: = T6 m −−
11: MUL m j T7
12: MUL i a T8
13: ADD T7 T8 T9
14: = T9 b −−

The main data structure used in the value numbering method is a hash-coded table of available expressions. As each 4-tuple is encountered from the start of a Basic Block, this table is searched for a previous instance of the same expression. If found, all the subsequent instances can be replaced by a reference to the first one.

In order for this scheme to work, we have to determine when two operands are holding identical values. This is provided by a system of value numbers, where each unique value generated or used within the block is assigned an identifying number. Two entities have the same value number if and only if, based upon the information from the block alone, their values are provably identical. For example, after the second 4-tuple is scanned, the value numbers of constant 4, T1 and variable a are the same.

The current value number of variable or a constant is kept in the Symbol Table. The value number of result of a 4-tuple is kept in the table of available expressions and as an auxiliary field in the 4-tuple itself. The hash function for entry to the table of available expressions is based on value numbers of the operands and a code for the operator.

Constant folding is handled via a flag in the Symbol Table entry, indicating whether that entry refers to a constant and a flag in the 4-tuple to indicate if the result is a constant. We also need a table of constants, indexed by the value number and holding actual constant values.

Algorithm 10.2.1 gives an algorithm to handle value numbering scheme. Inputs to the algorithm are a Basic Block of 4-tuples and a Symbol Table. Output from the algorithm is an improved Basic Block. It uses two tables – a table of available expressions availtab and a table of constant values consttab.

The following actions take place when this algorithm is applied to the example 4-tuple IR given above: 1: to 5: Value numbers are assigned to variables a, i, j, k and to constants 4 and 5. The results of 3: and 4:, i.e. T2 and T3 are recorded as available. In the Symbol Table, the assigned value numbers are as follows:

The auxiliary field of 4-tuples have:

The availtab looks like:

And the consttab contains (valno, value) = (1, 4) and (5, 5).

6: The algorithm looks up constant 5 and a, finds that both of them are constants. The result 20 is computed and a new (valno, value) pair (7, 20) is inserted in consttab. The 4-tuple 6 is deleted.

7: Modified to use constant 20 in place of T4.

8: to 10: The information collected is:

In the Symbol Table:

The auxiliary field of 4-tuples have:

The availtab looks like:

The consttab contains (valno, value) = (1, 4), (5, 5) and (7, 20).

11: The algorithm finds that value numbers for variables m and j are 2 and 3, respectively, and there is an available computation of these values as 4-tuple number 3. Thus, 4-tuple 11 is deleted and subsequent references to its result T7 are replaced by T2.

Optimized final code is shown below:

1:  LD 4 T1 −−
2:  = Tl a −−
3:  MUL i j T2
4:  ADD T2 5 T3
5:  = T3 k −−
7:  MUL 20 k T5
8:  = T5 1 −−
9:  = i T6 −−
10: = T6 m −−
12: MUL i a T8
13: DD T2 T8 T9
14: = T9 b −−

It is interesting to note that 4-tuple 11 is found out to be same as 4-tuple 3, even though the variable names were different.

The above method can be further developed to be able to handle array references and data structures.

Further, such methods, which do local analysis limited to a Basic Block, can be modified to provide useful information for global analysis.