---
_id: '7158'
abstract:
- lang: eng
text: "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"
article_number: '23'
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Prateesh
full_name: Goyal, Prateesh
last_name: Goyal
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Goharshady AK, Goyal P, Ibsen-Jensen R, Pavlogiannis A. Faster
algorithms for dynamic algebraic queries in basic RSMs with constant treewidth.
ACM Transactions on Programming Languages and Systems. 2019;41(4). doi:10.1145/3363525
apa: Chatterjee, K., Goharshady, A. K., Goyal, P., Ibsen-Jensen, R., & Pavlogiannis,
A. (2019). Faster algorithms for dynamic algebraic queries in basic RSMs with
constant treewidth. ACM Transactions on Programming Languages and Systems.
ACM. https://doi.org/10.1145/3363525
chicago: Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Prateesh Goyal, Rasmus
Ibsen-Jensen, and Andreas Pavlogiannis. “Faster Algorithms for Dynamic Algebraic
Queries in Basic RSMs with Constant Treewidth.” ACM Transactions on Programming
Languages and Systems. ACM, 2019. https://doi.org/10.1145/3363525.
ieee: K. Chatterjee, A. K. Goharshady, P. Goyal, R. Ibsen-Jensen, and A. Pavlogiannis,
“Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth,”
ACM Transactions on Programming Languages and Systems, vol. 41, no. 4.
ACM, 2019.
ista: Chatterjee K, Goharshady AK, Goyal P, Ibsen-Jensen R, Pavlogiannis A. 2019.
Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth.
ACM Transactions on Programming Languages and Systems. 41(4), 23.
mla: Chatterjee, Krishnendu, et al. “Faster Algorithms for Dynamic Algebraic Queries
in Basic RSMs with Constant Treewidth.” ACM Transactions on Programming Languages
and Systems, vol. 41, no. 4, 23, ACM, 2019, doi:10.1145/3363525.
short: K. Chatterjee, A.K. Goharshady, P. Goyal, R. Ibsen-Jensen, A. Pavlogiannis,
ACM Transactions on Programming Languages and Systems 41 (2019).
date_created: 2019-12-09T08:33:33Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2026-05-19T22:31:14Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3363525
ec_funded: 1
external_id:
isi:
- '000564108400004'
file:
- access_level: open_access
checksum: 291cc86a07bd010d4815e177dac57b70
content_type: application/pdf
creator: dernst
date_created: 2020-10-08T12:58:10Z
date_updated: 2020-10-08T12:58:10Z
file_id: '8632'
file_name: 2019_ACMTransactions_Chatterjee.pdf
file_size: 667357
relation: main_file
success: 1
file_date_updated: 2020-10-08T12:58:10Z
has_accepted_license: '1'
intvolume: ' 41'
isi: 1
issue: '4'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: ACM Transactions on Programming Languages and Systems
publication_identifier:
issn:
- 0164-0925
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Faster algorithms for dynamic algebraic queries in basic RSMs with constant
treewidth
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 41
year: '2019'
...