Combining Analyses
When we do an analysis of a program, we gain certain information.
We can then use that information in later analyses.
For example, we've seen how constant propagation can be used to eliminate
edges that will never be traversed and thus allow computations to be moved
out of loops.
Sometimes, however, two analyses depend on each other in such a way that
they cannot effectively be carried out separately.
In that case, they should be combined
(Combining Analyses, Combining Optimizations,
ACM Transactions on Programming Languages and Systems 17 (March, 1995) 181196).
Example
Consider the following trivial C procedure:
int
p(void)
{ int x = 1;
do { if (x != 1) x = 2; } while (pred());
return x;
}
Here pred is some arbitrary predicate about which we know nothing.
[Discuss
 Regardless of the implementation of pred, p will
return 1 if it terminates
]
SSA representation

1:
p_{11}: x:=1
p_{12}: Jump(2)

2:
p_{21}: x_{1}:=phi(x,x_{3})
p_{22}: V_{21}:=x_{1}
p_{23}: V_{22}:=V_{21}!=1
p_{24}: JumpT(3,V_{22})
p_{25}: JumpF(4,V_{22})

3:
p_{31}: x_{2}:=2
p_{32}: Jump(4)

4:
p_{41}: x_{3}:=phi(x_{1},x_{2})
p_{42}: V_{41}:=pred
p_{43}: V_{42}:=V_{41}!=0
p_{44}: JumpT(2,V_{42})
p_{45}: JumpF(5,V_{42})

5:
p_{51}: V_{51}:=x_{3}
p_{52}: Return(V_{51})

[Discuss
 Control flow graph on the left, dominator tree on the right, dominance
frontiers in square brackets
 No global value numbering has been done
]
Propagate constants
Assume that the work list is operated like a stack.
We first run through all of the computations in order, as though they had
been on the work list.
As we do this, we place only lowernumbered program points on the
work list (because highernumbered ones will be reached in due course).
After the first complete scan, we take program points off of the work
list.
Step  Program point  Result  To work list


1  p_{11}  x = 1  

2  p_{21}  x_{1} = 1  

3  p_{22}  V_{21} = 1  

4  p_{23}  V_{22} = 0  

5  p_{31}  x_{2} = 2  

6  p_{41}  x_{3} = Variable  p_{21}

7  p_{42}  V_{41} = Variable  

8  p_{43}  V_{42} = Variable  

9  p_{51}  V_{51} = Variable  

10  p_{21}  x_{1} = Variable  p_{22},
p_{41}

11  p_{41}  x_{3} = Variable  

12  p_{22}  V_{21} = Variable  p_{23}

13  p_{23}  V_{22} = Variable  

[Discuss
 Because both V_{22} and V_{42} are variable, the
executability calculation will show that everything is executable
 Since the executability calculation depends on the results of constant
propagation, we can't do it first
]
Combine analyses
Suppose that we make the constant propagation calculation dependent on the
executability calculation as well as viceversa:
f_{e+}(e,v_{1},v_{2}) =
e == Nonexecutable ? Undetermined : f_{+}(v_{1},v_{2})
[Discuss
 The executability and constant propagation must now be executed at the
same time
 Information flow occurs in both directions
]
Combined calculation
Assume that the work list is operated like a stack.
We first run through all of the computations in order, as though they had
been on the work list.
As we do this, we place only lowernumbered program points on the
work list (because highernumbered ones will be reached in due course).
After the first complete scan, we take program points off of the work
list.
Step  Program point  Result  To work list


1  p_{11}
 x = 1  

Executable  

2  p_{21}
 x_{1} = 1  

Executable  

3  p_{22}
 V_{21} = 1  

Executable  

4  p_{23}
 V_{22} = 0  

Executable  

5  p_{24}  Nonexecutable  

6  p_{25}  Executable  

7  p_{31}
 x_{2} = Undetermined  

Nonexecutable  

8  p_{32}  Nonexecutable  

9  p_{41}
 x_{3} = 1  p_{21}

Executable  

10  p_{42}
 V_{41} = Variable  

Executable  

11  p_{43}
 V_{42} = Variable  

Executable  

12  p_{44}  Executable  

