Nordic Journal of Computing Bibliography

Abstract

In this paper we present a surprisingly simple reduction of the program dependence problem to the may-alias problem. While both problems are undecidable, providing a reduction between them has great practical importance. Program dependence information is used extensively in compiler optimizations, automatic program parallelizations, code scheduling for super-scale machines, and software engineering tools such as code slicers. When working with languages that support pointers and references, these systems are forced to make very conservative assumptions. This leads to many superfluous program dependences and limits compiler performance and the usability of software engineering tools. Fortunately, there are many algorithms for computing conservative approximations to the may-alias problem. The reduction has the important property of always computing conservative program dependences when used with a conservative may-alias algorithm. We believe that the simplicity of the reduction and the fact that it takes linear time may make it practical for realistic applications.

Categories and Subject Descriptors: D.3.3 [Programming Languages]: Language Constructs and Features; D.3.4 [Programming Languages]: Processors

Additional Key Words and Phrases: alias analysis, dataflow analysis, pointer analysis, program dependences, static analysis

Selected references

• Hiralal Agrawal and Joseph R. Horgan. Dynamic program slicing. In Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation (PLDI), pages 246-256, White Plains, New York, 20-22 June 1990. SIGPLAN Notices 25(6), June 1990.

• John Banning. An efficient way to find side effects of procedure calls and aliases of variables. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pages 29-41, San Antonio, Texas, January 1979.

• David R. Chase, Mark N. Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation (PLDI), pages 296-310, White Plains, New York, 20-22 June 1990. SIGPLAN Notices 25(6), June 1990.

• Jong-Deok Choi, Michael Burke, and Paul R. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 232-245, Charleston, South Carolina, January 1993.

• Keith D. Cooper and Ken Kennedy. Interprocedural side-effect analysis in linear time. In Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI), pages 57-66, Atlanta, Georgia, 22-24 June 1988. SIGPLAN Notices 23(7), July 1988.

• Alain Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (PLDI), pages 230-241, Orlando, Florida, 20-24 June 1994. SIGPLAN Notices 29(6), June 1994.

• Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (PLDI), pages 242-256, Orlando, Florida, 20-24 June 1994. SIGPLAN Notices 29(6), June 1994.

• Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

• Rakesh Ghiya and Laurie J. Hendren. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In Conference Record of POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1-15, St. Petersburg Beach, Florida, 21-24 January 1996.

• Rakesh Ghiya and Laurie J. Hendren. Putting pointer analysis to work. In Conference Record of POPL '98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 121-133, San Diego, California, 19-21 January 1998.

• Susan Horwitz, Phil Pfeiffer, and Thomas W. Reps. Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN'89 Conference on Programming Language Design and Implementation (PLDI), pages 28-40, Portland, Oregon, 21-23 June 1989. SIGPLAN Notices 24(7), July 1989.

• Neil D. Jones and Steven S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, pages 66-74, Albequerque, New Mexico, January 1982.

• David J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe. Dependence graphs and compiler optimizations. In Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, pages 207-218, Williamsburg, Virginia, January 1981.

• William Landi and Barbara G. Ryder. Pointer-induced aliasing: A problem classification. In Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, pages 93-103, Orlando, Florida, January 1991.

• William Landi, Barbara G. Ryder, and Sean Zhang. Interprocedural side effect analysis with pointer aliasing. In Proceedings of the ACM SIGPLAN'93 Conference on Programming Language Design and Implementation (PLDI), pages 56-67, Albuquerque, New Mexico, 23-25 June 1993. SIGPLAN Notices 28(6), June 1993.

• James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the ACM SIGPLAN'88 Conference on Programming Language Design and Implementation (PLDI), pages 21-34, Atlanta, Georgia, 22-24 June 1988. SIGPLAN Notices 23(7), July 1988.

• Thomas W. Reps. Solving demand versions of interprocedural analysis problems. In Peter Fritzon, editor, Compiler Construction, 5th International Conference, volume 786 of Lecture Notes in Computer Science, pages 389-403, Edinburgh, U.K., 7-9 April 1994. Springer.

• Erik Ruf. Partitioning dataflow analyses using types. In Conference Record of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 15-26, Paris, France, 15-17 January 1997.

• Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. Solving shape-analysis problems in languages with destructive updating. In Conference Record of POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 16-31, St. Petersburg Beach, Florida, 21-24 January 1996.

• Marc Shapiro and Susan Horwitz. Fast and accurate flow-insensitive points-to analysis. In Conference Record of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1-14, Paris, France, 15-17 January 1997.

• Bjarne Steensgaard. Points-to analysis in almost linear time. In Conference Record of POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32-41, St. Petersburg Beach, Florida, 21-24 January 1996.

• Robert P. Wilson and Monica S. Lam. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation (PLDI), pages 1-, La Jolla, California, 18-21 June 1995. SIGPLAN Notices 30(6), June 1995.

Shortcuts: