Sharing analysis of arrays, collections, and recursive structures

ABSTRACT

Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of significant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel version. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efficient manner. The effectiveness of the approach is evaluated on a set of challenge problems from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups.

REFERENCES

• 1: http://cs.unm.edu/~marron.
• 2: J. Berdine, C. Calcagno, B. Cook, D. Distefano, P. O'Hearn, T. Wies, and H. Yang. Shape analysis for composite data structures. In CAV, 2007.
• 3: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 4: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Journal of Parallel and Distributed Computing, v.38 n.2, p.248-255, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0145]
• 5: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 6: S. Chong and R. Rugina. Static analysis of accessed regions in recursive data structures. In SAS, 2003.
• 7: Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.230-241, June 20-24, 1994, Orlando, Florida, United States
• 8: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 9: Rakesh Ghiya , Laurie J. Hendren , Yingchun Zhu, Detecting Parallelism in C Programs with Recursive Darta Structures, Proceedings of the 7th International Conference on Compiler Construction, p.159-173, March 28-April 04, 1998
• 10: S. Gulwani and A. Tiwari. An abstract domain for analyzing heapmanipulating low-level software. In CAV, 2007.
• 11: Bolei Guo , Neil Vachharajani , David I. August, Shape analysis with inductive recursion synthesis, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 12: L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990 [doi>10.1109/71.80123]
• 13: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.28-40, June 19-23, 1989, Portland, Oregon, United States
• 14: JOlden Suite Collection. http://www.ali.cs.umass.edu/DaCapo/benchmarks.html.
• 15: M. Marron, D. Kapur, D. Stefanovic, and M. Hermenegildo. A static heap analysis for shape and connectivity. In LCPC, 2006.
• 16: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292552]
• 17: Standard Performance Evaluation Corporation. JVM98 Version 1.04, August 1998. http://www.spec.org/jvm98.
• 18: Reinhard Wilhelm , Shmuel Sagiv , Thomas W. Reps, Shape Analysis, Proceedings of the 9th International Conference on Compiler Construction, p.1-17, March 25-April 02, 2000
• 19: Hongseok Yang , Oukseh Lee , Josh Berdine , Cristiano Calcagno , Byron Cook , Dino Distefano , Peter O'Hearn, Scalable Shape Analysis for Systems Code, Proceedings of the 20th international conference on Computer Aided Verification, July 07-14, 2008, Princeton, NJ, USA [doi>10.1007/978-3-540-70545-1_36]
• 20: Craig B. Zilles, Benchmark health considered harmful, ACM SIGARCH Computer Architecture News, v.29 n.3, p.4-5, June 2001 [doi>10.1145/503205.503206]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

General Terms:
Languages, Performance

Keywords:
parallelism, shape analysis, shared structures