  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 \emph{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 \emph{one-time} preprocessing vs for \emph{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.
