Aarhus University Seal / Aarhus Universitets segl

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
ISBN (print)978-3-319-10935-0
ISBN (Electronic)978-3-319-10936-7
Publication statusPublished - 2014
EventInternational Static Analysis Symposium (SAS) - Munich, Germany
Duration: 11 Sep 201413 Sep 2014


ConferenceInternational Static Analysis Symposium (SAS)
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 81801440