SODA

On the Computation of Fixpoints in Static Program Analysis with an Application to AKL

Schön, Erik (1995) On the Computation of Fixpoints in Static Program Analysis with an Application to AKL. [SICS Report]

[img]Postscript
245Kb

Abstract

This report features an introduction to lattice- and fixpoint theory and a survey of methods and recent results for fixpoint computations in static program analysis. As the number of equations in static program analysis tend to be very large, it is extremely important to avoid unnecessary computations and hence to find an optimal order in which to compute the functions. It is also important to have an efficient method for detecting stability. An algorithm satisfying these two requirements is Bourdoncle's algorithm for finding a weak topological ordering of a directed graph which may contain cycles. This algorithm is a generalization of Tarjan's algorithm for finding the strongly connected components of a directed graph. This report presents results from experiments with a fixpoint solver in the analysis framework for AKL (Agents Kernel Language, a concurrent constraint language developed at SICS) using the above ideas showing that a considerable speed-up (up to 3000%) can be achieved compared to that of a fixpoint solver based on strongly connected components. This is explained by showing how weak topological orders computed by Bourdoncle's algorithm incorporate many intuitively good heuristics. The report also introduces partially argument independent functions, a class of functions particularly suited to the repetitive scheme of computations that arise in fixpoint computations. A function of this type needs to be re-evaluated only with respect to those of its arguments which have changed since its latest evaluation.

Item Type:SICS Report
Uncontrolled Keywords:static program analysis, fixpoint computations, dependency graphs, weak topological orders, topological sorting, strongly connected components, Tarjan's algorithm, partially argument-independent functions
ID Code:2146
Deposited By:Vicki Carleson
Deposited On:22 Oct 2007
Last Modified:18 Nov 2009 16:00

Repository Staff Only: item control page