Authors: David Grove, Greg DeFouw, Jeffrey Dean, and Craig Chambers
Citation: Proceedings of the 1997 ACM SIGPLAN conference on Object-oriented programming
systems, languages and applications October 5 - 9, 1997, Atlanta, GA USA.
This paper was selected as the Most Influential Paper of OOPSLA 1997
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.
ACM Definitive Copy
Preprint PDF
Conference Talk
Brief Retrospective Talk given at OOPSLA 2007
ACM - Copyright © 1997 by Association for Computing Machinery, Inc.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.