Global Optimization: Constant Propagation
- Some notations that would be used:
- T(Top) ⇒ X is not a constant or the value is not known now;
- C(Constant) ⇒ X is constant C;
- ⊥(Bottom) ⇒ X is dead.
- At each node, define value of X after each statement of the node, including the start and end node.
- Data flow analysis algorithms: The analysis of a complicated program can be expressed as a combination of simple rules relating the change in information between the adjacent statements.
- For each statement two functions are defined C(x,s,in)=value of x before s and C(x,s,out)=value of x after s; (C:constant information). Statement’s predecessor statements are also used.
- If the statement s is achieved after some independent statements pi; i=1,..n
1. C(x,pi,out) = T ∀i ⇒ C(x,s,in) = T 2. C(x,pi,out) = c or d and c ≠ d ∀i ⇒ C(x,s,in)=T 3. C(x,pi,out) = c or ⊥ ∀i ⇒ C(x,s,in) = c 4. C(x,pi,out) = ⊥ ∀i ⇒ C(x,s,in) = ⊥
- When same statement’s in and out to be calculated:
5. C(x, s, out) = ⊥ if s doesn't use x 6. C(x, x :=a, out) = x := a 7. C(x, x=f(...), out) = x := T //f(...) is a complicated expression 8. C(x, y=..., out) = x is unchanged.
- Algorithm looks like:
1. For entering node put X := T 2. for any other statement put x := ⊥ 3. Repeat till all the points from 1-8 are satisfied.
Example from 17:53 minute.