Optimal Dyck Reachability for Data-Dependence and Alias Analysis
Presented on January 29, 2018
Presenter: Lawton
Presenter: Lawton
Preview
Lawton will present “Optimal Dyck Reachability for Data-Dependence and Alias Analysis” by Chatterjee, Choudhary, and Pavlogiannis.
Summary
The paper provides an algorithm for field-sensitive data dependence in the presence of libraries (using Dyck reachability) that is faster than previous work; it summarizes the library code as much as possible, and then exploits the low treewidth of the program graphs to solve reachability queries fast.
The authors provide a second algorithm for reachability on bidirected graphs, and give an application to alias analysis. The key insight is that bidirected Dyck reachability induces an equivalence relation on the program graphs, and equivalence classes can be found quickly using a union-find data structure.