Authors: Greg DeFouw, David Grove, and Craig Chambers
Citation: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages January 19 - 21, 1998, San Diego, CA USA
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.
ACM Definitive Copy
Preprint PDF
An extended version includes raw experimental data and fixes a couple minor problems with the original.
ACM - Copyright © 1998 by Association for Computing Machinery, Inc.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.