13  p_{45}  Executable  

14  p_{51}
 V_{51} = 1  

Executable  

15  p_{52}  Executable  

16  p_{21}
 x_{1} = 1  

Executable  

[Discuss
 Computation at a program point is a multiple assignment
 By combining analyses, we discover that x does not change
 If the analyses are done separately, in either order, this fact will
not be discovered
 If two analyses do not use each others' results, combining doesn't help
]
Global value numbering
Global value numbering clearly uses information from constant propagation
and executability analysis; constant propagation can also use information
from global value numbering:
 Subtraction of congruent values yields 0
 Comparison of congruent values for equality yields true
 Undetermined value is congruent to everything
Here's an example in which global value numbering must be combined with
constant propagation and executability determination to get the right
answers:
main()
{ int x = 1;
int z = read(); /* z is not constant */
int y = z; /* y equal to z but not constant */
while (pred()) {
if (y != z) x = 2; /* y equal to z, so x unchanged */
x = 2  x; /* x is still 1 after this */
if (x != 1) y = 2; /* x == 1, so y unchanged */
}
printf("x is %d\n", x);
}
[Discuss
 Walk through the program, explaining its behavior
 Note why constant propagation and executability determination do not
suffice
]
Value numbering as a data flow analysis problem
Global value numbering establishes a value at each program point, in the
same manner as constant propagation.
But we've taken the position that we allow either a constant
or a value number as an operand of an expression and hence as a
value at each program point.
In some sense, constants are nothing but distinguished value numbers.
This implies that a single semilattice should describe both constants and
value numbers.
The meet operation and the functions in a single F set should also
yield both constants and value numbers, depending on their arguments.
[Discuss
 Value numbers are the results of computations
 An inference about the result of a computation can yield either a
constant or a value number
 Thus value numbering needs to use the same lattice as constant
propagation if the two analyses are to be combined
]
Lattice for global value numbering
 L = ({(f,v)  f in {K,V}, v in Z} union {Undetermined, Variable},
Undetermined, Variable, meet), where Z is the set of integers.
f is a flag that distinguishes between constants (K) and
value numbers (V).
 The meet operation is applied over the arguments of a phi
function, and is defined by the following table:
meet  Undetermined  a_{0}  Variable


Undetermined
 Undetermined
 a_{0}
 Variable


a_{1}
 a_{1}
 (a_{0}==a_{1})?a_{0}:Variable
 Variable


Variable
 Variable
 Variable
 Variable


a_{i} = (f_{i},v_{i})
[Discuss
 The lattice has the same form as the
lattice for constant propagation:
a top element and a bottom element with all other elements between them and
incomparable to each other
]
Functions for global value numbering
The set F contains functions similar to those in the set for
the constant computations.
Most can be derived in a straightforward way from those according to the
models provided by f_{e+} and
f_{e!=}:
f_{e+}(e,v_{1},v_{2}) =
e == Nonexecutable ? Undetermined : f_{+}(v_{1},v_{2})
f_{+}
 Undetermined
 (K,i_{0})
 (V,i_{0})
 Variable


Undetermined
 Undetermined
 Undetermined
 Undetermined
 Undetermined


(K,i_{1})
 Undetermined
 (K,i_{0}+i_{1})
 (V,C_{+}((V,i_{0}),(K,i_{1})))
 Variable


(V,i_{1})
 Undetermined
 (V,C_{+}((K,i_{0}),(V,i_{1})))
 (V,C_{+}((V,i_{0}),(V,i_{1})))
 Variable


Variable
 Undetermined
 Variable
 Variable
 Variable


Here the function C_{+} is the
congruence function that yields the
value number for the expression described by a + operator with two operands.
f_{e!=}(e,v_{1},v_{2}) =
e == Nonexecutable ? Undetermined : f_{!=}(v_{1},v_{2})
f_{!=}
 Undetermined
 (K,i_{0})
 (V,i_{0})
 Variable


Undetermined
 Undetermined
 Undetermined
 Undetermined
 Undetermined


(K,i_{1})
 Undetermined
 (K,i_{0}!=i_{1})
 (V,C_{!=}((V,i_{0}),(K,i_{1})))
 Variable


