Mechanically Translating Iterative Dataflow Analysis to Algebraic Program Analysis
This program is tentative and subject to change.
We propose a method for mechanically translating iterative dataflow analysis (IDA) algorithms to algebraic program analysis (APA) algorithms capable of computing exactly the same set of dataflow facts. The method is useful because while most of the dataflow analysis algorithms used in practice are expressed as iterative procedures, APA provides an alternative and inherently-compositional approach to solving dataflow problems, thus making it well suited for certain applications (e.g., incremental analysis of a program that goes through frequent code changes, or amortizing the cost of answering a large number of dataflow queries for the same program). However, manually crafting an APA algorithm not only is labor intensive and error prone but also can lead to suboptimal performance. Our method overcomes the limitation by providing a mechanical translation that guarantees to be correct by construction. Our method handles a broad class of dataflow analysis problems — the only requirements are that (1) the set of dataflow facts is finite and (2) the dataflow functions distribute over the confluence operation (e.g., set union). They include classical dataflow problems whose IDA algorithms can be expressed using Gen/Kill sets, such as reaching definitions, live variables, and available expressions. They also include non Gen/Kill problems such as copy constant propagation, truly-live variables, and possibly-initialized variables. Our experimental evaluation shows that the translated APA algorithms are not only simpler and easier to understand, but also significantly faster than manually-designed APA algorithms, especially for incremental program analysis.
This program is tentative and subject to change.
Tue 6 OctDisplayed time zone: Pacific Time (US & Canada) change
10:30 - 12:00 | |||
10:30 18mTalk | Hermes: Making Path-Sensitive Pointer Analysis Scalable for Sparse Value-Flow Analysis OOPSLA Yuxuan He School of Informatics, Xiamen University, Ruilin Jiang School of Informatics, Xiamen University, He Zhang School of Informatics, Xiamen University, Qingkai Shi Nanjing University, Huaxun Huang School of Informatics, Xiamen University, Rongxin Wu Xiamen University | ||
10:48 18mTalk | Heap Abstraction via Early-Confluent Object Merging for Pointer Analysis OOPSLA Jinpeng Wang Nanjing University, Yufei Liang Nanjing University, Zhongsheng Zhan Nanjing University, Tian Tan Nanjing University, Yue Li Nanjing University Pre-print | ||
11:06 18mTalk | Mechanically Translating Iterative Dataflow Analysis to Algebraic Program Analysis OOPSLA Chenyu Zhou University of Southern California, Jingbo Wang Purdue University, Chao Wang University of Southern California | ||
11:24 18mTalk | When FPGA Meets Dataflow Analysis: An Explorative Step OOPSLA Fang Wei Nanjing University, Qinlin Chen Nanjing University, Nairen Zhang Nanjing University, Jiacai Cui Nanjing University, Tian Tan Nanjing University, Zhiqiang Zuo Nanjing University, Yue Li Nanjing University | ||
11:42 18mTalk | Beyond Nominality: Faster Rapid Type Analysis in the Presence of Structural Subtyping OOPSLA | ||