Newtonian program analysis
Authors:
Open Access
- 1 October 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 57 (6) , 1-47
Abstract
This article presents a novel generic technique for solving dataflow equations in interprocedural dataflow analysis. The technique is obtained by generalizing Newton's method for computing a zero of a differentiable function to ω-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of ω-continuous semirings. We show that our generalized method always converges to the solution, and requires at most as many iterations as current methods based on Kleene's fixed-point theorem. We also show that, contrary to Kleene's method, Newton's method always terminates for arbitrary idempotent and commutative semirings. More precisely, in the latter setting the number of iterations required to solve a system of n equations is at most n .Keywords
This publication has 17 references indexed in Scilit:
- Computing the Least Fixed Point of Positive Polynomial SystemsSIAM Journal on Computing, 2010
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equationsJournal of the ACM, 2009
- On the convergence of Newton's method for monotone systems of polynomial equations2007
- Weighted pushdown systems and their application to interprocedural dataflow analysisScience of Computer Programming, 2005
- Interprocedural analyses: a comparisonThe Journal of Logic Programming, 2000
- Semirings and Formal Power Series: Their Relevance to Formal Languages and Automata1997
- Precise interprocedural dataflow analysis with applications to constant propagationTheoretical Computer Science, 1996
- Monotone data flow analysis frameworksActa Informatica, 1977
- A unified approach to global program optimization1973
- Derivatives of Regular ExpressionsJournal of the ACM, 1964