Garbage-Free Abstract Interpretation Through Abstract Reference Counting

Authors Noah Van Es, Quentin Stiévenart, Coen De Roover



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2019.10.pdf
  • Filesize: 1.49 MB
  • 33 pages

Document Identifiers

Author Details

Noah Van Es
  • Software Languages Lab, Vrije Universiteit Brussel, Belgium
Quentin Stiévenart
  • Software Languages Lab, Vrije Universiteit Brussel, Belgium
Coen De Roover
  • Software Languages Lab, Vrije Universiteit Brussel, Belgium

Cite AsGet BibTex

Noah Van Es, Quentin Stiévenart, and Coen De Roover. Garbage-Free Abstract Interpretation Through Abstract Reference Counting. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 10:1-10:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ECOOP.2019.10

Abstract

Abstract garbage collection is the application of garbage collection to an abstract interpreter. Existing work has shown that abstract garbage collection can improve both the interpreter’s precision and performance. Current approaches rely on heuristics to decide when to apply abstract garbage collection. Garbage will build up and impact precision and performance when the collection is applied infrequently, while too frequent applications will bring about their own performance overhead. A balance between these tradeoffs is often difficult to strike. We propose a new approach to cope with the buildup of garbage in the results of an abstract interpreter. Our approach is able to eliminate all garbage, therefore obtaining the maximum precision and performance benefits of abstract garbage collection. At the same time, our approach does not require frequent heap traversals, and therefore adds little to the interpreters’s running time. The core of our approach uses reference counting to detect and eliminate garbage as soon as it arises. However, reference counting cannot deal with cycles, and we show that cycles are much more common in an abstract interpreter than in its concrete counterpart. To alleviate this problem, our approach detects cycles and employs reference counting at the level of strongly connected components. While this technique in general works for any system that uses reference counting, we argue that it works particularly well for an abstract interpreter. In fact, we show formally that for the continuation store, where most of the cycles occur, the cycle detection technique only requires O(1) amortized operations per continuation push. We present our approach formally, and provide a proof-of-concept implementation in the Scala-AM framework. We empirically show our approach achieves both the optimal precision and significantly better performance compared to existing approaches to abstract garbage collection.

Subject Classification

ACM Subject Classification
  • Theory of computation → Program analysis
