Combining Analyses

Example

int
p(void)
{ int x = 1;
  do { if (x != 1) x = 2; } while (pred());
  return x;
}

[Discuss-

• Regardless of the implementation of pred, p will return 1 if it terminates

]

SSA representation

	1: p11: x:=1 p12: Jump(2)
	2: p21: x1:=phi(x,x3) p22: V21:=x1 p23: V22:=V21!=1 p24: JumpT(3,V22) p25: JumpF(4,V22)
	3: p31: x2:=2 p32: Jump(4)
	4: p41: x3:=phi(x1,x2) p42: V41:=pred p43: V42:=V41!=0 p44: JumpT(2,V42) p45: JumpF(5,V42)
	5: p51: V51:=x3 p52: Return(V51)

[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

[Discuss-

• Because both V₂₂ and V₄₂ 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

fe+(e,v1,v2) =
  e == Non-executable ? Undetermined : f+(v1,v2)

[Discuss-

• The executability and constant propagation must now be executed at the same time
• Information flow occurs in both directions

]

Combined calculation

[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

• Subtraction of congruent values yields 0
• Comparison of congruent values for equality yields true
• Undetermined value is congruent to everything

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

[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	a0	Variable
  Undetermined	Undetermined	a0	Variable
  a1	a1	(a0==a1)?a0: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

fe+(e,v1,v2) =
  e == Non-executable ? Undetermined : f+(v1,v2)

fe!=(e,v1,v2) =
  e == Non-executable ? Undetermined : f!=(v1,v2)

Function f_phi is not monotone:

fphi = v == Variable ? (V,NewValueNumber()) : v

[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: p11: x1:=1 p12: z1:=read() p13: y1:=z1 p14: Jump(2)
	2: p21: x2:=phi(x1,x52) p22: y2:=phi(y1,y2,y7) p23: V21:=pred() p24: JumpT(3,V21) p25: JumpF(8,V21)
	3: p31: V31:=y2!=z1 p32: JumpT(4,V31) p33: JumpF(5,V31)
	4: p41: x4:=2 p42: Jump(5)
	5: p51: x51:=phi(x2,x4) p52: x52:=2-x51 p53: Jump(6)
	6: p61: V61:=x52!=1 p62: JumpT(7,V61) p63: JumpF(2,V61)
	7: p71: y7:=2 p72: Jump(2)
	8: p81: V81:=x2 p82: printf(V81) p83: 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

[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

]