Projection merging: reducing redundancies in inclusion constraint graphs

ABSTRACT

Inclusion-based program analyses are implemented by adding new edges to directed graphs. In most analyses, there are many different ways to add a transitive edge between two nodes, namely through each different path connecting the nodes. This path redundancy limits the scalability of these analyses. We present projection merging, a technique to reduce path redundancy. Combined with cycle elimination [7], projection merging achieves orders of magnitude speedup of analysis time on programs over that of using cycle elimination alone.

REFERENCES

• 1: Alexander Aiken , Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su, A Toolkit for Constructing Type- and Constraint-Based Program Analyses, Proceedings of the Second International Workshop on Types in Compilation, p.78-96, March 25-27, 1998
• 2: AIKEN, A., AND WIMMERS, E. Solving Systems of Set Constraints. in Symposium on Logic in Computer Science (June 1992), pp. 329-340.
• 3: Alexander Aiken , Edward L. Wimmers, Type inclusion constraints and type inference, Proceedings of the conference on Functional programming languages and computer architecture, p.31-41, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165188]
• 4: Alexander Aiken , Edward L. Wimmers , T. K. Lakshman, Soft typing with conditional types, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177847]
• 5: ANDERSEN, L. O. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. DIKU report 9a/~9.
• 6: Manuel Alfred Fahndrich , Alexander Aiken, Bane: a library for scalable constraint-based program analysis, 1999
• 7: 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
• 8: Cormac Flanagan , Matthew Flatt , Shriram Krishnamurthi , Stephanie Weirich , Matthias Felleisen, Catching bugs in the web of program invariants, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.23-32, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 9: Jeffrey S. Foster , Manuel Fahndrich , Alexander Aiken, Flow-Insensitive Points-to Analysis with Term and Set Constraints, University of California at Berkeley, Berkeley, CA, 1997
• 10: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 11: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 12: HEINTZE, N., AND JAFFAR, j. A decision procedure for a class of Herbrand set constraints. In Symposium on Logic in Computer Science (June 1990), pp. 42-51.
• 13: Nevin Heintze , David McAllester, Linear-time subtransitive control flow analysis, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.261-272, June 16-18, 1997, Las Vegas, Nevada, United States
• 14: Nevin Heintze , David McAllester, On the Cubic Bottleneck in Subtyping and Flow Analysis, Proceedings of the 12th Annual IEEE Symposium on Logic in Computer Science, p.342, June 29-July 02, 1997
• 15: Neil D. Jones , Steven S. Muchnick, Flow analysis and optimization of LISP-like structures, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.244-256, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567776]
• 16: Simon Marlow , Philip Wadler, A practical subtyping system for Erlang, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.136-149, June 09-11, 1997, Amsterdam, The Netherlands
• 17: David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.74-89, June 12-13, 1997, Amsterdam, The Netherlands
• 18: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 19: Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
• 20: REYNOLDS, J. C. Automatic Computation of Data Set Definitions. Information Processing 68. North-Holland, 1969, pp. 456-461.
• 21: 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]
• 22: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 23: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Theory