一句话：提出在常量树宽递归状态机上支持代数路径性质多次查询的轻量预处理算法，并显著加速按需过程间数据流分析。
过程间分析是别名分析、常量传播等的核心，递归状态机（RSM）是其标准模型。论文考虑迁移由半环标注、路径性质以半环运算表达的 RSM 代数路径性质框架，可建模过程间数据流、最短路与最可能路径等问题。与传统固定方法入口的查询不同，本文面向别名分析等多次查询场景，区分一次性预处理与单次查询开销，并利用程序控制流图常量树宽的性质。作者给出简单可实现、支持常量树宽 RSM 多次代数路径性质查询的算法，理论上仅需少量一次性预处理，却能显著更快回答后续查询。并在标准基准上对活跃变量分析、到达定值等按需过程间数据流分析进行评测，结果与理论一致。
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. 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 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.
@article{paperbot699,
title = {Faster Algorithms for Dynamic Algebraic Queries in Basic RSMs with Constant Treewidth},
author = {Krishnendu Chatterjee and Amir Kafshdar Goharshady and Prateesh Goyal and Rasmus Ibsen-Jensen and Andreas Pavlogiannis},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {41},
number = {4},
year = {2019},
doi = {10.1145/3363525}
}