 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. ThenA 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.^[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.