Faster algorithms for algebraic path properties in recursive state machines with constant treewidth

K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, P. Goyal, ACM SIGPLAN Notices 50 (2015) 97–109.


Journal Article | Published | English
Department
Abstract
Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. 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, etc. 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 a very important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect that we consider is that the control flow graphs for most programs have constant treewidth. Our main contributions are simple and implementable algorithms that supportmultiple 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 best-known solutions for several important problems, such as interprocedural reachability and shortest path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path that gives a significant speed-up on several benchmarks.
Publishing Year
Date Published
2015-01-01
Journal Title
ACM SIGPLAN Notices
Acknowledgement
We thank anonymous reviewers for helpful comments to improve the presentation of the paper.
Volume
50
Issue
1
Page
97 - 109
Conference
SIGPLAN: Symposium on Principles of Programming Languages
Conference Location
Mumbai, India
Conference Date
2015-01-15 – 2015-01-17
IST-REx-ID

Cite this

Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 2015;50(1):97-109. doi:10.1145/2676726.2676979
Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., & Goyal, P. (2015). Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices, 50(1), 97–109. https://doi.org/10.1145/2676726.2676979
Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Andreas Pavlogiannis, and Prateesh Goyal. “Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth.” ACM SIGPLAN Notices 50, no. 1 (2015): 97–109. https://doi.org/10.1145/2676726.2676979.
K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, and P. Goyal, “Faster algorithms for algebraic path properties in recursive state machines with constant treewidth,” ACM SIGPLAN Notices, vol. 50, no. 1, pp. 97–109, 2015.
Chatterjee K, Ibsen-Jensen R, Pavlogiannis A, Goyal P. 2015. Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. ACM SIGPLAN Notices. 50(1), 97–109.
Chatterjee, Krishnendu, et al. “Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth.” ACM SIGPLAN Notices, vol. 50, no. 1, ACM, 2015, pp. 97–109, doi:10.1145/2676726.2676979.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Dissertation containing IST record

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1410.7724

Search this title in

Google Scholar