skip to main content
article
Open access

Heap reference analysis using access graphs

Published: 01 November 2007 Publication History

Abstract

Despite significant progress in the theory and practice of program analysis, analyzing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. The spatial and temporal structure of stack and static data is well understood while that of heap data seems arbitrary and is unbounded. We devise bounded representations that summarize properties of the heap data. This summarization is based on the structure of the program that manipulates the heap. The resulting summary representations are certain kinds of graphs called access graphs. The boundedness of these representations and the monotonicity of the operations to manipulate them make it possible to compute them through data flow analysis.
An important application that benefits from heap reference analysis is garbage collection, where currently liveness is conservatively approximated by reachability from program variables. As a consequence, current garbage collectors leave a lot of garbage uncollected, a fact that has been confirmed by several empirical studies. We propose the first ever end-to-end static analysis to distinguish live objects from reachable objects. We use this information to make dead objects unreachable by modifying the program. This application is interesting because it requires discovering data flow information representing complex semantics. In particular, we formulate the following new analyses for heap data: liveness, availability, and anticipability and propose solution methods for them. Together, they cover various combinations of directions of analysis (i.e., forward and backward) and confluence of information (i.e. union and intersection). Our analysis can also be used for plugging memory leaks in C/C++ languages.

References

[1]
Agesen, O., Detlefs, D., and Moss, J. E. 1998. Garbage collection and local variable type-precision and liveness in Java virtual machines. In PLDI '98: Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation. ACM, New York, 269--279.
[2]
Aho, A. V., Sethi, R., and Ullman, J. D. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA.
[3]
Blanchet, B. 1999. Escape analysis for object-oriented languages: Application to Java. In OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, New York, 20--34.
[4]
Blanchet, B. 2003. Escape analysis for Java#8482;: Theory and practice. ACM Trans. Prog. Lang. Syst. 25, 6, 713--775.
[5]
Boehm, H. 2007. An artificial garbage collection benchmark. http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_bench.html, Accessed: September 2007.
[6]
Cannarozzi, D. J., Plezbert, M. P., and Cytron, R. K. 2000. Contaminated garbage collection. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. ACM, New York, 264--273.
[7]
Carlisle, M. C. 1996. Olden: Parallelizing programs with dynamic data structures on distributed-memory machines. Ph.D. dissertation, Princeton University, Princeton, NJ.
[8]
Chase, D. R., Wegman, M., and Zadeck, F. K. 1990. Analysis of pointers and structures. In PLDI '90: Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation. ACM, New York, 296--310.
[9]
Cheng, B.-C. and Hwu, W.-M. W. 2000. Modular interprocedural pointer analysis using access paths: Design, implementation, and evaluation. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. ACM, New York, 57--69.
[10]
Cherem, S. and Rugina, R. 2006. Compile-time deallocation of individual objects. In ISMM '06: Proceedings of the 2006 International Symposium on Memory Management. ACM, New York, 138--149.
[11]
Choi, J.-D., Burke, M., and Carini, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, 232--245.
[12]
Choi, J.-D., Gupta, M., Serrano, M., Sreedhar, V. C., and Midkiff, S. 1999. Escape analysis for Java. In OOPSLA '99: Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, New York, 1--19.
[13]
Gadbois, D., Fiterman, C., Chase, D., Shapiro, M., Nilsen, K., Haahr, P., Barnes, N., and Pirinen, P. P. 2007. The GC FAQ. http://www.iecc.com/gclist/GC-faq.html, Accessed: September 2007.
[14]
Guyer, S. Z., McKinley, K. S., and Frampton, D. 2006. Free-me: A static analysis for automatic individual object reclamation. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN Conference on Programming language design and implementation. ACM, New York, 364--375.
[15]
Hackett, B. and Rugina, R. 2005. Region-based shape analysis with tracked locations. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, 310--323.
[16]
Hallenberg, N., Elsman, M., and Tofte, M. 2002. Combining region inference and garbage collection. In PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation. ACM, New York, 141--152.
[17]
Hecht, M. S. 1977. Flow Analysis of Computer Programs. Elsevier Science Inc., New York.
[18]
Hind, M., Burke, M., Carini, P., and Choi, J.-D. 1999. Interprocedural pointer alias analysis. ACM Trans. Prog. Lang. Syst. 21, 4, 848--894.
[19]
Hirzel, M., Diwan, A., and Henkel, J. 2002a. On the usefulness of type and liveness accuracy for garbage collection and leak detection. ACM Trans. Prog. Lang. Syst. 24, 6, 593--624.
[20]
Hirzel, M., Henkel, J., Diwan, A., and Hind, M. 2002b. Understanding the connectivity of heap objects. In ISMM '02: Proceedings of the 3rd International Symposium on Memory Management. ACM, New York, 36--49.
[21]
Horwitz, S., Pfeiffer, P., and Reps, T. 1989. Dependence analysis for pointer variables. In PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation. ACM, New York, 28--40.
[22]
Iyer, P. C. 2005. PVS based proofs of safety properties of access graph operations. http://www.cse.iitb.ac.in/~uday/hraResources/AGSafety.html.
[23]
Jones, N. D. and Muchnick, S. S. 1979. Flow analysis and optimization of LISP-like structures. In POPL '79: Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. ACM, New York, 244--256.
[24]
Jones, N. D. and Muchnick, S. S. 1982. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In POPL '82: Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, New York, 66--74.
[25]
Karkare, A. 2005. XSB-Prolog based prototype implementation of heap reference analysis. http://www.cse.iitb.ac.in/~uday/hraResources/hraPrototpye.html.
[26]
Karkare, A., Khedker, U., and Sanyal, A. 2007a. Liveness of heap data for functional programs. In HAV 2007: Heap Analysis and Verification Workshop. 64--80. http://research.microsoft.com/~jjb/papers/HAV_proceedings.pdf.
[27]
Karkare, A., Sanyal, A., and Khedker, U. 2007b. Heap reference analysis for functional programs. http://arvix.org/abs/0710,1482.
[28]
Karkare, B. 2007. Complexity and efficiency issues in data flow analysis. Ph.D. dissertation, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay. (Submitted).
[29]
Khedker, U. P. 2002. Data flow analysis. In Compiler Design Handbook: Optimizations and Machine Code Generation, Y. N. Srikant and P. Shankar, Eds. CRC Press, Inc., Boca Raton, FL.
[30]
Khedker, U. P., Dhamdhere, D. M., and Mycroft, A. 2003. Bidirectional data flow analysis for type inferencing. Comput. Lang. Syst. Struct. 29, 1-2, 15--44.
[31]
Larus, J. R. and Hilfinger, P. N. 1988. Detecting conflicts between structure accesses. In PLDI '88: Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation. ACM, New York, 24--31.
[32]
McDowell, C. E. 1998. Reducing garbage in java. SIGPLAN Notices 33, 9, 84--86.
[33]
Reid, A., McCorquodale, J., Baker, J., Hsieh, W., and Zachary, J. 1999. The need for predictable garbage collection. In Proceedings of the ACM SIGPLAN Workshop on Compiler Support for System Software (WCSSS'99). ACM, New York.
[34]
Sagiv, M., Reps, T., and Wilhelm, R. 2002. Shape analysis and applications. In Compiler Design Handbook: Optimizations and Machine Code Generation, Y. N. Srikant and P. Shankar, Eds. CRC Press, Inc, Boca Raton, FL.
[35]
Shaham, R., Kolodner, E. K., and Sagiv, M. 2000. On effectiveness of GC in java. In ISMM '00: Proceedings of the 2nd International Symposium on Memory Management. ACM, New York, 12--17.
[36]
Shaham, R., Kolodner, E. K., and Sagiv, M. 2001. Heap profiling for space-efficient java. In PLDI '01: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation. ACM Press, New York, NY, USA, 104--113.
[37]
Shaham, R., Kolodner, E. K., and Sagiv, M. 2002. Estimating the impact of heap liveness information on space consumption in Java. In ISMM '02: Proceedings of the 3rd International Symposium on Memory Management. ACM Press, New York, 64--75.
[38]
Shaham, R., Yahav, E., Kolodner, E. K., and Sagiv, S. 2003. Establishing local temporal heap safety properties with applications to compile-time memory management. In SAS '03: Proceedings of the 10th International Symposium on Static Analysis. Springer-Verlag, London, UK, 483--503.
[39]
Tofte, M. and Birkedal, L. 1998. A region inference algorithm. ACM Trans. Prog. Lang. Syst. 20, 4, 724--767.
[40]
Vallée-Rai, R., Co, P., Gagnon, E., Hendren, L., Lam, P., and Sundaresan, V. 1999. Soot---A Java bytecode optimization framework. In CASCON '99: Proceedings of the 1999 Conference of the Centre for Advanced Studies on Collaborative Research. IBM, 13.
[41]
Wilson, R. P. and Lam, M. S. 1995. Efficient, context-sensitive pointer analysis for C programs. In PLDI '95: Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation. ACM, New York, 1--12.
[42]
Yong, S. H., Horwitz, S., and Reps, T. 1999. Pointer analysis for programs with structures and casting. In PLDI '99: Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation. ACM, New York, 91--103.

Cited By

View all
  • (2025)Modular unification of unilingual pointer analyses to multilingual FFI-based programsScience of Computer Programming10.1016/j.scico.2025.103278243(103278)Online publication date: Jul-2025
  • (2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
  • (2024)Boosting the Performance of Multi-Solver IFDS Algorithms with Flow-Sensitivity OptimizationsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444884(296-307)Online publication date: 2-Mar-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems
ACM Transactions on Programming Languages and Systems  Volume 30, Issue 1
November 2007
241 pages
ISSN:0164-0925
EISSN:1558-4593
DOI:10.1145/1290520
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2007
Published in TOPLAS Volume 30, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Aliasing
  2. data flow analysis
  3. heap references
  4. liveness

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)100
  • Downloads (Last 6 weeks)13
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Modular unification of unilingual pointer analyses to multilingual FFI-based programsScience of Computer Programming10.1016/j.scico.2025.103278243(103278)Online publication date: Jul-2025
  • (2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
  • (2024)Boosting the Performance of Multi-Solver IFDS Algorithms with Flow-Sensitivity OptimizationsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444884(296-307)Online publication date: 2-Mar-2024
  • (2023)Understanding the Impact of Fingerprinting in Android Hybrid Apps2023 IEEE/ACM 10th International Conference on Mobile Software Engineering and Systems (MOBILESoft)10.1109/MOBILSoft59058.2023.00011(28-39)Online publication date: May-2023
  • (2023)Demand-driven Information Flow Analysis of WebView in Android Hybrid Apps2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE59848.2023.00020(415-426)Online publication date: 9-Oct-2023
  • (2022)Inferring Region Types via an Abstract Notion of Environment TransformationProgramming Languages and Systems10.1007/978-3-031-21037-2_3(45-64)Online publication date: 5-Dec-2022
  • (2021)The Agile Success ModelACM Transactions on Software Engineering and Methodology10.1145/346493830:4(1-46)Online publication date: 23-Jul-2021
  • (2021)EagleACM Transactions on Software Engineering and Methodology10.1145/345049230:4(1-46)Online publication date: 23-Jul-2021
  • (2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
  • (2020)Bidirectionality in flow-sensitive demand-driven analysisScience of Computer Programming10.1016/j.scico.2020.102391(102391)Online publication date: Jan-2020
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media