Abstract
This paper presents a heap analysis algorithm that characterizes how programs access regions within recursive data structures, such as sublists within lists or subtrees within trees. The analysis precisely computes cyclicity, reachability, and heap access region information for programs with destructive updates.
The algorithm uses a shape graph abstraction of the heap that identifies connected, single-entry heap regions, whose entries are directly accessible from the stack. The edges of the shape graphs encode reachability information. This yields a more compact heap representation compared to the existing abstractions, making the analysis more efficient. Furthermore, the algorithm expresses heap access information using labels on the nodes of the shape graphs. The labels characterize the concrete locations that abstract nodes represent and make it possible to compare the sets of concrete locations modeled by nodes in different shape graphs. The labels allow the analysis to express the heap access information with respect to the nodes at a particular program point, for instance at the beginning of the current procedure. Our analysis is able to precisely and efficiently compute heap access region information for complex heap manipulations such as a recursive quicksort program that sorts a list in-place, using destructive updates.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Chase, M. Wegman, and F. Zadek. Analysis of pointers and structures. In Proceedings of the SIGPLAN’90 Conference on Program Language Design and Implementation, White Plains, NY, June 1990.
A. Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In Proceedings of the SIGPLAN’94 Conference on Program Language Design and Implementation, Orlando, FL, June 1994.
N. Dor, M. Rodeh, and M. Sagiv. Checking cleanness in linked lists. In Proceedings of the 8th International Static Analysis Symposium, Santa Barbara, CA, July 2000.
M. Emami, R. Ghiya, and L. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the SIGPLAN’94 Conference on Program Language Design and Implementation, Orlando, FL, June 1994.
R. Ghiya and L. Hendren. Connection analysis: A practical interprocedural heap analysis for C. In Proceedings of the Eighth Workshop on Languages and Compilers for Parallel Computing, Columbus, OH, August 1995.
R. Ghiya and L. Hendren. Is is a tree, a DAG or a cyclic graph? A shape analysis for heap-directed pointers in C. In Proceedings of the 23rd Annual ACM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, January 1996.
L. Hendren, J. Hummel, and A. Nicolau. Abstractions for recursive pointer data structures: Improving the analysis and transformation of imperative programs. In Proceedings of the SIGPLAN’ 92 Conference on Program Language Design and Implementation, San Francisco, CA, June 1992.
L. Hendren, J. Hummel, and A. Nicolau. A general data dependence test for dynamic, pointer-based data structures. In Proceedings of the SIGPLAN’94 Conference on Program Language Design and Implementation, Orlando, FL, June 1994.
L. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Transactions on Parallel and Distributed Systems, 1(1):35–47, January 1990.
N. Jones and S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In Conference Record of the 9th Annual ACM Symposium on the Principles of Programming Languages, Albuquerque, NM, January 1982.
J. Larus and P. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the SIGPLAN’88 Conference on Program Language Design and Implementation, Atlanta, GA, June 1988.
T. Lev-ami, T. Reps, M. Sagiv, and R. Wilhelm. Putting static analysis to work for verification: A case study. In 2000 International Symposium on Software Testing and Analysis, August 2000.
N. Rinetzky and M. Sagiv. Interprocedural shape analysis for recursive programs. In Proceedings of the 2001 International Conference on Compiler Construction, Genova, Italy, April 2001.
R. Rugina and M. Rinard. Pointer analysis for multithreaded programs. In Proceedings of the SIGPLAN’99 Conference on Program Language Design and Implementation, Atlanta, GA, May 1999.
M. Sagiv, T. Reps, and R. Wilhelm. Solving shape-analysis problems in languages with destructive updating. ACM Transactions on Programming Languages and Systems, 20(1):1–50, January 1998.
M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. In Proceedings of the 26th Annual ACM Symposium on the Principles of Programming Languages, San Antonio, TX, January 1999.
R. Wilhelm, M. Sagiv, and T. Reps. Shape analysis. In Proceedings of the 2000 International Conference on Compiler Construction, Berlin, Germany, April 2000.
R. Wilson and M. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the SIGPLAN’95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chong, S., Rugina, R. (2003). Static Analysis of Accessed Regions in Recursive Data Structures. In: Cousot, R. (eds) Static Analysis. SAS 2003. Lecture Notes in Computer Science, vol 2694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44898-5_26
Download citation
DOI: https://doi.org/10.1007/3-540-44898-5_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40325-8
Online ISBN: 978-3-540-44898-3
eBook Packages: Springer Book Archive