Compiler Designing W08L1505

Liveness Analysis

  • A variable is live if it holds a value that may be needed in the future. Liveness is measured for each statement when control comes in and goes out of the statement.
  • Copy propagation can result in dead code. See examples,
X := 3
Y := 3*x         //X would be replaced with 3 and then first statement would be dead.
X:=3(dead);
X:=4;   //new value would be effective now
Y:=X;
  • As in the case of copy propagation, liveness depends on the information propagation between adjacent statements.
  • Livenesss can either be true or false; L(…)=true/false
  • Rules:
1. L(p,x,out) = ∨ {L(s,x,in) | s is a successor of p}
2. L(...=f(x),x, in) = true if x is used in the RHS of statement
3. L(x:=e,x,in) = false if e has nothing to do with x
4. L(s,x,in) = L(s,x,out) when s doesn't use x.

Algorithm:

initially take L(...)= false at all the point
and repeat till all the statements satisfy the above 4 rules.

Example from 7:50 minute.

  • A value of liveness can only change once, from false to true. Hence false < true.
  • Liveness is a backward analysis while constant propagation is a forward analysis.
Advertisements

Help to improve or comment as you wish

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

WordPress.com Logo

You are commenting using your WordPress.com 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