Article

Free access

Precise interprocedural dataflow analysis via graph reachability

Authors:

Mooly SagivAuthors Info & Claims

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 49 - 61

https://doi.org/10.1145/199448.199462

Published: 25 January 1995 Publication History

Abstract

The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts must be a finite set, and that the dataflow functions must distribute over the confluence operator (either union or intersection). This class of probable problems includes—but is not limited to—the classical separable problems (also known as “gen/kill” or “bit-vector” problems)—e.g., reaching definitions, available expressions, and live variables. In addition, the class of problems that our techniques handle includes many non-separable problems, including truly-live variables, copy constant propagation, and possibly-uninitialized variables.

Results are reported from a preliminary experimental study of C programs (for the problem of finding possibly-uninitialized variables).

References

[1]

Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA (1974).]]

Digital Library

[2]

Aho, A.V., Ganapathi, M., and Tjiang, S.W.K., "Code generation using tree matching and dynamic programming," A CM Trans. Program. Lang. Syst. 11(4) pp. 491-516 (October 1989).]]

Digital Library

[3]

Baker, B., "An algorithm for structuring flowgraphs," J. A CM 24(1) pp. 98-120 (January 1977).]]

Digital Library

[4]

Cai, J, and Paige, R., "Program derivation by fixed point computation," Science of Computer Programming 11 pp. 197-261 (1988/89).]]

Digital Library

[5]

Callahan, D., Cooper, K.D., Kennedy, K., and Torczon, L., "Interprocedural constant propagation," Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, (Palo Alto, CA, June 25-27, 1986), ACM SIGPLAN Notices 21(7) pp. 152-i61 (July 1986).]]

Digital Library

[6]

Callahan, D., "The program summary graph and flow-sensitive interprocedural data flow analysis," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 47-56 (July 1988).]]

Digital Library

[7]

Cooper, K.D, and Kennedy, K., "Interprocedural side-effect analysis in linear time," Proceedings of the A CM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 57-66 (July 1988).]]

Digital Library

[8]

Cooper, K.D. and Kennedy, K., "Fast interprocedural alias analysis," pp. 49-59 in Conference Record of the Sixteenth ACM Symposium on Principles of Programming Languages, (Austin, TX, Jan. I1-i3, 1989), ACM, New York, NY (1989).]]

Digital Library

[9]

Cousot, P. and Cousot, R., "Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints," pp. 238-252 in Conference Record of the Fourth A CM Symposium on Principles of Programming Languages, (Los Angeles, CA, January 17-19, 1977), ACM, New York, NY (1977).]]

Digital Library

[10]

Cousot, P. and Cousot, R., "Static determination of dynamic properties of recursive procedures," pp. 237-277 in Formal Descriptions of Programming Concepts, (IFIP WG 2.2, St. Andrews, Canada, August 1977), ed. E.J. Neuhold,North-Holland, New York, NY (1978).]]

[11]

Duesterwald, E., Gupta, R., and Soffa, M.L., "Demand-driven computation of interprocedural data flow," in Conference Record of the Twenty-Second A CM Symposium on Principles of Programming Languages, (San Francisco, CA, Jan. 23-25, 1995), ACM, New York, NY (1995). (To appear.)]]

Digital Library

[12]

Fischer, C.N. and LeBlanc, R.J., Crafting a Compiler, Benjamin/Cummings Publishing Company, Inc., Menlo Park, CA (1988).]]

Digital Library

[13]

Giegerich, R., Moncke, U., and Wilhelm, R., "Invariance of approximative semantics with respect to program transformation," pp. 1-10 in Informatik-Fachberichte 50, Springer-Verlag, New York, NY (1981).]]

Digital Library

[14]

Grove, D. and Torczon, L., "Interprocedural constant propagation: A study of jump function implementation," pp. 90-99 in Proceedings of the A CM SIGPLAN 93 Conference on Programming Language Design and Implementation, (Albuquerque, NM, June 23-25, 1993), ACM, New York, NY (1993).]]

Digital Library

[15]

