Data-flow analysis

Data-flow analysis propagates facts about values or variable uses through a control-flow graph. Each program operation transforms incoming facts, and a join combines information from possible predecessor paths. A compiler can use the result to justify compiler optimization or issue warnings. Clang's introduction develops this method using sets of possible values and iteration to a fixed point.^[ref]

For example, live-variable analysis asks which current values might be read later before being overwritten. For a basic block $b$, with uses before any local definition in ${\mathrm{USE}}_b$ and definitions in ${\mathrm{DEF}}_b$, the backward equations areA use requires the incoming value; an intervening definition removes that requirement. Iterating from empty sets terminates for a finite graph and finite variable set because these equations only add facts. The result guides register allocation.

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.