(V,i_{1})
 Undetermined
 (V,C_{!=}((K,i_{0}),(V,i_{1})))
 i_{0}==i_{1} ? (K,0) :
(V,C_{!=}((V,i_{0}),(V,i_{1})))
 Variable


Variable
 Undetermined
 Variable
 Variable
 Variable


Here the function C_{!=} is the
congruence function that yields the
value number for the expression described by a + operator with two operands.
Function f_{phi} is not monotone:
f_{phi} = v == Variable ? (V,NewValueNumber()) : v
(Here v is the meet of all of the arguments and
NewValueNumber is a function that yields a value number that
has never been used.)
[Discuss
 Variable<(V,23) but f_{phi}(Variable) is
unrelated to f_{phi}((V,23))
 The fact that f_{phi} is not monotone does not
invalidate a termination proof if all other functions are
monotone:
After f_{phi} is evaluated with argument
Variable, it will never be returned to the work list again because
its argument will never change
]
SSA representation of main

1:
p_{11}: x_{1}:=1
p_{12}: z_{1}:=read()
p_{13}: y_{1}:=z_{1}
p_{14}: Jump(2)

2:
p_{21}: x_{2}:=phi(x_{1},x_{52})
p_{22}: y_{2}:=phi(y_{1},y_{2},y_{7})
p_{23}: V_{21}:=pred()
p_{24}: JumpT(3,V_{21})
p_{25}: JumpF(8,V_{21})

3:
p_{31}: V_{31}:=y_{2}!=z_{1}
p_{32}: JumpT(4,V_{31})
p_{33}: JumpF(5,V_{31})

4:
p_{41}: x_{4}:=2
p_{42}: Jump(5)

5:
p_{51}: x_{51}:=phi(x_{2},x_{4})
p_{52}: x_{52}:=2x_{51}
p_{53}: Jump(6)

6:
p_{61}: V_{61}:=x_{52}!=1
p_{62}: JumpT(7,V_{61})
p_{63}: JumpF(2,V_{61})

7:
p_{71}: y_{7}:=2
p_{72}: Jump(2)

8:
p_{81}: V_{81}:=x_{2}
p_{82}: printf(V_{81})
p_{83}: Return()

[Discuss
 Control flow graph on the left, dominator tree on the right, dominance
frontiers in square brackets
 No global value numbering has been done
]
Combined global value numbering
Assume that the work list is operated like a stack.
We first run through all of the computations in order, as though they had
been on the work list.
As we do this, we place only lowernumbered program points on the
work list (because highernumbered ones will be reached in due course).
After the first complete scan, we take program points off of the work
list.
Step  Program point  Result  To work list


1  p_{11}
 x_{1} = (K,1)  

Executable  

2  p_{12}
 z_{1} = (V,1)  

Executable  

3  p_{13}
 y_{1} = (V,1)  

Executable  

4  p_{14}  Executable  

5  p_{21}
 x_{2} = 1  

Executable  

6  p_{22}
 y_{2} = (V,1)  

Executable  

7  p_{23}
 V_{21} = (V,2)  

Executable  

8  p_{24}  Executable  

9  p_{25}  Executable  

10  p_{31}
 V_{31} = 0  

Executable  

11  p_{32}  Nonexecutable  

12  p_{33}  Executable  

13  p_{41}
 x_{4} = Undetermined  

Nonexecutable  

14  p_{42}  Nonexecutable  

15  p_{51}
 x_{51} = 1  

Executable  

16  p_{52}
 x_{52} = 1  p_{21}

Executable  

17  p_{53}  Executable  

18  p_{61}
 V_{61} = 0  

Executable  

19  p_{62}  Nonexecutable  

20  p_{63}  Executable  

21  p_{71}
 y_{7} = Undetermined  

Nonexecutable  

22  p_{72}  Nonexecutable  

23  p_{81}
 V_{81} = 1  

Executable  

24  p_{82}  Executable  

25  p_{83}  Executable  

26  p_{21}
 x_{2} = 1  

[Discuss
 Develop the table from the definitions of the functions
 Combining global value numbering with constant propagation and
executability analysis provides substantially more accurate information
than doing these analyses separately
]