### 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