A Framework For Call Graph
Construction Algorithms
David Grove and Craig Chambers
ACM Transactions on Programming Languages and Systems (TOPLAS),
Vol. 23, No. 6, pp. 685-746, November 2001.
A large number of call graph construction algorithms for
object-oriented and functional languages have been proposed, each
embodying different tradeoffs between analysis cost and call graph
precision. In this article we present a unifying framework for
understanding call graph construction algorithms and an empirical
comparison of a representative set of algorithms. We first present a
general parameterized algorithm that encompasses many well-known and
novel call graph construction algorithms. We have implemented this
general algorithm in the Vortex compiler infrastructure, a mature,
multilanguage, optimizing compiler. The Vortex implementation provides
a "level playing field" for meaningful cross-algorithm performance
comparisons. The costs and benefits of a number of call graph
construction algorithms are empirically assessed by applying their
Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of
code) Cecil and Java programs. For many of these applications,
interprocedural analysis enabled substantial speed-ups over an already
highly optimized baseline. Furthermore, a significant fraction of
these speed-ups can be obtained through the use of a scalable,
near-linear time call graph construction algorithm.
To get the PDF file, click
here.
Cecil/Vortex
Project