| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Framework to Capture Dynamic Data Structures in Pointer-Based Codes
February 2004 (vol. 15 no. 2)
pp. 151-166
Abstract—To successfully exploit all the possibilities of current computer/multicomputer architectures, optimization compiling techniques are a must. However, for codes based on pointers and dynamic data structures, these optimization techniques have to be necessarily carried out after identifying the characteristics and properties of the data structure used in the code. In this paper, we describe the framework and the analyzer we have implemented to capture complex data structures generated, traversed, and modified in codes based on pointers. Our method assigns a Reduced Set of Reference Shape Graph (RSRSG) to each statement to approximate the shape of the data structure after the execution of such a statement. With the properties and operations that define the behavior of our RSRSG, the method can accurately detect complex recursive data structures such as a doubly linked list of pointers to trees where the leaves point to additional lists. Several experiments are carried out with real codes to validate the capabilities of our analyzer.
[1] B. Steensgaard, Points-To Analysis in Almost Linear Time Proc. 23rd ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, pp. 32-41, 1996.
[2] L. Andersen, Program Analysis and Specialization for the C Programming Language PhD thesis, DIKU, Univ. of Copenhagen, DIKU report 94/19, May 1994.
[3] M. Shapiro and S. Horwitz, Fast and Accurate Flow Insensitive Points-To Analysis Proc. Symp. Principles of Programming Languages, pp. 1-14, 1997.
[4] M. Das, Unification-Based Pointer Analysis with Directional Assignments Proc. ACM SIGPLAN Notices, vol. 35, no. 5, pp. 35-46, 2000.
[5] R.P. Wilson and M.S. Lam, Efficient Context-Sensitive Pointer Analysis for C Programs Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, pp. 18-21, 1995.
[6] M. Hind and A. Pioli, Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses Proc. Static Analysis Symp., pp. 57-81, 1998.
[7] R. Ghiya and L.J. Hendren, Putting Pointer Analysis to Work Proc. ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, pp. 121-133, 1998.
[8] T.M. Chilimbi, M.D. Hill, and J.R. Larus, Cache-Conscious Structure Layout Proc. SIGPLAN Conf. Programming Language Design and Implementation, pp. 1-12, 1999.
[9] T.M. Chilimbi, Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation, 2001.
[10] Y. Zhu and L. Hendren, Locality Analysis for Parallel C Programs IEEE Trans. Parallel and Distributed Systems, vol. 10, no. 2, Feb. 1999.
[11] Y. Zhu and L.J. Hendren, Communication Optimizations for Parallel C Programs J. Parallel and Distributed Computing, vol. 58, no. 2, pp. 301-332, 1999.
[12] A. Rogers, M.C. Carlisle, J.H. Reppy, and L.J. Hendren, Supporting Dynamic Data Structures on Distributed-Memory Machines ACM Trans. Programming Languages and Systems, vol. 17, no. 2, pp. 233-263, Mar. 1995.
[13] R. Ghiya, Putting Pointer Analysis to Work PhD thesis, School of Computer Science, McGill Univ., Montreal, May 1998.
[14] R. Ghiya and L.J. Hendren, Is it a Tree, a Dag, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C Proc. 23rd ACM Symp. Principles of Programming Languages, pp. 1-15, 1996.
[15] P. Cousot and R. Cousot, Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints Proc. Fourth ACM Symp. Principles of Programming Language, pp. 238-252, 1977.
[16] Y.S. Hwang and J.H. Saltz, Identifying DEF/USE Information of Statements that Construct and Traverse Dynamic Recursive Data Structures Proc. 10th Int'l Workshop Languages and Compilers for Parallel Computing, pp. 131-145, 1997.
[17] J. Barnes and P. Hut, A Hierarchical${\rm{O(n\!\cdot \log n)}}$Force Calculation Algorithm Nature, vol. 324, Dec. 1986.
[18] J. Hummel, L.J. Hendren, and A. Nicolau, A General Data Dependence Test for Dynamic, Pointer-Based Data Structures Proc. SIGPLAN Conf. Programming Language Design and Implementation, pp. 218-229, 1994.
[19] A. Matsumoto, D.S. Han, and T. Tsuda, Alias Analysis of Pointers in Pascal and Fortran 90: Dependence Analysis between Pointer References Acta Informatica, vol. 33, pp. 99-130, 1996.
[20] D.R. Chase, M. Wegman, and F.K. Zadek, Analysis of Pointers and Structures Proc. SIGPLAN Conf. Programming Language Design and Implementation, pp. 296-310, 1990.
[21] J. Plevyak, A. Chien, and V. Karamcheti, Analysis of Dynamic Structures for Efficient Parallel Execution Languages and Compilers for Parallel Computing, pp. 37-57, Berlin: Springer-Verlag, 1993.
[22] M. Sagiv, T. Reps, and R. Wilhelm, Solving Shape-Analysis Problems in Laguages with Destructive Updating ACM Trans. Programming Languages and Systems, vol. 20, no. 1, pp. 1-50, Jan. 1998.
[23] F. Corbera, R. Asenjo, and E. Zapata, New Shape Analysis for Automatic Parallelization of C Codes Proc. ACM Int'l Conf. Supercomputing, pp. 220-227, 1999.
[24] N. Jones and S. Muchnick, Flow Analysis and Optimization of Lisp-like Structures, chapter 4, pp. 102-131, Prentice Hall, 1981.
[25] S. Horwitz, P. Pfeiffer, and T. Reps, Dependence Analysis for Pointer Variables Proc. ACM SIGPLAN Notices, vol. 24, no. 7, pp. 28-40, 1989.
[26] M. Sagiv, T.W. Reps, and R. Wilhelm, Parametric Shape Analysis via 3-Valued Logic Proc. Symp. Principles of Programming Languages, pp. 105-118, 1999.
[27] T. Lev-Ami and M. Sagiv, TVLA: A System for Implementing Static Analyses Proc. Static Analysis Symp., pp. 280-301, 2000.
Index Terms:
Shape analysis, pointers, recursive data structures, shape graphs, optimizing compiler, irregular codes.
Citation:
Francisco Corbera, Rafael Asenjo, Emilio L. Zapata, "A Framework to Capture Dynamic Data Structures in Pointer-Based Codes," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, pp. 151-166, Feb. 2004, doi:10.1109/TPDS.2004.1264798
