Polymorphic splitting: an effective polyvariant flow analysis

ABSTRACT

This article describes a general-purpose program analysis that computes global control-flow and data-flow information for higher-order, call-by-value languages. The analysis employs a novel form of polyvariance called polymorhic splitting that uses let-expressions as syntactic clues to gain precision. The information derived from the analysis is used both to eliminate run-time checks and to inline procedure. The analysis and optimizations have been applied to a suite of Scheme programs. Experimental results obtained from the prototype implementation indicate that the analysis is extremely precise and has reasonable cost. Compared to monovariant flow analyses such as 0CFA, or analyses based on type inference such as soft typing, the analysis eliminates significantly more run-time checks. Run-time check elimination and inlining together typically yield a 20 to 40% performance improvement for the benchmark suite, with some programs running four times as fast.

REFERENCES

• 1: Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
• 2: Alexander Aiken , Manuel Fähndrich, Dynamic typing and subtype inference, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.182-191, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224201]
• 3: 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]
• 4: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 5: J. Michael Ashley, A practical and flexible flow analysis for higher-order languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-194, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237773]
• 6: BARENDREGT, H. P. 1984. The Lambda Calculus: Its Syntax and Semantics, Revised ed. Studies in Logic and the Foundations of Mathematics, vol. 103. North-Holland, Amsterdam.
• 7: BEER, R. D. 1987. Preliminary report on a practical type inference system for Common Lisp. Lisp Pointers 1, 2, 5-11.
• 8: BULYONKOV, M. 1984. Polyvariant mixed computation for analyzer programs. Acta Inf. 21, 473-484.
• 9: Robert Cartwright , Mike Fagan, Soft typing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.278-292, June 24-28, 1991, Toronto, Ontario, Canada
• 10: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 11: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 12: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams, IV , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand , William Clinger , Jonathan Rees, Revised report on the algorithmic language scheme, ACM SIGPLAN Lisp Pointers, v.IV n.3, p.1-55, July, 1991 [doi>10.1145/382130.382133]
• 13: Keith D. Cooper , Mary W. Hall , Linda Torczon, An experiment with inline substitution, Software—Practice & Experience, v.21 n.6, p.581-601, June 1991 [doi>10.1002/spe.4380210604]
• 14: Keith D. Cooper , Mary W. Hall , Linda Torczon, Unexpected side effects of inline substitution: a case study, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.22-32, March 1992 [doi>10.1145/130616.130619]
• 15: CURRY, H. B. AND FEYS, R. 1958. Combinatory Logic. Vol. 1. North-Holland, Amsterdam.
• 16: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• 17: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 18: Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
• 19: R. Kent Dybvig, The SCHEME programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 20: Marc Feeley , Marcel Turcotte , Guy Lapalme, Using Multilisp for solving constraint satisfaction problems: an application to nucleic acid 3D structure determination, Lisp and Symbolic Computation, v.7 n.2-3, p.231-247, June 1994 [doi>10.1007/BF01018696]
• 21: FELLEISEN, M. AND FRIEDMAN, D. P. 1986. Control operators, the SECD-machine, and the A- calculus. In Formal Description of Programming Concepts. Vol. 3. North-Holland, Amsterdam, 193-217.
• 22: FLANAGAN, C. AND FELLEISEN, M. 1995. Set-based analysis for full Scheme and its use in softtyping. Tech. Rep. TR95-253, Rice Univ., Houston, Tex.
• 23: GREENGARD, L. 1987. The Rapid Evaluation of Potential Fields in Particle Systems. ACM Press, New York.
• 24: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
• 25: 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
• 26: Fritz Henglein, Global tagging optimization by type inference, Proceedings of the 1992 ACM conference on LISP and functional programming, p.205-215, June 22-24, 1992, San Francisco, California, United States
• 27: Fritz Henglein , Jakob Rehof, Safe polymorphic type inference for a dynamically typed language: translating Scheme to ML, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.192-203, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224203]
• 28: HINDLEY, R. 1969. The principal type-scheme of an object in combinatory logic. Trans. Am. Math. Soc. 146, 29-60.
• 29: Suresh Jagannathan , Stephen Weeks, A unified treatment of flow analysis in higher-order languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.393-407, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199536]
• 30: Suresh Jagannathan , Stephen Weeks , Andrew K. Wright, Type-Directed Flow Analysis for Typed Intermediate Languages, Proceedings of the 4th International Symposium on Static Analysis, p.232-249, September 08-10, 1997
• 31: Suresh Jagannathan , Andrew K. Wright, Effective Flow Analysis for Avoiding Run-Time Checks, Proceedings of the Second International Symposium on Static Analysis, p.207-224, September 25-27, 1995
• 32: Suresh Jagannathan , Andrew Wright, Flow-directed inlining, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.193-205, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 33: 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]
• 34: Marc A. Kaplan , Jeffrey D. Ullman, A Scheme for the Automatic Inference of Variable Types, Journal of the ACM (JACM), v.27 n.1, p.128-145, Jan. 1980 [doi>10.1145/322169.322181]
• 35: K.-L. Ma , R. R. Kessler, TICL—a type inference system for common Lisp, Software—Practice & Experience, v.20 n.6, p.593-623, June 1990 [doi>10.1002/spe.4380200606]
• 36: Robert A. MacLachlan, The Python compiler for CMU Common Lisp, Proceedings of the 1992 ACM conference on LISP and functional programming, p.235-246, June 22-24, 1992, San Francisco, California, United States
• 37: ~/{ILNER, R. 1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 348-375.
• 38: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 39: John C. Mitchell, Type systems for programming languages, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 40: Flemming Nielson , Hanne Riis Nielson, Infinitary control flow analysis: a collecting semantics for closure analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.332-345, January 15-17, 1997, Paris, France [doi>10.1145/263699.263745]
• 41: Jens Palsberg, Closure analysis in constraint form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.47-62, Jan. 1995 [doi>10.1145/200994.201001]
• 42: PANDE, H. D. AND RYDER, B. G. 1994. Static type determination for C++. In Usenix C-I--I- Conference Proceedings. MIT Press, Cambridge, Mass., 85-97.
• 43: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
• 44: Manuel Serrano , Marc Feeley, Storage use analysis and its applications, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.50-61, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 45: SESTOFT, P. 1988. Replacing function parameters by global variables. M.S. thesis, DIKU, Univ. of Copenhagen, Denmark.
• 46: SHIVERS, O. 1990. Data-flow analysis and type recovery in Scheme. In Topics in Advanced Language Implementation. MIT Press, Cambridge, Mass.
• 47: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 48: Peter Steenkiste , John Hennessy, Tags and type checking in LISP: hardware and software approaches, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.50-59, October 1987, Palo Alto, California, United States
• 49: Andrew K. Wright, Simple imperative polymorphism, Lisp and Symbolic Computation, v.8 n.4, p.343-355, Dec. 1995 [doi>10.1007/BF01018828]
• 50: Andrew K. Wright , Robert Cartwright, A practical soft type system for scheme, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.87-152, Jan. 1997 [doi>10.1145/239912.239917]
• 51: WRIGHT, A. K. AND DUBA, B. F. 1993. Pattern matching for Scheme. Unpublished document. Available from http:////www.intertrust.com//star//wright//code.html.
• 52: ZHAO, F. 1987. An O(N) algorithm for three-dimensional N-body simulations. M.S. thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, Mass.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

General Terms:
Experimentation, Performance

Keywords:
flow analysis, inlining, polyvariance, run-time checks