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