Fast Interprocedural Class Analysis

Greg DeFouw, David Grove, and Craig Chambers
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 0-CFA and Heintze's set-based analysis), or unification and take O(Na(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(Nalpha(N,N)), O(N^2), and O(N^2alpha(N,N)) time; our O(N) and O(Nalpha(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.
Published in the proceedings of POPL'98, San Diego, CA, January, 1998.

To get the PostScript file, click here. A version of this paper with some small fixes and raw experimental data is available as UW CSE Technical report 97-07-02b.

Cecil/Vortex Project