Call Graph Construction in Object-Oriented Languages
David Grove,
Greg DeFouw,
Jeffrey Dean, and
Craig Chambers
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.
Published in the proceedings of OOPSLA'97, Atlanta, GA, October, 1997.
To get the PostScript file, click
here.
Cecil/Vortex
Project