= Live-variable analysis
<Live-variable analysis> computes which <program variables> may be read in the future before their current values are overwritten. It is a backward <data-flow analysis>: future uses make information flow toward earlier instructions. For a basic block $B$, let $\mathrm{USE}(B)$ contain values read before being defined in that block and let $\mathrm{DEF}(B)$ contain its definitions. Then
$$
\mathrm{OUT}(B)=\bigcup_{C\in\operatorname{succ}(B)}\mathrm{IN}(C),\qquad
\mathrm{IN}(B)=\mathrm{USE}(B)\cup\bigl(\mathrm{OUT}(B)\setminus\mathrm{DEF}(B)\bigr).
$$
A value is needed on entry if the block itself first reads it, or if a successor needs it and the block does not replace it.<The LLVM Target-Independent Code Generator>[Live Variable Analysis and Live Intervals]{ref}
For a block `x = y + 1; return x;`, `y` is live on entry but the old `x` is not. Iterating the equations over a finite <control-flow graph> yields a conservative answer useful for <register allocation>. Syntactically possible paths may include paths that execution can never take, so computed liveness need not prove that a use actually occurs.
Back to article page
