Data-flow analysis
= 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>.<Data flow analysis: an informal introduction in the Clang documentation>[Data flow analysis, joins and fixed-point computation]{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 are
$$
\mathrm{OUT}_b=\bigcup_{s\in\mathrm{succ}(b)}\mathrm{IN}_s,\qquad
\mathrm{IN}_b=\mathrm{USE}_b\cup(\mathrm{OUT}_b\setminus\mathrm{DEF}_b).
$$
A 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>.