research-article

A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithms

Authors:

Michael G. Burke,

Barbara G. RyderAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 16, Issue 7

Pages 723 - 728

https://doi.org/10.1109/32.56098

Published: 01 July 1990 Publication History

Publisher Site

Abstract

A model of data flow analysis and fixed point iteration solution procedures is presented. The faulty incremental iterative algorithm is introduced. Examples of the imprecision of restarting iteration from the intraprocedural and interprocedural domains are given. Some incremental techniques which calculate precise data flow information are summarized.

References

[1]

{1} A. V. Aho, R. Sethi, and J. D. Ullman, Compliers: Principles. Techniques, and Tools. Reading, MA. Addison-Wesley, 1986.

Crossref

Google Scholar

[2]

{2} F. E. Allen and J. Cocke. "A program data flow analysis procedure," Commun. ACM. vol. 19, no. 3, pp. 137-147, 1976.

Digital Library

Google Scholar

[3]

{3} J. Banning, "An efficient way to find the side effects or procedure: calls and the aliases of variables," in Conf. Rec., Sixth Annu. ACM Symp. Principles of Programming Languages. Jan. 1979, pp. 29-41.

Digital Library

Google Scholar

[4]

{4} M. Burke, "An interval-based approach to exhaustive and incremental Interprocedural data flow analysis," IBM Thomas J. Watson Research Center. Yorktown Heights. NY. Comput. Sci. Tech. Rep. RC12702. Aug. 1987; to appear in ACM Trans. Program. Lang. Syst., July 1990.

Crossref

Google Scholar

[5]

{5} M. D. Carroll, "Dataflow update via attribute and dominator update," Ph.D. dissertation, Dep. Comput. Sci., Rutgers Univ., May 1988.

Google Scholar

[6]

{6} M. D. Carroll and B. G. Ryder, "Incremental data flow analysis via dominator and attribute updates," in Conf. Rec. Fifteenth Annu. ACM Symp. Principles of Programming Languages, Jan. 1988, pp. 274- 284.

Crossref

Google Scholar

[7]

{7} K. Cooper, "Analyzing aliases of reference formal parameters," in Conf. Rec. Twelfth Annu. ACM Symp. Principles of Programming Languages, Jan. 1985, pp. 281-290.

Crossref

Google Scholar

[8]

{8} K. Cooper and K. Kennedy, "Efficient computation of flow insensitive interprocedural summary information," SIGPLAN Notices (Proc. ACM SIGPLAN Symp. Compiler Construction), vol. 19, no. 6, pp. 247-258, June 1984.

Crossref

Google Scholar

[9]

{9} K. D. Cooper, "Interprocedural data flow analysis in a programming environment," Ph.D. dissertation, Dep. Math. Sci., Rice Univ., 1983.

Digital Library

Google Scholar

[10]

{10} V. Ghodssi, "Incremental analysis of programs," Ph.D. dissertation, Dep. Comput. Sci., Univ. Central Florida, 1983.

Digital Library

Google Scholar

[11]

{11} S. Graham and M. Wegman, "'Fast and usually linear algorithm for global flow analysis," J. ACM, vol. 23, no. 1, pp. 172-202, Jan. 1976.

Digital Library

Google Scholar

[12]

{12} M. S. Hecht and J. D. Ullman, "A simple algorithm for global data flow analysis problems," SIAM J. Comput., vol. 4, no, 4, pp. 519- 532, Dec. 1977.

Google Scholar

[13]

{13} J. B. Kam and J. D. Ullman, "Global flow analysis and iterative algorithms," J. ACM, vol. 23, no. 1, pp. 158-171, 1976.

Digital Library

Google Scholar

[14]

{14} G. Kildall, "A unified approach to global program optimization," in Conf. Rec. ACM Symp. Principles of Programming Languages, Jan. 1973, pp. 194-206.

Crossref

Google Scholar

[15]

{15} T. J. Marlowe, "Data flow analysis and incremental iteration," Ph.D. dissertation, Dep. Comput. Sci., Rutgers Univ., Aug. 1989.

Crossref

Google Scholar

[16]