Holley, L.H. and Rosen, B.K., "Qualified data flow problems," IEEE Transactions on Software Engineering SE-7(1)pp. 60-78 (January 1981).]]

Digital Library

[16]

Horwitz, S., Reps, T., and Binkley, D., "Interprocedural slicing using dependence graphs," ACM Trans. Program. Lang. Syst. 12(1)pp. 26-60 (January 1990).]]

Digital Library

[17]

Horwitz, S., Reps, T., and Sagiv, M., "Demand interprocedural dataflow analysis," Unpublished Report, Computer Sciences Department, University of Wisconsin, Madison, WI 0. (In preparation.)]]

[18]

Jones, N.D. and Mycroft, A., "Data flow analysis of applicative programs using minimal function graphs," pp. 296-306 in Conference Record of the Thirteenth A CM Symposium on Principles of Programming Languages, (St. Petersburg, FL, Jan. 13-15, 1986), ACM, New York, NY (1986).]]

Digital Library

[19]

Kernighan, B.W., "Ratfor- A preprocessor for a rational Fortran," Software- Practice & Experience 5(4) pp. 395-406 (1975).]]

[20]

Kildall, G., "A unified approach to global program optimization," pp. 194-206 in Conference Record of the First ACM Symposium on Principles of Programming Languages, ACM, New York, NY (1973).]]

Digital Library

[21]

Knoop, J. and Steffen, B., "The interprocedural coincidence theorem," pp. 125-140 in Proceedings of the Fourth International Conference on Compiler Construction, (Paderborn, FRG, October 5- 7, 1992), Lecture Notes in Computer Science, Vol. 641, ed. U. Kastens and P. Pfahler, Springer-Vedag, New York, NY (1992).]]

Digital Library

[22]

Knoop, J. and Steffen, B., "Efficient and optimal bit-vector data flow analyses: A uniform interprocedural framework," Bericht Nr. 9309, Institut fuer Informatik und Praktische Mathematik, Christian- Albrechts-Universitaet zu Kiel, KieI, Germany (April 1993).]]

[23]

Kou, L.T., "On live-dead analysis for global data flow problems," Journal of the ACM 24(3) pp. 473-483 (July 1977).]]

Digital Library

[24]

Landi, W. and Ryder, B.G., "Pointer-induced aliasing: A problem classification," pp. 93-103 in Conference Record of the Eighteenth ACM Symposium on Principles of Programming Languages, (Orlando, FL, January 1991), ACM, New York, NY (1991).]]

Digital Library

[25]

Nielson, F. and Nielson, H.R., "Finiteness conditions for fixed point iteration," in Conference Record of the 1992 A CM Symposium on Lisp and Functional Programming, (San Francisco, CA, June 22-24 1992), ACM, New York, NY (1992).]]

Digital Library

[26]

Nielson, H.R. and Nielson, F., "Bounded fixed point iteration," pp. 71-82 in Conference Record of the Nineteenth ACM Symposium on Principles of Programming Languages, (Albuquerque, NM, January 1992), ACM, New York, NY (1992).]]

Digital Library

[27]

Reps, T., Sagiv, M., and Horwitz, S., "Interprocedural dataflow analysis via graph reachability," TR 94-14, Datalogisk Institut, University of Copenhagen, Copenhagen, Denmark (April 1994). (Available through World Wide Web at ftp://ftp.diku.dk/diku/semantics/papers/D-215.ps.Z.)]]

[28]

Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., "Speeding up slicing," SIGSOFT 94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19(December 1994). (To appear.)]]

Digital Library

[29]

Reps, T., "Solving demand versions of interprocedural analysis problems," pp. 389-403 in Proceedings of the Fifth International Conference on Compiler Construction, (Edinburgh, Scotland, April 7-9, 1994), Lecture Notes in Computer Science, Vol. 786, ed. P. Fritzson,Springer-Verlag, New York, NY (1994).]]

Digital Library

[30]

Sagiv, M., Reps, T., and Horwitz, S., "Precise interprocedural dataflow analysis with applications to constant propagation," Unpublished Report, Comp. Sci. Dept., Univ. of Wisconsin, Madison, WI (Oct. 1994). (Submitted for conference publication.)]]

