Reference:

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Newtonian program analysis. Technical report, Technische Universität München, Institut für Informatik, April 2009.

Abstract:

This paper 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 omega-continuous semirings. Complete semilattices, the common program analysis framework, are a special class of omega-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. Furthermore, the number of iterations required to solve a system of n equations is at most n.

Suggested BibTeX entry:

@techreport{EKL09:newtProgAn,
    author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {April},
    title = {Newtonian Program Analysis},
    year = {2009}
}