Linear-time subtransitive control flow analysis
- 1 May 1997
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 32 (5) , 261-272
- https://doi.org/10.1145/258916.258939
Abstract
We present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA) algorithm. Our algorithm can be used to list all functions calls from all call sites in (optimal) quadratic time. More importantly, it can be used to give linear-time algorithms for CFA-consuming applications such as:• effects analysis: find the side-effecting expressions in a program.• k-limited CFA: for each call-site, list the functions if there are only a few of them (≤ k) and otherwise output "many".• called-once analysis: identify all functions called from only one call-site.Keywords
This publication has 9 references indexed in Scilit:
- Interconvertbility of set constraints and context-free language reachabilityPublished by Association for Computing Machinery (ACM) ,1997
- Interprocedural control flow analysis of first-order programs with tail-call optimizationACM Transactions on Programming Languages and Systems, 1997
- Safety Analysis versus Type InferenceInformation and Computation, 1995
- A type system equivalent to flow analysisPublished by Association for Computing Machinery (ACM) ,1995
- Set-based analysis of ML programsPublished by Association for Computing Machinery (ACM) ,1994
- Efficient analyses for realistic off-line partial evaluationJournal of Functional Programming, 1993
- Type inference with polymorphic recursionACM Transactions on Programming Languages and Systems, 1993
- Control flow analysis in schemePublished by Association for Computing Machinery (ACM) ,1988
- Time and tape complexity of pushdown automaton languagesInformation and Control, 1968