Automatic generation and management of interprocedural program analyses

ABSTRACT

We have designed and implemented an interprocedural program analyzer generator, called system Z. Our goal is to automate the generation and management of semantics-based interprocedural program analysis for a wide range of target languages. System Z is based on the abstract interpretation framework. The input to system Z is a high-level specification of an abstract interpreter. The output is a C code for the specified interprocedural program analyzer. The system provides a high-level command set (called projection expressions) in which the user can tune the analysis in accuracy and cost. The user writes projection expressions for selected domains; system Z takes care of the remaining things so that the generated analyzer conducts an analysis over the projected domains, which will vary in cost and accuracy according to the projections. We demonstrate the system's capabilities by experiments with a set of generated analyzers which can analyze C, FORTRAN, and SCHEME programs.

REFERENCES

• 1: S. Abramsky , C. Hankin, Abstract interpretation of declarative languages, Halsted Press, New York, NY, 1987
• 2: Jeffrey M. Barth, An interprocedural data flow analysis algorithm, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-131, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512962]
• 3: Geoffrey L. Burn. Abstract Interpretation and the Parallel Evaluation ofFunctionalLanguages. PhD thesis, Department of Computing, Imperial College, University of London, March 1987.
• 4: Geoffrey Burn, Lazy functional languages: abstract interpretation and compilation, MIT Press, Cambridge, MA, 1991
• 5: D. Callahan, The program summary graph and flow-sensitive interprocedual data flow analysis, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.47-56, June 20-24, 1988, Atlanta, Georgia, United States
• 6: 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]
• 7: 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]
• 8: Harald Ganzinger , Robert Giegerich , Ulrich Möncke , Reinhard Wilhelm, A truly generative semantics-directed compiler generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.172-184, June 23-25, 1982, Boston, Massachusetts, United States
• 9: Williams Ludwell Harrison UI. Generalized iteration space and the parallelization of symbolic programs (extended abstract). In Proceedings of the workshop on compilation of (symbolic) Ianguages for parallel computers, October 1991.
• 10: Williams Ludwell Harrison lII, Semantic Analysis of Symbolic Programs for Automatic Parallelization. Book in preparation, 1992.
• 11: Williams Ludwell Harrison, III , Zahira Ammarguellat, A Program's Eye View of Miprac, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.512-537, August 03-05, 1992
• 12: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 13: Paul Hudak , Jonathan Young, Collecting interpretations of expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.269-290, April 1991 [doi>10.1145/103135.103139]
• 14: Kai Koskimies , Otto Nurmi , Jukka Pakki, The design of a language processor generator, Software—Practice & Experience, v.18 n.2, p.107-135, Feb., 1988 [doi>10.1002/spe.4380180202]
• 15: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 16: D.E. Rutherford. Introduction to Lattice Theory. Hafner Publishing Company, New York, 1965.
• 17: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 18: Masataka Sassa, Rie and Jun: towards the generation of all compiler phases, Proceedings of the third international workshop on Compiler compilers, p.56-70, February 1991, Schwerin, Germany
• 19: Bernhard Steffen, Data Flow Analysis as Model Checking, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.346-365, September 24-27, 1991
• 20: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 21: Steven W. K. Tjiang , John L. Hennessy, Sharlit—a tool for building optimizers, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.82-93, June 15-19, 1992, San Francisco, California, United States
• 22: G. A. Venkatesh, A framework for construction and evaluation of high-level specifications for program analysis techniques, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.1-12, June 19-23, 1989, Portland, Oregon, United States
• 23: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]
• 24: Reinhard Wilhelm. Global flow analysis and optimization in the mug2 compiler generating system. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 5. Prentice-Hall, 1981.
• 25: Kwangkeun Yi and Williams Ludwell Harrison HI. Z: Interprocedural data flow analysis specification language (in preparation). Technical report, Center for Supercomputing Research and Development, University of Illinois at Urbarla- Champaign, 1992.
• 26: Jonathan Hood Young, The theory and practice of semantic program analysis for higher-order functional programming languages, 1989

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications

          Nouns: Z
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Experimentation, Languages