article

Free access

Linear-time subtransitive control flow analysis

Authors:

David McAllesterAuthors Info & Claims

ACM SIGPLAN Notices, Volume 32, Issue 5

Pages 261 - 272

https://doi.org/10.1145/258916.258939

Published: 01 May 1997 Publication History

Abstract

We present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA) algorithm. Our algorithm can be used to list all functions calls from all call sites in (optimal) quadratic time. More importantly, it can be used to give linear-time algorithms for CFA-consuming applications such as:• effects analysis: find the side-effecting expressions in a program.• k-limited CFA: for each call-site, list the functions if there are only a few of them (≤ k) and otherwise output "many".• called-once analysis: identify all functions called from only one call-site.

References

[1]

A. Aho, J. Hopcroft, and J. Ullmann, ~Time and tape complexity of pushdown automaton languages", Information and Control, vol. 13, no. 3, pp. 186-206, 1968.

[2]

A. Bondorf and J. Jorgensen, "Efficient analysis for realistic off-line partial evaluation', Journal of Functional Programming, Vol. 3, No. 3, July 1993.

[3]

S. Debray and T. Proebsting, "Interprocedural Control Flow Analysis of First Order Programs with Tail Call Optimization", draft, May 1996. (http://~ ~. ~. ~i~on ~. ~du / p~opl~/ debray/papers/cfa, ps)

Digital Library

[4]

N. Heintze, 'Set-Based Analysis of ML Programs", A CM Conference on Lisp and Functional Programming, pp 306-317, 1994.

Digital Library

[5]

N. Heintze, "Control-Flow Analysis and Type Systems~, Static Analysis Symposium, 1995, pp 189-206.

Digital Library

[6]

N. Heintze and D. McAllester, "On the Cubic-Bottleneck of Subtyping and Flow Analysis~ IEEE Symposium on Logic in Computer Science, 1997, to appear.

Digital Library

[7]

F. Henglein, "Type Inference with Polymorphic Recursion', Transactions on Program. rainy Languages and Systems, Vol. 15, No. 2, pp. 253-289, 1993.

Digital Library

[8]

N. Jones, "Flow Analysis of Lambda Expressions', Sffmp. on Functional Languages and Computer Architecture, pp. 66-74, 1981.

[9]

N. Jones, "Flow Analysis of Lazy Higher- Order Functional Programs~, in Abstract Interpretation of Declarative Languages, S. Abramsky and C. Hankin (Eds.), Ellis Hotwood, 1987.

[10]

D. McAllester, "Inferring Recursive Data Types", draft manuscript, July 1996.

[11]

C. Mossin, "Control Flow Analysis for Higher-Order Typed Programs", draft Ph.D. thesis, DIKU, University of Copenhagen, December, 1996.

[12]

E. Melski and T. Reps, "Interconvertibility of Set Constraints and Context-Free Language Reachability~, PEPM'97, to appear.

Digital Library

[13]

R. Milner, M. Tofte and R. Harper, "The Definition of Standard ML', MIT Press, 1990.

Digital Library

[14]

R. Neat, "The computational complexity of taxonomic inference", unpublished manuscript, 18 pages, 1989, (ftp://fro. cs. u toronto, ca / pub / raxlford / taxc.ps.Z).

[15]

J. Palsberg and P. O'Keefe, "A Type System Equivalent to Flow Analysis~, POPL- 95, pp. 367-378, 1995.

Digital Library

[16]

J. Palsbetg and M. Schwaxtzbach, "S~ety Analysis versus Type inference' Information and Computation, Vol. 118, No. 1, pp. 128-141, April 1995.

Digital Library

[17]

O. Shivers, "Control Flow Analysis in Scheme", Proc. 1988 A GM Conf. on Programming Language Design and Implementation, Atlanta, pp. 164-174, June 1988.

Digital Library

Cited By

Sin'Ya RAsada KKobayashi NTsukada T(2017)Almost Every Simply Typed $$\lambda $$-Term Has a Long $$\beta $$-Reduction SequenceProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_4(53-68)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_4
Terao TKobayashi N(2014)A ZDD-Based Efficient Higher-Order Model Checking AlgorithmProgramming Languages and Systems10.1007/978-3-319-12736-1_19(354-371)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12736-1_19
Sridharan MChandra SDolby JFink SYahav E(2013)Alias analysis for object-oriented programsAliasing in Object-Oriented Programming10.5555/2554511.2554523(196-232)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2554511.2554523
Show More Cited By

Index Terms

Linear-time subtransitive control flow analysis
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical software
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Linear-time subtransitive control flow analysis
PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

We present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA) algorithm. Our algorithm can be used to list all ...
Pushdown control-flow analysis for free
POPL '16

Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...
Pushdown control-flow analysis for free
POPL '16: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 32, Issue 5

May 1997

365 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/258916

Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Marina Chen
Boston Univ., Boston, MA
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Issue’s Table of Contents

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation
May 1997
365 pages
ISBN:0897919076
DOI:10.1145/258915
Chairmen:
Marina Chen
Boston Univ., Boston, MA
,
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Copyright © 1997 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1997

Published in SIGPLAN Volume 32, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
631
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)13

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sin'Ya RAsada KKobayashi NTsukada T(2017)Almost Every Simply Typed $$\lambda $$-Term Has a Long $$\beta $$-Reduction SequenceProceedings of the 20th International Conference on Foundations of Software Science and Computation Structures - Volume 1020310.1007/978-3-662-54458-7_4(53-68)Online publication date: 22-Apr-2017
https://dl.acm.org/doi/10.1007/978-3-662-54458-7_4
Terao TKobayashi N(2014)A ZDD-Based Efficient Higher-Order Model Checking AlgorithmProgramming Languages and Systems10.1007/978-3-319-12736-1_19(354-371)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12736-1_19
Sridharan MChandra SDolby JFink SYahav E(2013)Alias analysis for object-oriented programsAliasing in Object-Oriented Programming10.5555/2554511.2554523(196-232)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2554511.2554523
Sridharan MChandra SDolby JFink SYahav E(2013)Alias Analysis for Object-Oriented ProgramsAliasing in Object-Oriented Programming. Types, Analysis and Verification10.1007/978-3-642-36946-9_8(196-232)Online publication date: 2013
https://doi.org/10.1007/978-3-642-36946-9_8
Tobita YTsukada TKobayashi N(2012)Exact flow analysis by higher-order model checkingProceedings of the 11th international conference on Functional and Logic Programming10.1007/978-3-642-29822-6_22(275-289)Online publication date: 23-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29822-6_22
Sridharan MFink S(2009)The Complexity of Andersen's Analysis in PracticeProceedings of the 16th International Symposium on Static Analysis10.1007/978-3-642-03237-0_15(205-221)Online publication date: 12-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03237-0_15
FÄHNDRICH MREHOF J(2008)Type-based flow analysis and context-free language reachabilityMathematical Structures in Computer Science10.1017/S096012950800696818:5(823-894)Online publication date: 1-Oct-2008
https://doi.org/10.1017/S0960129508006968
Mossin C(2003)Exact flow analysisMathematical Structures in Computer Science10.1017/S096012950200385713:1(125-156)Online publication date: 1-Feb-2003
https://dl.acm.org/doi/10.1017/S0960129502003857
Grove DChambers C(2001)A framework for call graph construction algorithmsACM Transactions on Programming Languages and Systems10.1145/506315.50631623:6(685-746)Online publication date: 1-Nov-2001
https://dl.acm.org/doi/10.1145/506315.506316
Fähndrich MRehof JDas M(2000)Scalable context-sensitive flow analysis using instantiation constraintsACM SIGPLAN Notices10.1145/358438.34933235:5(253-263)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1145/358438.349332
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 Issue’s Table of Contents