Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
RISE - Research Institutes of Sweden, ICT, SICS.
1995 (English)Report (Other academic)
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. , p. 77
Series
SICS Research Report, ISSN 0283-3638 ; R95:06
Keywords [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 Sciences
Identifiers
URN: urn:nbn:se:ri:diva-21397OAI: oai:DiVA.org:ri-21397DiVA, id: diva2:1041433
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2025-09-23Bibliographically approved

Open Access in DiVA

fulltext(6240 kB)157 downloads
File information
File name FULLTEXT01.pdfFile size 6240 kBChecksum SHA-512
c39d54cb4f52b96996aa7afa2d5c15962c390589800716069d56af27bfc6854c5484480854852bbd6337c82caaf732f8a44176022d9e098c155f6ea7155f7ee1
Type fulltextMimetype application/pdf

By organisation
SICS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 157 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 309 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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