Sparse Dataflow Analysis with Pointers and Reachability

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.

Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.
Original languageEnglish
Title of host publicationStatic Analysis : 21st International Symposium, SAS 2014, Munich, Germany, September 11-13, 2014. Proceedings
EditorsMarkus Müller-Olm , Helmut Seidl
Number of pages18
PublisherSpringer VS
Publication year2014
Pages201-218
ISBN (print)978-3-319-10935-0
ISBN (Electronic)978-3-319-10936-7
DOIs
Publication statusPublished - 2014
EventInternational Static Analysis Symposium (SAS) - Munich, Germany
Duration: 11 Sep 201413 Sep 2014

Conference

ConferenceInternational Static Analysis Symposium (SAS)
LandGermany
ByMunich
Periode11/09/201413/09/2014
SeriesLecture Notes in Computer Science
Volume8723
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 81801440