Interprocedural may-alias analysis for pointers: beyond k-limiting

ABSTRACT

Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store-based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by Jones and Muchnick a decade ago. As a result, optimizing, verifying and parallelizing programs with pointers has remained difficult. We present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. The key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds. Based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [CWZ90, He90, LR92, CBC93].

REFERENCES

• POP91: ACM Press. Eighteenth Annual ACM Sy~p. on Principles of Programming Languages, Orlando, FL, Jan. 1991.
• PLD92: ACM Press. SIGPLAN'9~ Conf. on Programming Language Design and implementation, volume 27(7) of SIG- PLAN Notices, San Francisco, June 1992.
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• BK89: V. Balasundaram , K. Kennedy, A technique for summarizing data access and its use in parallelism enhancing transformations, ACM SIGPLAN Notices, v.24 n.7, p.41-53, July 1989
• Br64: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• CWZ90: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
• CBC93: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• CCF91: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• Co81: P, Cousot. Semantic foundations of program analysis. In Program Flow Analysis: Theory and Applications, pp. 303-342. Prentice-Hall, 1981.
• CC77a: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• CC77b: Patrick Causot , Radhia Cousot, Static determination of dynamic properties of generalized type unions, ACM SIGPLAN Notices, v.12 n.3, p.77-94, March 1977
• CC77c: P. Cousot and R. Cousot. Static determination of dynamic properties of recursive procedures. In Working Conf. on Formal Description o~ Programming Concepts. IFIP WG 2.2, North-Holland, Aug. 1977.
• CC79: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• CC92: Patrick Cousot , Radhia Cousot, Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation, Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, p.269-295, August 26-28, 1992
• CH78: Patrick Cousot , Nicolas Halbwachs, Automatic discovery of linear restraints among variables of a program, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512770]
• De90: 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]
• De92a: A. Deutsch. Operational Models of Programming Languages and Representations of Relations on Regular Languages with Application to the Static Determination of Dynamic Aliasing Properties of Data. PhD thesis, LIX, Ecole Polytechnique, F-91128, Palaiseau, France, 1992.
• De92b: A. Deutsch. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In {IC092}, pp. 2-13.
• DGS94: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Reducing the Cost of Data Flow Analysis By Congruence Partitioning, Proceedings of the 5th International Conference on Compiler Construction, p.357-373, April 07-09, 1994
• Ei74: Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
• Gr89: P. Granger. Static analysis of arithmetical congruences. International Journal of Computer Mathematics, 30:165-190, 1989.
• Gr91: Philippe Granger, Static analysis of linear congruence equalities among variables of a program, Proceedings of the international joint conference on theory and practice of software development on Colloquium on trees in algebra and programming (CAAP '91): vol 1, p.169-192, April 1991, Brighton, United Kingdom
• Gr92: Philippe Granger, Improving the Results of Static Analyses Programs by Local Decreasing Iteration, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.68-79, December 18-20, 1992
• Ha79: N. Halbwachs. Dgterm~nation automatique de relations lin~aires vdrifi~es par lea variables d'un programme. PhD thesis, Universit~ Sclentlfique et M~dicale de Grenoble & Institut National Polytechnique de Grenoble, Grenoble, France, Mar. 1979.
• Ha89: W.L. Harrison. The interprocedural analysis and automatic parallelisation of Scheme programs. Lisp and Symbolic Computation, 2(3):176-396, Oct. 1989.
• He88: L, Hederman. Compile time garbage collection. Master's thesis, Rice University, Houston, Aug. 1988. Tech. report COMP TR88-75.
• He90: 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]
• HG92: L.J. Hendren and G.R. Gao. Designing programming languages for analysability: a fresh look at pointer data structures. In {ICC92}, pp. 242-251.
• HHN92: Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, ACM SIGPLAN Notices, v.27 n.7, p.249-260, July 1992
• HPR89: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• Hu86: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• ICC92: Proc. of the IEEE 1992 International Conf. on Computer Languages, San Francisco, Apr. 1992. IEEE Press.
• Jo81: N.D. Jones. Flow analysis of lambda expressions. In Symp. on Functional Languages and Computer Architecture, pp. 376-401. Chalmers University of Technology, June 1981.
• JM81: N.D. Jones and S. Muchnick. Flow analysis and optimization of Lisp-like structures. In S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, pp. 102-131. Prentlce-Hall, 1981.
• JM82: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• Jo81: H.B.M. Jonkers. Abstract storage structures. In de Bakker and van Vllet, editors, Algorithmic Languages, pp. 321- 343. IFIP, North Holland, 1981.
• Ka76: M. Karr. Affine relationships among variables of a program. Acts Informatica, 6:133-151, 1976.
• Ki73: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• La92a: William Alexander Landi, Interprocedural aliasing in the presence of pointers, Rutgers University, New Brunswick, NJ, 1992
• La92b: William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992 [doi>10.1145/161494.161501]
• LR91: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• LR92: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• LH88a: 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
• LH88b: James R. Larus , Paul N. Hilfinger, Restructuring Lisp programs for concurrent execution, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.100-110, July 19-21, 1988, New Haven, Connecticut, United States
• ML+93: Thomas J. Marlowe , William G. Landi , Barbara G. Ryder , Jong-Deok Choi , Michael G. Burke , Paul Carini, Pointer-induced aliasing: a clarification, ACM SIGPLAN Notices, v.28 n.9, p.67-70, Sept. 1993 [doi>10.1145/165364.165387]
• MR89: T.J. Marlowe and B.G. Ryder. Hybrid incremental alias algorithms. Tech. report LCSR-TR-129, Rutgers University, Oct. 1989.
• Ma91: F. Masdupuy. Using abstract interpretation to detect array data dependencies. In Proc. of the International Syrup. on 8upercomputing, pp. 19-27. Kyushu University Press, Nov. 1991. ISBN 4-87378-284-8.
• Mo84: E Morel, Data flow analysis and global optimization, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
• NPD87: A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
• Pa66: Rohit J. Parikh, On Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.570-581, Oct. 1966 [doi>10.1145/321356.321364]
• RF93: B. Ramakrishna Rau , Joseph A. Fisher, Instruction-level parallel processing: history, overview, and perspective, The Journal of Supercomputing, v.7 n.1-2, p.9-50, May 1993 [doi>10.1007/BF01205181]
• RM88: 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]
• SF+90: Shmuel Sagiv , Nissim Francez , Michael Rodeh , Reinhard Wilhelm, A Logic-Based Approach to Data Flow Analysis Problem, Proceedings of the 2nd International Workshop on Programming Language Implementation and Logic Programming, p.277-292, August 20-22, 1990
• SP81: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis, in S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, pp. 189-234. Prentice-Hall, 1981.
• Sh91: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• St92: Jan Stransky, A lattice for abstract interpretation of dynamic (LISP-like) structures, Information and Computation, v.101 n.1, p.70-102, Nov. 1992 [doi>10.1016/0890-5401(92)90076-R]
• Wa91: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• We80: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

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

General Terms:
Algorithms, Performance