A framework for call graph construction algorithms
David Grove, Craig Chambers · ACM Transactions on Programming Languages and Systems · 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.
Cited by 256 works. doi:10.1145/506315.506316 Open-access PDF
Authors
References
- The Java Language Specification
- Abstract interpretation
- Efficiency of a Good But Not Linear Set Union Algorithm
- A unified approach to global program optimization
- Efficient implementation of the smalltalk-80 system
- Global Data Flow Analysis and Iterative Algorithms
- Points-to analysis in almost linear time
- Two approaches to interprocedural data flow analysis
- Efficient context-sensitive pointer analysis for C programs
- Context-sensitive interprocedural points-to analysis in the presence of function pointers