More Web Proxy on the site http://driver.im/

research-article

An Incremental Version of Iterative Data Flow Analysis

Authors:

M. L. SoffaAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 15, Issue 12

Pages 1537 - 1549

https://doi.org/10.1109/32.58766

Published: 01 December 1989 Publication History

Abstract

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 information. The authors show that for both union and intersection problems, some changes can be incrementally incorporated immediately into the data-flow sets while others are handled by a two-phase approach. The first phase updates the data-flow sets to overestimate the effect of the program change, enabling the second phase to incrementally update the affected data-flow sets to reflect the actual program change. An important problem that is addressed is the computation of the data-flow changes that need to be propagated throughout a program, based on different local code changes. The technique is compared to other approaches to incremental data-flow analysis.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

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

Digital Library

[4]

{4} K. Cooper, K. Kennedy, and L. Torczon, "The impact of interprocedural analysis and optimization on the design of a software development environment," in Proc. ACM Symp. Language Issues in Programming Environments, June 1985, pp. 107-116.

Digital Library

[5]

{5} J. Ellis, Bulldog: A Compiler for VLIW Architectures. Cambridge, MA: MIT Press, 1985.

Digital Library

[6]

{6} V. Ghodssi, "Incremental analysis of programs," Ph.D. dissertation, Univ. Central Florida, 1983.

Digital Library

[7]

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

Digital Library

[8]

{8} R. Gupta and M. Soffa, "Region scheduling," in Proc. Second Int. Conf. Supercomputing, vol. III, May 1987, pp. 141-148.

[9]

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

Digital Library

[10]

{10} S. Jain and C. Thompson, "An efficient approach to data flow analysis in a multiple-pass global optimizer," in Proc. ACM SIGPLAN 1988 Conf. Programming Language Design and Implementation, June 1988, pp. 154-163.

Digital Library

[11]

{11} J. Keables, K. Roberson, and A. von Mayrhauser, "Data flow analysis and its application to software maintenance," in Proc. IEEE Conf. Software Maintenance, Oct. 1988, pp. 335-347.

[12]

{12} K. Kennedy, "A survey of data flow analysis techniques," in Program Flow Analysis Theory and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1981.

Digital Library

[13]

{13} L. Pollock, "An approach to incremental compilation of optimized code," Ph.D. dissertation, Univ. Pittsburgh, Pittsburgh, PA, Apr. 1986.

Digital Library

[14]

{14} T. Reps, T. Teitelbaum, and A. Demers, "Incremental context-dependent analysis for language-based editors," ACM TOPLAS, vol. 5, no. 3, pp. 449-477, July 1983.

Digital Library

[15]

{15} B. Ryder, "Incremental data flow analysis," in Conf. Rec. Tenth ACM POPL Conf. Jan. 1983, pp. 167-176.

Digital Library

[16]

{16} B. Ryder, T. Marlowe, and M. Paull, "Incremental iteration: When will it work?," Dep. Comput. Sci., Rutgers Univ., New Brunswick, NJ, Tech. Rep. LCSR-TR-89, 1987.

[17]

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

Digital Library

[18]

{18} J. Ullman, "Fast algorithms for the elimination of common subexpressions," Acta Inform., vol. 2, no. 3, pp. 191-213, 1973.

Digital Library

[19]

{19} F. Zadeck, "Incremental data flow analysis in a structured program editor," in Proc. ACM SIGPLAN 1984 Symp. Compiler Construction , June 1984.

Digital Library

Cited By

Liu JQu WGaboardi MGarg DUllman J(2024)Program Analysis for Adaptive Data AnalysisProceedings of the ACM on Programming Languages10.1145/36564148:PLDI(914-938)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656414
Nougrahiya ANandivada V(2024)Homeostasis: Design and Implementation of a Self-Stabilizing CompilerACM Transactions on Programming Languages and Systems10.1145/364930846:2(1-58)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3649308
Stein BChang BSridharan M(2024)Interactive Abstract Interpretation with Demanded SummarizationACM Transactions on Programming Languages and Systems10.1145/364844146:1(1-40)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648441
Show More Cited By

Index Terms

An Incremental Version of Iterative Data Flow Analysis
1. Software and its engineering

Recommendations

Incremental analysis for flow- and context-sensitive data-flow problems (software maintenance)
A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithms

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 ...
Reviser: efficiently updating IDE-/IFDS-based data-flow analyses in response to incremental program changes
ICSE 2014: Proceedings of the 36th International Conference on Software Engineering

Most application code evolves incrementally, and especially so when being maintained after the applications have been deployed. Yet, most data-flow analyses do not take advantage of this fact. Instead they require clients to recompute the entire ...

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 15, Issue 12

December 1989

160 pages

ISSN:0098-5589

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

Issue’s Table of Contents

Copyright © Copyright © 1989 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 December 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
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

Liu JQu WGaboardi MGarg DUllman J(2024)Program Analysis for Adaptive Data AnalysisProceedings of the ACM on Programming Languages10.1145/36564148:PLDI(914-938)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656414
Nougrahiya ANandivada V(2024)Homeostasis: Design and Implementation of a Self-Stabilizing CompilerACM Transactions on Programming Languages and Systems10.1145/364930846:2(1-58)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3649308
Stein BChang BSridharan M(2024)Interactive Abstract Interpretation with Demanded SummarizationACM Transactions on Programming Languages and Systems10.1145/364844146:1(1-40)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648441
Wu RHe YHuang JWang CTang WShi QXiao XZhang CRoychoudhury APaiva AAbreu RStorey M(2024)LibAlchemy: A Two-Layer Persistent Summary Design for Taming Third-Party Libraries in Static Bug-Finding SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639132(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639132
Liblit BLyu YMukherjee RTripp OWang Y(2024)User-assisted code query customization and optimizationInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-024-00763-026:5(607-619)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10009-024-00763-0
Ji SGong JDong HZhang PZhu S(2024)IABC‐TCGJournal of Software: Evolution and Process10.1002/smr.271936:12Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1002/smr.2719
Szabó TChandra SBlincoe KTonella P(2023)Incrementalizing Production CodeQL AnalysesProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3613860(1716-1726)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3613860
Liblit BLyu YMukherjee RTripp OWang YFerrara PHadarean L(2023)User-Assisted Code Query OptimizationProceedings of the 12th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3589250.3596148(40-46)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3589250.3596148
Van der Plas JStiévenart QDe Roover C(2023)Result Invalidation for Incremental Modular AnalysesVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_14(296-319)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-24950-1_14
Szabó TErdweg SBergmann GFreund SYahav E(2021)Incremental whole-program analysis in Datalog with latticesProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454026(1-15)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454026
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents