Compilers: Principles and Practice

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 ...