{16} T. J. Marlowe and B. G, Ryder, "An efficient hybrid algorithm for incremental data flow analysis," in Conf. Rec. Seventeenth Annu. ACM Symp. Principles of Programming Languages, Jan, 1990, pp. 184-196.

Crossref

Google Scholar

[17]

{17} L. Pollock, "An approach to incremental compilation of optimized code," Ph.D. dissertation, Univ. Pittsburgh, 1986; also available as Dep. Comput. Sci. Tech. Rep. 86-3.

Digital Library

Google Scholar

[18]

{18} L. Pollock and M. Sofia, "An incremental version of iterative data flow analysis," IEEE Trans. Software Eng., vol. 15, no. 12, Dec. 1989.

Digital Library

Google Scholar

[19]

{19} B. K. Rosen, "High-level data flow analysis," Commun. ACM, vol. 20, no. 10, pp. 712-724, Oct. 1977.

Digital Library

Google Scholar

[20]

{20} B. K. Rosen, "Monoids for rapid data flow analysis," SIAM J. Comput., vol. 9, no. 1, pp. 159-196, Nov. 1980.

Crossref

Google Scholar

[21]

{21} B. K. Rosen, "A lubricant for data flow analysis," SIAM J. Comput., vol. 11, no. 3, pp. 493-511, Aug. 1982.

Crossref

Google Scholar

[22]

{22} B. G. Ryder, "Incremental data flow analysis," in Conf. Rec. Tenth Annu. ACM Symp. Principles of Programming Languages, Jan. 1983, pp. 167-176.

Crossref

Google Scholar

[23]

{23} B. G. Ryder and M. D. Carroll, "An incremental algorithm for software analysis," in Proc. ACM SIGSOFT/SIGPLAN Software Engineering Symp. Practical Software Development Environments, Dec. 1986, pp. 171-179.

Crossref

Google Scholar

[24]

{24} B. G. Ryder, T. J. Marlowe, and M. C. Paull, "Conditions for incremental iteration: Examples and counterexamples," Sci. Program., vol. 11, pp. 1-15, 1988.

Digital Library

Google Scholar

[25]

{25} B. G, Ryder and M. C. Paull, "Elimination algorithms for data flow analysis," ACM Comput. Survey, vol. 18, no. 3, pp. 277-316, Sept. 1986.

Digital Library

Google Scholar

[26]

{26} B. G, Ryder and M. C. Paull, "Incremental data flow analysis algorithms," ACM Trans. Program. Lang. Syst., vol. 10, no. 1, pp. 1-50, Jan. 1988.

Digital Library

Google Scholar

[27]

{27} J. T. Schwartz and M. Sharir, "A design for optimizations of bivectoring class," Courant Inst. Math. Sci., New York Univ. Comput. Sci. Tech. Rep. 17, Sept. 1979.

Google Scholar

[28]

{28} R. E. Tarjan, "Testing flow graph reducibility," J. Comput. Syst. Sci., vol. 9, pp. 355-365, 1974.

Digital Library

Google Scholar

[29]

{29} R. E. Tarjan, "Fast algorithms for solving path problems," J. ACM, vol. 28, no. 3, pp. 594-614, 1981.

Digital Library

Google Scholar

[30]

{30} R. E. Tarjan, "A unified approach to path problems," J. ACM, vol. 28, no. 3, pp. 577-593, 1981.

Digital Library

Google Scholar

[31]

{31} F. K. Zadeck, "'Incremental data flow analysis in a structured program editor," SIGPLAN Notices (Proc. ACM SIGPLAN Symp. Compiler Construction), vol. 19, no. 6, pp. 132-143, June 1984.

Digital Library

Google Scholar

Cited By

View all

Krishna SLal APavlogiannis ATuppe O(2024)On-the-Fly Static Analysis via Dynamic Bidirected Dyck ReachabilityProceedings of the ACM on Programming Languages10.1145/36328848:POPL(1239-1268)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632884
Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Sathyanathan PHe WTzen TReddi VSmith ATang L(2017)Incremental whole program optimization and compilationProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049857(221-232)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049857
Show More Cited By

Index Terms

A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithms
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
  2. Software notations and tools
    1. Compilers

