Call graph construction in object-oriented languages
David Grove, Greg DeFouw, Jeffrey Dean et al. · ACM SIGPLAN Notices · 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.
Cited by 66 works. doi:10.1145/263700.264352
Authors
References
- The Java Language Specification
- Abstract interpretation
- 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
- Efficient context-sensitive pointer analysis for C programs
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Pizza into Java
- Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language