Record Details

Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth
 
Creator CHATTERJEE, K
IBSEN-JENSEN, R
PAVLOGIANNIS, A
GOYAL, P
 
Subject Interprocedural analysis
Constant treewidth graphs
Dataflow analysis
Reachability and shortest path
 
Description 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 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 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.
 
Publisher ASSOC COMPUTING MACHINERY
 
Date 2016-01-15T09:56:13Z
2016-01-15T09:56:13Z
2015
 
Type Article
 
Identifier ACM SIGPLAN NOTICES, 50(1)97-109
0362-1340
1558-1160
http://dx.doi.org/10.1145/2676726.2676979
http://dspace.library.iitb.ac.in/jspui/handle/100/18307
 
Language en