Recommendations

An Incremental Version of Iterative Data Flow Analysis

A technique is presented for incrementally updating solutions to both union and intersection data-flow problems in response to program edits and transformations. For generality, the technique is based on the iterative approach to computing data-flow ...
Interprocedural data flow analysis in Soot using value contexts
SOAP '13: Proceedings of the 2nd ACM SIGPLAN International Workshop on State Of the Art in Java Program analysis

An interprocedural analysis is precise if it is flow sensitive and fully context-sensitive even in the presence of recursion. Many methods of interprocedural analysis sacrifice precision for scalability while some are precise but limited to only a ...
Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems

Precise static analyses are context-, field- and flow-sensitive. Context- and field-sensitivity are both expressible as context-free language (CFL) reachability problems. Solving both CFL problems along the same data-flow path is undecidable, which is ...

Reviews

Reviewer: William M. Waite

Computation of dataflow information is expensive, so we would like to avoid a complete recomputation if a small change is made to the program. Unfortunately, some algorithms that update dataflow information affected by program changes do not yield the results that would have been obtained had the analysis been done from scratch after the changes. Burke and Ryder present a general model of dataflow analysis and fixed point iteration solution procedures, and use that model to characterize the situations in which incremental algorithms yield the “wrong” answer. They apply their techniques to a number of common problems (such as live variable analysis and interprocedural potential alias analysis), showing failures of published algorithms. Finally, they briefly discuss algorithms that do not fail in this way. The purpose of this research paper is to point out a fundamental limitation of certain kinds of incremental analysis procedures. It fulfills this goal well, providing both an intuitive appreciation and a precise characterization of the failure mode. Thus it is accessible to anyone who has a basic understanding of the data flow analysis problem.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 16, Issue 7

July 1990

99 pages

ISSN:0098-5589

Editor:
Victor R. Basili
Univ. of Maryland, College Park

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 July 1990

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Krishna SLal APavlogiannis ATuppe O(2024)On-the-Fly Static Analysis via Dynamic Bidirected Dyck ReachabilityProceedings of the ACM on Programming Languages10.1145/36328848:POPL(1239-1268)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632884
Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Sathyanathan PHe WTzen TReddi VSmith ATang L(2017)Incremental whole program optimization and compilationProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049857(221-232)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049857
Vora KGupta RXu G(2016)Synergistic Analysis of Evolving GraphsACM Transactions on Architecture and Code Optimization10.1145/299278413:4(1-27)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2992784
Arzt SBodden EJalote PBriand LHoek A(2014)Reviser: efficiently updating IDE-/IFDS-based data-flow analyses in response to incremental program changesProceedings of the 36th International Conference on Software Engineering10.1145/2568225.2568243(288-298)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2568225.2568243
Lu YShang LXie XXue J(2013)An incremental points-to analysis with CFL-ReachabilityProceedings of the 22nd international conference on Compiler Construction10.1007/978-3-642-37051-9_4(61-81)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37051-9_4
Eichberg MKahl MSaha DMezini MOstermann K(2007)Automatic incrementalization of prolog based static analysesProceedings of the 9th international conference on Practical Aspects of Declarative Languages10.1007/978-3-540-69611-7_7(109-123)Online publication date: 14-Jan-2007
https://dl.acm.org/doi/10.1007/978-3-540-69611-7_7
Saha DRamakrishnan CBarahona PFelty A(2005)Incremental and demand-driven points-to analysis using logic programmingProceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1069774.1069785(117-128)Online publication date: 11-Jul-2005
https://dl.acm.org/doi/10.1145/1069774.1069785
Carroll SPolychronopoulos C(2004)A framework for incremental extensible compiler constructionInternational Journal of Parallel Programming10.1023/B:IJPP.0000035816.93295.6832:4(289-316)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1023/B%3AIJPP.0000035816.93295.68
Besson FJensen T(2003)Modular class analysis with DATALOGProceedings of the 10th international conference on Static analysis10.5555/1760267.1760270(19-36)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.5555/1760267.1760270
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

An Incremental Version of Iterative Data Flow Analysis

Interprocedural data flow analysis in Soot using value contexts

Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations