Call graph construction in object-oriented languages

ABSTRACT

Interprocedural analyses enable optimizing compilers to more precisely model the effects of non-inlined procedure calls, potentially resulting in substantial increases in application performance. Applying interprocedural analysis to programs written in object-oriented or functional languages is complicated by the difficulty of constructing an accurate program call graph. This paper presents a parameterized algorithmic framework for call graph construction in the presence of message sends and/or first class functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empirically assess these algorithms by applying them to a suite of medium-sized programs written in Cecil and Java, reporting on the relative cost of the analyses, the relative precision of the constructed call graphs, and the impact of this precision on the effectiveness of a number of interprocedural optimizations.

REFERENCES

• Agesen 94: Ole Agosen. Constraint-Based Type inference and Pa/ametrie Polymorphism. In First International Static Analysis Symposium, September 1994.
• Agesen 95: 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
• Agesen 96: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• Alt & Martin 95: Martin Alt , Florian Martin, Generation of Efficient Interprocedural Analyzers with PAG, Proceedings of the Second International Symposium on Static Analysis, p.33-50, September 25-27, 1995
• Bacon & Sweeney 96: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• Bracha & Griswold 93: Gilad Bracha , David Griswold, Strongtalk: typechecking Smalltalk in a production environment, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.215-230, September 26-October 01, 1993, Washington, D.C., United States
• Callahan et. al.90: David Callahan , Alan Carle , Mary Wolcott Hall , Ken Kennedy, Constructing the Procedure Call Multigraph, IEEE Transactions on Software Engineering, v.16 n.4, p.483-487, April 1990 [doi>10.1109/32.54302]
• Chambers & Ungar 89: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• Chambers & Ungar 90: 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
• 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.
• Cooper et. al. 92: Keith D. Cooper, Mary W. Hall, and Ken Kennedy, Procedure Cloning. In Proceedings of 1992 IEEE lnternation, al Conference on Computer Languages, pages 96--105, Oakland, CA, April 1992.
• Cousot & Cousot 77: 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]
• Dean 96: Jeffrey Adgate Dean , Craig Chambers, Whole-program optimization of object-oriented languages, 1996
• Dean et. al. 95: 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
• Dean et. al. 96: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
• DeFouw et. al. 97: Greg DeFouw, David Grove, and Craig Chambers. Fast Interprocedural Class Analysis. Technical Report TR-97- 07-02, Department of Computer Science and Engineering. University of Washington, July 1997.
• Deutsch & Schiffman 84: 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]
• Diwan et. al. 96: 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
• Emami et. al. 94: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• Gosling et. al, 96: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Grove et. al. 95: 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
• Hall & Kennedy 92: Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992 [doi>10.1145/151640.151643]
• Hölzle & Agesen 96: Urs Htilzle and Ole Agesen. Dy_narnie vs. Static Optimization Techniques for Object-Oriented Languages. Theory and Practice of Object Systems, i(3), 1996._
• Hölzle & Ungar 94: 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
• Jagannathan & Weeks 95: 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]
• Johnson 88: Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.18-26, September 25-30, 1988, San Diego, California, United States
• Kam & Ullman 76: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• Kildall 73: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• Kranz 88: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• Lakhotia 93: Arun Lakhotia, Constructing call multigraphs using dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158647]
• Landi et. al. 93: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
• Nielson & Nielson 97: 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]
• Odersky & Wadler 97: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• Oxhøj et.al. 92: Nicholas Oxhøj , Jens Palsberg , Michael I. Schwartzbach, Making Type Inference Practical, Proceedings of the European Conference on Object-Oriented Programming, p.329-349, June 29-July 03, 1992
• Palsberg & Schwartzbach 91: 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
• Plevyak & Chien 94: 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
• Plevyak & Chien 95: John Plevyak , Andrew A. Chien, Type Directed Cloning for Object-Oriented Programs, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.566-580, August 10-12, 1995
• plevyak 96: John Bradley Plevyak , Andrew Chien, Optimization of object-oriented and concurrent programs, 1996
• Ryder 79: Barbara Ryder. Constructing the Call Graph of a Program. IEEETransactions on Software Engineering, 5(3):216- 225, 1979.
• Shivers 88: 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
• Shivers 91a: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• Shivers 91b: Olin Shivers. Data Flow Analysis and Type Recovery in Scheme. In Topics in Advanced Language Implementation. M1T Press, 1991. Edited by Peter Lee. -
• Steensgaard 94: Bjarne Steensgaard. A Polyvariant Closure Analysis with Dynamic Abstraction. Unpublished manuscript, 1994.
• Steensgaard 96: 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]
• Stefanescu & Zhou 94: Dan Stefanescu , Yuli Zhou, An equational framework for the flow analysis of higher order functional programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.318-327, June 27-29, 1994, Orlando, Florida, United States
• Wilson & Lam 95: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, ACM SIGPLAN Notices, v.30 n.6, p.1-12, June 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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