Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis

Chatterjee, Krishnendu, Goharshady, Amir Kafshdar, Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas (2020) Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis. PROGRAMMING LANGUAGES AND SYSTEMS ( ESOP 2020), 12075. pp. 112-140.

Text 2001.11070.pdf - Submitted version Download (1MB) | Preview

Abstract

<jats:title>Abstract</jats:title><jats:p>Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is <jats:italic>IFDS</jats:italic>, which encompasses distributive data-flow functions over a finite domain. <jats:italic>On-demand</jats:italic> data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an <jats:italic>offline (or preprocessing) phase</jats:italic>, where the program is partially analyzed and analysis summaries are created, and (ii) an <jats:italic>online (or query) phase</jats:italic>, where analysis queries arrive on demand and the summaries are used to speed up answering queries.</jats:p><jats:p>In this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are <jats:italic>space and time optimal</jats:italic> for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are <jats:italic>embarrassingly parallelizable</jats:italic>, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	Data-flow analysis, IFDS, Treewidth
Depositing User:	Symplectic Admin
Date Deposited:	22 Apr 2020 15:18
Last Modified:	18 Jan 2023 23:54
DOI:	10.1007/978-3-030-44914-8_5
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3084307