Keywords
  • abstract interpretation
  • abstract garbage collection
  • reference counting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Leif Andersen and Matthew Might. Multi-core Parallelization of Abstracted Abstract Machines. In Proceedings of the 2013 Workshop on Scheme and Functional Programming, Washington, DC. Citeseer, 2013. Google Scholar
  2. David F. Bacon, Perry Cheng, and V. T. Rajan. A unified theory of garbage collection. In Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2004, October 24-28, 2004, Vancouver, BC, Canada, pages 50-68, 2004. URL: http://dx.doi.org/10.1145/1028976.1028982.
  3. David F. Bacon and V. T. Rajan. Concurrent Cycle Collection in Reference Counted Systems. In ECOOP 2001 - Object-Oriented Programming, 15th European Conference, Budapest, Hungary, June 18-22, 2001, Proceedings, pages 207-235, 2001. URL: http://dx.doi.org/10.1007/3-540-45337-7_12.
  4. Gogul Balakrishnan and Thomas W. Reps. Recency-Abstraction for Heap-Allocated Storage. In Static Analysis, 13th International Symposium, SAS 2006, Seoul, Korea, August 29-31, 2006, Proceedings, pages 221-239, 2006. URL: http://dx.doi.org/10.1007/11823230_15.
  5. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. A New Approach to Incremental Cycle Detection and Related Problems. ACM Trans. Algorithms, 12(2):14:1-14:22, 2016. URL: http://dx.doi.org/10.1145/2756553.
  6. Lars Bergstrom. Arity raising and control-flow analysis in Manticore. Master’s thesis, University of Chicago, 2009. Google Scholar
  7. Lars Bergstrom, Matthew Fluet, Matthew Le, John H. Reppy, and Nora Sandler. Practical and effective higher-order optimizations. In Proceedings of the 19th ACM SIGPLAN international conference on Functional programming, Gothenburg, Sweden, September 1-3, 2014, pages 81-93, 2014. URL: http://dx.doi.org/10.1145/2628136.2628153.
  8. Hans-Juergen Boehm. The space cost of lazy reference counting. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2004, Venice, Italy, January 14-16, 2004, pages 210-219, 2004. URL: http://dx.doi.org/10.1145/964001.964019.
  9. Thomas W. Christopher. Reference Count Garbage Collection. Softw., Pract. Exper., 14(6):503-507, 1984. URL: http://dx.doi.org/10.1002/spe.4380140602.
  10. George E. Collins. A method for overlapping and erasure of lists. Commun. ACM, 3(12):655-657, 1960. URL: http://dx.doi.org/10.1145/367487.367501.
  11. Patrick Cousot. The Verification Grand Challenge and Abstract Interpretation. In Verified Software: Theories, Tools, Experiments, First IFIP TC 2/WG 2.3 Conference, VSTTE 2005, Zurich, Switzerland, October 10-13, 2005, Revised Selected Papers and Discussions, pages 189-201, 2005. URL: http://dx.doi.org/10.1007/978-3-540-69149-5_21.
  12. Patrick Cousot and Radhia Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, pages 238-252, 1977. URL: http://dx.doi.org/10.1145/512950.512973.
  13. Patrick Cousot and Radhia Cousot. Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation. In Programming Language Implementation and Logic Programming, 4th International Symposium, PLILP'92, Leuven, Belgium, August 26-28, 1992, Proceedings, pages 269-295, 1992. URL: http://dx.doi.org/10.1007/3-540-55844-6_142.
  14. David Darais, Nicholas Labich, Phuc C. Nguyen, and David Van Horn. Abstracting definitional interpreters (functional pearl). PACMPL, 1(ICFP):12:1-12:25, 2017. URL: http://dx.doi.org/10.1145/3110256.
  15. L. Peter Deutsch and Daniel G. Bobrow. An Efficient, Incremental, Automatic Garbage Collector. Commun. ACM, 19(9):522-526, 1976. URL: http://dx.doi.org/10.1145/360336.360345.
  16. Christopher Earl, Ilya Sergey, Matthew Might, and David Van Horn. Introspective pushdown analysis of higher-order programs. In ACM SIGPLAN International Conference on Functional Programming, ICFP'12, Copenhagen, Denmark, September 9-15, 2012, pages 177-188, 2012. URL: http://dx.doi.org/10.1145/2364527.2364576.
  17. Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. The Essence of Compiling with Continuations. In Proceedings of the ACM SIGPLAN'93 Conference on Programming Language Design and Implementation (PLDI), Albuquerque, New Mexico, USA, June 23-25, 1993, pages 237-247, 1993. URL: http://dx.doi.org/10.1145/155090.155113.
  18. Richard P. Gabriel. Performance and evaluation of LISP systems, volume 263. MIT press Cambridge, Mass., 1985. Google Scholar
  19. Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems. ACM Computing Surveys (CSUR), 23(3):319-344, 1991. Google Scholar
  20. Thomas Gilray, Michael D. Adams, and Matthew Might. 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, Nara, Japan, September 18-22, 2016, pages 407-420, 2016. URL: http://dx.doi.org/10.1145/2951913.2951936.
  21. Thomas Gilray, Steven Lyde, Michael D. Adams, Matthew Might, and David Van Horn. Pushdown control-flow analysis for free. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, pages 691-704, 2016. URL: http://dx.doi.org/10.1145/2837614.2837631.
  22. Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan. Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. ACM Trans. Algorithms, 8(1):3:1-3:33, 2012. URL: http://dx.doi.org/10.1145/2071379.2071382.
  23. David Van Horn and Matthew Might. Abstracting abstract machines. In Proceeding of the 15th ACM SIGPLAN international conference on Functional programming, ICFP 2010, Baltimore, Maryland, USA, September 27-29, 2010, pages 51-62, 2010. URL: http://dx.doi.org/10.1145/1863543.1863553.
  24. Paul Hudak. A semantic model of reference counting and its abstraction (detailed summary). In Proceedings of the 1986 ACM conference on LISP and functional programming, pages 351-363. ACM, 1986. Google Scholar
  25. Paul Hudak and Adrienne G. Bloss. The Aggregate Update Problem in Functional Programming Systems. In Conference Record of the Twelfth Annual ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, USA, January 1985, pages 300-314, 1985. URL: http://dx.doi.org/10.1145/318593.318660.
  26. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type Analysis for JavaScript. In Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings, pages 238-255, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03237-0_17.
  27. J. Ian Johnson, Nicholas Labich, Matthew Might, and David Van Horn. Optimizing abstract abstract machines. In ACM SIGPLAN International Conference on Functional Programming, ICFP'13, Boston, MA, USA - September 25 - 27, 2013, pages 443-454, 2013. URL: http://dx.doi.org/10.1145/2500365.2500604.
  28. J. Ian Johnson, Ilya Sergey, Christopher Earl, Matthew Might, and David Van Horn. Pushdown flow analysis with abstract garbage collection. J. Funct. Program., 24(2-3):218-283, 2014. Google Scholar
  29. James Ian Johnson. Automating abstract interpretation of abstract machines. PhD thesis, Northeastern University, 2015. Google Scholar
  30. James Ian Johnson and David Van Horn. Abstracting abstract control. In DLS'14, Proceedings of the 10th ACM Symposium on Dynamic Languages, part of SLASH 2014, Portland, OR, USA, October 20-24, 2014, pages 11-22, 2014. URL: http://dx.doi.org/10.1145/2661088.2661098.
  31. Richard Jones, Antony Hosking, and Eliot Moss. The garbage collection handbook: the art of automatic memory management. Chapman and Hall/CRC, 2016. Google Scholar
  32. Simon B. Jones and Daniel Le Métayer. Compile-time garbage collection by sharing analysis. In Proceedings of the fourth international conference on Functional programming languages and computer architecture, pages 54-74. ACM, 1989. Google Scholar
  33. Henry G. Baker Jr. List Processing in Real Time on a Serial Computer. Commun. ACM, 21(4):280-294, 1978. URL: http://dx.doi.org/10.1145/359460.359470.
  34. Eric Jean Knauel. A flow analysis framework for realistic scheme programs. PhD thesis, University of Tübingen, Germany, 2008. URL: http://tobias-lib.ub.uni-tuebingen.de/volltexte/2008/3363/.
  35. Yossi Levanoni and Erez Petrank. An on-the-fly reference-counting garbage collector for java. ACM Trans. Program. Lang. Syst., 28(1):1-69, 2006. URL: http://dx.doi.org/10.1145/1111596.1111597.
  36. Henry Lieberman and Carl Hewitt. A Real-Time Garbage Collector Based on the Lifetimes of Objects. Commun. ACM, 26(6):419-429, 1983. URL: http://dx.doi.org/10.1145/358141.358147.
  37. Alejandro D. Martínez, Rosita Wachenchauzer, and Rafael D. Lins. Cyclic reference counting with local mark-scan. Information Processing Letters, 34(1):31-35, 1990. Google Scholar
  38. Matthew Might. Environment Analysis of Higher-Order Languages. PhD thesis, Georgia Institute of Technology, Atlanta, GA, USA, 2007. URL: http://hdl.handle.net/1853/16289.
  39. Matthew Might. Logic-flow analysis of higher-order programs. In Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2007, Nice, France, January 17-19, 2007, pages 185-198, 2007. URL: http://dx.doi.org/10.1145/1190216.1190247.
  40. Matthew Might. Abstract Interpreters for Free. In Static Analysis - 17th International Symposium, SAS 2010, Perpignan, France, September 14-16, 2010. Proceedings, pages 407-421, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15769-1_25.
  41. Matthew Might, Benjamin Chambers, and Olin Shivers. Model Checking Via GammaCFA. In Verification, Model Checking, and Abstract Interpretation, 8th International Conference, VMCAI 2007, Nice, France, January 14-16, 2007, Proceedings, pages 59-73, 2007. URL: http://dx.doi.org/10.1007/978-3-540-69738-1_4.
  42. Matthew Might and Olin Shivers. Improving flow analyses via ΓCFA: Abstract garbage collection and counting. In Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming, ICFP 2006, Portland, Oregon, USA, September 16-21, 2006, pages 13-25, 2006. URL: http://dx.doi.org/10.1145/1159803.1159807.
  43. Matthew Might and Olin Shivers. Exploiting reachability and cardinality in higher-order flow analysis. J. Funct. Program., 18(5-6):821-864, 2008. URL: http://dx.doi.org/10.1017/S0956796808006941.
  44. Matthew Might, Yannis Smaragdakis, and David Van Horn. Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis. In Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2010, Toronto, Ontario, Canada, June 5-10, 2010, pages 305-315, 2010. URL: http://dx.doi.org/10.1145/1806596.1806631.
  45. Alan Mycroft. Abstract interpretation and optimising transformations for applicative programs. PhD thesis, University of Edinburgh, UK, 1982. URL: http://hdl.handle.net/1842/6602.
  46. Jens Nicolay, Carlos Noguera, Coen De Roover, and Wolfgang De Meuter. Detecting function purity in JavaScript. In 15th IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM 2015, Bremen, Germany, September 27-28, 2015, pages 101-110, 2015. URL: http://dx.doi.org/10.1109/SCAM.2015.7335406.
  47. Hakjoo Oh and Kwangkeun Yi. Access-based abstract memory localization in static analysis. Sci. Comput. Program., 78(9):1701-1727, 2013. URL: http://dx.doi.org/10.1016/j.scico.2013.04.002.
  48. Noam Rinetzky, Jörg Bauer, Thomas W. Reps, Shmuel Sagiv, and Reinhard Wilhelm. A semantics for procedure local heaps and its abstractions. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, January 12-14, 2005, pages 296-309, 2005. URL: http://dx.doi.org/10.1145/1040305.1040330.
  49. Ilya Sergey, Dominique Devriese, Matthew Might, Jan Midtgaard, David Darais, Dave Clarke, and Frank Piessens. Monadic abstract interpreters. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, Seattle, WA, USA, June 16-19, 2013, pages 399-410, 2013. URL: http://dx.doi.org/10.1145/2491956.2491979.
  50. Rifat Shahriyar, Stephen M. Blackburn, and Daniel Frampton. Down for the count? Getting reference counting back in the ring. In International Symposium on Memory Management, ISMM '12, Beijing, China, June 15-16, 2012, pages 73-84, 2012. URL: http://dx.doi.org/10.1145/2258996.2259008.
  51. Olin Shivers. Control-Flow Analysis in Scheme. In Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, USA, June 22-24, 1988, pages 164-174, 1988. URL: http://dx.doi.org/10.1145/53990.54007.
  52. Ragnar Lárus Sigur\dhsson. Practical performance of incremental topological sorting and cycle detection algorithms. Master’s thesis, Chalmers University of Technology, 2016. Google Scholar
  53. Quentin Stiévenart, Jens Nicolay, Wolfgang De Meuter, and Coen De Roover. Building a modular static analysis framework in Scala (tool paper). In Proceedings of the 7th ACM SIGPLAN Symposium on Scala, SCALA@SPLASH 2016, Amsterdam, Netherlands, October 30 - November 4, 2016, pages 105-109, 2016. URL: http://dx.doi.org/10.1145/2998392.3001579.
  54. Quentin Stiévenart, Maarten Vandercammen, Wolfgang De Meuter, and Coen De Roover. Scala-AM: A Modular Static Analysis Framework. In 16th IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM 2016, Raleigh, NC, USA, October 2-3, 2016, pages 85-90, 2016. URL: http://dx.doi.org/10.1109/SCAM.2016.14.
  55. Robert Endre Tarjan. Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2):306-318, 1985. Google Scholar
  56. Joseph Weizenbaum. Recovery of reentrant list structures in SLIP. Commun. ACM, 12(7):370-372, 1969. URL: http://dx.doi.org/10.1145/363156.363159.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail