Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. It uses the control-flow graph of the program to determine which parts of the program a value assigned to a variable might propagate to, and it forms the foundation for many compiler optimizations and program verification techniques. A simple way to perform it is to set up data-flow equations for each node of the control-flow graph and solve them by repeatedly computing each node's output from its input until the whole system stabilizes at a fixpoint. This general approach, also known as Kildall's method, was developed by Gary Kildall while teaching at the Naval Postgraduate School. Reaching definitions is the canonical example, and live variable analysis, available expressions and constant propagation are other common analyses.