Which pointer analysis should I use?

ABSTRACT

During the past two decades many different pointer analysis algorithms have been published. Although some descriptions include measurements of the effectiveness of the algorithm, qualitative comparisons among algorithms are difficult because of varying infrastructure, benchmarks, and performance metrics. Without such comparisons it is not only difficult for an implementor to determine which pointer analysis is appropriate for their application, but also for a researcher to know which algorithms should be used as a basis for future advances.This paper describes an empirical comparison of the effectiveness of five pointer analysis algorithms on C programs. The algorithms vary in their use of control flow information (flow-sensitivity) and alias data structure, resulting in worst-case complexity from linear to polynomial. The effectiveness of the analyses is quantified in terms of compile-time precision and efficiency. In addition to measuring the direct effects of pointer analysis, precision is also reported by determining how the information computed by the five pointer analyses affects typical client analyses of pointer information: Mod/Ref analysis, live variable analysis and dead assignment identification, reaching definitions analysis, dependence analysis, and conditional constant propagation and unreachable code identification. Efficiency is reported by measuring analysis time and memory consumption of the pointer analyses and their clients.

REFERENCES

• 1: Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.85-96, June 17-19, 1998, Montreal, Quebec, Canada
• 2: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. Available at ftp.diku.dk/pub/diku/semantics/papers/D-203.dvi.Z.
• 3: Darren C. Atkinson , William G. Griswold, Effective whole-program analysis in the presence of pointers, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.46-55, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 4: T. Austin. Pointer-intensive benchmark suite, version 1.1. http://www.cs.wisc.edu/~austin/ptr-dist.html, 1995.
• 5: Michael G. Burke , Paul R. Carini , Jong-Deok Choi , Michael Hind, Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.234-250, August 08-10, 1994
• 6: 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]
• 7: 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]
• 8: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
• 9: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 10: Rakesh Ghiya , Laurie J. Hendren, Connection analysis: a practical interprocedural heap analysis for C, International Journal of Parallel Programming, v.24 n.6, p.547-578, Dec. 1996
• 11: Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268957]
• 12: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 13: Michael Hind , Anthony Pioli, Assessing the Effects of Flow-Sensitivity on Pointer Alias Analyses, Proceedings of the 5th International Symposium on Static Analysis, p.57-81, September 14-16, 1998
• 14: Michael Hind , Anthony Pioli, Traveling Through Dakota: Experiences with an Object-Oriented Program Analysis System, Proceedings of the Technology of Object-Oriented Languages and Systems (TOOLS 34'00), p.49, July 30-August 03, 2000
• 15: Michael Karasick, The architecture of Montana: an open and extensible programming environment with an incremental C++ compiler, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.131-142, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 16: 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]
• 17: W. Landi. Personal communication, Oct. 1997.
• 18: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• 19: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
• 20: W. A. Landi, B. G. Ryder, P. A. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural modi~cation side-e~ect analysis with pointer aliasing. Technical Report DCS-TR-336, Department of Computer Science, Rutgers University, May 1998.
• 21: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 22: 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]
• 23: T. J. Marlowe, B. G. Ryder, and M. G. Burke. De~ning ow sensitivity indata ow problems. Technical Report RC 20138, IBM T. J. Watson Research Center, July 1995.
• 24: John David Morgenthaler, Static analysis for a software transformation tool, University of California at San Diego, La Jolla, CA, 1998
• 25: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 26: A. Pioli. Conditional pointer aliasing and constant propagation. Master's thesis, SUNY at New Paltz, 1999. Available at http://www.mcs.newpaltz.edu/tr as Technical Report # 99-102.
• 27: A. Pioli and M. Hind. Combining interprocedural pointer analysis and conditional constant propagation. Research Report 21532, IBM T. J. Watson Research Center, Mar. 1999. Also available as SUNY at New Paltz Technical Report #99-103.
• 28: G. Ramalingam, The undecidability of aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1467-1471, Sept. 1994 [doi>10.1145/186025.186041]
• 29: Erik Ruf, Context-insensitive alias analysis reconsidered, ACM SIGPLAN Notices, v.30 n.6, p.13-22, June 1995
• 30: E. Ruf. Personal communication, Oct. 1997.
• 31: Rutgers PROLANGS. http://www.prolangs.rutgers.edu/public.html, 1999.
• 32: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 33: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 34: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 35: Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.21-31, March 02-04, 1998, Clearwater Beach, Florida, United States
• 36: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 37: F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121{189, 1995.
• 38: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 39: Robert Paul Wilson , Monica S. Lam, Efficient, context-sensitive pointer analysis for c programs, 1998
• 40: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, ACM SIGPLAN Notices, v.30 n.6, p.1-12, June 1995
• 41: Suan Hsi Yong , Susan Horwitz , Thomas Reps, Pointer analysis for programs with structures and casting, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.91-103, May 01-04, 1999, Atlanta, Georgia, United States
• 42: Sean Zhang , Barbara G. Ryder , William Landi, Program decomposition for pointer aliasing: a step toward practical analyses, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.81-92, October 16-18, 1996, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Reliability, Theory

Keywords:
data flow analysis, interprocedural pointer analysis