A general data dependence test for dynamic, pointer-based data structures

ABSTRACT

Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations.

In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.

References

1. App85.Andrew W. Appel. An efficient program for many-body simulation. SIAM J. Sci. $tat. Comput., 6(1):85-103, 1985.
2. Bak90.H. Baker. Unify and conquer (garbage, updating, aliasing, ..) in functional languages. In Proceedings o.f the '90 A CM Conference on LISP and Functional Programming, June 1990.
3. Ban93.U. Banerjee. Loop Transformations for Restructuring Compilers: The Foundations. Kluwer, 1993.
4. BH86.Josh Barnes and Pier Hut. A hierarchical O(NlogN) force-calculation algorithm. Nature, 324:446-449, 4 December 1986. The code can be obtained from Prof. Barnes at the University of Hawaii, or from jhummel~ics.uci.edu.
5. CBC93.J. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side-effects. In Proceedings of the A CM ~Oth Symposium on Principles o/Programming Languages, pages 232- 245, January 1993.
6. Cou86.D. Coutant. Retargetable high-level alias analysis. in Proceedings of the A CM Symposium on Principles of Programming Languages, pages 110-118, january 1986.
7. CWZ90.D.R. Chase, M. Wegman, and F.K. Zadek. Analysis of pointers and structures. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 296-310, 1990.
8. DDQ78.P. Denning, J. Dennis, and J. Qualitz. Machines, Languages, and Computation. Prentice- Hall, 1978.
9. Deu92.A. Deutsch. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations, in Proceedings of the IEEE 1992 International Conference on Computer Languages, pages 2-13, April 1992.
10. EGH94.M. Emami, R. Ghiya, and L. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1994.
11. Gua88.Vincent A. Guarna Jr. A technique for analyzing pointer and structure references in parallel restructuring compilers. In Proceedings of the International Conference on Parallel Processing, volume 2, pages 212-220, 1988.
12. HA93.W. Ludwell Harrison Ill and Z. Ammarguellat. A program's eye view of Miprac. in U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Fifth International Workshop on Lan. guages and Compilers for Parallel Computing, volume 757 of Lecture Notes in Computer Science, pages 512-537. $prlnger-Verlag, 1993.
13. Har89.W. Ludwell Harrison III. The interprocedural analysis and automatic parallelization of Scheme programs. Lisp and Symbolic Cornpuration, 2(3/4):179-396, 1989.
14. HDE+93.L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, and B. Sridharan. Designing the Me- CAT compiler based on a family of structured intermediate representations. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Fifth international Workshop on Languages and Compilers for Parallel Computing, volume 757 of Lecture Notes in Computer Science, pages 406-420. Springer-Verlag, 1993.
15. HHN92.L. Hendren, J. Hummel, and A. Nicolan. Abstractions for recursive pointer data structures: Improving the analysis and transformation of imperative programs. In Proceedings o/the SIG- PLAN '9~ Conference on Programming Language Design and Implementation, pages 249- 260, June 1992.
16. HHN94.J. Hummel, L. Hendren, and A. Nicolau. A language for conveying the aliasing properties of dynamic, pointer-based data structures. In Proceedings of the 8th International Parallel Processing Symposium, April 1994.
17. HN90.Laurie J. Hendren and Alexandru Nicolau. Parallelizing programs with recursive data structures. IEEE Trans. on Parallel and Distributed Computing, 1(1):35-47, January 1990.
18. HPR89.Susan Horwitz, Phil Pfeiffer, and Thomas Reps. Dependence analysis for pointer variables, in Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, pages 28-40, June 1989.
19. HU79.J. Hopcroft and J. UUman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
20. Hud86.P. Hudak. A semantic model of reference counting and its abstraction. In Proceedings of the 1986 ACM Conference on LISP and Functional Programming, 1986.
21. ISY88.K. Inoue, H. Seki, and H. Yagi. Analysis of functional programs to detect run-time garbage cells. A CM TOPLAS, 10(4):555-578, October 1988.
22. JM82.N.D. Jones and S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In 9th A CM Symposium on Principles of Programming Languages, pages 66-74, 1982.
23. Ken90.K. Kennedy. Foreword of Supercompilers for Parallel and Vector Computers, 1990. The text is written by Hans Zima with Barbara Chapman, available from the ACM Press.
24. KKK90.David Klappholz, Apostolos D. Kallis, and Xiangyun Kang. Refined C: An update. In David Gelernter, Alexandru Nicolau, and David Padua, editors, Languages and Compilers for Parallel Computing, pages 331-357. The MIT Press, 1990.
25. KS93.N. Klarlund and M. Schwartzbach. Graph types. In Proceedings of the A CM ~Oth Sglmposlum on Principles of Programming Languages, pages 196-205, January 1993.
26. Kun86.K. Kundert. Sparse matrix techniques. In A. Ruehli, editor, Circuit Analysis, Simulation and Design, pages 281-324. Elsevier Science Publishers B.V. (North-Holland), 186.
27. Lan92.W. Landi. Undecidability of static analysis. A CM Letters on Programming Languages and Systems, 1(4), December 1992.
28. LG88.J.M. Lucassen and D. K. Gifford. Polymorphic effect systems. In Proceedings 15th A CM Symposium on Principles of Programming Languages, pages 47-57, 1988.
29. LH88.James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 21-34, June 1988.
30. LMSS91.J. Loeliger, R. Metzger, M. Seligman, and S. Stroud. Pointer target tracking- an empirical study. In Proceedings of Supercomputing '91, pages 14-23, November 1991.
31. LR92.W. Landi and B. Ryder. A safe approximation algorithm for interprocedural pointer aliazing. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 235-248, June 1992.
32. MLR+93.T. Marlowe, W. Landi, B. Ryder, J. Choi, M. Burke, and P. Carini. Pointer-induced aliasing: A clarification. A CM SIGPLAN Notices, 28(9):67-70, September 1993.
33. NPD89.A. Neirynck, P. Panangaden, and A. J. Dereefs. Effect analysis in higher-order languages. International Journal o/Parallel Programming, 18(1):1-37, 1989.
34. PCK94.J. Plevyak, A. Chien, and V. Karamcheti. Analysis of dynamic structures for efficient parallel execution. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Sixth international Workshop on Languages and Compilers for Parallel Computing, volume 768 of Lecture Notes in Computer Science, pages 37-56. Springer-Verlag, 1994.
35. PS85.F. Preparata and M. Shamos. Computational Geometry: An introdution. Springer-Verlag, 1985.
36. PW86.David A. Padua and Michael J. Wolfe. Advanced compiler optimization for supercomputers. Communications of the ACM, 29(12), December 1986.
37. RM88.C. Ruggieri and T. P. Murtagh. Lifetime analysis of dynamically allocated objects. In Proceedings of the 15th A CM Symposium on Principles of Programming Languages, pages 285- 293, 1988.
38. Sam90.Hanan Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, 1990.
39. Sta80.Thomas A. Standish. Data Structure Techniques. Addison-Wesley, 1980.
40. SWG91.J. Singh, W. Weber, and A. Gupta. SPLASH: Stanford parallel applications for sharedmemory. Technical Report CSL-TR-91-469, Stanford University, 1991. FTP to mojave.stanford.edu.
41. WH92.E. Wang and P. Hflfinger. Analysis of recursive types in LISP-like languages. In Proceedings of the '9~ A CM Conference on LISP and Func~ tional Programming, pages 216-225, June 1992.
42. WS92.M. Warren and J. Salmon. Astrophysical nbody simulations using hierarchical tree data structures. In Proceedings of Supercomputing 1992, pages 570-576, November 1992.
43. ZC90.Hans Zima and Barbara Chapman. Supercompilers for Parallel and Vector Computers. ACM Press, 1990.

Index Terms

• Information systems

  • Information storage systems

    • Record storage systems

      • Directory structures

        • B-trees

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Trees

  • Mathematical analysis

    • Numerical analysis

      • Computations on matrices

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

        • Data types and structures