Data-flow analysis

This article is about static program analysis. For dynamic program analysis, see Dynamic program analysis § Dynamic data-flow analysis.

Part of a series on
Software development
Core activities
Paradigms and models
Methodologies and frameworks
Supporting disciplines
Practices
Tools
Standards and bodies of knowledge
Glossaries
Outlines

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control-flow graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program. A canonical example of a data-flow analysis is reaching definitions.

A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control-flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fixpoint. This general approach, also known as Kildall's method, was developed by Gary Kildall while teaching at the Naval Postgraduate School.[1][2][3][4]

  1. ^ Cite error: The named reference Kildall_1972_Optimization was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference Kildall_1973_Optimization was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference Cortesi_1999 was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference Laws_2014_IEEE was invoked but never defined (see the help page).