Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs

Abstract

Even though impressive progress has been made in the area of optimizing and parallelizing programs with arrays, the application of similar techniques to programs with pointer data structures has remained difficult. In this paper we introduce a new approach that leads to improved analysis and transformation of programs with recursively-defined pointer data structures.

We discuss how an abstract data structure description can improve program analysis by presenting an analysis approach that combines an alias analysis technique, path matrix, with information available from an ADDS declaration. Given this improved alias analysis technique, we provide a concrete example of applying a software pipelining transformation to loops involving pointer data structures.

References

1. AK87 Randy Allen and Ken Kennedy. Automatic translation of FORTRAN programs to vector form. A CM Transactions on Programming Languages and Systems, 9(4), October 1987.
2. AN88a A. Aiken and A. Nicolau. Optimal Loop Parallelization, in Proceedings of the SIGPLAN 1988 Conference on Programming Language Design and Implementation, pages 308-317, June 1988.
3. AN88b A. Aiken and A. Nicolau. Perfect Pipelining: A new loop parallelization technique. In Proceedings of the 1988 EuroIaean Symposium on Pro~ramruing. Springer Verlag Lecture Notes in Computer Science No.300, March 1988.
4. App85 Andrew W. Appel. An Efficient Program for Many-Body Simulation. SIAM J. Sci. Stat. Cornput., 6(1):85-103, 1985.
5. ASU87 Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1987.
6. BH86 Josh Barnes and Piet 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.
7. CON CONVEX Computer Corporation. CONVEX C and FORTRAN Language Reference Manuals. 1990.
8. 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.
9. DH79 J.J. Dongarra and A.R. Hinds. Unrolling loops in FORTRAN. So/tware-Practice and Experience, 9:219-226, 1979.
10. EN89 Kemai Ebcioglu and Toshio Nakatani. A New Compilation Technique for Parallelizing Loops Loops with Unpredictable Branches on a VLIW Architecture. In Proceedings o/the Second Workshop on Programming Languages and Compilers /or Parallel Computing, Research Monographs in Parallel and Distributed Computing. MtT-Press, 1989.
11. Gro91 Josef Grosch. Tool support for data structures. Structured Programming, 12(1):31-38, January 1991.
12. Gua88 Vincent A. Guarna Jr. A technique for analyzing pointer and structure references in parallel restructuring compilers. In Proceedings o/the International Conference on Parallel Processing, volume 2, pages 212-220, 1988.
13. Har89 W. Ludwell Harrison III. The interprocedural analysis and automatic parallelization of scheme programs. Lisp and Symbolic Computation, 2(3/4):179-396, 1989.
14. Har91 W. Ludwell Harrison III. Generalized iteration space and the parallelization of symbolic programs. In Inn Foster and Evan Tick, editors, Proceedings of the Workshop on Computation o/Symbolic Languages for Parallel Computers. Argonne National Laboratory, October 1991. ANL-91/34.
15. Hen90 Laurie J. Hendren. Parallelizing Programs with Recursive Data Structures. PhD thesis, Cornell University, April 1990. TR 90-1114.
16. HG92 Laurie J. Hendren and Guang R. Gao. Designing Programming Languages for Analyzability: A Fresh Look at Pointer Data Structures. In Proceedngs o/the ~th IEEE International Conference on Computer Languages (to appear, also available as A CAPS Technical Memo 28, McGill University), April 1992.
17. HN90 Laurie J. ttendren and Alexandru Nicolau. I>arallelizing 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. JM81 N. D. Jones and S. S. Muchnick. Program Flow Analysis, Theory and Applications, chapter 4, Flow Analysis and Optimization of LISP-like Structures, pages 102-131. Prentice-Hall, 1981.
20. 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 /or Parallel Computing, pages 331-357. The MIT Press, 1990.
21. Kuc78 D.J. Kuck. The Structure o/Computers and Computations: Volume I. Wiley, 1978.
22. Lam88 Monica Lam. Software Pipelining: An Effective Scheduling Technique for VLIW Machines. In Proceedings o/the SiGPLAN 1988 Con{erence on Programming Language Design and Implementation, pages 318-328, June 1988.
23. Lar89 James R. Larus. Restructuring Symbolic Programs/or Concurrent Execution on Multiprocessots. PhD thesis, University of California, Berkeley, 1989.
24. LH88a James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings o/the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 21-34, June 1988.
25. LH88b James R. Larus and Paul N. Hilfinger. Restructuring Lisp programs for concurrent execution. In Proceedings o/the A CM/SIGPLAN PPEALS 1988- Parallel Programming: Experience with Applications, Languages and Systems, pages 100-110, July 1988.
26. Lov77 D.B. Loveman. Program Improvement by Sourceto-Source Transformation. Journal o/the A CM, 24(1):121-145, January 1977.
27. MR90 Michael Metcalf and John Reid. Fortran 90 Explained. Oxford University Press, 1990.
28. NPW91 A. Nicolau, R. Potasman, and H. Wang. Register Allocation, Renaming and their impact on Finegrain Parallelism. in Proceedings of the Fourth Workshop on Languages and Compilers/or Parallel Computing, August 1991.
29. PW86 David A. Padua and Michael J. Wolfe. Advanced compiler optimization for supercomputers. Communications of the ACM, 29(12), December 1986.
30. RG82 B. R. Rau and C. D. Glaeser. Efficient Code Generation for Horizontal Architectures: Compiler Techniques and Architectural Support. In Proceedings of the 9th Symposium on Computer Architecture, April 1982.
31. Sam90 Hanan Samet. The Design and Analysis o/Spatial Data Structures. Addison-Wesley, 1990.
32. Sol90 Ion A. Solworth. The PARSEQ Project: An Interim Report. in David Gelernter, Alexandru Nicolau, and David Padua, editors, Languages and Compilers for Parallel Computing, pages 490-510. The MIT Press, 1990.
33. Sta80 Thomas A, Standish, Data Structure Techniques. Addison-Wesley, 1980.
34. ZC90 Hans Zima and Barbara Chapman. Supercompilers /or Parallel and Vector Computers. ACM Press, 1990.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Semantics and reasoning

    • Program constructs