Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-24T22:36:13.445Z Has data issue: false hasContentIssue false
  • English
  • Français

Abstract allocation as a unified approach to polyvariance in control-flow analyses

Published online by Cambridge University Press:  01 August 2018

THOMAS GILRAY ,
MICHAEL D. ADAMS  and
MATTHEW MIGHT
THOMAS GILRAY
Affiliation:
University of Maryland, College Park (e-mail: [email protected])
MICHAEL D. ADAMS
Affiliation:
University of Utah (e-mail: [email protected])
MATTHEW MIGHT
Affiliation:
University of Alabama, Birmingham (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In higher order settings, control-flow analysis aims to model the propagation of both data and control by finitely approximating program behaviors across all possible executions. The polyvariance of an analysis describes the number of distinct abstract representations, or variants, for each syntactic entity (e.g., functions, variables, or intermediate expressions). Monovariance, one of the most basic forms of polyvariance, maintains only a single abstract representation for each variable or expression. Other polyvariant strategies allow a greater number of distinct abstractions and increase analysis complexity with the aim of increasing analysis precision. For example, k-call sensitivity distinguishes flows by the most recent k call sites, k-object sensitivity by a history of allocation points, and argument sensitivity by a tuple of dynamic argument types. From this perspective, even a concrete operational semantics may be thought of as an unboundedly polyvariant analysis. In this paper, we develop a unified methodology that fully captures this design space. It is easily tunable and guarantees soundness regardless of how tuned. We accomplish this by extending the method of abstracting abstract machines, a systematic approach to abstract interpretation of operational abstract-machine semantics. Our approach permits arbitrary instrumentation of the underlying analysis and arbitrary tuning of an abstract-allocation function. We show that the design space of abstract allocators both unifies and generalizes existing notions of polyvariance. Simple changes to the behavior of this function recapitulate classic styles of analysis and yield novel combinations and variants.

Type
Research Article
Information
Journal of Functional Programming , Volume 28 , 2018 , e18
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

*This material is partially based on research sponsored by DARPA under agreements number AFRL FA8750-15-2-0092 and FA8750-12-2-0106, by NSF under CAREER grant 1350344, and by the Victor Basili fellowship at the University of Maryland, College Park.

References

Agesen, O. (1995) The Cartesian Product Algorithm. Lecture Notes in Computer Science, vol. 952. Berlin, Heidelberg: Springer, pp. 2–26.Google Scholar
Amtoft, T. & Turbak, F. (2000) Faithful Translations Between Polyvariant Flows and Polymorphic Types. Lecture Notes in Computer Science, vol. 1782. Berlin, Heidelberg: Springer, pp. 26–40.Google Scholar
Appel, A. W. (2007) Compiling with Continuations. Cambridge University Press.Google Scholar
Banerjee, A. (1997) A modular, polyvariant and type-based closure analysis. In Proceedings of the 2nd ACM SIGPLAN International Conference on Functional Programming, ICFP '97. New York, NY, USA: ACM, pp. 1–10.Google Scholar
Besson, F. (2009) CPA beats ∞-CFA. In Proceedings of the 11th International Workshop on Formal Techniques for Java-like Programs, FTfJP '09. New York, NY, USA: ACM, pp. 7:1–7:6.Google Scholar
Bravenboer, M. & Smaragdakis, Y. (2009) Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '09. New York, NY, USA: ACM, pp. 243–262.Google Scholar
Cousot, P. (1997) Types as abstract interpretations. In Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '97. New York, NY, USA: ACM, pp. 316–331.Google Scholar
Cousot, P. & Cousot, R. (1976) Static determination of dynamic properties of programs. In Proceedings of the 2nd International Symposium on Programming. Paris, France, pp. 106–130.Google Scholar
Cousot, P. & Cousot, R. (1977) Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '77. New York, NY, USA: ACM, pp. 238–252.Google Scholar
Cousot, P. & Cousot, R. (1979) Systematic design of program analysis frameworks. In Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '79. New York, NY, USA: ACM, pp. 269–282.Google Scholar
Earl, C., Sergey, I., Might, M. & Van Horn, D. (2012 September) Introspective pushdown analysis of higher-order programs. In International Conference on Functional Programming, pp. 177–188.Google Scholar
Flanagan, C., Sabry, A., Duba, B. F. & Felleisen, M. (1993) The essence of compiling with continuations. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, PLDI '93. New York, NY, USA: ACM, pp. 237–247.Google Scholar
Gilray, T. & Might, M. (2013 November) A unified approach to polyvariance in abstract interpretations. In Proceedings of the Workshop on Scheme and Functional Programming, Scheme '13.Google Scholar
Gilray, T. & Might, M. (2014) A Survey of Polyvariance in Abstract Interpretations. Theoretical Computer Science and General Issues, vol. 8322. Berlin, Heidelberg: Springer, pp. 134–148.Google Scholar
Gilray, T., Adams, M. D. & Might, M. (2016a) Allocation characterizes polyvariance: A unified methodology for polyvariant control-flow analysis. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, ICFP 2016. New York, NY, USA: ACM, pp. 407–420.Google Scholar
Gilray, T., Lyde, S., Adams, M. D., Might, M. & Van Horn, D. (2016b) Pushdown control-flow analysis for free. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '16. New York, NY, USA: ACM, pp. 691–704.Google Scholar
Harrison, W. L. (1989) The interprocedural analysis and automatic parallelization of Scheme programs. Lisp Symb. Comput. 2 (3–4), 179–396.Google Scholar
Holdermans, S. & Hage, J. (2010) Polyvariant flow analysis with higher-ranked polymorphic types and higher-order effect operators. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP '10. New York, NY, USA: ACM, pp. 63–74.Google Scholar
Jagannathan, S. & Weeks, S. (1995) A unified treatment of flow analysis in higher-order languages. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '95. New York, NY, USA: ACM, pp. 393–407.Google Scholar
Jagannathan, S., Weeks, S. & Wright, A. (1997) Type-Directed Flow Analysis for Typed Intermediate Languages. Lecture Notes in Computer Science, vol. 1302. Berlin, Heidelberg: Springer, pp. 232–249.Google Scholar
Jenkins, M., Andersen, L., Gilray, T. & Might, M. (2014 November) Concrete and abstract interpretation: Better together. In Workshop on Scheme and Functional Programming, Scheme '14.Google Scholar
Johnson, J. I., Labich, N., Might, M. & Van Horn, D. (2013) Optimizing abstract machines. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, ICFP '13. New York, NY, USA: ACM, pp. 443–454.Google Scholar
Jones, N. D. & Muchnick, S. S. (1982) A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '82. New York, NY, USA: ACM, pp. 66–74.Google Scholar
Kahn, G. (1987) Natural Semantics. Lecture Notes in Computer Science, vol. 247. Berlin, Heidelberg: Springer, pp. 22–39.Google Scholar
Kastrinis, G. & Smaragdakis, Y. (2013) Hybrid context-sensitivity for points-to analysis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13. New York, NY, USA: ACM, pp. 423–434.Google Scholar
Kennedy, A. (2007) Compiling with continuations, continued. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP '07. New York, NY, USA: ACM, pp. 177–190.Google Scholar
Koot, R. & Hage, J. (2015) Type-based exception analysis for non-strict higher-order functional languages with imprecise exception semantics. In Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation, PEPM '15. New York, NY, USA: ACM, pp. 127–138.Google Scholar
Lhoták, O. (2006) Program Analysis Using Binary Decision Diagrams. Ph.D. thesis, McGill University.Google Scholar
Lhoták, O. & Hendren, L. (2006) Context-Sensitive Points-to Analysis: Is it Worth It? Theoretical Computer Science and General Issues, vol. 3923. Berlin, Heidelberg: Springer, pp. 47–64.Google Scholar
Lhoták, O. & Hendren, L. (2008) Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation. ACM Trans. Softw. Eng. Methodol. 18 (1), 3:1–3:53.Google Scholar
Liang, D., Pennings, M. & Harrold, M. J. (2005) Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs. In Proceedings of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE '05, vol. 31, no. 1. New York, NY, USA: ACM, pp. 6–12.Google Scholar
Liang, S. & Might, M. (2012) Hash-flow taint analysis of higher-order programs. In Proceedings of the 7th Workshop on Programming Languages and Analysis for Security, PLAS '12. New York, NY, USA: ACM, pp. 8:1–8:12.Google Scholar
Maurer, L., Downen, P., Ariola, Z. M. & Peyton Jones, S. (2017) Compiling without continuations. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017. New York, NY, USA: ACM, pp. 482–494.Google Scholar
Midtgaard, J. (2012) Control-flow analysis of functional programs. ACM Comput. Surv. 44 (3), 10:1–10:33.Google Scholar
Midtgaard, J. & Horn, D. V. (2009 May) Subcubic Control Flow Analysis Algorithms. Computer Science Research Report 125. Roskilde, Denmark: Roskilde University.Google Scholar
Might, M. (2010) Abstract Interpreters for Free. Programming and Software Engineering, vol. 6337. Berlin, Heidelberg: Springer, pp. 407–421.Google Scholar
Might, M. & Manolios, P. (2009) A Posteriori Soundness for Non-Deterministic Abstract Interpretations. Theoretical Computer Science and General Issues, vol. 5403. Berlin, Heidelberg: Springer, pp. 260–274.Google Scholar
Might, M. & Shivers, O. (2006) Improving flow analyses via ΓCFA: Abstract garbage collection and counting. In Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming, ICFP '06. New York, NY, USA: ACM, pp. 13–25.Google Scholar
Might, M., Smaragdakis, Y. & Van Horn, D. (2010) Resolving and exploiting the k-CFA paradox: Illuminating functional versus object-oriented program analysis. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '10. New York, NY, USA: ACM, pp. 305–315.Google Scholar
Milanova, A., Rountev, A. & Ryder, B. G. (2005) Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methdol. 14 (1), 1–41.Google Scholar
Naik, M., Aiken, A. & Whaley, J. (2006) Effective static race detection for Java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '06. New York, NY, USA: ACM, pp. 308–319.Google Scholar
Oxhøj, N., Palsberg, J. & Schwartzbach, M. I. (1992) Making Type Inference Practical. Lecture Notes in Computer Science, vol. 615. Berlin, Heidelberg: Springer, pp. 329–349.Google Scholar
Palsberg, J. & Pavlopoulou, C. (2001) From polyvariant flow information to intersection and union types. J. Funct. Program. 11 (3), 263–317.Google Scholar
Plotkin, G. D. (1981) A Structural Approach to Operational Semantics. Tech. rept. DAIMI Arhus, Denmark.Google Scholar
Racket Community. (2015) Racket Programming Language. Accessed December 26, 2017. Available at: http://racket-lang.org/.Google Scholar
Sharir, M. & Pnueli, A. (1981) Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and S pplications, Muchnick, S. S. & Jones, N. D. (eds), Prentice Hall International, pp. 189–234. Available at: http://www.cmi.ac.in/~madhavan/courses/program-analysis-2011/papers/sharir-pnueli-interproc-analysis-1981.pdf.Google Scholar
Shivers, O. (1991 May) Control-Flow Analysis of Higher-Order Languages. Ph.D. thesis, Pittsburgh, PA: Carnegie-Mellon University.Google Scholar
Smaragdakis, Y., Bravenboer, M. & Lhoták, O. (2011) Pick your contexts well: Understanding object-sensitivity. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '11. New York, NY, USA: ACM, pp. 17–30.Google Scholar
Tarski, A. (1955) A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5 (2), 285–309.Google Scholar
Van Horn, D. & Mairson, H. G. (2008) Deciding kCFA is complete for EXPTIME. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming, ICFP '08. New York, NY, USA: ACM, pp. 275–282.Google Scholar
Van Horn, D. & Might, M. (2010) Abstracting abstract machines. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP '10. New York, NY, USA: ACM, pp. 51–62.Google Scholar
Vardoulakis, D. & Shivers, O. (2010) CFA2: A context-free approach to control-flow analysis. In Proceedings of the European Symposium on Programming, vol. 6012, LNCS, pp. 570–589.Google Scholar
Verstoep, H. & Hage, J. (2015) Polyvariant cardinality analysis for non-strict higher-order functional languages: Brief announcement. In Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation, PEPM '15. New York, NY, USA: ACM, pp. 139–142.Google Scholar
Wright, A. K. & Jagannathan, S. (1998) Polymorphic splitting: An effective polyvariant flow analysis. ACM Trans. Program. Lang. Syst. 20 (1), 166–207.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.