CFA2: a Context-Free Approach to Control-Flow Analysis

Dimitrios Vardoulakis; Olin Shivers

doi:10.2168/LMCS-7(2:3)2011

Dimitrios Vardoulakis ; Olin Shivers - CFA2: a Context-Free Approach to Control-Flow Analysis

lmcs:684 - Logical Methods in Computer Science, May 1, 2011, Volume 7, Issue 2 - https://doi.org/10.2168/LMCS-7(2:3)2011

CFA2: a Context-Free Approach to Control-Flow AnalysisArticle

Authors: Dimitrios Vardoulakis ; Olin Shivers

In a functional language, the dominant control-flow mechanism is function call and return. Most higher-order flow analyses, including k-CFA, do not handle call and return well: they remember only a bounded number of pending calls because they approximate programs with control-flow graphs. Call/return mismatch introduces precision-degrading spurious control-flow paths and increases the analysis time. We describe CFA2, the first flow analysis with precise call/return matching in the presence of higher-order functions and tail calls. We formulate CFA2 as an abstract interpretation of programs in continuation-passing style and describe a sound and complete summarization algorithm for our abstract semantics. A preliminary evaluation shows that CFA2 gives more accurate data-flow information than 0CFA and 1CFA.

https://doi.org/10.2168/LMCS-7(2:3)2011

Source: arXiv.org:1102.3676

Volume: Volume 7, Issue 2

Published on: May 1, 2011

Imported on: June 11, 2010

Keywords: Computer Science - Programming Languages,F.3.2, D.3.4

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Companion to Analytic Philosophy 2; Code: PTDC/FER-FIL/28442/2017

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

21 Documents citing this article

Eli Pregerson;Shaheen Cullen-Baratloo;David Chen;Duy Lam;Max Szostak;et al., 2023 IEEE/ACM 11th International Conference on Formal Methods in Software Engineering (FormaliSE), Formalizing Path Explosion for Recursive Functions via Asymptotic Path Complexity, 25, pp. 76-85, 2023, Melbourne, Australia, 10.1109/formalise58978.2023.00016.

Benjamin Quiring;John Reppy;Olin Shivers, 2022, Analyzing binding extent in 3CPS, Proceedings of the ACM on Programming Languages, 6, ICFP, pp. 650-678, 10.1145/3547645, https://doi.org/10.1145/3547645.

Kimball Germane;Jay McCarthy, 2021, Newly-single and loving it: improving higher-order must-alias analysis with heap fragments, Proceedings of the ACM on Programming Languages, 5, ICFP, pp. 1-28, 10.1145/3473601, https://doi.org/10.1145/3473601.

Yuyan Bao;Guannan Wei;Oliver Bračevac;Yuxuan Jiang;Qiyang He;et al., 2021, Reachability types: tracking aliasing and separation in higher-order functional programs, Proceedings of the ACM on Programming Languages, 5, OOPSLA, pp. 1-32, 10.1145/3485516, https://doi.org/10.1145/3485516.

Zvonimir Pavlinovic;Yusen Su;Thomas Wies, 2021, Data flow refinement type inference, Proceedings of the ACM on Programming Languages, 5, POPL, pp. 1-31, 10.1145/3434300, https://doi.org/10.1145/3434300.

Kimball Germane;Michael D. Adams, Lecture notes in computer science, Liberate Abstract Garbage Collection from the Stack by Decomposing the Heap, pp. 197-223, 2020, 10.1007/978-3-030-44914-8_8, https://doi.org/10.1007/978-3-030-44914-8_8.

Guannan Wei;Yuxuan Chen;Tiark Rompf, 2019, Staged abstract interpreters: fast and modular whole-program analysis via meta-programming, Proceedings of the ACM on Programming Languages, 3, OOPSLA, pp. 1-32, 10.1145/3360552, https://doi.org/10.1145/3360552.

Kimball Germane;Jay McCarthy;Michael D. Adams;Matthew Might, Lecture notes in computer science, Demand Control-Flow Analysis, pp. 226-246, 2019, 10.1007/978-3-030-11245-5_11.

David Darais;Nicholas Labich;Phúc C. Nguyen;David Van Horn, 2017, Abstracting definitional interpreters (functional pearl), Proceedings of the ACM on Programming Languages, 1, ICFP, pp. 1-25, 10.1145/3110256, https://doi.org/10.1145/3110256.

Martin Lester;Luke Ong;Max Schäfer, 2016, Information flow analysis for a dynamically typed language with staged metaprogramming, Oxford University Research Archive (ORA) (University of Oxford), 24, 5, pp. 541-582, 10.3233/jcs-160557, https://ora.ox.ac.uk/objects/uuid:2f0851f4-64f3-4446-ab30-817e9db17ff3.

Martin Lester, 2015, Control Flow Analysis for SF Combinator Calculus, arXiv (Cornell University), 199, pp. 51-67, 10.4204/eptcs.199.4.

Dionna Glaze;David Van Horn, 2014, Abstracting abstract control, ACM SIGPLAN Notices, 50, 2, pp. 11-22, 10.1145/2775052.2661098.

Dionna Glaze;Nicholas Labich;Matthew Might;David Van Horn, arXiv (Cornell University), Optimizing abstract abstract machines, 2013, Boston Massachusetts USA, 10.1145/2500365.2500604, https://arxiv.org/abs/1211.3722.

Dionna Glaze;Nicholas Labich;Matthew Might;David Van Horn, 2013, Optimizing abstract abstract machines, arXiv (Cornell University), 48, 9, pp. 443-454, 10.1145/2544174.2500604, https://arxiv.org/abs/1211.3722.

Martin Lester;Luke Ong;Max Schaefer, Oxford University Research Archive (ORA) (University of Oxford), Information Flow Analysis for a Dynamically Typed Language with Staged Metaprogramming, pp. 209-223, 2013, New Orleans, LA, 10.1109/csf.2013.21, https://ora.ox.ac.uk/objects/uuid:2f0851f4-64f3-4446-ab30-817e9db17ff3.

Nikhil Swamy;Joel Weinberger;Cole Schlesinger;Juan Chen;Benjamin Livshits, 2013, Verifying higher-order programs with the dijkstra monad, CiteSeer X (The Pennsylvania State University), 48, 6, pp. 387-398, 10.1145/2499370.2491978, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.366.8229.

Nikhil Swamy;Joel Weinberger;Cole Schlesinger;Juan Chen;Benjamin Livshits, CiteSeer X (The Pennsylvania State University), Verifying higher-order programs with the dijkstra monad, pp. 387-398, 2013, Seattle Washington USA, 10.1145/2491956.2491978, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.366.8229.

DAVID VAN HORN;MATTHEW MIGHT, 2012, Systematic abstraction of abstract machines, Journal of Functional Programming, 22, 4-5, pp. 705-746, 10.1017/s0956796812000238, https://doi.org/10.1017/s0956796812000238.

Yoshihiro Tobita;Takeshi Tsukada;Naoki Kobayashi, Lecture notes in computer science, Exact Flow Analysis by Higher-Order Model Checking, pp. 275-289, 2012, 10.1007/978-3-642-29822-6_22.

Dimitrios Vardoulakis;Olin Shivers, 2011, Pushdown flow analysis of first-class control, ACM SIGPLAN Notices, 46, 9, pp. 69-80, 10.1145/2034574.2034785.

Dimitrios Vardoulakis;Olin Shivers, Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, Pushdown flow analysis of first-class control, 2011, Tokyo Japan, 10.1145/2034773.2034785.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1715 times.

This article's PDF has been downloaded 464 times.