Editing Data-flow analysis (section)

{{Short description|Method of analyzing variables in software}}
{{About|static program analysis|dynamic program analysis|Dynamic program analysis#Dynamic data-flow analysis}}
{{More citations needed section|date=February 2018}}
{{Use dmy dates|date=January 2020|cs1-dates=y}}
{{Software development process}}
'''Data-flow analysis''' is a technique for gathering information about the possible set of values calculated at various points in a [[computer program]]. It forms the foundation for a wide variety of compiler optimizations and program verification techniques. 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 [[compiler]]s when [[optimizing compiler|optimizing]] a program. A canonical example of a data-flow analysis is [[reaching definitions]]. Other commonly used data-flow analyses include live variable analysis, available expressions, constant propagation, and very busy expressions, each serving a distinct purpose in compiler optimization passes.

A simple way to perform data-flow analysis of programs is to set up data-flow equations for each [[node (computer science)|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]]. The efficiency and precision of this process are significantly influenced by the design of the data-flow framework, including the direction of analysis (forward or backward), the domain of values, and the join operation used to merge information from multiple control paths.{{anchor|Kildall's method}}This general approach, also known as ''Kildall's method''<!-- or ''Kildall's algorithm'' -->, was developed by [[Gary Kildall]] while teaching at the [[Naval Postgraduate School]].<ref name="Kildall_1972_Optimization"/><ref name="Kildall_1973_Optimization"/><ref name="Cortesi_1999"/><ref name="Laws_2014_IEEE"/><ref name="Kildall19732">Kildall, Gary A. (1973). "A Unified Approach to Global Program Optimization". Proceedings of the ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL '73). ACM. pp. 194–206. doi:10.1145/512927.512945.</ref><ref name="Aho2006">Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. ISBN 978-0321486813.</ref><ref>Nielson, Flemming; Nielson, Hanne R.; Hankin, Chris (2005). Principles of Program Analysis. Springer. ISBN 978-3540654100.</ref><ref>Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1558603202.</ref>