[31]

Sharir, M. and Pnueli, A., "Two approaches to interprocedural data flow analysis," pp. 189-233 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (1981).]]

[32]

Zadeck, F.K., "Incremental data flow analysis in a structured program editor," Proceedings of the SIGPLAN 84 Symposium on Compiler Construction, (Montreal, Can., June 20-22, 1984), ACM SIGPLAN Notices 19(6)pp. 132-143 (june 1984).]]

Digital Library

Cited By

Balaji SCharumathi DAhmed MAppu A(2024)The influence of job satisfaction on retention of primary healthcare professionals in Tamil NaduInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02511:2(238-247)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.025
Umann KHorváth GPorkoláb Z(2024)Uncovering Hidden Dependencies: Constructing Intelligible Path Witnesses using Dataflow AnalysesActa Cybernetica10.14232/actacyb.29980526:3(713-747)Online publication date: 4-Mar-2024
https://doi.org/10.14232/actacyb.299805
Quiring BVan Horn D(2024)Deriving with Derivatives: Optimizing Incremental Fixpoints for Higher-Order Flow AnalysisProceedings of the ACM on Programming Languages10.1145/36746508:ICFP(728-755)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674650
Show More Cited By

Index Terms

Precise interprocedural dataflow analysis via graph reachability

Recommendations

Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Precise interprocedural analysis using random interpretation
Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We describe a unified framework for random interpretation that generalizes previous randomized intraprocedural analyses, and also extends naturally to efficient interprocedural analyses. There is no such natural extension known for deterministic ...
Precise interprocedural analysis using random interpretation
POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We describe a unified framework for random interpretation that generalizes previous randomized intraprocedural analyses, and also extends naturally to efficient interprocedural analyses. There is no such natural extension known for deterministic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1995

415 pages

ISBN:0897916921

DOI:10.1145/199448

Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Peter Lee
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 January 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL95

Sponsor:

POPL95: 22nd ACM Symposium on Principles of Programming Languages

January 23 - 25, 1995

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

968
Total Citations
View Citations
7,954
Total Downloads

Downloads (Last 12 months)1,164
Downloads (Last 6 weeks)203

Reflects downloads up to 12 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balaji SCharumathi DAhmed MAppu A(2024)The influence of job satisfaction on retention of primary healthcare professionals in Tamil NaduInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02511:2(238-247)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.025
Umann KHorváth GPorkoláb Z(2024)Uncovering Hidden Dependencies: Constructing Intelligible Path Witnesses using Dataflow AnalysesActa Cybernetica10.14232/actacyb.29980526:3(713-747)Online publication date: 4-Mar-2024
https://doi.org/10.14232/actacyb.299805
Quiring BVan Horn D(2024)Deriving with Derivatives: Optimizing Incremental Fixpoints for Higher-Order Flow AnalysisProceedings of the ACM on Programming Languages10.1145/36746508:ICFP(728-755)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674650
Beyer DKettl MLemberger T(2024)Decomposing Software Verification using Distributed Summary SynthesisProceedings of the ACM on Software Engineering10.1145/36607661:FSE(1307-1329)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660766
Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Erhard JSchinabeck JSchwarz MSeidl HMonat RRubio-González C(2024)When to Stop Going Down the Rabbit Hole: Taming Context-Sensitivity on the FlyProceedings of the 13th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3652588.3663321(35-44)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652588.3663321
Sistla MChaudhuri SReps T(2024)CFLOBDDs: Context-Free-Language Ordered Binary Decision DiagramsACM Transactions on Programming Languages and Systems10.1145/365115746:2(1-82)Online publication date: 2-May-2024
https://dl.acm.org/doi/10.1145/3651157
Shi CLi HLu JLi LChristakis MPradel M(2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680346
Xu PLei YSui YXue J(2024)Iterative-Epoch Online Cycle Elimination for Context-Free Language ReachabilityProceedings of the ACM on Programming Languages10.1145/36498628:OOPSLA1(1437-1462)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649862
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

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents