Fast interprocedural class analysis
Greg DeFouw, David Grove, Craig Chambers · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1998
Previous algorithms for interprocedural control flow analysis of higher-order and/or object-oriented languages have been described that perform propagation or constraint satisfaction and take O(N3) time (such as Shivers's O-CFA and Heintze's set-based analysis), or unification and take O(Nα (N,N) time (such as Steensgaard's pointer analysis), or optimistic reachability analysis and take O(N) time (such as Bacon and Sweeney's Rapid Type Analysis). We describe a general parameterized analysis framework that integrates propagation-based and unification-based analysis primitives and optimistic reachability analysis, whose instances mimic these existing algorithms as well as several new algorithms taking O(N), O(Nα(N,N)), O(N2), and O(N2α(N,N)) time; our O(N) and O(Nα(N,N)) algorithms produce more precise results than the previous algorithms with these complexities. We implemented our algorithm framework in the Vortex optimizing compiler, and we measured the cost and benefit of these interprocedural analysis algorithms in practice on a collection of substantial Cecil and Java programs.
Cited by 82 works. doi:10.1145/268946.268965
Authors
References
- The Java Language Specification
- Efficiency of a Good But Not Linear Set Union Algorithm
- Efficient implementation of the smalltalk-80 system
- Points-to analysis in almost linear time
- Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis
- Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language
- Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language
- Fast static analysis of C++ virtual function calls
- TS: an optimizing compiler for smalltalk
- Control flow analysis in scheme