Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Computation of Fixpoints in Static Program Analysis with an Application to AKL
Number of Authors: 1
1995 (English)Report (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 1995, 1. , 77 p.
Series
SICS Research Report, ISSN 0283-3638 ; R95:06
Keyword [en]
static program analysis, fixpoint computations, dependency graphs, weak topological orders, topological sorting, strongly connected components, Tarjan's algorithm, partially argument-independent functions
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-21397OAI: oai:DiVA.org:ri-21397DiVA: diva2:1041433
Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

fulltext
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.27.0