Incremental and demand-driven points-to analysis using logic programming

ABSTRACT

Several program analysis problems can be cast elegantly as a logic program. In this paper we show how recently-developed techniques for incremental evaluation of logic programs can be refined and used for deriving practical implementations of incremental program analyzers. Incremental program analyzers compute the changes to the analysis information due to small changes in the input program rather than re-analyzing the program. Demand-driven analyzers compute only the information requested by the client analysis/optimization. We describe a framework based on logic programming for implementing program analyses that combines incremental and demand driven techniques. We show the effectiveness of this approach by building a practical incremental and demand-driven context insensitive points-to analysis and evaluating this implementation for analyzing C programs with 10-70K lines of code. Experiments show that our technique can compute the changes to analysis information due to small changes in the input program in, on the average, 6% of the time it takes to reanalyze the program from scratch, and with little space overhead.

REFERENCES

• 1: Gagan Agrawal , Jinqian Li , Qi Su, Evaluating a Demand Driven Technique for Call Graph Construction, Proceedings of the 11th International Conference on Compiler Construction, p.29-45, April 08-12, 2002
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: L. O. Anderson. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, Unversity of Copenhagen, 1994.
• 4: 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
• 5: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• 6: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 7: Michael G. Burke , Barbara G. Ryder, A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithms, IEEE Transactions on Software Engineering, v.16 n.7, p.723-728, July 1990 [doi>10.1109/32.56098 ]
• 8: Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
• 9: M. D. Carroll , B. G. Ryder, Incremental data flow analysis via dominator and attribute update, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.274-284, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73584]
• 10: Weidong Chen , David S. Warren, Tabled evaluation with delaying for general logic programs, Journal of the ACM (JACM), v.43 n.1, p.20-74, Jan. 1996 [doi>10.1145/227595.227597]
• 11: Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.117-126, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 12: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A demand-driven analyzer for data flow testing at the integration level, Proceedings of the 18th international conference on Software engineering, p.575-584, March 25-29, 1996, Berlin, Germany
• 13: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical framework for demand-driven interprocedural data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.992-1030, Nov. 1997 [doi>10.1145/267959.269970]
• 14: 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
• 15: Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
• 16: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, Polymorphic versus Monomorphic Flow-Insensitive Points-to Analysis for C, Proceedings of the 7th International Symposium on Static Analysis, p.175-198, June 29-July 01, 2000
• 17: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 18: S. Guyer and C. Lin. Client-driven pointer analysis. In Static Analysis Symposium, pages 214--236, 2003.
• 19: Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.24-34, June 2001, Snowbird, Utah, United States
• 20: 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
• 21: 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]
• 22: Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.104-115, October 12-15, 1995, Washington, D.C., United States
• 23: 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
• 24: Donglin Liang , Mary Jean Harrold, Efficient Computation of Parameterized Pointer Information for Interprocedural Analyses, Proceedings of the 8th International Symposium on Static Analysis, p.279-298, July 16-18, 2001
• 25: Thomas J. Marlowe , Barbara G. Ryder, An efficient hybrid algorithm for incremental data flow analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, December 1989, San Francisco, California, United States [doi>10.1145/96709.96728]
• 26: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 27: L. L. Pollock , M. L. Soffa, An Incremental Version of Iterative Data Flow Analysis, IEEE Transactions on Software Engineering, v.15 n.12, p.1537-1549, December 1989 [doi>10.1109/32.58766 ]
• 28: Lori L. Pollock , Mary Lou Soffa, Incremental global reoptimization of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.2, p.173-200, April 1992 [doi>10.1145/128861.128865]
• 29: R. Ramakrishnan. Magic Templates: A spellbinding approach to logic programming. In JICSLP, 1988.
• 30: P. Rao, C. R. Ramakrishnan, and I. V. Ramakrishnan. A thread in time saves tabling time. In Joint International Conference/Symposium on Logic Programming. MIT Press, 1996.
• 31: T. W. Reps. Demand interprocedural program analysis using logic databases. In Workshop on Programming with Logic Databases, ILPS, pages 163--196, 1993.
• 32: Barbara G. Ryder , Marvin C. Paull, Incremental data-flow analysis algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.1, p.1-50, Jan. 1988 [doi>10.1145/42192.42193]
• 33: D. Saha and C. R. Ramakrishnan. Incremental and demand-driven points-to analysis using logic programming. Downloads are available at www.lmc.cs.sunysb.edu/~dsaha/incr_pta.
• 34: D. Saha and C. R. Ramakrishnan. Incremental evaluation of tabled logic programs. In International Conference on Logic Programming, volume 2916 of LNCS, pages 389--406, 2003.
• 35: Oleg Sokolsky , Scott A. Smolka, Incremental Model Checking in the Modal Mu-Calculus, Proceedings of the 6th International Conference on Computer Aided Verification, p.351-363, June 21-23, 1994
• 36: 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]
• 37: Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325706]
• 38: Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
• 39: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 40: Frédéric Vivien , Martin Rinard, Incrementalized pointer and escape analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.35-46, June 2001, Snowbird, Utah, United States
• 41: David S. Warren, Memoing for logic programs, Communications of the ACM, v.35 n.3, p.93-111, March 1992 [doi>10.1145/131295.131299]
• 42: 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
• 43: XSB. The XSB logic programming system. Available from http://xsb.sourceforge.net.
• 44: Jyh-shiarn Yur , Barbara G. Ryder , William A. Landi, An incremental flow- and context-sensitive pointer aliasing analysis, Proceedings of the 21st international conference on Software engineering, p.442-451, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302676]
• 45: Jyh-Shiarn Yur , Barbara G. Ryder , William A. Landi , Phil Stocks, Incremental analysis of side effects for C software system, Proceedings of the 19th international conference on Software engineering, p.422-432, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253369]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

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

Keywords:
demand-drive analysis, incremental analysis, logic programming, pointer analysis