--- res: bibo_abstract: - "Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, and so on. Recursive state machines (RSMs) are standard models for interprocedural analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring and path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, and so on. The traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in an important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect we consider is that the control flow graphs for most programs have constant treewidth.\r\n\r\nOur main contributions are simple and implementable algorithms that support multiple queries for algebraic path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have small additional one-time preprocessing but can answer subsequent queries significantly faster as compared to the current algorithmic solutions for interprocedural dataflow analysis. We have also implemented our algorithms and evaluated their performance for performing on-demand interprocedural dataflow analysis on various domains, such as for live variable analysis and reaching definitions, on a standard benchmark set. Our experimental results align with our theoretical statements and show that after a lightweight preprocessing, on-demand queries are answered much faster than the standard existing algorithmic approaches.\r\n@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: Prateesh foaf_name: Goyal, Prateesh foaf_surname: Goyal - 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.1145/3363525 bibo_issue: '4' bibo_volume: 41 dct_date: 2019^xs_gYear dct_identifier: - UT:000564108400004 dct_isPartOf: - http://id.crossref.org/issn/0164-0925 dct_language: eng dct_publisher: ACM@ dct_title: Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth@ ...