lnu.sePublications
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
Fast and Precise Points-to Analysis
Växjö University, Faculty of Mathematics/Science/Technology, School of Mathematics and Systems Engineering. (Software Technology)ORCID iD: 0000-0001-9775-4594
Växjö University, Faculty of Mathematics/Science/Technology, School of Mathematics and Systems Engineering. (Software Technology)
Växjö University, Faculty of Mathematics/Science/Technology, School of Mathematics and Systems Engineering. (Software Technology)
Växjö University, Faculty of Mathematics/Science/Technology, School of Mathematics and Systems Engineering. (Software Technology)ORCID iD: 0000-0002-7565-3714
2009 (English)In: Information and Software Technology, ISSN 0950-5849, E-ISSN 1873-6025, Vol. 51, no 10, p. 1428-1439Article in journal (Refereed) Published
Abstract [en]

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, software engineering applications used in an edit-compile cycle need points-to analysis to be fast and precise.

In this article, we present a new context- and flow-sensitive approach to points-to analysis where calling contexts are distinguished by the points-to sets analyzed for their call target expressions. Compared to other well-known context-sensitive techniques it is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments using a number of abstract precision metrics and a concrete client application: escape analysis.

Place, publisher, year, edition, pages
2009. Vol. 51, no 10, p. 1428-1439
Keywords [en]
Points-to analysis; Dataflow analysis; Escape analysis
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science
Identifiers
URN: urn:nbn:se:vxu:diva-5907DOI: 10.1016/j.infsof.2009.04.012OAI: oai:DiVA.org:vxu-5907DiVA, id: diva2:236880
Available from: 2009-09-25 Created: 2009-09-25 Last updated: 2018-05-17Bibliographically approved
In thesis
1. Fast and Precise Points-to Analysis
Open this publication in new window or tab >>Fast and Precise Points-to Analysis
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. The software engineering applications are often user-interactive, or used in an edit-compile cycle, and need the points-to analysis to be fast and precise.

In this compilation thesis, we present a new context- and flow-sensitive approach to points-to analysis that is both fast and precise. This is accomplished by a new SSA-based flow-sensitive dataflow algorithm (Paper 1) and a new context-sensitive analysis (Paper 2). Compared to other well-known analysis approaches our approach is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments in Paper 2.

Paper 3 is a systematic comparison of ten different variants of context-sensitive points-to analysis using different call-depths  for separating the contexts. Previous works indicate that analyses with a call-depth  only provides slightly better precision than context-insensitive analysis and they find no substantial precision improvement when using a more expensive analyses with call-depth . The hypothesis in Paper 3 is that substantial differences between the context-sensitive approaches show if (and only if) the precision is measured by more fine-grained metrics focusing on individual objects (rather than methods and classes) and references between them. These metrics are justified by the many applications requiring such detailed object reference information.

The main results in Paper 3 show that the differences between different context-sensitive analysis techniques are substantial, also the differences between the context-insensitive and the context-sensitive analyses with call-depth are substantial. The major surprise was that increasing the call-depth  did not lead to any substantial precision improvements. This is a negative result since it indicates that, in practice, we cannot get a more precise points-to analysis by increasing the call-depth. Further investigations show that substantial precision improvements can be detected for but they occur at such a low detail level that they are unlikely to be of any practical use.

Place, publisher, year, edition, pages
Växjö: Linnaeus University Press, 2014. p. 52
Series
Linnaeus University Dissertations ; 175/2014
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-36236 (URN)978-91-87427-89-3 (ISBN)
Public defence
2014-06-13, M1083, Södrasalen, Hus M, Växjö, 13:00 (English)
Opponent
Supervisors
Available from: 2014-08-21 Created: 2014-08-02 Last updated: 2018-05-17Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttp://dx.doi.org/10.1016/j.infsof.2009.04.012

Authority records BETA

Lundberg, JonasGutzmann, TobiasEdvinsson, MarcusLöwe, Welf

Search in DiVA

By author/editor
Lundberg, JonasGutzmann, TobiasEdvinsson, MarcusLöwe, Welf
By organisation
School of Mathematics and Systems Engineering
In the same journal
Information and Software Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 182 hits
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