Liberate Abstract Garbage Collection from the Stack by Decomposing the Heap

Kimball Germane and Michael D. Adams

Status: Published

Abstract

Abstract garbage collection and the use of pushdown systems each enhance the precision of control-flow analysis (CFA). However, their respective needs conflict: abstract garbage collection requires the stack but pushdown systems obscure it. Though several existing techniques address this conflict, none take full advantage of the underlying interplay. In this paper, we dissolve this conflict with a technique which exploits the precision of pushdown systems to decompose the heap across the continuation.This technique liberates abstract garbage collection from the stack, increasing its effectiveness and the compositionality of its host analysis. We generalize our approach to apply compositional treatment to abstract timestamps which induces the context abstraction of m-CFA, an abstraction more precise than k-CFA’s for many common programming patterns.

Citation

Kimball Germane and Michael D. Adams. Liberate abstract garbage collection from the stack by decomposing the heap. In Programming Languages and Systems - 29th European Symposium on Programming, ESOP 2020, volume 12075 of Lecture Notes in Computer Science, pages 197–223. Springer International Publishing, April 2020. ISBN 978-3-030-44914-8. doi: 10.1007/978-3-030-44914-8_8.

BibTeX Entry

@inproceedings{germane2020liberate,
  author = {Germane, Kimball and Adams, Michael D.},
  title = {Liberate Abstract Garbage Collection from the Stack by Decomposing the Heap},
  booktitle = {Programming Languages and Systems - 29th European Symposium on Programming, {ESOP} 2020},
  pages = {197--223},
  year = {2020},
  volume = {12075},
  series = {Lecture Notes in Computer Science},
  month = apr,
  publisher = {Springer International Publishing},
  isbn = {978-3-030-44914-8},
  doi = {10.1007/978-3-030-44914-8\_8},
}