Environment analysis via ΔCFA

ABSTRACT

We describe a new program-analysis framework, based on CPS and procedure-string abstractions, that can handle critical analyses which the k-CFA framework cannot. We present the main theorems concerning correctness, show an application analysis, and describe a running implementation.

REFERENCES

• 1: 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]
• 2: 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]
• 3: HARRISON, W. L. The interprocedural analysis and automatic parallelization of Scheme programs. Lisp and Symbolic Computation 2, 3/4 (Oct. 1989), 179--396.
• 4: 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]
• 5: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 6: MIGHT, M., AND SHIVERS, O. Environmental analysis of higher-order languages. In preparation. Current draft available at http://matt.might.net/research/drafts/, July 2005.
• 7: MOSSIN,C. Flow Analysis of Typed Higher-Order Programs. PhD thesis, DIKU, University of Copenhagen, Denmark, 1997. Technical Report DIKU-TR-97/1.
• 8: SESTOFT, P. Replacing function parameters by global variables. Master's thesis, DIKU, University of Copenhagen, Denmark, Oct. 1988.
• 9: SHARIR, M., AND PNUELI, A. Two approaches to interprocedural data flow analysis. In Program Flow Analysis, Theory and Application, S. Muchnick and N. Jones, Eds. Prentice Hall International, 1981, ch. 7.
• 10: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 11: SHIVERS, O., AND FISHER, D. Multi-return function call. Journal of Functional Programming. To appear.
• 12: STECKLER,P.,AND WAND, M. Selective thunkification. In Proceedings of the First International Static Analysis Symposium (SAS'94) (Namur, Belgium, Sept. 1994), vol. 864 of Lecture Notes in Computer Science, Springer, pp. 162--178.
• 13: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 14: Mitchell Wand , Igor Siveroni, Constraint systems for useless variable elimination, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.291-302, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292567]
• 15: Mitchell Wand , Paul Steckler, Selective and lightweight closure conversion, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.435-445, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178044]

INDEX TERMS

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

General Terms:
Languages

Keywords:
CPS, continuations, delta-CFA, environment analysis, flow analysis, functional languages, inlining, lambda calculus, program analysis, super-beta