Compiler Designing W08L1502

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.


Help to improve or comment as you wish

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s