 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.