A comparison of algorithms for interprocedural class analysis

ABSTRACT

Message passing overhead is often a substantial source of runtime overhead in object-oriented applications. To combat this performance problem, a number of techniques have been developed to convert message sends into statically-bound procedure calls, which are then amenable to traditional compiler optimizations such as inline expansion. In this paper, we examine one such technique, interprocedural class analysis. We develop a general model for describing interprocedural class analysis algorithms, present several previously developed algorithms using this model, and empirically assess the algorithms by applying them to a suite of Cecil applications.

REFERENCES

• 1: Urs Hölzle , Ole Agesen, Dynamic versus static optimization techniques for object-oriented languages, Theory and Practice of Object Systems, v.1 n.3, p.167-188, Fall 1995
• 2: Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
• 3: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• 4: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
• 5: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, ACM SIGPLAN Notices, v.25 n.6, p.150-164, Jun. 1990
• 6: {Chambers 93} Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report TR- 93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993.
• 7: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 8: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 9: David Grove, The impact of interprocedural class analysis on optimization, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.25, November 07-09, 1995, Toronto, Ontario, Canada
• 10: 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
• 11: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 12: Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, ACM SIGPLAN Notices, v.23 n.11, p.18-26, Nov. 1988
• 13: Jens Palsberg , Michael I. Schwartzbach, Type substitution for object-oriented programming, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.151-160, September 1990, Ottawa, Canada
• 14: {Phillips & Shepard 94} G. Phillips and T. Shepard. Static Typing Without Explicit Types. Unpublished report, Dept. of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, Ontario, Canada, 1994.
• 15: 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
• 16: 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
• 17: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 18: {Shivers 91b} Olin Shivers. Topics in Advanced Language Implementation (edited by Peter Lee), chapter Data Flow Analysis and Type Recovery in Scheme. MIT Press, 1991.
• 19: Jan Vitek , R. Nigel Horspool , James S. Uhl, Compile-Time Analysis of Object-Oriented Programs, Proceedings of the 4th International Conference on Compiler Construction, p.236-250, October 05-07, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Object-oriented design methods
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines; Classes and objects

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory