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 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 compilers when 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 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.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]^[5]^[6]^[7]^[8]

^ Cite error: The named reference Kildall_1972_Optimization was invoked but never defined (see the help page).
^ Cite error: The named reference Kildall_1973_Optimization was invoked but never defined (see the help page).
^ Cite error: The named reference Cortesi_1999 was invoked but never defined (see the help page).
^ Cite error: The named reference Laws_2014_IEEE was invoked but never defined (see the help page).
^ 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.
^ Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. ISBN 978-0321486813.
^ Nielson, Flemming; Nielson, Hanne R.; Hankin, Chris (2005). Principles of Program Analysis. Springer. ISBN 978-3540654100.
^ Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1558603202.

[Kildall_1972_Optimization-1] Cite error: The named reference Kildall_1972_Optimization was invoked but never defined (see the help page).

[Kildall_1973_Optimization-2] Cite error: The named reference Kildall_1973_Optimization was invoked but never defined (see the help page).

[Cortesi_1999-3] Cite error: The named reference Cortesi_1999 was invoked but never defined (see the help page).

[Laws_2014_IEEE-4] Cite error: The named reference Laws_2014_IEEE was invoked but never defined (see the help page).

[Kildall19732-5] 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.

[Aho2006-6] Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. ISBN 978-0321486813.

[7] Nielson, Flemming; Nielson, Hanne R.; Hankin, Chris (2005). Principles of Program Analysis. Springer. ISBN 978-3540654100.

[8] Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1558603202.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]