--- res: bibo_abstract: - "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 IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand 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 offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries.\r\nIn 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 space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, 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.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Krishnendu foaf_name: Chatterjee, Krishnendu foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Amir Kafshdar foaf_name: Goharshady, Amir Kafshdar foaf_surname: Goharshady foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-1702-6584 - foaf_Person: foaf_givenName: Rasmus foaf_name: Ibsen-Jensen, Rasmus foaf_surname: Ibsen-Jensen foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-4783-0389 - foaf_Person: foaf_givenName: Andreas foaf_name: Pavlogiannis, Andreas foaf_surname: Pavlogiannis foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-8943-0722 bibo_doi: 10.1007/978-3-030-44914-8_5 bibo_volume: 12075 dct_date: 2020^xs_gYear dct_identifier: - UT:000681656800005 dct_isPartOf: - http://id.crossref.org/issn/03029743 - http://id.crossref.org/issn/16113349 - http://id.crossref.org/issn/9783030449131 dct_language: eng dct_publisher: Springer Nature@ dct_title: Optimal and perfectly parallel algorithms for on-demand data-flow analysis@ ...