Abstract description of pointer data structures: an approach for improving the analysis and optimization of imperative programs

ABSTRACT

Even though impressive progress has been made in the area of optimizing and parallelizing array-based programs, the application of similar techniques to programs using pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties, pointers can be used to implement a wide variety of structures which exhibit a much larger set of properties. The diversity of these structures implies that programs with pointer data structures cannot be effectively analyzed by traditional optimizing and parallelizing compilers. In this paper we present a new approach that leads to the improved analysis and transformation of programs with recursively defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS). ADDS is a simple extension to existing imperative languages that allows the programmer to explicitly describe the important properties of a large class of data structures. These abstract descriptions may be used by the compiler to achieve more accurate program analysis in the presence of pointers, which in turn enables and improves the application of numerous optimizing and parallelizing transformations. We present ADDS by describing various data structures; we discuss how such descriptions can be used to improve analysis and debugging; and we supply three important transformations enabled by ADDS.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 3: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• 4: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 5: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 6: APPEL, A.W. All efficient program for many-body simulation. SIAM J. Sci. Stat. Comput. 6, 1 (1985), 85-103.
• 7: Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France [doi>10.1145/91556.91652]
• 8: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 9: Utpal Banerjee, Speedup of ordinary programs, 1979
• 10: BARNES, J., AND HUT, P. A hierarchical O(N log N) force-calculation algorithm. Nature 324 (Dec. 4, 1986), 446-449. Can be obtained from J. Barnes at the University of Hawaii.
• 11: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• 12: 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
• 13: CONVEX COMPUTER CORPORATION. CONVEX C and FORTRAN Language Reference Manuals. Convex Computer Corp., 1990.
• 14: DEUTSCH, A. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In Proceedings of the IEEE '92 International Conference on Computer Languages (Apr. 1992). IEEE, New York.
• 15: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• 16: DONGARRA, J. J., AND HINDS, A. R. Unrolling loops in FORTRAN. Softw.-Pract. Exper. 9 (1979), 219-226.
• 17: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 18: Guang R. Gao , Yue-Bong Wong , Qi Ning, A timed Petri-net model for fine-grain loop scheduling, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.204-218, June 24-28, 1991, Toronto, Ontario, Canada
• 19: V. A. Guarna , D. Gannon, Jr. , Y. Gaur , D. Jablonowski, FAUST: an environment for programming parallel scientific applications, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.3-10, November 12-17, 1988, Orlando, Florida, United States
• 20: HARRISON, W. a., III The interprocedural analysis and automatic parallelization of Scheme programs. Lisp Symb. Comput. 2, 3/4 (1989), 179-396.
• 21: Williams Ludwell Harrison, III , Zahira Ammarguellat, A Program's Eye View of Miprac, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.512-537, August 03-05, 1992
• 22: Laurie Jane Hendren, Parallelizing programs with recursive data structures, Cornell University, Ithaca, NY, 1990
• 23: HENDREN, L. J., AND GAO, G.R. Designing programming languages for analyzability: A fresh look at pointer data structures. In Proceedings of the 4th IEEE International Conference on Computer Languages (Apr. 1992). IEEE, New York.
• 24: 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]
• 25: Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
• 26: 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
• 27: Lorenz Huelsbergen , James R. Larus, Dynamic program parallelization, Proceedings of the 1992 ACM conference on LISP and functional programming, p.311-323, June 22-24, 1992, San Francisco, California, United States
• 28: HUMMEL, J., HENDREN, L. J., AND NICOLAU, A. Applying an abstract data structure description approach to parallelizing scientific pointer programs. In Proceedings of the 21st Annual International Conference on Parallel Processing, Volume H (Aug. 1992). 100-104.
• 29: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• 30: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 31: I~NNEDY, K. Foreword. In Supercompilers for Parallel and Vector Computers, ACM Press, New York, 1990.
• 32: David Klappholz , Apostolos D. Kallis , Xiangyun Kong, Refined C: an update, Selected papers of the second workshop on Languages and compilers for parallel computing, p.331-357, May 1990, Urbana, Illinois, United States
• 33: KUCK, D., BUDNIK, P., CHEN, S., LAWRIE, D., TOWLE, R., STREBENDT, R., DAVIS, E., HAN, J., KRASKA, P., AND MURAOKA, Y. Measurements of parallelism in ordinary FORTRAN programs. Computer 7, 1 (Jan. 1974), 37-46.
• 34: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 35: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 36: James Richard Larus , Paul Hifinger, Restructuring symbolic programs for concurrent execution on multiprocessors, 1989
• 37: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 38: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• 39: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 40: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 41: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
• 42: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 43: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 44: Richard Snodgrass, The interface description language: definition and use, Computer Science Press, Inc., New York, NY, 1989
• 45: Jon A. Solworth, The PARSEQ project: an interim report, Selected papers of the second workshop on Languages and compilers for parallel computing, p.490-510, May 1990, Urbana, Illinois, United States
• 46: Edward Wang , Paul N. Hilfinger, Analysis of recursive types in Lisp-like languages, Proceedings of the 1992 ACM conference on LISP and functional programming, p.216-225, June 22-24, 1992, San Francisco, California, United States
• 47: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 48: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990
• 49: ZIMA, H., BAST, H-J., AND GERNDT, M. Superb: A tool for semi-automatic MIMD/SIMD parallelization. Parall. Comput. 6 (1988), 1-18.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Compilers

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Algorithms, Languages