Semi-sparse flow-sensitive pointer analysis

ABSTRACT

Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-sensitivity, and while there has been significant recent progress regarding scalable context-sensitive pointer analysis, relatively little progress has been made in improving the scalability of flow-sensitive pointer analysis.

This paper presents a new interprocedural, flow-sensitive pointer analysis algorithm that combines two ideas-semi-sparse analysis and a novel use of BDDs-that arise from a careful understanding of the unique challenges that face flow-sensitive pointer analysis. We evaluate our algorithm on 12 C benchmarks ranging from 11K to 474K lines of code. Our fastest algorithm is on average 197x faster and uses 4.6x less memory than the state of the art, and it can analyze programs that are an order of magnitude larger than the previous state of the art.

REFERENCES

• 1: John Aycock , R. Nigel Horspool, Simple Generation of Static Single-Assignment Form, Proceedings of the 9th International Conference on Compiler Construction, p.110-124, March 25-April 02, 2000
• 2: Thomas Ball , Rupak Majumdar , Todd Millstein , Sriram K. Rajamani, Automatic predicate abstraction of C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.203-213, June 2001, Snowbird, Utah, United States
• 3: Rajeev Barua , Walter Lee , Saman Amarasinghe , Anant Agarawal, Compiler Support for Scalable and Efficient Memory Systems, IEEE Transactions on Computers, v.50 n.11, p.1234-1247, November 2001 [doi>10.1109/12.966497]
• 4: Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 5: Gianfranco Bilardi , Keshav Pingali, Algorithms for computing the static single assignment form, Journal of the ACM (JACM), v.50 n.3, p.375-425, May 2003 [doi>10.1145/765568.765573]
• 6: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 7: Walter Chang , Brandon Streiff , Calvin Lin, Efficient and extensible security enforcement using dynamic data flow analysis, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455778]
• 8: 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
• 9: Peng-Sheng Chen , Ming-Yu Hung , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Compiler support for speculative multithreading architecture with probabilistic points-to analysis, ACM SIGPLAN Notices, v.38 n.10, October 2003
• 10: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, ACM SIGPLAN Notices, v.35 n.5, p.57-69, May 2000
• 11: 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]
• 12: Fred C. Chow , Sun Chan , Shin-Ming Liu , Raymond Lo , Mark Streich, Effective Representation of Aliases and Indirect Memory Operations in SSA Form, Proceedings of the 6th International Conference on Compiler Construction, p.253-267, April 24-26, 1996
• 13: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 14: Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.36-45, June 21-25, 1993, Albuquerque, New Mexico, United States
• 15: Ron K. Cytron , Jeanne Ferrante, Efficiently computing Φ-nodes on-the-fly, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.487-506, May 1995 [doi>10.1145/203095.203099]
• 16: 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
• 17: Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146254]
• 18: 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]
• 19: D. Goyal, An Improved Intra-procedural May-alias Analysis Algorithm, New York University, New York, NY, 1999
• 20: Samuel Z. Guyer , Calvin Lin, Error checking with client-driven pointer analysis, Science of Computer Programming, v.58 n.1-2, p.83-114, October 2005 [doi>10.1016/j.scico.2005.02.005]
• 21: Brian Hackett , Radu Rugina, Region-based shape analysis with tracked locations, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.310-323, January 12-14, 2005, Long Beach, California, USA
• 22: Ben Hardekopf , Calvin Lin, The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 23: B. Hardekopf and C. Lin. Exploiting pointer and location equivalence to optimize pointer analysis. In International Static Analysis Symposium (SAS), pages 265--280, 2007.
• 24: Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.97-105, June 17-19, 1998, Montreal, Quebec, Canada
• 25: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 26: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 27: 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]
• 28: 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
• 29: Vineet Kahlon, Bootstrapping: a technique for scalable flow and context-sensitive pointer alias analysis, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 30: H.-S. Kim, E. M. Nystrom, R. D. Barnes, and W.-M. W. Hwu. Compaction algorithm for precise modular context-sensitive points--to analysis. Technical report IMPACT-03-03, Center for Reliable and High Performance Computing, University of Illinois, Urbana-Champaign, 2003.
• 31: Christopher Lapkowski , Laurie J. Hendren, Extended SSA numbering: introducing SSA properties to languages with multi-level pointers, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.23, November 12-14, 1996, Toronto, Ontario, Canada
• 32: C. Lattner. LLVM: An infrastructure for multi-stage optimization. Master's thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Dec 2002.
• 33: C. Lattner and V. Adve. Data structure analysis: An efficient context-sensitive heap analysis. Technical Report UIUCDCS-R-2003-2340, Computer Science Dept, University of Illinois at Urbana-Champaign, 2003.
• 34: O. Lhotak, S. Curial, and J. Amaral. Using ZBDDs in points-to analysis. In Workshops on Languages and Compilers for Parallel Computing (LCPC), 2007.
• 35: J. Lind-Nielson. BuDDy, a binary decision package.
• 36: Ana Milanova , Barbara G. Ryder, Annotated Inclusion Constraints for Precise Flow Analysis, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.187-196, September 25-30, 2005 [doi>10.1109/ICSM.2005.24]
• 37: Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587062]
• 38: D. Novillo. Design and implementation of Tree SSA, 2004.
• 39: E. M. Nystrom, H.-S. Kim, and W. mei W. Hwu. Bottom-up and top-down context-sensitive summary-based pointer analysis. In International Symposium on Static Analysis, pages 165--180, 2004.
• 40: David J. Pearce , Paul H. J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis for C, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996835]
• 41: D. J. Pearce, P. H. J. Kelly, and C. Hankin. Online cycle detection and difference propagation for pointer analysis. In 3rd International IEEE Workshop on Source Code Analysis and Manipulation (SCAM), pages 3--12, 2003.
• 42: G. Ramalingam, On sparse evaluation representations, Theoretical Computer Science, v.277 n.1-2, p.119-147, April 28, 2002 [doi>10.1016/S0304-3975(00)00315-7]
• 43: John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
• 44: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, ACM SIGPLAN Notices, v.35 n.5, p.47-56, May 2000
• 45: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 46: Marc Shapiro, II , Susan Horwitz, The Effects of the Precision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 47: T. B. Tok, S. Z. Guyer, and C. Lin. Efficient flow-sensitive interprocedural data-flow analysis in the presence of pointers. In 15th International Conference on Compiler Construction (CC), pages 17--31, 2006.
• 48: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 49: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 50: Jianwen Zhu, Symbolic pointer analysis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.150-157, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774594]
• 51: Jianwen Zhu, Towards scalable flow and context sensitive pointer analysis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065798]
• 52: Jianwen Zhu , Silvian Calman, Symbolic pointer analysis revisited, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Languages

Keywords:
alias analysis, pointer analysis